# Boosting the Confidence of Generalization for $L_{2}$-Stable Randomized
Learning Algorithms

Xiao-Tong Yuan and Ping Li

Cognitive Computing Lab
Baidu Research
No. 10 Xibeiwang East Road, Beijing 100193, China
10900 NE 8th St. Bellevue, Washington 98004, USA
E-mail: {xtyuan1980<EMAIL_ADDRESS>
###### Abstract

Exponential generalization bounds with near-tight rates have recently been
established for uniformly stable learning algorithms (Feldman and Vondrák,
2019; Bousquet et al., 2020). The notion of uniform stability, however, is
stringent in the sense that it is invariant to the data-generating
distribution. Under the weaker and distribution dependent notions of stability
such as hypothesis stability and $L_{2}$-stability, the literature suggests
that only polynomial generalization bounds are possible in general cases. The
present paper addresses this long standing tension between these two regimes
of results and makes progress towards relaxing it inside a classic framework
of confidence-boosting. To this end, we first establish an in-expectation
first moment generalization error bound for potentially randomized learning
algorithms with $L_{2}$-stability, based on which we then show that a properly
designed subbagging process leads to near-tight exponential generalization
bounds over the randomness of both data and algorithm. We further
substantialize these generic results to stochastic gradient descent (SGD) to
derive improved high-probability generalization bounds for convex or non-
convex optimization problems with natural time decaying learning rates, which
have not been possible to prove with the existing hypothesis stability or
uniform stability based results.

#### Key words.

Algorithmic stability, Randomized learning algorithms, Subbagging,
Generalization, Excess risk, Stochastic gradient methods

##  1 Introduction

In many statistical learning problems, the ultimate goal is to design a
suitable algorithm $A:\mathcal{Z}^{N}\mapsto\mathcal{W}$ that maps a training
data set $S=\\{Z_{i}\\}_{i\in[N]}\in\mathcal{Z}^{N}$ to a model $A(S)$ in a
closed subset $\mathcal{W}$ of an Euclidean space such that the following
population risk evaluated at the model is as small as possible:

$R(A(S)):=\mathbb{E}_{Z\sim\mathcal{D}}[\ell(A(S);Z)].$

Here $\ell:\mathcal{W}\times\mathcal{Z}\mapsto\mathbb{R}^{+}$ is a non-
negative bounded loss function whose value $\ell(w;z)$ measures the loss
evaluated at $z$ with parameter $w$, and $\mathcal{D}$ represents a data
distribution over $\mathcal{Z}$. It is generally the case that the underlying
data distribution is unknown, and in this case the training data is usually
assumed to be an i.i.d. set, i.e.,
$S\overset{\text{i.i.d.}}{\sim}\mathcal{D}^{N}$. Then, a natural alternative
measurement that mimics the computationally intractable population risk is the
empirical risk given by

$R_{S}(A(S)):=\mathbb{E}_{Z\sim\texttt{Unif}(S)}[\ell(A(S);Z)]=\frac{1}{N}\sum_{i=1}^{N}\ell(A(S);Z_{i}).$

The bound on the difference between population and empirical risks is of
central interest in understanding the generalization performance of learning
algorithm $A$. Particularly, we hope to derive a suitable law of large
numbers, i.e., a sample size vanishing rate $b_{N}$ such that the
generalization bound $|R_{S}(A(S))-R(A(S))|\lesssim b_{N}$ holds with high
probability over the randomness of $S$ and potentially the randomness of $A$
as well. Provided that $A(S)$ is an almost minimizer of the empirical risk
function $R_{S}$, say
$R_{S}(A(S))\lesssim\min_{w\in\mathcal{W}}R_{S}(w)+\Delta_{\text{opt}}$, the
generalization bound immediately implies an _excess risk_ bound
$R(A(S))-\min_{w\in\mathcal{W}}R(w)\lesssim
b_{N}+\Delta_{\text{opt}}+\frac{1}{\sqrt{N}}$ in view of the standard risk
decomposition and Hoeffding’s inequality. Therefore, generalization bounds
also play a crucial role in understanding the stochastic optimization
performance of a learning algorithm.

A powerful proxy for analyzing the generalization bounds is the _stability_ of
learning algorithms to changes in the training dataset. Since the seminal work
of Bousquet and Elisseeff (2002), stability has been extensively demonstrated
to beget dimension-independent generalization bounds for deterministic
learning algorithms (Mukherjee et al., 2006; Shalev-Shwartz et al., 2010), as
well as for randomized learning algorithms such as bagging and SGD (Elisseeff
et al., 2005; Hardt et al., 2016). So far, the best known results about
generalization bounds are offered by approaches based on the strongest notion
of uniform stability (Feldman and Vondrák, 2018, 2019; Bousquet et al., 2020)
which is independent to the underlying distribution of data. Under the weaker
and distribution dependent notions of stability such as hypothesis stability
and $L_{2}$-stability, the literature suggests that only in-expectation or
polynomial generalization bounds are possible in general cases (Bousquet and
Elisseeff, 2002; Hardt et al., 2016). Motivated by this gap between the two
regimes of results, we seek to explore the opportunity of _deriving
exponential generalization bounds for randomized learning algorithms under
$L_{2}$-stability_. A concrete working example of our study is the widely used
stochastic gradient descent (SGD) algorithm that carries out the following
recursion for all $t\geq 1$ with learning rate $\eta_{t}>0$:

$w_{t}:=\Pi_{\mathcal{W}}\left(w_{t-1}-\eta_{t}\nabla_{w}\ell(w_{t-1};Z_{\xi_{t}})\right),$
(1.1)

where $\xi_{t}\in[N]$ is a uniform random index of data under with or without
replacement sampling, and $\Pi_{\mathcal{W}}$ is the Euclidean projection
operator associated with $\mathcal{W}$. In spite of its popularity in the
study of algorithmic stability theory (Hardt et al., 2016; Lei and Ying, 2020;
Zhou et al., 2022), the exponential generalization bounds of SGD are still
under explored through the lens of algorithmic stability.

###  1.1 Prior Results

Let us start by briefly reviewing some state-of-the-art exponential
generalization bounds under the most stringent notion of uniform stability and
its randomized variants. We denote by $S\doteq\tilde{S}$ if a pair of data
sets $S$ and $\tilde{S}$ differ in a single data point. A randomized learning
algorithm $A$ is said to have on-average $\gamma_{u,N}$-uniform stability if
it satisfies the following uniform bound

$\sup_{S\doteq\tilde{S},Z\in\mathcal{Z}}|\mathbb{E}_{A}[\ell(A(S);Z)]-\mathbb{E}_{A}[\ell(A(\tilde{S});Z)]|\leq\gamma_{u,N}.$

This definition is equivalent to the concept of uniform stability defined over
the on-average loss $\mathbb{E}_{A}[\ell(A(S);Z)]$. Suppose that the loss
function is uniformly bounded in the interval $(0,1]$. Then essentially it has
been shown in Feldman and Vondrák (2019) that for any $\delta\in(0,1)$, with
probability at least $1-\delta$ over $S$, the on-average generalization error
is upper bounded by

$\left|\mathbb{E}_{A}\left[R(A(S))-R_{S}(A(S))\right]\right|\lesssim\gamma_{u,N}\log(N)\log\left(\frac{N}{\delta}\right)+\sqrt{\frac{\log\left(1/\delta\right)}{N}}.$
(1.2)

Recently, Bousquet et al. (2020) derived a slightly improved uniform stability
bound that implies

$\left|\mathbb{E}_{A}\left[R(A(S))-R_{S}(A(S))\right]\right|\lesssim\gamma_{u,N}\log(N)\log\left(\frac{1}{\delta}\right)+\sqrt{\frac{\log\left(1/\delta\right)}{N}}.$
(1.3)

These generalization bounds are near-tight (up to a logarithmic factor
$\log(N)$) in the sense of an
$\mathcal{O}\big{(}\gamma_{u,N}\log\left(\frac{1}{\delta}\right)+\sqrt{\frac{\log\left(1/\delta\right)}{N}}\big{)}$
lower deviation bound on sum of random functions with $\gamma_{u,N}$-uniform
stability (Bousquet et al., 2020, Proposition 9). While sharp in the
dependence on sample size, one common limitation of the above uniform
stability implied generalization bounds lies in that these high-probability
results only hold _in expectation_ with respect to the internal randomness of
algorithm.

Further suppose that $A$ has $\gamma_{u,N}$-uniform stability with probability
at least $1-\delta^{\prime}$ for some $\delta^{\prime}\in(0,1)$ over the
randomness of $A$, i.e.,

$\mathbb{P}_{A}\left\\{\sup_{S\doteq\tilde{S},z\in\mathcal{Z}}|\ell(A(S);z)-\ell(A(\tilde{S});z)|\leq\gamma_{u,N}\right\\}\geq
1-\delta^{\prime}.$ (1.4)

Suppose that the randomness of $A$ is independent of the training set $S$.
Then with probability at least $1-\delta-\delta^{\prime}$ over $S$ and $A$,
the bound of Bousquet et al. (2020) naturally implies

$\left|R(A(S))-R_{S}(A(S))\right|\lesssim\gamma_{u,N}\log(N)\log\left(\frac{1}{\delta}\right)+\sqrt{\frac{\log\left(1/\delta\right)}{N}}.$
(1.5)

This is by far the best known generalization bound of randomized stable
algorithms that hold with high probability jointly over data and algorithm.
The result, however, relies heavily on the high-probability uniform stability
condition expressed in (1.4). For the SGD (see (1.1)) with fixed learning rate
$\eta_{t}\equiv\eta$, it is possible to show that
$\gamma_{u,N}\lesssim\eta\sqrt{T}+\frac{\eta T}{N}$ and
$\delta^{\prime}=N\exp(-\frac{N}{2})$ in (1.4) (Bassily et al., 2020). For SGD
with time decaying learning rate that has been widely studied in theory
(Rakhlin et al., 2012; Harvey et al., 2019) and applied in practice for
training popular deep nets such as ResNet and DenseNet (Bengio et al., 2017),
it is not clear if the condition in (1.4) is still valid for $\gamma_{u,N}$
and $\delta^{\prime}$ of interest. In the meanwhile, it is possible to show
(see the proofs of Corollary 1 and 2) that SGD with time decaying learning
rate has $L_{2}$-stability (see Definition 1) which is distribution dependent
and much weaker than uniform stability. However, through the notions of
hypothesis stability or $L_{2}$-stability, only in-expectation or
$\mathcal{O}(1/\delta)$-polynomial-tail generalization bounds are available in
literature (Bousquet and Elisseeff, 2002; Hardt et al., 2016).

More specially for randomized learning methods such as bagging (Breiman, 1996)
and SGD (1.1), the randomness of algorithm can be precisely characterized by a
vector of i.i.d. parameters $\xi=\\{\xi_{1},...,\xi_{T}\\}$ which are
independent on data $S$. In such cases, suppose that $A(S;\xi)$ has uniform
stability with respect to $\xi$ at any given $S$, i.e.,
$\sup_{\xi\doteq\xi^{\prime}}|\ell(A(S;\xi))-\ell(A(S;\xi^{\prime}))|\leq\rho_{u,T}$.
Then the high probability bound established in Elisseeff et al. (2005) shows
that with probability at least $1-\delta$,

$\left|R(A(S))-R_{S}(A(S))\right|\lesssim\gamma_{u,N}+\left(\frac{1+N\gamma_{u,N}}{\sqrt{N}}+\sqrt{T}\rho_{u,T}\right)\sqrt{\log\left(\frac{1}{\delta}\right)}.$
(1.6)

Provided that $\gamma_{u,N}\lesssim\frac{1}{N}$ and
$\rho_{u,T}\lesssim\frac{1}{T}$, the above bound shows that the generalization
bound scales as
$\mathcal{O}\big{(}\frac{1}{\sqrt{N}}+\frac{1}{\sqrt{T}}\big{)}$ with high
probability. However, the above bound will show no guarantee on convergence if
$\gamma_{u,N}\gtrsim\frac{1}{\sqrt{N}}$ and/or
$\rho_{u,T}\gtrsim\frac{1}{\sqrt{T}}$. For example, this is actually the case
for SGD with decaying learning rate $\eta_{t}=O\big{(}\frac{1}{t}\big{)}$ on
non-convex loss functions in which $\gamma_{u,N}\lesssim\frac{\sqrt{T}}{N}$
and $\rho_{u,T}$ can scale as large as $\mathcal{O}(1)$.

Open problem. Keeping the merits and deficiencies of above recalled prior
results in mind, it still remains an open issue if the exponential
generalization bounds of uniformly stable algorithms might possibly be
obtained for randomized algorithms under weaker and distribution dependent
notions of stability like $L_{2}$-stability (e.g., fulfilled by SGD with time
decaying learning rates). The focus of the present study is to explore the
opportunity of answering this open question affirmatively.

###  1.2 Overview of Our Results

The confidence-boosting technique of Schapire (1990) is a classic meta
approach that allows us to boost the dependence of a learning algorithm on the
failure probability $\delta$ from $1/\delta$ to $\log(1/\delta)$, at a certain
cost of computational complexity. The fundamental contribution of our work is
to reveal that the confidence-boosting trick yields near-tight exponential
generalization bounds for $L_{2}$-stable randomized learning algorithms. The
novelty lies in a refined analysis of the in-expectation first moment
generalization error bound for a randomized learning algorithm with
$L_{2}$-stability, which leads to desirable exponential generalization bounds
over the randomness of data and algorithm via confidence-boosting. More
specifically, given a randomized learning algorithm $A$, we propose to study a
subbagging based confidence-boosting procedure as following described.

Boosting the confidence via subbagging. We independently run $A$ over $K$
_disjoint_ and uniformly divided training subsets $\\{S_{k}\\}_{k\in[K]}$ to
obtain solutions $\\{A_{k}(S_{k})\\}_{k\in[K]}$. Then we evaluate the
validation error of each candidate solution over its complementary training
subset, and output $A_{k^{*}}(S_{k^{*}})$ that has the smallest gap between
training error and validation error, i.e.,
$k^{*}=\mathop{\arg\min}_{k\in[K]}\left|R_{S\setminus
S_{k}}(A_{k}(S_{k}))-R_{S_{k}}(A_{k}(S_{k}))\right|$. Specially when $A$ is
deterministic, this reduces to a standard subbagging process, namely a
variation of bagging using without-replacement sampling for subsets generation
(see, e.g., Andonova et al., 2002). In general, this is essentially a
subbagging procedure with greedy model selection for randomized algorithms
over multiple disjoint subsets. Throughout this paper, we assume without loss
of generality that $N$ is a multiplier of $K$. The considered procedure of
confidence-boosting for randomized learning is outlined in Algorithm 1.

Input : A randomized learning algorithm $A$ and a training data set
$S=\\{Z_{i}\\}_{i\in[N]}\overset{\text{i.i.d.}}{\sim}\mathcal{D}^{N}$.

Output : $A_{k^{*}}(S_{k^{*}})$.

Uniformly divide $S$ into $K$ _disjoint_ subsets such that
$S=\bigcup_{k\in[K]}S_{k}$ and $|S_{k}|=\frac{N}{K}$, $\forall k\in[K]$.

for  _$k=1,2,...,K$_ do

Estimate $A_{k}(S_{k})$ as an output of the randomized algorithm $A$ over
subset $S_{k}$.

end for

Select the subset index $k^{*}$ according to
$k^{*}=\mathop{\arg\min}_{k\in[K]}\left|R_{S\setminus
S_{k}}(A_{k}(S_{k}))-R_{S_{k}}(A_{k}(S_{k}))\right|.$

Algorithm 1 Confidence-Boosting for Randomized Learning Algorithms

Main results. In what follows, we highlight our main results on the
generalization bounds of the output of Algorithm 1 along with the implications
for SGD:

  * •

_General results._ Suppose that the loss is Lipschitz and upper bounded. Our
main result in Theorem 1 show that for any $\delta\in(0,1)$, setting
$K\asymp\log(\frac{1}{\delta})$ yields the following generalization bound of
the output of Algorithm 1 that holds with probability at least $1-\delta$ over
$S$ and $\\{A_{k}\\}_{k\in[K]}$:

$\left|R(A_{k^{*}}(S_{k^{*}}))-R_{S}(A_{k^{*}}(S_{k^{*}}))\right|\lesssim\frac{1}{K}\left(\gamma_{\texttt{L}_{2},\frac{N}{K}}+\sqrt{\frac{K}{N}}\right)+\sqrt{\frac{\log(K/\delta)}{N}},$

where $\gamma_{\texttt{L}_{2},N}$ is the $L_{2}$-stability parameter
introduced in Definition 1. In contrast to the bounds in (1.5) and (1.6), our
bound is not relying on the uniform stability of algorithm with respect to
data or internal random bits.

  * •

_Sharper deviation bounds for SGD via confidence-boosting._ We then use our
general results to study the benefit of confidence-boosting on the
generalization bounds of SGD-w (SGD via with-replacement sampling as outlined
in Algorithm 2). The main results are a series of corollaries of Theorem 1
when substantialized to SGD with smooth (Corollary 1) or non-smooth (Corollary
2) convex losses, and smooth non-convex losses (Corollary 3) as well. For an
instance, our result in Corollary 1 showcases that when invoked to SGD-w on
smooth convex loss with learning rates
$\eta_{t}=\mathcal{O}(\frac{1}{\sqrt{t}})$, the generalization bound of the
output of Algorithm 1 with $K\asymp\log(\frac{1}{\delta})$ is upper bounded by

$\left|R(A_{\texttt{SGD-w},k^{*}}(S_{k^{*}}))-R_{S}(A_{\texttt{SGD-w},k^{*}}(S_{k^{*}}))\right|\lesssim\sqrt{\frac{\log(T)}{N}}+\frac{\sqrt{T}+\sqrt{N}\log(1/\delta)}{N}.$

Compared with the $\mathcal{O}\big{(}\frac{\sqrt{T}}{N}\big{)}$ in-expectation
bound of smooth convex SGD (Hardt et al., 2016), our above bound is comparable
for $T=\mathcal{O}(N)$ while it holds with high confidence over the randomness
of data and stochastic sampling.

In addition to the generalization bounds, we have also derived an exponential
excess risk bound for $L_{2}$-stable randomized learning with confidence-
boosting. More specifically, with a proper modification of the output of
Algorithm 1, we can show that with probability at least $1-\delta$ over $S$
and $\\{A_{k}\\}_{k\in[K]}$:

$R(A_{k^{*}}(S_{k^{*}}))-\min_{w\in\mathcal{W}}R(w)\lesssim\gamma_{\texttt{L}_{2},\frac{N}{K}}+\Delta_{\text{opt}}+\sqrt{\frac{\log(K/\delta)}{N}},$

where $\Delta_{\text{opt}}$ is the in-expectation empirical risk minimization
sub-optimality as given by (2.1).

##  2 Exponential Generalization Bounds for Confidence-Boosting

In this section, we present a set of generic results on the generalization
bounds of randomized learning algorithms with confidence-boosting as described
in Algorithm 1.

###  2.1 Preliminaries and a Key Lemma

Notation. Recall that $S=\\{Z_{1},Z_{2},...,Z_{N}\\}$ is a set of i.i.d.
training data points. Denote by
$S^{\prime}=\\{Z^{\prime}_{1},Z^{\prime}_{2},...,Z^{\prime}_{N}\\}$ another
i.i.d. sample from the same distribution as that of $S$ and we write
$S^{(i)}=\\{Z_{1},...,Z_{i-1},Z^{\prime}_{i},Z_{i+1},...,Z_{N}\\}$. For a
real-valued random variable $Y$, its $L_{q}$-norm for $q\geq 1$ is given by
$\|Y\|_{q}=\left(\mathbb{E}[|Y|^{q}]\right)^{1/q}$. We say a function $f$ is
$G$-Lipschitz continuous over $\mathcal{W}$ if $|f(w)-f(w^{\prime})|\leq
G\|w-w^{\prime}\|$ for all $w,w^{\prime}\in\mathcal{W}$, and it is $L$-smooth
if $\|\nabla f(w)-\nabla f(w^{\prime})\|\leq L\|w-w^{\prime}\|$ for all
$w,w^{\prime}\in\mathcal{W}$. We abbreviate $[N]:=\\{1,...,N\\}$.

Let us first introduce the following notion of $L_{2}$-stability due to Kale
et al. (2011), which extends the weak and distribution dependent hypothesis
stability (Bousquet and Elisseeff, 2002) from $L_{1}$-norm criterion to
$L_{2}$-norm criterion.

######  Definition 1 ($L_{2}$-Stability of Randomized Learning Algorithms).

Let $A:\mathcal{Z}^{N}\mapsto\mathcal{W}$ be a randomized learning algorithm
that maps a data set $S\in\mathcal{Z}^{N}$ to a model $A(S)\in\mathcal{W}$.
Then $A$ is said to have $L_{2}$-stability by $\gamma_{\texttt{L}_{2},N}$ if
for all $N\geq 1$ and $i\in[N]$,

$\left\|\ell(A(S);Z)-\ell(A(S^{(i)});Z)\right\|_{2}\leq\gamma_{\texttt{L}_{2},N},$

where the expectation associated with $\|\cdot\|_{2}$ is taken over the
randomness of $A,S,S^{(i)}$ and $Z\in\mathcal{Z}$, and the algorithm outputs
$A(S)$ and $A(S^{(i)})$ share the same random bits associated with the
algorithm.

Inspired by a second moment bound for generalization error of uniformly stable
algorithms from Bousquet et al. (2020, Section 5), we first establish the
following lemma which states that if a randomized learning algorithm has
$L_{2}$-stability by $\gamma_{\texttt{L}_{2},N}$, then its on-average first
moment generalization error bound will be as small as
$\mathcal{O}\big{(}\gamma_{\texttt{L}_{2},N}+\frac{1}{\sqrt{N}}\big{)}$. For
the sake of completeness, we provide a proof for this result in Appendix B.1.

######  Lemma 1.

Suppose that a randomized learning algorithm
$A:\mathcal{Z}^{N}\mapsto\mathcal{W}$ has $L_{2}$-stability by
$\gamma_{\texttt{L}_{2},N}$. Assume that the loss function satisfies
$\|\ell(A(S);Z)\|_{2}\leq M$. Then we have

$\mathbb{E}_{A,S}\left[|R(A(S))-R_{S}(A(S))|\right]\leq
3\gamma_{\texttt{L}_{2},N}+\frac{2M}{\sqrt{N}}.$

######  Remark 1.

Under the notion of on-average uniform stability, it is well-known that the
in-expectation generalization error can be bounded as
$\left|\mathbb{E}_{A,S}\left[R(A(S))-R_{S}(A(S))\right]\right|\lesssim\gamma_{u,N}$
(see, e.g., Hardt et al., 2016, Theorem 2.2). In comparison, our on-average
first moment bound in Lemma 1 is substantially stronger, despite that the
$L_{2}$-stability condition is weaker. This result turns out to play a crucial
role in deriving high probability bounds for randomized algorithms. When $A$
is deterministic, the above bound reduces to the explicitly or implicitly
known first moment bound for uniformly stable algorithms (see, e.g., Feldman
and Vondrák, 2018; Bousquet et al., 2020). In this deterministic case, our
bound is stronger than the bound from Bousquet and Elisseeff (2002, Lemma 9)
which essentially scales as
$\mathcal{O}\left(\frac{1}{\sqrt{N}}+\sqrt{\gamma_{\texttt{L}_{2},N}}\right)$
using our notation.

###  2.2 Main Results

Let us recall the subbagging process as described in Algorithm 1: we
independently run $A$ over $K$ even and disjoint training subsets
$\\{S_{k}\\}_{k\in[K]}$ to obtain solutions $\\{A_{k}(S_{k})\\}_{k\in[K]}$,
and then pick $A_{k^{*}}(S_{k^{*}})$ that has the smallest difference between
training error and validation error (over the complementary training subset
$S\setminus S_{k^{*}}$). The following theorem is our main result about the
high probability generalization bound of the output $A_{k^{*}}(S_{k^{*}})$
evaluated over the entire training set $S$. See Appendix B.2 for its proof
which builds largely on the first moment bound in Lemma 1 and the fact that at
least one of the solutions generated by subbagging generalizes well with high
probability.

######  Theorem 1.

Suppose that a randomized learning algorithm
$A:\mathcal{Z}^{N}\mapsto\mathcal{W}$ has $L_{2}$-stability by
$\gamma_{\texttt{L}_{2},N}$. Assume that the loss function $\ell$ is bounded
in the range of $[0,M]$. Then for any $\alpha,\delta\in(0,1)$ and
$K\geq\frac{1}{1-\alpha}\log(\frac{4}{\delta})$, with probability at least
$1-\delta$ over the randomness of $S$ and $\\{A_{k}\\}_{k\in[K]}$, the output
of Algorithm 1 satisfies

$\left|R(A_{k^{*}}(S_{k^{*}}))-R_{S}(A_{k^{*}}(S_{k^{*}}))\right|\lesssim\frac{1}{\alpha
K}\left(\gamma_{\texttt{L}_{2},\frac{N}{K}}+M\sqrt{\frac{K}{N}}\right)+M\sqrt{\frac{\log(K/\delta)}{N}}.$

###### Proof in sketch.

In light of the first moment bound in Lemma 1, we first establish a key
intermediate result, Lemma 6, which confirms that for large enough $K$, at
least one of the $K$ base models generated by subbagging generalizes well with
high probability over data. To be more precise, under the given conditions,
Lemma 6 shows that if $K\gtrsim\frac{1}{1-\alpha}\log(\frac{1}{\delta})$, then
$\min_{k\in[K]}\left|R(A_{k}(S_{k}))-R_{S_{k}}(A_{k}(S_{k}))\right|$ can be
well upper bounded with high probability in terms of
$\gamma_{\texttt{L}_{2},\frac{N}{K}}$. Then we show that the proposed greedy
model selection strategy guarantees that the selected $A_{k^{*}}(S_{k^{*}})$
mimics the generalization behavior of that best performer among the $K$
candidates, also with high probability. Finally, the desired bound follows
immediately via union probability. See Appendix B.2 for a full proof. ∎

######  Remark 2.

To gain some intuition on the superiority of our bound in Theorem 1, let us
consider $K\asymp\log\left(\frac{1}{\delta}\right)$ as allowed in the
conditions. If $\gamma_{\texttt{L}_{2},N}\lesssim\frac{1}{\sqrt{N}}$, then our
high-probability bound in Theorem 1 roughly scales as
$\mathcal{O}\left(\sqrt{\frac{\log(1/\delta)}{N}}\right)$ which is sharper
than the on-average bounds in (1.2) and (1.3) with
$\gamma_{u,N}\lesssim\frac{1}{\sqrt{N}}$. More precise consequences of these
general results on SGD will be discussed shortly in the sections to follow.

######  Remark 3.

In sharp contrast to the bound in (1.5) that requires high probability uniform
stability and the bound in (1.6) that assumes uniform stability over the
random bits of algorithm, our bound in Theorem 1 holds under a substantially
milder notion of $L_{2}$-stability over data. In terms of the tightness of
bound, note that the confidence term $\sqrt{\frac{\log(1/\delta)}{N}}$ is
necessary even for an algorithm with fixed output. The stability term
$\gamma_{\texttt{L}_{2},\frac{N}{K}}$ are also near-tight as the algorithm
output can change arbitrarily with respect to the quantity.

Let us consider a specification of Theorem 1 to a deterministic algorithm $A$
with $L_{2}$-stability. Since there is no randomness contained in $A$, we have
that Algorithm 1 outputs $A_{k}(S_{k})=A(S_{k})$ for all $k\in[K]$ in such a
deterministic case. In the regime
$\gamma_{\texttt{L}_{2},N}\lesssim\frac{1}{\sqrt{N}}$ which is of interest in
many popular deterministic learning algorithms such as regularized ERM
(Shalev-Shwartz et al., 2009) and full gradient descent (Feldman and Vondrák,
2019), the generalization bound in Theorem 1 with $\alpha=0.5$ and
$K\asymp\log(\frac{1}{\delta})$ implies a generalization bound for
$A(S_{k^{*}})$ over the data set $S$ that scales as
$\left|R(A(S_{k^{*}}))-R_{S}(A(S_{k^{*}}))\right|\lesssim\sqrt{\frac{\log\left(1/\delta\right)}{N}}$.
In comparison, the best known bound in (1.5) gives
$\left|R(A(S))-R_{S}(A(S))\right|\lesssim\frac{\log(N)}{\sqrt{N}}\log(\frac{1}{\delta})$
(keep in mind that $\delta^{\prime}=0$ in the deterministic case) Bousquet et
al. (2020). As we can see that inside the carefully designed framework of
confidence-boosting via subbagging, our generalization bound gets rid of the
logarithmic factor $\log(N)$ from the above best known result, though the
generalization is with respect to the estimation over a specific part of the
training sample. We expect this result will fuel future research towards fully
resolving the corresponding open question raised by Bousquet et al. (2020).

The result in Theorem 1 is about the generalization bound with respect to the
empirical risk over the entire training set $S$. We comment in passing that up
to the multipliers of $K$, these bounds are also valid for the generalization
error
$\left|R(A_{k^{*}}(S_{k^{*}}))-R_{S_{k^{*}}}(A_{k^{*}}(S_{k^{*}}))\right|$
over the subset $S_{k^{*}}$.

###  2.3 On Excess Risk Bounds

To understand the optimization performance of a randomized learning algorithm
$A$ with confidence-boosting, we further study here the excess risk bounds of
Algorithm 1 which are of special interest for stochastic convex optimization
problems. In the following analysis, the global minimizer of the population
risk and in-expectation empirical risk sub-optimality of the randomized
algorithm are respectively denoted by
$w^{*}:=\mathop{\arg\min}_{w\in\mathcal{W}}R(w)$ and

$\Delta_{\text{opt}}:=\mathbb{E}_{A,S}\left[R_{S}(A(S))-\min_{w\in\mathcal{W}}R_{S}(w)\right].$
(2.1)

Throughout this paper , we assume that the sub-optimality
$\Delta_{\text{opt}}$ is invariant to the size of training data $S$. In order
to derive the excess risk guarantees, we first need to slightly modify the
output of Algorithm 1 as $A_{k^{*}}(S_{k^{*}})$ with

$k^{*}=\mathop{\arg\min}_{k\in[K]}R_{S\setminus S_{k}}(A_{k}(S_{k})).$ (2.2)

The following theorem is our main result about the high probability excess
risk bounds of such a modified output of confidence-boosting. See Appendix B.3
for its proof.

######  Theorem 2.

Suppose that a randomized learning algorithm
$A:\mathcal{Z}^{N}\mapsto\mathcal{W}$ has $L_{2}$-stability by
$\gamma_{\texttt{L}_{2},N}$. Assume that the loss function $\ell$ is bounded
in $[0,M]$. Then for any $\alpha,\delta\in(0,1)$ and
$K\geq\frac{1}{1-\alpha}\log(\frac{4}{\delta})$, with probability at least
$1-\delta$ over the randomness of $S$ and $\\{A_{k}\\}_{k\in[K]}$, the
modified output of Algorithm 1 given by (2.2) satisfies

$R(A_{k^{*}}(S_{k^{*}}))-R(w^{*})\lesssim\frac{1}{\alpha}\left(\gamma_{\texttt{L}_{2},\frac{N}{K}}+\Delta_{\text{opt}}\right)+M\sqrt{\frac{\log(K/\delta)}{N}}.$

######  Remark 4.

Consider $K\asymp\log\left(\frac{1}{\delta}\right)$ and
$\gamma_{\texttt{L}_{2},N}\lesssim\frac{1}{\sqrt{N}}$. Then the bound in
Theorem 2 is roughly
$\mathcal{O}\big{(}\sqrt{\frac{\log(1/\delta)}{N}}+\Delta_{\text{opt}}\big{)}$.
Compared with the generalization error bound in Theorem 1, the excess risk
bound established in Theorem 2 has an additional term of in-expectation
optimization error for minimizing the empirical risk. For deterministic
optimization algorithms such as ERMs with $\Delta_{\text{opt}}=0$, similar
excess risk bounds can be implied by the generic results of Shalev-Shwartz et
al. (2010, Theorem 26) developed for the confidence-boosting approach.

Finally, we comment on the difference between the generalization error and
excess risk analysis inside the considered confidence-boosting framework.
Since the excess risk is always non-negative and its in-expectation bound more
or less standardly known under $L_{2}$-stability , the high-confidence bound
in Theorem 2 can be easily derived via invoking Markov inequality to the
independent runs of algorithm over $K$ disjoint subsets. The generalization
error analysis, however, is significantly more challenging in the sense that
establishing tight in-expectation first moment generalization bound (see Lemma
1) for $L_{2}$-stable randomized algorithms is by itself non-trivial.

##  3 Implications for SGD

In this section we demonstrate the applications of the generic bounds in
Theorem 1 and Theorem 2 to the widely used SGD algorithm. We focus on a
variant of SGD under with-replacement sampling as outlined in Algorithm 2,
which we call $A_{\texttt{SGD-w}}$. In what follows, we denote by
$\\{A_{\texttt{SGD-w},k}\\}_{k\in K}$ the outputs of $A_{\texttt{SGD-w}}$ over
subsets $\\{S_{k}\\}_{k\in K}$ when implemented with Algorithm 1. Our results
readily extend to the without-replacement variant of SGD and the corresponding
results can be found in Appendix D.

Input : Data set
$S=\\{Z_{i}\\}_{i\in[N]}\overset{\text{i.i.d.}}{\sim}\mathcal{D}^{N}$, step-
sizes $\\{\eta_{t}\\}_{t\geq 1}$, #iterations $T$, initialization $w_{0}$.

Output : $\bar{w}_{T}=\frac{1}{T}\sum_{t\in[T]}w_{t}$.

for  _$t=1,2,...,T$_ do

Uniformly randomly sample an index $\xi_{t}\in[N]$ with replacement;

Compute
$w_{t}=\Pi_{\mathcal{W}}\left(w_{t-1}-\eta_{t}\nabla_{w}\ell(w_{t-1};Z_{\xi_{t}})\right)$.

end for

Algorithm 2 $A_{\texttt{SGD-w}}$: SGD under With-Replacement Sampling

###  3.1 Convex Optimization with Smooth Loss

For smooth and convex losses such as logistic loss, we can derive the
following result as a direct consequence of Theorem 1 with $\alpha=1/2$ when
applied to $A_{\texttt{SGD-w}}$. See Appendix C.1 for its proof.

######  Corollary 1.

Suppose that the loss function is $\ell(\cdot;\cdot)$ is convex, $G$-Lipschitz
and $L$-smooth with respect to its first argument, and is bounded in $[0,M]$.
Consider Algorithm 1 specified to $A_{\texttt{SGD-w}}$ with learning rate
$\eta_{t}\leq 2/L$ for $t\geq 1$. Then for any $\delta\in(0,1)$ and
$K\asymp\log(\frac{4}{\delta})$, with probability at least $1-\delta$ over the
randomness of $S$ and $\\{A_{\texttt{SGD-w},k}\\}_{k\in[K]}$, the
generalization error is upper bounded as

$\left|R(A_{\texttt{SGD-w},k^{*}}(S_{k^{*}}))-R_{S}(A_{\texttt{SGD-w},k^{*}}(S_{k^{*}}))\right|\lesssim
G^{2}\sqrt{\frac{1}{N}\left(\sum_{t=1}^{T}\eta^{2}_{t}+\frac{1}{N}\left(\sum_{t=1}^{T}\eta_{t}\right)^{2}\right)}+M\sqrt{\frac{\log(1/\delta)}{N}}.$

######  Remark 5.

For the conventional step-size choice of $\eta_{t}=\frac{2}{L\sqrt{t}}$, the
high probability generalization bound in Corollary 1 is of scale
$\mathcal{O}\big{(}\sqrt{\frac{\log(T)}{N}}+\frac{\sqrt{T}+\sqrt{N\log(1/\delta)}}{N}\big{)}$,
which matches the corresponding $\mathcal{O}(\frac{\sqrt{T}}{N})$ in-
expectation bound for SGD with smooth and convex losses (Hardt et al., 2016).

Combining with the standard in-expectation optimization error bound of convex
SGD (see, e.g., Shamir and Zhang, 2013), we can show the following excess risk
bound as a direct consequence of Theorem 2 to $A_{\texttt{SGD-w}}$ with convex
and smooth losses:

$\displaystyle R(A_{\texttt{SGD-w},k^{*}}(S_{k^{*}}))-R(w^{*})$
$\displaystyle\lesssim$ $\displaystyle
G^{2}\sqrt{\frac{1}{N}\left(\sum_{t=1}^{T}\eta^{2}_{t}+\frac{1}{N}\left(\sum_{t=1}^{T}\eta_{t}\right)^{2}\right)}+M\sqrt{\frac{\log(1/\delta)}{N}}+\frac{\|w_{0}-w^{*}\|^{2}+G^{2}\sum_{t=1}^{T}\eta_{t}^{2}}{\sum_{t=1}^{T}\eta_{t}}.$

With learning rate $\eta_{t}=\frac{2}{L\sqrt{t}}$, the right hand side of the
above scales as
$\mathcal{O}\big{(}\sqrt{\frac{\log(T)}{N}}+\frac{\sqrt{T}+\sqrt{N\log(1/\delta)}}{N}+\frac{\log(T)}{\sqrt{T}}\big{)}$,
which matches the high-probability excess risk bonds of convex SGD by Harvey
et al. (2019, Remark 3.7).

###  3.2 Convex Optimization with Non-smooth Loss

Now we turn to study the case where the loss is convex but not necessarily
smooth, such as the hinge loss and absolute loss. The following result as a
direct consequence of Theorem 1 for the specification of Algorithm 1 to
$A_{\texttt{SGD-w}}$ with non-smooth convex loss and time varying learning
rate $\\{\eta_{t}\\}_{t\geq 1}$. Its proof is provided in Appendix C.2.

######  Corollary 2.

Suppose that the loss function is $\ell(\cdot;\cdot)$ is convex and
$G$-Lipschitz with respect to its first argument, and is bounded in the range
of $[0,M]$. Consider Algorithm 1 specified to $A_{\texttt{SGD-w}}$. Then for
any $\delta\in(0,1)$ and $K\asymp\log(\frac{4}{\delta})$, with probability at
least $1-\delta$ over the randomness of $S$ and
$\\{A_{\texttt{SGD-w},k}\\}_{k\in[K]}$, the generalization error satisfies

$\left|R(A_{\texttt{SGD-w},k^{*}}(S_{k^{*}}))-R_{S}(A_{\texttt{SGD-w},k^{*}}(S_{k^{*}}))\right|\lesssim
G^{2}\sqrt{\sum_{t=1}^{T}\eta^{2}_{t}+\frac{1}{N^{2}}\left(\sum_{t=1}^{T}\eta_{t}\right)^{2}}+M\sqrt{\frac{\log(1/\delta)}{N}}.$

######  Remark 6.

For constant learning rates $\eta_{t}\equiv\eta$, Corollary 2 admits a high-
probability generalization bound of scale
$\mathcal{O}\big{(}\eta\sqrt{T}+\eta\frac{T}{N}+\sqrt{\frac{\log(1/\delta)}{N}}\big{)}$
which matches the near-optimal rate by Bassily et al. (2020, Theorem 3.3).

###  3.3 Non-convex Optimization with Smooth Loss

We further study the performance of Algorithm 1 for SGD on smooth but not
necessarily convex loss functions, such as normalized sigmoid loss (Mason et
al., 1999). The following result is a direct application of Theorem 1 to
$A_{\texttt{SGD-w}}$ with smooth non-convex loss. See Appendix C.3 for its
proof.

######  Corollary 3.

Suppose that the loss function is $\ell(\cdot;\cdot)$ is $G$-Lipschitz and
$L$-smooth with respect to its first argument, and is bounded in $[0,M]$.
Consider Algorithm 1 specified to $A_{\texttt{SGD-w}}$ with
$\eta_{t}\leq\frac{1}{L}$. Let
$u_{t}:=\eta^{2}_{t}+2\eta_{t}\sum_{\tau=1}^{t-1}\exp(L\sum_{i=\tau+1}^{t-1}\eta_{i})\eta_{\tau}$
for all $t\geq 1$. Then for any $\delta\in(0,1)$ and
$K\asymp\log(\frac{4}{\delta})$, with probability at least $1-\delta$ over the
randomness of $S$ and $\\{A_{\texttt{SGD-w},k}\\}_{k\in[K]}$, the
generalization error is upper bounded as

$\left|R(A_{\texttt{SGD-w},k^{*}}(S_{k^{*}}))-R_{S}(A_{\texttt{SGD-w},k^{*}}(S_{k^{*}}))\right|\lesssim
G^{2}\sqrt{\frac{1}{N}\sum_{t=1}^{T}\exp\left(L\sum_{\tau=t+1}^{T}\eta_{\tau}\right)u_{t}}+M\sqrt{\frac{\log(1/\delta)}{N}}.$

######  Remark 7.

For the constant learning rates $\eta_{t}\equiv\frac{1}{LT}$, Corollary 3
admits high-probability generalization bound of scale
$\mathcal{O}\big{(}\sqrt{\frac{\log(1/\delta)}{N}}\big{)}$. For time decaying
learning rates $\eta_{t}=\frac{1}{L\nu t}$ with arbitrary $\nu\geq 1$, it can
be verified that the corresponding bound is of scale
$\mathcal{O}\big{(}\sqrt{\frac{T^{1/\nu}\log(T)}{\nu
N}}+\sqrt{\frac{\log(1/\delta)}{N}}\big{)}$.

##  4 Other Related Work

The idea of using stability of a learning algorithm, namely the sensitivity of
estimated model to the changes in training data, for generalization
performance analysis dates back to the seventies (Vapnik and Chervonenkis,
1974; Rogers and Wagner, 1978; Devroye and Wagner, 1979). For deterministic
learning algorithms, algorithmic stability has been extensively studied with a
bunch of applications to establishing strong generalization and excess risk
bounds for stable learning models like $k$-NN and regularized ERMs (Bousquet
and Elisseeff, 2002; Zhang, 2003; Klochkov and Zhivotovskiy, 2021). The
stability theory for randomized learning algorithms was formally introduced
and investigated by Elisseeff et al. (2005). In a recent breakthrough work
(Hardt et al., 2016), it was shown in that the solution obtained via
stochastic gradient descent is expected to be stable and generalize well for
smooth convex and non-convex loss functions. For non-smooth convex losses, the
stability induced generalization bounds of SGD have been established in
expectation (Lei and Ying, 2020) or deviation (Bassily et al., 2020). In the
work of Kuzborskij and Lampert (2018), a set of data-dependent generalization
bounds for SGD were derived based on the stability of algorithm. More broadly,
generalization bounds for stable learning algorithms that converge to global
minima were established in Charles and Papailiopoulos (2018); Lei and Ying
(2021). For non-convex sparse learning, algorithmic stability theory has been
applied to derive the generalization bounds of the popularly used iterative
hard thresholding (IHT) algorithm (Yuan and Li, 2021). The uniform stability
bounds on SGD have also been extensively used for designing differential
privacy stochastic optimization algorithms (Bassily et al., 2019; Feldman et
al., 2020).

Bagging (or bootstrap aggregating) is one of the earliest yet most popular
ensemble methods that has been widely applied to reduce the variance for
unstable learning algorithms such as decision tree and neural networks
(Breiman, 1996; Opitz and Maclin, 1999), and sometimes stable algorithms such
as SVMs (Valentini and Dietterich, 2003). As an important variant of bagging,
subbagging has been proposed to reduce the computational cost of bagging via
training base models under without-replacement sampling (Bühlmann, 2012). The
stability and generalization bounds of bagging have been analyzed for both
uniform (Elisseeff et al., 2005) and non-uniform (Foster et al., 2019)
averaging schemes. Unlike these prior results for bagging with averaging
aggregation, our bounds are obtained based on a confidence-boosting greedy
aggregation scheme which turns out to yield sharper dependence on the uniform
stability parameter.

The confidence-boosting technique has long been applied for obtaining sharp
high-probability excess risk bounds from the corresponding strong in-
expectation bounds (Shalev-Shwartz et al., 2010; Mehta, 2017). For generic
statistical learning problems, confidence-boosting has been used to convert
any low-confidence learning algorithm with linear dependence on $1/\delta$ to
a high-confidence algorithm with logarithmic factor $\log(1/\delta)$. For
learning with exp-concave losses, a relevant ERM estimator with in-expectation
fast rate of convergence was converted to a high-confidence learning algorithm
with an almost identical fast rate of convergence up to a logarithmic factor
on $1/\delta$ (Mehta, 2017). While sharing a similar spirit of boosting the
confidence, our generalization analysis is substantially more challenging than
those prior excess risk analysis in terms of tightly deriving in-expectation
first moment generalization bound for $L_{2}$-stable randomized algorithms.

##  5 Conclusions

In this paper we presented a meta framework of confidence-boosting for
deriving near-optimal exponential generalization bounds for $L_{2}$-stable
randomized learning algorithms. At a nutshell, our main results in Theorem 1
and Theorem 2 reveal that a carefully designed subbagging process in Algorithm
1 can yield high-confidence generalization and risk bounds under the weak and
distribution dependent notion of $L_{2}$-stability. Our theory has been
substantialized to SGD on both convex and non-convex losses to obtain stronger
generalization bounds especially in the case of time decaying learning rates.
When reduced to deterministic algorithms, the proposed method removes a
logarithmic factor on sample size from the best known bounds through uniform
stability. While sharper in the dependence on tail bound, our confidence-
boosting results are only applicable to one of the independent runs of
algorithm $A$ over $K$ disjoint training subsets of equal size with
$K\asymp\log\left(\frac{1}{\delta}\right)$. It is so far not clear if these
near-optimal bounds can be further extended to the full-batch setting where
the generalization is with respect to the evaluation of algorithm over the
entire training sample. We leave the full understanding of such an open
question raised by Bousquet et al. (2020) for future investigation.

## Acknowledgements

Xiao-Tong Yuan was supported in part by the National Key Research and
Development Program of China under Grant No. 2018AAA0100400 and in part by
Natural Science Foundation of China (NSFC) under Grant No.61876090,
No.61936005 and No.U21B2049.

## References

  * Andonova et al. (2002) Savina Andonova, André Elisseeff, Theodoros Evgeniou, and Massimiliano Pontil.  A simple algorithm for learning stable machines.  In Frank van Harmelen, editor, _Proceedings of the 15th European Conference on Artificial Intelligence (ECAI)_ , pages 513–517, Lyon, France, 2002\.
  * Bassily et al. (2019) Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Guha Thakurta.  Private stochastic convex optimization with optimal rates.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , pages 11279–11288, Vancouver, Canada, 2019.
  * Bassily et al. (2020) Raef Bassily, Vitaly Feldman, Cristóbal Guzmán, and Kunal Talwar.  Stability of stochastic gradient descent on nonsmooth convex losses.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , virtual, 2020.
  * Bengio et al. (2017) Yoshua Bengio, Ian Goodfellow, and Aaron Courville.  _Deep learning_ , volume 1.  MIT press Massachusetts, USA:, 2017.
  * Bousquet and Elisseeff (2002) Olivier Bousquet and André Elisseeff.  Stability and generalization.  _J. Mach. Learn. Res._ , 2:499–526, 2002.
  * Bousquet et al. (2020) Olivier Bousquet, Yegor Klochkov, and Nikita Zhivotovskiy.  Sharper bounds for uniformly stable algorithms.  In _Proceedings of the Conference on Learning Theory (COLT)_ , pages 610–626, Virtual Event [Graz, Austria], 2020.
  * Breiman (1996) Leo Breiman.  Bagging predictors.  _Mach. Learn._ , 24(2):123–140, 1996.
  * Bühlmann (2012) Peter Bühlmann.  Bagging, boosting and ensemble methods.  In _Handbook of computational statistics_ , pages 985–1022. Springer, 2012.
  * Charles and Papailiopoulos (2018) Zachary Charles and Dimitris S. Papailiopoulos.  Stability and generalization of learning algorithms that converge to global optima.  In _Proceedings of the 35th International Conference on Machine Learning (ICML)_ , pages 744–753, Stockholmsmässan, Stockholm, Sweden, 2018\.
  * Devroye and Wagner (1979) Luc Devroye and Terry J. Wagner.  Distribution-free inequalities for the deleted and holdout error estimates.  _IEEE Trans. Inf. Theory_ , 25(2):202–207, 1979\.
  * Elisseeff et al. (2005) André Elisseeff, Theodoros Evgeniou, and Massimiliano Pontil.  Stability of randomized learning algorithms.  _J. Mach. Learn. Res._ , 6:55–79, 2005.
  * Feldman and Vondrák (2018) Vitaly Feldman and Jan Vondrák.  Generalization bounds for uniformly stable algorithms.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , pages 9770–9780, Montréal, Canada, 2018.
  * Feldman and Vondrák (2019) Vitaly Feldman and Jan Vondrák.  High probability generalization bounds for uniformly stable algorithms with nearly optimal rate.  In _Proceedings of the Conference on Learning Theory (COLT)_ , pages 1270–1279, Phoenix, AZ, 2019.
  * Feldman et al. (2020) Vitaly Feldman, Tomer Koren, and Kunal Talwar.  Private stochastic convex optimization: optimal rates in linear time.  In _Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC)_ , pages 439–449, Chicago, IL, 2020.
  * Foster et al. (2019) Dylan J. Foster, Spencer Greenberg, Satyen Kale, Haipeng Luo, Mehryar Mohri, and Karthik Sridharan.  Hypothesis set stability and generalization.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , pages 6726–6736, Vancouver, Canada, 2019.
  * Hardt et al. (2016) Moritz Hardt, Ben Recht, and Yoram Singer.  Train faster, generalize better: Stability of stochastic gradient descent.  In _Proceedings of the 33nd International Conference on Machine Learning (ICML)_ , pages 1225–1234, New York City, NY, 2016.
  * Harvey et al. (2019) Nicholas J. A. Harvey, Christopher Liaw, Yaniv Plan, and Sikander Randhawa.  Tight analyses for non-smooth stochastic gradient descent.  In _Proceedings of the Conference on Learning Theory (COLT)_ , pages 1579–1613, Phoenix, AZ, 2019.
  * Kale et al. (2011) Satyen Kale, Ravi Kumar, and Sergei Vassilvitskii.  Cross-validation and mean-square stability.  In _Proceedings of the Innovations in Computer Science (ICS)_ , pages 487–495, Beijing, China, 2011.
  * Klochkov and Zhivotovskiy (2021) Yegor Klochkov and Nikita Zhivotovskiy.  Stability and deviation optimal risk bounds with convergence rate $o(1/n)$.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , pages 5065–5076, virtual, 2021.
  * Kuzborskij and Lampert (2018) Ilja Kuzborskij and Christoph H. Lampert.  Data-dependent stability of stochastic gradient descent.  In _Proceedings of the 35th International Conference on Machine Learning (ICML)_ , pages 2820–2829, Stockholmsmässan, Stockholm, Sweden, 2018.
  * Lei and Ying (2020) Yunwen Lei and Yiming Ying.  Fine-grained analysis of stability and generalization for stochastic gradient descent.  In _Proceedings of the 37th International Conference on Machine Learning (ICML)_ , pages 5809–5819, Virtual Event, 2020.
  * Lei and Ying (2021) Yunwen Lei and Yiming Ying.  Sharper generalization bounds for learning with gradient-dominated objective functions.  In _Proceedings of the 9th International Conference on Learning Representations (ICLR)_ , Virtual Event, Austria, 2021.
  * Mason et al. (1999) Llew Mason, Jonathan Baxter, Peter L. Bartlett, and Marcus R. Frean.  Boosting algorithms as gradient descent.  In _Advances in Neural Information Processing Systems (NIPS)_ , pages 512–518, Denver, CA, 1999.
  * Mehta (2017) Nishant A. Mehta.  Fast rates with high probability in exp-concave statistical learning.  In _Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS)_ , pages 1085–1093, Fort Lauderdale, FL, 2017.
  * Mukherjee et al. (2006) Sayan Mukherjee, Partha Niyogi, Tomaso A. Poggio, and Ryan M. Rifkin.  Learning theory: stability is sufficient for generalization and necessary and sufficient for consistency of empirical risk minimization.  _Adv. Comput. Math._ , 25(1-3):161–193, 2006\.
  * Nagaraj et al. (2019) Dheeraj Nagaraj, Prateek Jain, and Praneeth Netrapalli.  SGD without replacement: Sharper rates for general smooth convex functions.  In _Proceedings of the 36th International Conference on Machine Learning (ICML)_ , pages 4703–4711, Long Beach, CA, 2019.
  * Opitz and Maclin (1999) David W. Opitz and Richard Maclin.  Popular ensemble methods: An empirical study.  _J. Artif. Intell. Res._ , 11:169–198, 1999.
  * Rakhlin et al. (2012) Alexander Rakhlin, Ohad Shamir, and Karthik Sridharan.  Making gradient descent optimal for strongly convex stochastic optimization.  In _Proceedings of the 29th International Conference on Machine Learning (ICML)_ , Edinburgh, Scotland, UK, 2012.
  * Rogers and Wagner (1978) William H Rogers and Terry J Wagner.  A finite sample distribution-free performance bound for local discrimination rules.  _The Annals of Statistics_ , pages 506–514, 1978.
  * Schapire (1990) Robert E. Schapire.  The strength of weak learnability.  _Mach. Learn._ , 5:197–227, 1990.
  * Schmidt et al. (2011) Mark Schmidt, Nicolas Le Roux, and Francis R. Bach.  Convergence rates of inexact proximal-gradient methods for convex optimization.  In _Advances in Neural Information Processing Systems (NIPS)_ , pages 1458–1466, Granada, Spain, 2011.
  * Shalev-Shwartz et al. (2009) Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan.  Stochastic convex optimization.  In _Proceedings of the 22nd Conference on Learning Theory (COLT)_ , Montreal, Canada, 2009.
  * Shalev-Shwartz et al. (2010) Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan.  Learnability, stability and uniform convergence.  _J. Mach. Learn. Res._ , 11:2635–2670, 2010.
  * Shamir (2016) Ohad Shamir.  Without-replacement sampling for stochastic gradient methods.  In _Advances in Neural Information Processing Systems (NIPS)_ , pages 46–54, Barcelona, Spain, 2016.
  * Shamir and Zhang (2013) Ohad Shamir and Tong Zhang.  Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes.  In _Proceedings of the 30th International Conference on Machine Learning (ICML)_ , pages 71–79, Atlanta, GA, 2013.
  * Valentini and Dietterich (2003) Giorgio Valentini and Thomas G. Dietterich.  Low bias bagged support vector machines.  In _Proceedings of the Twentieth International Conference on Machine Learning (ICML)_ , pages 752–759, Washington, DC, 2003.
  * Vapnik and Chervonenkis (1974) V. N. Vapnik and A. Ya. Chervonenkis.  _Theory of Pattern Recognition [in Russian]_.  Nauka, 1974.
  * Yuan and Li (2021) Xiaotong Yuan and Ping Li.  Stability and risk bounds of iterative hard thresholding.  In _Proceedings of the 24th International Conference on Artificial Intelligence and Statistics (AISTATS)_ , pages 1702–1710, Virtual Event, 2021.
  * Zhang (2003) Tong Zhang.  Leave-one-out bounds for kernel methods.  _Neural Comput._ , 15(6):1397–1437, 2003.
  * Zhou et al. (2022) Yi Zhou, Yingbin Liang, and Huishuai Zhang.  Understanding generalization error of SGD in nonconvex optimization.  _Mach. Learn._ , 111(1):345–375, 2022.

##  Appendix A Auxiliary Lemmas

We need the following lemma from Hardt et al. [2016] which shows that SGD
iteration is non-expansive on convex and smooth loss.

######  Lemma 2 (Hardt et al. [2016]).

Assume that $f$ is convex and $L$-smooth. Then for any
$w,w^{\prime}\in\mathcal{W}$ and $\alpha\leq 2/L$, we have the following bound
holds

$\|w-\alpha\nabla f(w)-(w^{\prime}-\alpha\nabla
f(w^{\prime}))\|\leq\|w-w^{\prime}\|.$

The following lemma, which can be proved by induction [see, e.g., Schmidt et
al., 2011], will be used to prove the main results in Section 3.

######  Lemma 3.

Assume that the nonnegative sequence $\\{u_{\tau}\\}_{\tau\geq 1}$ satisfies
the following recursion for all $t\geq 1$:

$u^{2}_{t}\leq S_{t}+\sum_{\tau=1}^{t}\alpha_{\tau}u_{\tau},$

with $\\{S_{\tau}\\}_{\tau\geq 1}$ an increasing sequence, $S_{0}\geq
u_{0}^{2}$ and $\alpha_{\tau}\geq 0$ for all $\tau$. Then, the following
inequality holds for all $t\geq 1$:

$u_{t}\leq\sqrt{S_{t}}+\sum_{\tau=1}^{t}\alpha_{\tau}.$

For analyzing SGD with convex and non-smooth loss functions, we need the
following lemma by Bassily et al. [2020, Lemma 3.1] that quantifies the
deviation between the online gradient descent trajectories.

######  Lemma 4 (Bassily et al. [2020]).

Consider the two sequences $\\{w_{t}\\}_{t\geq 0}$ and
$\\{w^{\prime}_{t}\\}_{t\geq 0}$ generated according to the following
recursions respectively over the convex and $G$-Lipschitz objectives
$\\{f_{t}\\}_{t\geq 0}$ and $\\{f^{\prime}_{t}\\}_{t\geq 0}$ from
$w_{0}=w^{\prime}_{0}$:

$\displaystyle w_{t}=$
$\displaystyle\Pi_{\mathcal{W}}\left(w_{t-1}-\eta_{t}\nabla
f_{t-1}(w_{t-1})\right)$ $\displaystyle w^{\prime}_{t}=$
$\displaystyle\Pi_{\mathcal{W}}\left(w^{\prime}_{t-1}-\eta_{t}\nabla
f^{\prime}_{t-1}(w^{\prime}_{t-1})\right).$

Let $t_{0}:=\inf\\{t:f_{t}\neq f^{\prime}_{t}\\}$ and
$\beta_{t}:=\mathbf{1}_{\left\\{f_{t}\neq f^{\prime}_{t}\right\\}}$. Then for
any $T\geq 1$,

$\|w_{T}-w^{\prime}_{T}\|\leq
2G\sqrt{\sum_{t=t_{0}}^{T-1}\eta_{t}^{2}}+4G\sum_{t=t_{0}+1}^{T-1}\eta_{t}\beta_{t}.$

##  Appendix B Proofs for the Results in Section 2

In this section, we present the technical proofs for the main results stated
in Section 2.

###  B.1 Proof of Lemma 1

We need the following lemma essentially from Bousquet et al. [2020] that
provides a first moment bound for the sum of random functions.

######  Lemma 5.

Let $S=\\{Z_{1},Z_{2},...,Z_{N}\\}$ be a set of i.i.d. random variables valued
in $\mathcal{Z}$. Let $g_{1},...,g_{N}$ be a set of measurable functions
$g_{i}:\mathcal{Z}^{N}\mapsto\mathbb{R}$ that satisfy $\|g_{i}(S)\|_{2}\leq M$
and $\mathbb{E}_{Z_{i}}[g_{i}(S)]=0$ for all $i\in[N]$. Then we have

$\left\|\sum_{i=1}^{N}g_{i}(S)\right\|_{2}\leq\sqrt{\sum_{i\neq
j}\left\|g_{i}(S)-g_{i}(S^{(j)})\right\|_{2}^{2}}+M\sqrt{N}.$

###### Proof.

We reproduce the proof in view of the argument in Bousquet et al. [2020,
Section 5] showing that $\\{g_{i}\\}$ are weakly correlated. For any $i\neq
j$, since $\mathbb{E}_{Z_{i}}[g_{i}(S)]=0$ and
$\mathbb{E}_{Z_{j}}[g_{j}(S)]=0$, we can verify that

$\displaystyle\mathbb{E}_{S}\left[g_{i}(S^{(j)})g_{j}(S)\right]=$
$\displaystyle\mathbb{E}_{S\setminus
Z_{j}}\left[\mathbb{E}_{Z_{j}}\left[g_{i}(S^{(j)})g_{j}(S)\mid S\setminus
Z_{j}\right]\right]$ $\displaystyle=$ $\displaystyle\mathbb{E}_{S\setminus
Z_{j}}\left[g_{i}(S^{(j)})\mathbb{E}_{Z_{j}}\left[g_{j}(S)\mid S\setminus
Z_{j}\right]\right]=0,$

where we have used the independence of the elements in
$S\cup\\{Z^{\prime}_{j}\\}$. Similarly, we can show that

$\mathbb{E}_{S}\left[g_{i}(S)g_{j}(S^{(i)})\right]=\mathbb{E}_{S}\left[g_{i}(S^{(j)})g_{j}(S^{(i)})\right]=0.$

Then it follows that for any $i\neq j$,

$\displaystyle\left|\mathbb{E}_{S}\left[g_{i}(S)g_{j}(S)\right]\right|=$
$\displaystyle\left|\mathbb{E}_{S,S^{(i)},S^{(j)}}\left[g_{i}(S)g_{j}(S)\right]\right|$
$\displaystyle=$
$\displaystyle\left|\mathbb{E}_{S,S^{(i)},S^{(j)}}\left[(g_{i}(S)-g_{i}(S^{(j)}))(g_{j}(S)-g_{j}(S^{(i)}))\right]\right|$
$\displaystyle\leq$
$\displaystyle\mathbb{E}_{S,S^{(i)},S^{(j)}}\left[\left|(g_{i}(S)-g_{i}(S^{(j)}))(g_{j}(S)-g_{j}(S^{(i)}))\right|\right].$

Based on the above bound we can further show that

$\displaystyle\left\|\sum_{i=1}^{N}g_{i}(S)\right\|_{2}=$
$\displaystyle\sqrt{\mathbb{E}_{S}\left[\left(\sum_{i=1}^{N}g_{i}(S)\right)^{2}\right]}=\sqrt{\sum_{i\neq
j}\mathbb{E}_{S}\left[g_{i}(S)g_{j}(S)\right]+\sum_{i=1}^{N}\mathbb{E}_{S}[g^{2}_{i}(S)]}$
$\displaystyle\leq$ $\displaystyle\sqrt{\sum_{i\neq
j}\mathbb{E}_{S,S^{(i)},S^{(j)}}\left[\left|(g_{i}(S)-g_{i}(S^{(j)}))(g_{j}(S)-g_{j}(S^{(i)}))\right|\right]}+M\sqrt{N}$
$\displaystyle\leq$ $\displaystyle\sqrt{\frac{1}{2}\sum_{i\neq
j}\mathbb{E}_{S,S^{(i)},S^{(j)}}\left[\left(g_{i}(S)-g_{i}(S^{(j)})\right)^{2}+\left(g_{j}(S)-g_{j}(S^{(i)})\right)^{2}\right]}+M\sqrt{N}$
$\displaystyle=$ $\displaystyle\sqrt{\sum_{i\neq
j}\mathbb{E}_{S,S^{(j)}}\left[\left(g_{i}(S)-g_{i}(S^{(j)})\right)^{2}\right]}+M\sqrt{N}$
$\displaystyle=$ $\displaystyle\sqrt{\sum_{i\neq
j}\left\|g_{i}(S)-g_{i}(S^{(j)})\right\|_{2}^{2}}+M\sqrt{N}.$

This proves the desired bound. ∎

Now we are ready to prove the result in Lemma 1.

###### Proof of Lemma 1.

Let us consider $h_{i}(S):=R(A(S))-\ell(A(S);Z_{i})$ and
$g_{i}(S)=h_{i}(S)-\mathbb{E}_{Z_{i}}[h_{i}(S)]$ for $i\in[N]$. Then by
assumption we have

$\mathbb{E}_{Z_{i}}[g_{i}(S)]=0,\ \ \ \|g_{i}(S)\|_{2}\leq\|h_{i}(S)\|_{2}\leq
2M.$

For any $j\neq i$, since the loss is non-negative, it can be verified that

$|g_{i}(S)-g_{i}(S^{(j)})|\leq\max\left\\{\left|h_{i}(S)-h_{i}(S^{(j)})\right|,\left|\mathbb{E}_{Z_{i}}[h_{i}(S)-h_{i}(S^{(j)})]\right|\right\\},$

which readily implies

$\left\|g_{i}(S)-g_{i}(S^{(j)})\right\|_{2}\leq\left\|h_{i}(S)-h_{i}(S^{(j)})\right\|_{2}\leq
2\gamma_{\texttt{L}_{2},N},$

where in the last inequality we have used the $L_{2}$-stability conditions on
$A$. Then invoking Lemma 5 to $\\{g_{i}\\}$ yields

$\left\|\sum_{i=1}^{N}g_{i}(S)\right\|_{2}\leq\sqrt{\sum_{i\neq
j}\left\|g_{i}(S)-g_{i}(S^{(j)})\right\|_{2}^{2}}+2M\sqrt{N}\leq
2N\gamma_{\texttt{L}_{2},N}+2M\sqrt{N}.$ (B.1)

Further, it can be verified that

$\displaystyle\left\|\sum_{i=1}^{N}\mathbb{E}_{Z_{i}}[h_{i}(S)]\right\|_{2}=$
$\displaystyle\left\|\sum_{i=1}^{N}\mathbb{E}_{Z_{i}}[R(A(S))-\ell(A(S);Z_{i})]\right\|_{2}$
(B.2) $\displaystyle=$
$\displaystyle\left\|\sum_{i=1}^{N}\mathbb{E}_{Z_{i},Z^{\prime}_{i}}[\ell(A(S);Z^{\prime}_{i})-\ell(A(S);Z_{i})]\right\|_{2}$
$\displaystyle=$
$\displaystyle\left\|\sum_{i=1}^{N}\mathbb{E}_{Z_{i}}\left[\mathbb{E}_{Z^{\prime}_{i}}[\ell(A(S);Z^{\prime}_{i})]-\mathbb{E}_{Z^{\prime}_{i}}[\ell(A(S^{(i)});Z^{\prime}_{i})]\right]\right\|_{2}$
$\displaystyle\leq$
$\displaystyle\sum_{i=1}^{N}\left\|\ell(A(S);Z^{\prime}_{i})-\ell(A(S^{(i)});Z^{\prime}_{i})\right\|_{2}\leq
N\gamma_{\texttt{L}_{2},N}.$

By combining (B.1) and (B.2) we obtain

$\displaystyle\mathbb{E}_{A,S}\left[\left|R(A(S))-R_{S}(A(S))\right|\right]$
$\displaystyle=$ $\displaystyle\left\|R(A(S))-R_{S}(A(S))\right\|_{1}$
$\displaystyle\leq$ $\displaystyle\left\|R(A(S))-R_{S}(A(S))\right\|_{2}$
$\displaystyle=$
$\displaystyle\frac{1}{N}\left\|\sum_{i=1}^{N}\left(g_{i}(S)+\mathbb{E}_{Z_{i}}[h_{i}(S)]\right)\right\|_{2}$
$\displaystyle\leq$
$\displaystyle\frac{1}{N}\left\|\sum_{i=1}^{N}g_{i}(S)\right\|_{2}+\frac{1}{N}\left\|\sum_{i=1}^{N}\mathbb{E}_{Z_{i}}[h_{i}(S)]\right\|_{2}$
$\displaystyle\leq$ $\displaystyle
3\gamma_{\texttt{L}_{2},N}+\frac{2M}{\sqrt{N}}.$

The proof is completed. ∎

###  B.2 Proof of Theorem 1

We first establish the following intermediate result that captures the effects
of subbagging on randomized algorithms: it basically tells that with
$K\asymp\log(\frac{1}{\delta})$, at least one of the solutions generated by
subbagging generalizes well with high probability.

######  Lemma 6.

Suppose that a randomized learning algorithm
$A:\mathcal{Z}^{N}\mapsto\mathcal{W}$ has $L_{2}$-stability by
$\gamma_{\texttt{L}_{2},N}$. Assume that the loss function satisfies
$\|\ell(A(S);Z)\|_{2}\leq M$. Then for any $\alpha,\delta\in(0,1)$ and
$K\geq\frac{\log(2/\delta)}{1-\alpha}$, with probability at least $1-\delta$
over the randomness of $\\{(A_{k},S_{k})\\}_{k\in[K]}$, the sequence
$\\{A_{k}(S_{k})\\}_{k\in[K]}$ generated by Algorithm 1 satisfies

$\min_{k\in[K]}\left|R(A_{k}(S_{k}))-R_{S_{k}}(A_{k}(S_{k}))\right|\lesssim\frac{1}{\alpha}\left(\gamma_{\texttt{L}_{2},\frac{N}{K}}+M\sqrt{\frac{K}{N}}\right).$

###### Proof.

From Lemma 1 we have that over randomized algorithm $A$ and data $\tilde{S}$
with $|\tilde{S}|=\frac{N}{K}$,

$\mathbb{E}_{A,\tilde{S}}\left[|R(A(\tilde{S}))-R_{\tilde{S}}(A(\tilde{S}))|\right]\leq
3G\gamma_{\texttt{L}_{2},\frac{N}{K}}+2M\sqrt{\frac{K}{N}}.$

Since $\\{A_{k},S_{k}\\}_{k\in[K]}$ are independent to each other, by Markov
inequality we know that

$\mathbb{P}_{\\{A_{k},S_{k}\\}}\left(\min_{k\in[K]}\left|R(A_{k}(S_{k}))-R_{S_{k}}(A_{k}(S_{k}))\right|\geq\frac{1}{\alpha}\left(3\gamma_{\texttt{L}_{2},\frac{N}{K}}+2M\sqrt{\frac{K}{N}}\right)\right)\leq\alpha^{K}\leq\delta,$

which implies the desired bound. ∎

With Lemma 6 in place, we can proceed to prove the main result in Theorem 1.

###### Proof of Theorem 1.

Let us consider the following three events:

$\displaystyle\mathcal{E}:=$
$\displaystyle\left\\{\left|R(A_{k^{*}}(S_{k^{*}}))-R_{S}(A_{k^{*}}(S_{k^{*}}))\right|\lesssim\frac{1}{\alpha
K}\left(\gamma_{\texttt{L}_{2},\frac{N}{K}}+M\sqrt{\frac{K}{N}}\right)+M\sqrt{\frac{K\log(K/\delta)}{(K-1)N}}\right\\},$
$\displaystyle\mathcal{E}_{1}:=$
$\displaystyle\left\\{\max_{k\in[K]}|R(A_{k}(S_{k}))-R_{S\setminus
S_{k}}(A_{k}(S_{k}))|\lesssim
M\sqrt{\frac{K\log(K/\delta)}{(K-1)N}}\right\\},$
$\displaystyle\mathcal{E}_{2}:=$
$\displaystyle\left\\{\min_{k\in[K]}\left|R(A_{k}(S_{k}))-R_{S_{k}}(A_{k}(S_{k}))\right|\lesssim\frac{1}{\alpha}\left(\gamma_{\texttt{L}_{2},\frac{N}{K}}+M\sqrt{\frac{K}{N}}\right)\right\\}.$

We can show that $\mathcal{E}\supseteq\mathcal{E}_{1}\cap\mathcal{E}_{2}$.
Indeed, suppose that $\mathcal{E}_{1}$ and $\mathcal{E}_{2}$ simultaneously
occur. Consequently the following inequality is valid:

$\displaystyle\left|R(A_{k^{*}}(S_{k^{*}}))-R_{S}(A_{k^{*}}(S_{k^{*}}))\right|$
$\displaystyle=$
$\displaystyle\left|R(A_{k^{*}}(S_{k^{*}}))-\frac{1}{K}R_{S_{k^{*}}}(A_{k^{*}}(S_{k^{*}}))-\frac{K-1}{K}R_{S\setminus
S_{k^{*}}}(A_{k^{*}}(S_{k^{*}}))\right|$ $\displaystyle\leq$
$\displaystyle\frac{1}{K}\left|R(A_{k^{*}}(S_{k^{*}}))-R_{S_{k^{*}}}(A_{k^{*}}(S_{k^{*}}))\right|+\frac{K-1}{K}\left|R(A_{k^{*}}(S_{k^{*}}))-R_{S\setminus
S_{k^{*}}}(A_{k^{*}}(S_{k^{*}}))\right|$ $\displaystyle\leq$
$\displaystyle\frac{1}{K}\left|R_{S\setminus
S_{k^{*}}}(A_{k^{*}}(S_{k^{*}}))-R_{S_{k^{*}}}(A_{k^{*}}(S_{k^{*}}))\right|+\left|R(A_{k^{*}}(S_{k^{*}}))-R_{S\setminus
S_{k^{*}}}(A_{k^{*}}(S_{k^{*}}))\right|$ $\displaystyle\overset{\zeta_{1}}{=}$
$\displaystyle\frac{1}{K}\min_{k\in[K]}\left|R_{S\setminus
S_{k}}(A_{k}(S_{k}))-R_{S_{k}}(A_{k}(S_{k}))\right|+\left|R(A_{k^{*}}(S_{k^{*}}))-R_{S\setminus
S_{k^{*}}}(A_{k^{*}}(S_{k^{*}}))\right|$ $\displaystyle=$
$\displaystyle\frac{1}{K}\min_{k\in[K]}\left|R_{S\setminus
S_{k}}(A_{k}(S_{k}))-R(A_{k}(S_{k}))+R(A_{k}(S_{k}))-R_{S_{k}}(A_{k}(S_{k}))\right|$
$\displaystyle+\left|R(A_{k^{*}}(S_{k^{*}}))-R_{S\setminus
S_{k^{*}}}(A_{k^{*}}(S_{k^{*}}))\right|$ $\displaystyle\leq$
$\displaystyle\frac{1}{K}\min_{k\in[K]}\left|R(A_{k}(S_{k}))-R_{S_{k}}(A_{k}(S_{k}))\right|+\frac{1}{K}\max_{k\in[K]}\left|R_{S\setminus
S_{k}}(A_{k}(S_{k}))-R(A_{k}(S_{k}))\right|$
$\displaystyle+\left|R(A_{k^{*}}(S_{k^{*}}))-R_{S\setminus
S_{k^{*}}}(A_{k^{*}}(S_{k^{*}}))\right|$ $\displaystyle\leq$
$\displaystyle\frac{1}{K}\min_{k\in[K]}\left|R(A_{k}(S_{k}))-R_{S_{k}}(A_{k}(S_{k}))\right|+\frac{K+1}{K}\max_{k\in[K]}\left|R(A_{k}(S_{k}))-R_{S\setminus
S_{k}}(A_{k}(S_{k}))\right|$ $\displaystyle\overset{\zeta_{2}}{\lesssim}$
$\displaystyle\frac{1}{\alpha
K}\left(\gamma_{\texttt{L}_{2},\frac{N}{K}}+M\sqrt{\frac{K}{N}}\right)+M\sqrt{\frac{K\log(K/\delta)}{(K-1)N}},$

where in “$\zeta_{1}$” we have used the definition of $k^{*}$, and
“$\zeta_{2}$” follows from $\mathcal{E}_{1},\mathcal{E}_{2}$. With leading
terms preserved in the above we can see that $\mathcal{E}$ occurs.

Next we can show that
$\mathbb{P}_{S,\\{A_{k}\\}}(\overline{\mathcal{E}_{1}})\leq\frac{\delta}{2}$.
Toward this end, let us consider the following events for all $k\in[K]$:

$\mathcal{E}^{k}_{1}:=\left\\{|R(A_{k}(S_{k}))-R_{S\setminus
S_{k}}(A_{k}(S_{k}))|\lesssim
M\sqrt{\frac{K\log(K/\delta)}{(K-1)N}}\right\\}.$

Clearly, it is true that
$\mathcal{E}_{1}=\bigcap_{k=1}^{K}\mathcal{E}^{k}_{1}$. It is sufficient to
prove that
$\mathbb{P}_{S,A_{k}}\left(\overline{\mathcal{E}^{k}_{1}}\right)\leq\frac{\delta}{2K}$
holds for each $k\in[K]$. Indeed, consider the random indication function
$\beta(S,A_{k}):=\mathbf{1}_{\overline{\mathcal{E}^{k}_{1}}}$ associated with
the event $\overline{\mathcal{E}^{k}_{1}}$. Then we have the following holds
for each $k\in[K]$:

$\displaystyle\mathbb{P}_{S,A_{k}}\left(\overline{\mathcal{E}^{k}_{1}}\right)$
$\displaystyle=$
$\displaystyle\mathbb{E}_{S,A_{k}}\left[\beta(S,A_{k})\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}_{A_{k},S_{k}}\left[\mathbb{E}_{S\setminus S_{k}\mid
A_{k},S_{k}}\left[\beta(S,A_{k})\mid A_{k},S_{k}\right]\right]$
$\displaystyle\overset{\zeta_{1}}{=}$
$\displaystyle\mathbb{E}_{A_{k},S_{k}}\left[\mathbb{E}_{S\setminus
S_{k}}\left[\beta(S,A_{k})\mid A_{k},S_{k}\right]\right]$ $\displaystyle=$
$\displaystyle\mathbb{E}_{A_{k},S_{k}}\left[\mathbb{P}_{S\setminus
S_{k}}\left(|R(A_{k}(S_{k}))-R_{S\setminus S_{k}}(A_{k}(S_{k}))|\gtrsim
M\sqrt{\frac{K\log(K/\delta)}{(K-1)N}}\right)\mid A_{k},S_{k}\right]$
$\displaystyle\overset{\zeta_{2}}{\leq}$
$\displaystyle\mathbb{E}_{A_{k},S_{k}}\left[\frac{\delta}{2K}\mid
A_{k},S_{k}\right]=\frac{\delta}{2K},$

where in “$\zeta_{1}$” we have used the independence between
$\\{A_{k},S_{k}\\}$ and $S\setminus S_{k}$, and “$\zeta_{2}$” is due to
Hoeffding’s inequality conditioned on $\\{A_{k},S_{k}\\}$, keeping in mind
that $A_{k}(S_{k})$ is independent on the data set $S\setminus S_{k}$ of size
$(1-1/K)N$. It follows by union probability that

$\mathbb{P}_{S,\\{A_{k}\\}}\left(\overline{\mathcal{E}_{1}}\right)=\mathbb{P}_{S,\\{A_{k}\\}}\left(\bigcup_{k=1}^{K}\overline{\mathcal{E}^{k}_{1}}\right)\leq\sum_{k=1}^{K}\mathbb{P}_{S,A_{k}}\left(\overline{\mathcal{E}^{k}_{1}}\right)\leq\frac{\delta}{2}.$

Further, from the part(b) of Lemma 6 we have
$\mathbb{P}_{S,\\{A_{k}\\}}(\bar{\mathcal{E}_{2}})\leq\frac{\delta}{2}$.
Combining this and the preceding bound yields

$\mathbb{P}_{S,\\{A_{k}\\}}\left(\mathcal{E}\right)\geq\mathbb{P}_{S,\\{A_{k}\\}}\left(\mathcal{E}_{1}\cap\mathcal{E}_{2}\right)\geq
1-\mathbb{P}_{S,\\{A_{k}\\}}\left(\bar{\mathcal{E}_{1}}\right)-\mathbb{P}_{S,\\{A_{k}\\}}(\bar{\mathcal{E}_{2}})\geq
1-\frac{\delta}{2}-\frac{\delta}{2}=1-\delta.$

This implies the desired result in part(b) as $K/(K-1)\leq 2$ for $K\geq 2$. ∎

###  B.3 Proof of Theorem 2

We first present the following simple lemma about the in-expectation risk
bounds of a randomized algorithm which will be used in our analysis.

######  Lemma 7.

Suppose that a randomized learning algorithm
$A:\mathcal{Z}^{N}\mapsto\mathcal{W}$ has $L_{2}$-stability by
$\gamma_{\texttt{L}_{2},N}$. Then,

$\mathbb{E}_{A,S}\left[R(A(S))-R(w^{*})\right]\leq\gamma_{\texttt{L}_{2},N}+\Delta_{\text{opt}}.$

###### Proof.

It can be verified that

$\displaystyle\left|\mathbb{E}_{A,S}\left[R(A(S))-R_{S}(A(S))\right]\right|$
(B.3) $\displaystyle=$
$\displaystyle\frac{1}{N}\left|\sum_{i=1}^{N}\mathbb{E}_{A,S}[R(A(S))-\ell(A(S);Z_{i})]\right|$
$\displaystyle=$
$\displaystyle\frac{1}{N}\left|\sum_{i=1}^{N}\mathbb{E}_{A,S,Z^{\prime}_{i}}[\ell(A(S);Z^{\prime}_{i})-\ell(A(S);Z_{i})]\right|$
$\displaystyle=$
$\displaystyle\frac{1}{N}\left|\sum_{i=1}^{N}\mathbb{E}_{A,S,Z^{\prime}_{i}}[\ell(A(S);Z^{\prime}_{i})-\ell(A(S^{(i)});Z^{\prime}_{i})]\right|$
$\displaystyle\leq$
$\displaystyle\frac{1}{N}\sum_{i=1}^{N}\left\|\ell(A(S);Z^{\prime}_{i})-\ell(A(S^{(i)});Z^{\prime}_{i})\right\|_{2}\leq\gamma_{\texttt{L}_{2},N}.$

By standard risk decomposition we can show that

$\displaystyle\mathbb{E}_{A,S}\left[R(A(S))-R(w^{*})\right]$ $\displaystyle=$
$\displaystyle\mathbb{E}_{A,S}\left[R(A(S))-R_{S}(A(S))+R_{S}(A(S))-R_{S}(w^{*})+R_{S}(w^{*})-R(w^{*})\right]$
$\displaystyle\leq$
$\displaystyle\left|\mathbb{E}_{A,S}\left[R(A(S))-R_{S}(A(S))\right]\right|+\Delta_{\text{opt}}$
$\displaystyle\leq$
$\displaystyle\gamma_{\texttt{L}_{2},N}+\Delta_{\text{opt}},$

where in the last inequality we have used (B.3). ∎

######  Lemma 8.

Suppose that a randomized learning algorithm
$A:\mathcal{Z}^{N}\mapsto\mathcal{W}$ has $L_{2}$-stability by
$\gamma_{\texttt{L}_{2},N}$. Then for any $\alpha,\delta\in(0,1)$ and
$K\geq\frac{\log(2/\delta)}{1-\alpha}$, with probability at least $1-\delta$
over the randomness of $\\{(A_{k},S_{k})\\}_{k\in[K]}$, the sequence
$\\{A_{k}(S_{k})\\}_{k\in[K]}$ generated by Algorithm 1 with the modified
output satisfies

$\min_{k\in[K]}R(A_{k}(S_{k}))-R(w^{*})\lesssim\frac{1}{\alpha}\left(\gamma_{\texttt{L}_{2},\frac{N}{K}}+\Delta_{\text{opt}}\right).$

###### Proof.

Recall the modified output $A_{k^{*}}(S_{k^{*}})$ where
$k^{*}=\mathop{\arg\min}_{k\in[K]}R_{S\setminus S_{k}}(A_{k}(S_{k}))$. From
Lemma 7 we have that over randomized algorithm $A$ and data $\tilde{S}$ with
$|\tilde{S}|=\frac{N}{K}$,

$\mathbb{E}_{A,\tilde{S}}\left[R(A(\tilde{S}))-R(w^{*})\right]\leq\gamma_{\texttt{L}_{2},\frac{N}{K}}+\Delta_{\text{opt}}.$

Since $\\{A_{k},S_{k}\\}_{k\in[K]}$ are independent to each other, by Markov
inequality we know that

$\mathbb{P}_{\\{A_{k},S_{k}\\}}\left(\min_{k\in[K]}R(A_{k}(S_{k}))-R(w^{*})\geq\frac{1}{\alpha}\left(\gamma_{\texttt{L}_{2},\frac{N}{K}}+\Delta_{\text{opt}}\right)\right)\leq\alpha^{K}\leq\delta,$

which implies the desired bound in part(b). ∎

Next we proceed to prove the main result in Theorem 2.

###### Proof of Theorem 2.

Let us consider the following three events:

$\displaystyle\mathcal{E}:=$
$\displaystyle\left\\{\left|R(A_{k^{*}}(S_{k^{*}}))-R_{S}(A_{k^{*}}(S_{k^{*}}))\right|\lesssim\frac{1}{\alpha}\left(\gamma_{\texttt{L}_{2},\frac{N}{K}}+\Delta_{\text{opt}}\right)+M\sqrt{\frac{K\log(K/\delta)}{(K-1)N}}\right\\},$
$\displaystyle\mathcal{E}_{1}:=$
$\displaystyle\left\\{\max_{k\in[K]}|R(A_{k}(S_{k}))-R_{S\setminus
S_{k}}(A_{k}(S_{k}))|\lesssim
M\sqrt{\frac{K\log(K/\delta)}{(K-1)N}}\right\\},$
$\displaystyle\mathcal{E}_{2}:=$
$\displaystyle\left\\{\min_{k\in[K]}R(A_{k}(S_{k}))-R(w^{*})\lesssim\frac{1}{\alpha}\left(\gamma_{\texttt{L}_{2},\frac{N}{K}}+\Delta_{\text{opt}}\right)\right\\}.$

Similarly, we show that
$\mathcal{E}\supseteq\mathcal{E}_{1}\cap\mathcal{E}_{2}$. Indeed, suppose that
$\mathcal{E}_{1}$ and $\mathcal{E}_{2}$ simultaneously occur. Consequently the
following inequality is valid:

$\displaystyle R(A_{k^{*}}(S_{k^{*}}))-R(w^{*})$ $\displaystyle=$
$\displaystyle R(A_{k^{*}}(S_{k^{*}}))-R_{S\setminus
S_{k^{*}}}(A_{k^{*}}(S_{k^{*}}))+R_{S\setminus
S_{k^{*}}}(A_{k^{*}}(S_{k^{*}}))-R(w^{*})$
$\displaystyle\overset{\zeta_{1}}{=}$ $\displaystyle
R(A_{k^{*}}(S_{k^{*}}))-R_{S\setminus
S_{k^{*}}}(A_{k^{*}}(S_{k^{*}}))+\min_{k\in[K]}R_{S\setminus
S_{k}}(A_{k}(S_{k}))-R(w^{*})$ $\displaystyle=$ $\displaystyle
R(A_{k^{*}}(S_{k^{*}}))-R_{S\setminus
S_{k^{*}}}(A_{k^{*}}(S_{k^{*}}))+\min_{k\in[K]}\left\\{R_{S\setminus
S_{k}}(A_{k}(S_{k}))-R(A_{k}(S_{k}))+R(A_{k}(S_{k}))-R(w^{*})\right\\}$
$\displaystyle\leq$
$\displaystyle\min_{k\in[K]}(R(A_{k}(S_{k}))-R(w^{*}))+2\max_{k\in[K]}\left|R_{S\setminus
S_{k}}(A_{k}(S_{k}))-R(A_{k}(S_{k}))\right|$
$\displaystyle\overset{\zeta_{2}}{\lesssim}$
$\displaystyle\frac{1}{\alpha}\left(\gamma_{\texttt{L}_{2},\frac{N}{K}}+\Delta_{\text{opt}}\right)+M\sqrt{\frac{K\log(K/\delta)}{(K-1)N}},$

where in “$\zeta_{1}$” we have used the definition of $k^{*}$, and
“$\zeta_{2}$” follows from $\mathcal{E}_{1},\mathcal{E}_{2}$. With leading
terms preserved in the above we can see that $\mathcal{E}$ occurs.

Based on the identical proof argument as that of the part(b) of Theorem 1 we
can show that
$\mathbb{P}_{S,\\{A_{k}\\}}(\overline{\mathcal{E}_{1}})\leq\frac{\delta}{2}$.
Further, from the part(b) of Lemma 8 we have
$\mathbb{P}_{S,\\{A_{k}\\}}(\bar{\mathcal{E}_{2}})\leq\frac{\delta}{2}$.
Combining this and the preceding bound yields

$\mathbb{P}_{S,\\{A_{k}\\}}\left(\mathcal{E}\right)\geq\mathbb{P}_{S,\\{A_{k}\\}}\left(\mathcal{E}_{1}\cap\mathcal{E}_{2}\right)\geq
1-\mathbb{P}_{S,\\{A_{k}\\}}\left(\bar{\mathcal{E}_{1}}\right)-\mathbb{P}_{S,\\{A_{k}\\}}(\bar{\mathcal{E}_{2}})\geq
1-\frac{\delta}{2}-\frac{\delta}{2}=1-\delta.$

This implies the desired result in part(b) as $K/(K-1)\leq 2$ for $K\geq 2$. ∎

##  Appendix C Proofs for the Results in Section 3

In this section, we present the technical proofs for the main results stated
in Section 3.

###  C.1 Proof of Corollary 1

We begin with presenting and proving the following lemma that gives the
$L_{2}$-stability bounds for $A_{\texttt{SGD-w}}$ on convex and smooth loss
functions such as logistic loss.

######  Lemma 9.

Suppose that the loss function is $\ell(\cdot;\cdot)$ is convex, $G$-Lipschitz
and $L$-smooth with respect to its first argument. Assume that $\eta_{t}\leq
2/L$ for all $t\geq 1$. Then $A_{\texttt{SGD-w}}$ has $L_{2}$-stability by

$\gamma_{\texttt{L}_{2},N}=G^{2}\sqrt{\frac{40}{N}\left(\sum_{t=1}^{T}\eta^{2}_{t}+\frac{1}{N}\left(\sum_{t=1}^{T}\eta_{t}\right)^{2}\right)}.$

###### Proof.

For any pair of data sets $S,S^{\prime}$ that differ in a single element, let
us define the sequences $\\{w_{t}\\}_{t\in[T]}$ and
$\\{w^{\prime}_{t}\\}_{t\in[T]}$ that are respectively generated over $S$ and
$S^{\prime}$ via $A_{\texttt{SGD-w}}$ via sample path
$\xi=\\{\xi_{t}\\}_{t\in[T]}$. Note by assumption that $w_{0}=w^{\prime}_{0}$.
We distinguish the following two complementary cases.

Case I: $z_{\xi_{t}}=z^{\prime}_{\xi_{t}}$. In this case, by invoking Lemma 2
we immediately get

$\displaystyle\|w_{t}-w^{\prime}_{t}\|^{2}=$
$\displaystyle\|\Pi_{\mathcal{W}}(w_{t-1}-\eta_{t}\nabla_{w}\ell(w_{t-1};z_{\xi_{t}}))-\Pi_{\mathcal{W}}(w^{\prime}_{t-1}-\eta_{t}\nabla_{w}\ell(w^{\prime}_{t-1};z^{\prime}_{\xi_{t}}))\|^{2}$
(C.1) $\displaystyle\leq$
$\displaystyle\|w_{t-1}-\eta_{t}\nabla_{w}\ell(w_{t-1};z_{\xi_{t}})-(w^{\prime}_{t-1}-\eta_{t}\nabla_{w}\ell(w^{\prime}_{t-1};z^{\prime}_{\xi_{t}}))\|^{2}$
$\displaystyle\leq$ $\displaystyle\|w_{t-1}-w^{\prime}_{t-1}\|^{2}.$

Case II: $z_{\xi_{t}}\neq z^{\prime}_{\xi_{t}}$. In this case, we have

$\displaystyle\|w_{t}-w^{\prime}_{t}\|^{2}=$
$\displaystyle\|\Pi_{\mathcal{W}}(w_{t-1}-\eta_{t}\nabla
f(w))-\Pi_{\mathcal{W}}(w^{\prime}-\alpha\nabla f(w^{\prime}))\|^{2}$ (C.2)
$\displaystyle\leq$
$\displaystyle\|w_{t-1}-\eta_{t}\nabla_{w}\ell(w_{t-1};z_{\xi_{t}})-(w^{\prime}_{t-1}-\eta_{t}\nabla_{w}\ell(w^{\prime}_{t-1};z^{\prime}_{\xi_{t}}))\|^{2}$
$\displaystyle\leq$
$\displaystyle\left(\|w_{t-1}-w^{\prime}_{t-1}\|+\eta_{t}(\|\nabla_{w}\ell(w_{t-1};z_{\xi_{t}})\|+\|\nabla_{w}\ell(w^{\prime}_{t-1};z^{\prime}_{\xi_{t}})\|)\right)^{2}$
$\displaystyle\leq$
$\displaystyle\left(\|w_{t-1}-w^{\prime}_{t-1}\|+2G\eta_{t}\right)^{2}$
$\displaystyle=$
$\displaystyle\|w_{t-1}-w^{\prime}_{t-1}\|^{2}+4G\eta_{t}\|w_{t-1}-w^{\prime}_{t-1}\|+4G^{2}\eta^{2}_{t},$

where in the last but inequality we have used $\ell(\cdot;\cdot)$ is
$G$-Lipschitz with respect to its first argument.

Let
$\beta_{t}=\beta_{t}(S,S^{\prime},\xi):=\mathbf{1}_{\left\\{z_{\xi_{t}}\neq
z^{\prime}_{\xi_{t}}\right\\}}$ be the random indication function associated
with event $z_{\xi_{t}}\neq z^{\prime}_{\xi_{t}}$. Based on the recursion
forms (C.1) and (C.2) and the condition $w_{0}=w^{\prime}_{0}$ we can show
that for all $t\geq 1$,

$\|w_{t}-w^{\prime}_{t}\|^{2}\leq\sum_{\tau=1}^{t}4G\beta_{\tau}\eta_{\tau}\|w_{\tau-1}-w^{\prime}_{\tau-1}\|+\sum_{\tau=1}^{t}4G^{2}\beta_{\tau}\eta^{2}_{\tau}.$

Then applying Lemma 3 with simple algebraic manipulation yields

$\|w_{t}-w^{\prime}_{t}\|^{2}\leq
8G^{2}\left(\sum_{\tau=1}^{t}\beta_{\tau}\eta^{2}_{\tau}+4\left(\sum_{\tau=1}^{t}\beta_{\tau}\eta_{\tau}\right)^{2}\right).$

Since by assumption $S$ and $S^{\prime}$ differ only in a single element,
under the scheme of uniform sampling without replacement, we can see that
$\beta_{t}(S,S^{\prime},\xi)\sim\texttt{Bernoulli}(1/N)$ and
$\\{\beta_{t}(S,S^{\prime},\xi)\\}$ is an i.i.d. sequence of Bernoulli random
variables. It follows that

$\displaystyle\mathbb{E}_{\xi_{[t]}}\left[\|w_{t}-w^{\prime}_{t}\|^{2}\right]$
$\displaystyle\leq$ $\displaystyle
8G^{2}\left(\sum_{\tau=1}^{t}\mathbb{E}_{\xi_{[t]}}[\beta_{\tau}]\eta^{2}_{\tau}+4\mathbb{E}_{\xi_{[t]}}\left[\left(\sum_{\tau=1}^{t}\beta_{\tau}\eta_{\tau}\right)^{2}\right]\right)$
$\displaystyle=$ $\displaystyle
8G^{2}\left(\sum_{\tau=1}^{t}\mathbb{E}_{\xi_{[t]}}[\beta_{\tau}+4\beta^{2}_{\tau}]\eta^{2}_{\tau}+4\sum_{\tau\neq\tau^{\prime}}1\mathbb{E}_{\xi_{[t]}}\left[\beta_{\tau}\beta_{\tau^{\prime}}\right]\eta_{\tau}\eta_{\tau^{\prime}}\right)$
$\displaystyle=$ $\displaystyle
8G^{2}\left(\frac{5}{N}\sum_{\tau=1}^{t}\eta^{2}_{\tau}+\frac{4}{N^{2}}\left(\sum_{\tau=1}^{t}\eta_{\tau}\right)^{2}\right)\leq
40G^{2}\left(\frac{1}{N}\sum_{\tau=1}^{T}\eta^{2}_{\tau}+\frac{1}{N^{2}}\left(\sum_{\tau=1}^{T}\eta_{\tau}\right)^{2}\right),$

where we have used
$\mathbb{E}_{\xi_{t}}[\beta_{t}]=\mathbb{E}_{\xi_{t}}[\beta^{2}_{t}]=\frac{1}{N}$.
The convexity of squared Euclidean norm leads to

$\mathbb{E}_{\xi}\left[\|\bar{w}_{T}-\bar{w}^{\prime}_{T}\|^{2}\right]\leq\frac{\sum_{t=1}^{T}\mathbb{E}_{\xi_{[t]}}\left[\|w_{t}-w^{\prime}_{t}\|^{2}\right]}{T}\leq
40G^{2}\left(\frac{1}{N}\sum_{t=1}^{T}\eta^{2}_{t}+\frac{1}{N^{2}}\left(\sum_{t=1}^{T}\eta_{t}\right)^{2}\right).$

Since the above holds for any $S\doteq S^{\prime}$, we have that for all
$i\in[N]$,

$\mathbb{E}_{\xi,S,S^{(i)}}\left[\|\bar{w}_{T}-\bar{w}^{(i)}_{T}\|^{2}\right]\leq\frac{40G^{2}}{N}\left(\sum_{t=1}^{T}\eta^{2}_{t}+\frac{1}{N}\left(\sum_{t=1}^{T}\eta_{t}\right)^{2}\right),$

where $\\{w^{(i)}_{t}\\}_{t\in[T]}$ is generated over $S^{(i)}$ via
$A_{\texttt{SGD-w}}$. Finally, since the loss is $G$-Lipschitz, it follows
from the above that for all $i\in[N]$,

$\left\|\ell(\bar{w}_{T};Z)-\ell(\bar{w}^{(i)}_{T};Z)\right\|_{2}\leq
G\left\|\bar{w}_{T}-\bar{w}^{(i)}_{T}\right\|_{2}\leq
G^{2}\sqrt{\frac{40}{N}\left(\sum_{t=1}^{T}\eta^{2}_{t}+\frac{1}{N}\left(\sum_{t=1}^{T}\eta_{t}\right)^{2}\right)}.$

This proves the desired $L_{2}$-stability bound. ∎

With Lemma 9 in place, we are ready to prove Corollary 1.

###### Proof of Corollary 1.

From Lemma 9 we know that $A_{\texttt{SGD-w}}$ has $L_{2}$-stability with
parameter

$\gamma_{\texttt{L}_{2},N}=G^{2}\sqrt{\frac{40}{N}\left(\sum_{t=1}^{T}\eta^{2}_{t}+\frac{1}{N}\left(\sum_{t=1}^{T}\eta_{t}\right)^{2}\right)}.$

The desired results then follow immediately via invoking Theorem 1 with
$\alpha=1/2$. ∎

###  C.2 Proof of Corollary 2

We first establish the following lemma on the mean(-square)-uniform stability
of $A_{\texttt{SGD-w}}$ in the case of non-smooth convex loss.

######  Lemma 10.

Suppose that the loss function is $\ell(\cdot;\cdot)$ is convex and
$G$-Lipschitz with respect to its first argument. Then $A_{\texttt{SGD-w}}$
has $L_{2}$-stability by

$\gamma_{\texttt{L}_{2},N}=G^{2}\sqrt{40\sum_{t=1}^{T}\eta^{2}_{t}+\frac{32}{N^{2}}\left(\sum_{t=1}^{T}\eta_{t}\right)^{2}}.$

###### Proof.

Let us define the sequences $\\{w_{t}\\}_{t\in[T]}$ and
$\\{w^{\prime}_{t}\\}_{t\in[T]}$ that are respectively generated over $S$ and
$S^{\prime}$ via $A_{\texttt{SGD-w}}$ via sample path
$\xi=\\{\xi_{t}\\}_{t\in[T]}$. Suppose that $S\doteq S^{\prime}$ and consider
a hitting time variable $t_{0}=\inf\\{t:z_{\xi_{t}}\neq
z^{\prime}_{\xi_{t}}\\}$. Let
$\beta_{t}=\beta_{t}(S,S^{\prime},\xi):=\mathbf{1}_{\left\\{z_{\xi_{t}}\neq
z^{\prime}_{\xi_{t}}\right\\}}$ be the random indication function associated
with event $z_{\xi_{t}}\neq z^{\prime}_{\xi_{t}}$. Then $\\{\beta_{t}\\}$ is
an i.i.d. sequence of $\texttt{Bernoulli}(1/N)$ random variables. Conditioned
on $t_{0}$, it has been shown by Bassily et al. [2020, Lemma 3.1] that

$\|w_{t}-w^{\prime}_{t}\|\leq
2G\sqrt{\sum_{\tau=t_{0}}^{t}\eta^{2}_{\tau}}+4G\sum_{\tau=t_{0}+1}^{t}\beta_{\tau}\eta_{\tau}\leq
2G\sqrt{\sum_{\tau=1}^{t}\eta^{2}_{\tau}}+4G\sum_{\tau=1}^{t}\beta_{\tau}\eta_{\tau}.$
(C.3)

Based on the square of the bound (C.3) we can show that

$\displaystyle\mathbb{E}_{\xi_{[t]}}\left[\|w_{t}-w^{\prime}_{t}\|^{2}\right]\leq$
$\displaystyle\mathbb{E}_{\xi_{[t]}}\left[8G^{2}\sum_{\tau=1}^{t}\eta^{2}_{\tau}+32G^{2}\left(\sum_{\tau=1}^{t}\beta_{\tau}\eta_{\tau}\right)^{2}\right]$
$\displaystyle=$ $\displaystyle
8G^{2}\sum_{\tau=1}^{t}\eta^{2}_{\tau}+32G^{2}\mathbb{E}_{\xi_{[t]}}\left[\sum_{\tau=1}^{t}\beta^{2}_{\tau}\eta^{2}_{\tau}+\sum_{\tau\neq\tau^{\prime}}\beta_{\tau}\beta_{\tau^{\prime}}\eta_{\tau}\eta_{\tau^{\prime}}\right]$
$\displaystyle=$ $\displaystyle
8G^{2}\sum_{\tau=1}^{t}\eta^{2}_{\tau}+32G^{2}\left(\frac{1}{N}\sum_{\tau=1}^{t}\eta^{2}_{\tau}+\frac{1}{N^{2}}\sum_{\tau\neq\tau^{\prime}}\eta_{\tau}\eta_{\tau^{\prime}}\right)$
$\displaystyle\leq$ $\displaystyle
40G^{2}\sum_{\tau=1}^{t}\eta^{2}_{\tau}+\frac{32G^{2}}{N^{2}}\left(\sum_{\tau=1}^{t}\eta_{\tau}\right)^{2},$

where we have used
$\mathbb{E}_{\xi_{t}}[\beta_{t}]=\mathbb{E}_{\xi_{t}}[\beta^{2}_{t}]=\frac{1}{N}$.
It follows directly from the convexity of squared loss that

$\mathbb{E}_{\xi_{[T]}}\left[\|\bar{w}_{T}-\bar{w}^{\prime}_{T}\|^{2}\right]\leq
40G^{2}\sum_{t=1}^{T}\eta^{2}_{t}+\frac{32G^{2}}{N^{2}}\left(\sum_{t=1}^{T}\eta_{t}\right)^{2}.$

Since the above holds for any $S\doteq S^{\prime}$, we have that for all
$i\in[N]$,

$\mathbb{E}_{\xi,S,S^{(i)}}\left[\|\bar{w}_{T}-\bar{w}^{(i)}_{T}\|^{2}\right]\leq
40G^{2}\sum_{t=1}^{T}\eta^{2}_{t}+\frac{32G^{2}}{N^{2}}\left(\sum_{t=1}^{T}\eta_{t}\right)^{2},$

where $\\{w^{(i)}_{t}\\}_{t\in[T]}$ is generated over $S^{(i)}$ via
$A_{\texttt{SGD-w}}$. Finally, since the loss is $G$-Lipschitz, it follows
from the above that for all $i\in[N]$,

$\left\|\ell(\bar{w}_{T};Z)-\ell(\bar{w}^{(i)}_{T};Z)\right\|_{2}\leq
G\left\|\bar{w}_{T}-\bar{w}^{(i)}_{T}\right\|_{2}\leq
G^{2}\sqrt{40\sum_{t=1}^{T}\eta^{2}_{t}+\frac{32}{N^{2}}\left(\sum_{t=1}^{T}\eta_{t}\right)^{2}}.$

This proves the desired $L_{2}$-stability bound. ∎

Equipped with Lemma 10, we are now in the position to prove Corollary 2.

###### Proof of Corollary 2.

From Lemma 10 we know that $A_{\texttt{SGD-w}}$ with non-smooth convex loss
has $L_{2}$-stability by

$\gamma_{\texttt{L}_{2},N}=G^{2}\sqrt{40\sum_{t=1}^{T}\eta^{2}_{t}+\frac{32}{N^{2}}\left(\sum_{t=1}^{T}\eta_{t}\right)^{2}}.$

The desired results then follow immediately via invoking Theorem 1 with
$\alpha=1/2$. ∎

###  C.3 Proof of Corollary 3

We first establish the following lemma on the mean(-square)-uniform stability
of $A_{\texttt{SGD-w}}$ in the considered non-convex regime.

######  Lemma 11.

Suppose that the loss function is $\ell(\cdot;\cdot)$ is $G$-Lipschitz and
$L$-smooth with respect to its first argument. Consider $\eta_{t}\leq 1/L$.
For all $t\geq 1$, let

$u_{t}:=\eta^{2}_{t}+2\eta_{t}\sum_{\tau=1}^{t-1}\exp\left(L\sum_{i=\tau+1}^{t-1}\eta_{i}\right)\eta_{\tau}.$

Then $A_{\texttt{SGD-w}}$ has $L_{2}$-stability by

$\gamma_{\texttt{L}_{2},N}=2G^{2}\sqrt{\frac{1}{N}\sum_{t=1}^{T}\exp\left(3L\sum_{\tau=t+1}^{T}\eta_{\tau}\right)u_{t}}.$

###### Proof.

Let us define the sequences $\\{w_{t}\\}_{t\in[T]}$ and
$\\{w^{\prime}_{t}\\}_{t\in[T]}$ that are respectively generated over $S$ and
$S^{\prime}$ via $A_{\texttt{SGD-w}}$ via sample path
$\xi=\\{\xi_{t}\\}_{t\in[T]}$. Suppose that $S\doteq S^{\prime}$. Let us
consider
$\Delta_{t}:=\mathbb{E}_{\xi_{[t]}}\left[\|w_{t}-w^{\prime}_{t}\|\right]$.
Then based on the arguments of Hardt et al. [2016, Theorem 3.8] we know that
with probability $1-\frac{1}{N}$ over $\xi_{t}$,
$\|w_{t}-w^{\prime}_{t}\|\leq(1+\eta_{t}L)\|w_{t-1}-w^{\prime}_{t-1}\|$, and
$\|w_{t}-w^{\prime}_{t}\|\leq\|w_{t-1}-w^{\prime}_{t-1}\|+2G\eta_{t}$ with
probability $\frac{1}{N}$. Therefore we have

$\displaystyle\Delta_{t}\leq$
$\displaystyle\left(1-\frac{1}{N}\right)(1+\eta_{t}L)\Delta_{t-1}+\frac{1}{N}\left(\Delta_{t-1}+2G\eta_{t}\right)$
$\displaystyle=$
$\displaystyle\left(\left(1-\frac{1}{N}\right)(1+\eta_{t}L)+\frac{1}{N}\right)\Delta_{t-1}+\frac{2G\eta_{t}}{N}$
$\displaystyle=$
$\displaystyle\left(1+\left(1-\frac{1}{N}\right)\eta_{t}L\right)\Delta_{t-1}+\frac{2G\eta_{t}}{N}$
$\displaystyle\leq$
$\displaystyle\exp\left(\left(1-\frac{1}{N}\right)\eta_{t}L\right)\Delta_{t-1}+\frac{2G\eta_{t}}{N}$
$\displaystyle\leq$
$\displaystyle\exp\left(\eta_{t}L\right)\Delta_{t-1}+\frac{2G\eta_{t}}{N},$

where we have used $1+x\leq\exp(x)$. Then we can unwind the above recursion
form to obtain that for all $t\geq 1$,

$\Delta_{t}\leq\sum_{\tau=1}^{t}\left\\{\prod_{i=\tau+1}^{t}\exp\left(\eta_{i}L\right)\right\\}\frac{2G\eta_{\tau}}{N}=\frac{2G}{N}\sum_{\tau=1}^{t}\exp\left(L\sum_{i=\tau+1}^{t}\eta_{i}\right)\eta_{\tau},$
(C.4)

where we have used $\Delta_{0}=0$. Now we consider
$\tilde{\Delta}_{t}:=\mathbb{E}_{\xi_{[t]}}\left[\|w_{t}-w^{\prime}_{t}\|^{2}\right]$.
Then we can verify that with probability $1-\frac{1}{N}$ over $\xi_{t}$,
$\|w_{t}-w^{\prime}_{t}\|^{2}\leq(1+\eta_{t}L)^{2}\|w_{t-1}-w^{\prime}_{t-1}\|^{2}$,
and with probability $\frac{1}{N}$,

$\|w_{t}-w^{\prime}_{t}\|^{2}\leq(\|w_{t-1}-w^{\prime}_{t-1}\|+2G\eta_{t})^{2}=\|w_{t-1}-w^{\prime}_{t-1}\|^{2}+4G\eta_{t}\|w_{t-1}-w^{\prime}_{t-1}\|+4G^{2}\eta_{t}^{2}.$

Therefore we have

$\displaystyle\tilde{\Delta}_{t}\leq$
$\displaystyle\left(1-\frac{1}{N}\right)(1+\eta_{t}L)^{2}\tilde{\Delta}_{t-1}+\frac{1}{N}\left(\tilde{\Delta}_{t-1}+4G\eta_{t}\Delta_{t-1}+4G^{2}\eta_{t}^{2}\right)$
$\displaystyle\leq$
$\displaystyle\left(\left(1-\frac{1}{N}\right)(1+\eta_{t}L)^{2}+\frac{1}{N}\right)\tilde{\Delta}_{t-1}+\frac{4G^{2}}{N}\left(\underbrace{\eta^{2}_{t}+2\eta_{t}\sum_{\tau=1}^{t-1}\exp\left(L\sum_{i=\tau+1}^{t-1}\eta_{i}\right)\eta_{\tau}}_{u_{t}}\right)$
$\displaystyle=$
$\displaystyle\left(1+\left(1-\frac{1}{N}\right)(2\eta_{t}L+\eta^{2}_{t}L^{2})\right)\tilde{\Delta}_{t-1}+\frac{4G^{2}u_{t}}{N}$
$\displaystyle\leq$
$\displaystyle\exp\left(\left(1-\frac{1}{N}\right)(2\eta_{t}L+\eta^{2}_{t}L^{2})\right)\tilde{\Delta}_{t-1}+\frac{4G^{2}u_{t}}{N}$
$\displaystyle\leq$
$\displaystyle\exp\left(2\eta_{t}L+\eta^{2}_{t}L^{2}\right)\tilde{\Delta}_{t-1}+\frac{4G^{2}u_{t}}{N},$

where in the second inequality we have used the bound (C.4) on $\Delta_{t}$.
Recall that $\tilde{\Delta}_{0}=0$. Then we can unwind the above recursion
form to obtain

$\tilde{\Delta}_{t}\leq\frac{4G^{2}}{N}\sum_{\tau=1}^{t}\left\\{\prod_{i=\tau+1}^{t}\exp\left(2\eta_{i}L+\eta^{2}_{i}L^{2}\right)\right\\}u_{\tau}\leq\frac{4G^{2}}{N}\sum_{\tau=1}^{t}\exp\left(3L\sum_{i=\tau+1}^{t}\eta_{i}\right)u_{\tau},$

where we have used $\eta_{t}\leq 1/L$. It follows immediately from the
convexity that

$\mathbb{E}_{\xi_{[T]}}\left[\|\bar{w}_{T}-\bar{w}^{\prime}_{T}\|^{2}\right]\leq\frac{\sum_{t=1}^{T}\mathbb{E}_{\xi_{[t]}}\left[\|w_{t}-w^{\prime}_{t}\|^{2}\right]}{T}\leq\frac{4G^{2}}{N}\sum_{t=1}^{T}\exp\left(3L\sum_{\tau=t+1}^{T}\eta_{\tau}\right)u_{t}.$

Since the above holds for any $S\doteq S^{\prime}$, we have that for all
$i\in[N]$,

$\mathbb{E}_{\xi,S,S^{(i)}}\left[\|\bar{w}_{T}-\bar{w}^{(i)}_{T}\|^{2}\right]\leq\frac{4G^{2}}{N}\sum_{t=1}^{T}\exp\left(3L\sum_{\tau=t+1}^{T}\eta_{\tau}\right)u_{t},$

where $\\{w^{(i)}_{t}\\}_{t\in[T]}$ is generated over $S^{(i)}$ via
$A_{\texttt{SGD-w}}$. Finally, since the loss is $G$-Lipschitz, it follows
from the above that for all $i\in[N]$,

$\left\|\ell(\bar{w}_{T};Z)-\ell(\bar{w}^{(i)}_{T};Z)\right\|_{2}\leq
G\left\|\bar{w}_{T}-\bar{w}^{(i)}_{T}\right\|_{2}\leq
2G^{2}\sqrt{\frac{1}{N}\sum_{t=1}^{T}\exp\left(3L\sum_{\tau=t+1}^{T}\eta_{\tau}\right)u_{t}}.$

This proves the desired $L_{2}$-stability bound. ∎

With Lemma 11 in place, we proceed to prove the main result in Corollary 3.

###### Proof of Corollary 3.

From Lemma 11 we know that $A_{\texttt{SGD-w}}$ with smooth non-convex loss
has $L_{2}$-stability by

$\gamma_{\texttt{L}_{2},N}=2G^{2}\sqrt{\frac{1}{N}\sum_{t=1}^{T}\exp\left(3L\sum_{\tau=t+1}^{T}\eta_{\tau}\right)u_{t}}.$

The desired results then follow immediately via invoking Theorem 1 with
$\alpha=1/2$. ∎

Input : Data set
$S=\\{Z_{i}\\}_{i\in[N]}\overset{\text{i.i.d.}}{\sim}\mathcal{D}^{N}$, step-
sizes $\\{\eta_{t}\\}_{t\geq 1}$, #iterations $T$, initialization $w_{0}$.

Output : $\bar{w}_{T}=\frac{1}{T}\sum_{t\in[T]}w_{t}$.

for  _$t=1,2,...,T$_ do

Uniformly randomly sample an index $\xi_{t}\in[N]$ _with_ or _without_
replacement;

Compute
$w_{t}=\Pi_{\mathcal{W}}\left(w_{t-1}-\eta_{t}\nabla_{w}\ell(w_{t-1};Z_{\xi_{t}})\right)$.

end for

Algorithm 3 $A_{\texttt{SGD-w/o}}$: SGD under Without-Replacement Sampling

##  Appendix D Augmented Results for SGD under Without-Replacement Sampling

In this section, we further consider applying our main results in Theorem 1 to
the variant of SGD under without-replacement sampling
($A_{\texttt{SGD-w/o}}$), as is outlined in Algorithm 3. For the sake of
simplicity and readability, we only consider single-epoch processing with
$T\leq N$, and we focus on the case where the loss is convex but non-smooth.
The extensions of our analysis to multi-epoch processing, i.e., $T\leq rN$ for
some integer $r\geq 1$ are more or less straightforward and thus are omit to
avoid redundancy.

###  D.1 Results for Convex and Smooth Loss

We start by considering the regime where the loss function is convex and
smooth. We need the following lemma on the $L_{2}$-stability of
$A_{\texttt{SGD-w/o}}$ which can be easily proved based on the result from
Bassily et al. [2020, Lemma 3.1].

######  Lemma 12.

Suppose that the loss function $\ell(\cdot;\cdot)$ is convex, $G$-Lipschitz
and $L$-smooth with respect to its first argument. Assume that $\eta_{t}\leq
2/L$ for all $t\geq 1$. Consider $T\leq N$. Then $A_{\texttt{SGD-w/o}}$ has
$L_{2}$-stability by

$\gamma_{\texttt{L}_{2},N}=2G^{2}\sqrt{\frac{1}{N}\sum_{t=1}^{T}\eta^{2}_{t}}.$

###### Proof.

Let $\bar{w}_{T}(S,\xi)$ and $\bar{w}_{T}(S^{\prime},\xi)$ respectively be the
output generated over $S=\\{z_{i}\\}_{i\in[N]}$ and
$S^{\prime}=\\{z^{\prime}_{i}\\}_{i\in[N]}$ by $A_{\texttt{SGD-w/o}}$ via
sample path $\xi=\\{\xi_{t}\\}_{t\in[T]}$. Recall that $T\leq N$. Let us
define a stopping time variable $t_{0}$ such that $z_{\xi_{t_{0}}}\neq
z^{\prime}_{\xi_{t_{0}}}$. Since $S\doteq S^{\prime}$, the uniform randomness
of $\xi_{t}$ implies that

$\mathbb{P}\left(t_{0}=j\right)=\frac{1}{N},\quad j\in[N].$

In the proof of Corollary 1 we have already shown that
$\|w_{t}-w^{\prime}_{t}\|^{2}\leq\|w_{t-1}-w^{\prime}_{t-1}\|^{2}$ if
$z_{\xi_{t}}=z^{\prime}_{\xi_{t}}$ and
$\|w_{t}-w^{\prime}_{t}\|^{2}\leq\|w_{t-1}-w^{\prime}_{t-1}\|^{2}+4G\eta_{t}\|w_{t-1}-w^{\prime}_{t-1}\|+4G^{2}\eta^{2}_{t}$
otherwise. Therefore, the without-replacement sampling implies that the
following bound holds for any given $t_{0}\leq t\leq T$:

$\|w_{t}-w^{\prime}_{t}\|^{2}\leq 4G^{2}\eta^{2}_{t_{0}},$

and $\|w_{t}-w^{\prime}_{t}\|^{2}=0$ for $0\leq t<t_{0}$. Then based on the
law of total expectation we can show that

$\mathbb{E}_{\xi_{[t]}}\left[\|w_{t}-w^{\prime}_{t}\|^{2}\right]\leq\frac{4G^{2}}{N}\sum_{t_{0}=1}^{t}\eta^{2}_{t_{0}}\leq\frac{4G^{2}}{N}\sum_{t=1}^{T}\eta^{2}_{t}.$

The convexity of squared Euclidean norm leads to

$\mathbb{E}_{\xi_{[T]}}\left[\|\bar{w}_{T}-\bar{w}^{\prime}_{T}\|^{2}\right]\leq\frac{\sum_{t=1}^{T}\eta_{t}\mathbb{E}_{\xi_{[t]}}\left[\|w_{t}-w^{\prime}_{t}\|^{2}\right]}{\sum_{t=1}^{T}\eta_{t}}\leq\frac{4G^{2}}{N}\sum_{t=1}^{T}\eta^{2}_{t}.$

Finally, since the loss is $G$-Lipschitz, it follows from the above that for
all $i\in[N]$,

$\left\|\ell(\bar{w}_{T};Z)-\ell(\bar{w}^{(i)}_{T};Z)\right\|_{2}\leq
G\left\|\bar{w}_{T}-\bar{w}^{(i)}_{T}\right\|_{2}\leq
2G^{2}\sqrt{\frac{1}{N}\sum_{t=1}^{T}\eta^{2}_{t}}.$

This proves the desired $L_{2}$-stability bound. ∎

The following result is a direct consequence of Theorem 1 and Theorem 2 when
invoking Algorithm 1 to $A_{\texttt{SGD-w/o}}$ with convex and smooth loss.

######  Corollary 4.

Suppose that the loss function $\ell(\cdot;\cdot)$ is convex, $G$-Lipschitz
and $L$-smooth with respect to its first argument, and is bounded in the range
of $[0,M]$. Consider Algorithm 1 specified to $A_{\texttt{SGD-w/o}}$ with
$T=N$ and learning rate $\eta_{t}\leq 2/L$ for all $t\geq 1$. Then for any
$\delta\in(0,1)$ and $K\geq 2\log(\frac{4}{\delta})$, with probability at
least $1-\delta$ over the randomness of $S$ and
$\\{A_{\texttt{SGD-w/o},k}\\}_{k\in[K]}$, the generalization bound of
Algorithm 1 is upper bounded as

$\left|R(A_{\texttt{SGD-w/o},k^{*}}(S_{k^{*}}))-R_{S}(A_{\texttt{SGD-w/o},k^{*}}(S_{k^{*}}))\right|\lesssim
G^{2}\sqrt{\frac{1}{N}\sum_{t=1}^{N}\eta^{2}_{t}}+M\sqrt{\frac{\log(K/\delta)}{N}}.$

Moreover assume that $\mathcal{W}$ is bounded with diameter $D$. Then with
constant learning rate
$\eta_{t}\equiv\min\\{\frac{2}{L},\frac{D}{G\sqrt{N}}\\}$, the excess risk of
the modified output (2.2) of Algorithm 1 satisfies

$\left|R(A_{\texttt{SGD-w/o},k^{*}}(S_{k^{*}}))-R(w^{*})\right|\lesssim\frac{GDK}{\sqrt{N}}+M\sqrt{\frac{\log(K/\delta)}{N}}+\frac{D^{2}L}{N}.$

###### Proof.

For the considered convex and smooth losses, from Lemma 12 we know that
$A_{\texttt{SGD-w/o}}$ with $T=N$ iterations has $L_{2}$-stability by

$\gamma_{\texttt{L}_{2},N}=2G^{2}\sqrt{\frac{1}{N}\sum_{t=1}^{N}\eta^{2}_{t}}.$

The first generalization error bound then follows immediately via invoking
Theorem 1 with $\alpha=1/2$. The second excess risk bound can be established
by invoking Theorem 2 with $\alpha=1/2$ and the following in-expectation
optimization error bound of $A_{\texttt{SGD-w/o}}$ with convex and smooth loss
functions under the given constant learning rate [Nagaraj et al., 2019,
Theorem 3]:

$\mathbb{E}\left[R_{S}(\bar{w}_{T})-R_{S}(w^{*})\right]\lesssim\frac{D^{2}L}{N}+\frac{GD}{\sqrt{N}}.$

This complete the proof. ∎

######  Remark 8.

Specially for constant learning rates
$\eta_{t}\equiv\eta\asymp\frac{1}{\sqrt{N}}$ and
$K\asymp\log\left(\frac{1}{\delta}\right)$, Corollary 4 admits a high-
probability generalization bound of order
$\mathcal{O}\left(\sqrt{\frac{\log(1/\delta)}{N}}+\frac{1}{\sqrt{N}}\right)$
and an excess bounds dominated by
$\mathcal{O}\left(\sqrt{\frac{\log(1/\delta)}{N}}+\frac{1}{N}\right)$. For
time varying learning rates $\eta_{t}\propto\frac{1}{\sqrt{t}}$, the
generalization bound scales as
$\mathcal{O}\left(\sqrt{\frac{\log(N)}{N}}+\sqrt{\frac{\log(1/\delta)}{N}}\right)$.

###  D.2 Results for Convex and Non-smooth Loss

We now turn to study the case of convex and non-smooth losses. The following
lemma is about the $L_{2}$-stability of $A_{\texttt{SGD-w/o}}$ in this case.

######  Lemma 13.

Suppose that the loss function $\ell(\cdot;\cdot)$ is convex and $G$-Lipschitz
with respect to its first argument. Consider $T\leq N$. Then
$A_{\texttt{SGD-w/o}}$ has $L_{2}$-stability by

$\gamma_{\texttt{L}_{2},N}=2G^{2}\sqrt{\frac{1}{N}\sum_{t_{0}=1}^{T}\sum_{t=t_{0}}^{T}\eta^{2}_{t}}.$

###### Proof.

Let $\bar{w}_{T}(S,\xi)$ and $\bar{w}_{T}(S^{\prime},\xi)$ respectively be the
output generated over $S=\\{z_{i}\\}_{i\in[N]}$ and
$S^{\prime}=\\{z^{\prime}_{i}\\}_{i\in[N]}$ by $A_{\texttt{SGD-w/o}}$ via
sample path $\xi=\\{\xi_{t}\\}_{t\in[T]}$. Recall that $T\leq N$. Let us
define a stopping time variable $t_{0}$ such that $z_{\xi_{t_{0}}}\neq
z^{\prime}_{\xi_{t_{0}}}$. Since $S\doteq S^{\prime}$, the uniform randomness
of $\xi_{t}$ and the without-replacement sampling strategy yield

$\mathbb{P}\left(t_{0}=j\right)=\frac{1}{N},\quad j\in[N].$

For any $t_{0}\leq t\leq T$, it follows from Lemma 4 and without-replacement
sampling that

$\|w_{t}-w^{\prime}_{t}\|^{2}\leq 4G^{2}\sum_{\tau=t_{0}}^{t}\eta^{2}_{\tau}.$

We use the convention $\sum_{\tau=t_{0}}^{t}\eta^{2}_{\tau}=0$ for $0\leq
t<t_{0}$. Then according to the law of total expectation we must have

$\mathbb{E}_{\xi_{[t]}}\left[\|w_{t}-w^{\prime}_{t}\|^{2}\right]\leq\frac{4G^{2}}{N}\sum_{t_{0}=1}^{t}\sum_{\tau=t_{0}}^{t}\eta^{2}_{\tau}\leq\frac{4G^{2}}{N}\sum_{t_{0}=1}^{T}\sum_{\tau=t_{0}}^{T}\eta^{2}_{\tau}.$

The convexity of squared Euclidean norm leads to

$\mathbb{E}_{\xi_{[T]}}\left[\|\bar{w}_{T}-\bar{w}^{\prime}_{T}\|^{2}\right]\leq\frac{\sum_{t=1}^{T}\mathbb{E}_{\xi_{[t]}}\left[\|w_{t}-w^{\prime}_{t}\|^{2}\right]}{T}\leq\frac{4G^{2}}{N}\sum_{t_{0}=1}^{T}\sum_{t=t_{0}}^{T}\eta^{2}_{t}.$

Since the loss is $G$-Lipschitz, it follows from the above that for all
$i\in[N]$,

$\left\|\ell(\bar{w}_{T};Z)-\ell(\bar{w}^{(i)}_{T};Z)\right\|_{2}\leq
G\left\|\bar{w}_{T}-\bar{w}^{(i)}_{T}\right\|_{2}\leq
2G^{2}\sqrt{\frac{1}{N}\sum_{t_{0}=1}^{T}\sum_{t=t_{0}}^{T}\eta^{2}_{t}}.$

This proves the desired $L_{2}$-stability bound. ∎

With the above lemma in hand, we can establish the following result as a
direct consequence of Theorem 1 when invoking Algorithm 1 to
$A_{\texttt{SGD-w/o}}$ with convex and non-smooth losses.

######  Corollary 5.

Suppose that the loss function $\ell(\cdot;\cdot)$ is convex and $G$-Lipschitz
with respect to its first argument, and is bounded in the range of $[0,M]$.
Consider Algorithm 1 specified to $A_{\texttt{SGD-w/o}}$ with $T=N$. Then for
any $\delta\in(0,1)$ and $K\geq 2\log(\frac{4}{\delta})$, with probability at
least $1-\delta$ over the randomness of $S$ and
$\\{A_{\texttt{SGD-w/o},k}\\}_{k\in[K]}$, the output of Algorithm 1 satisfies
the generalization bound

$\left|R(A_{\texttt{SGD-w/o},k^{*}}(S_{k^{*}}))-R_{S}(A_{\texttt{SGD-w/o},k^{*}}(S_{k^{*}}))\right|\lesssim
G^{2}\sqrt{\frac{1}{N}\sum_{t_{0}=1}^{N}\sum_{t=t_{0}}^{N}\eta^{2}_{t}}+M\sqrt{\frac{\log(K/\delta)}{N}}.$

###### Proof.

For the considered convex and Lipschitz loss functions, from Lemma 13 we know
that $A_{\texttt{SGD-w/o}}$ with $T=N$ iterations has $L_{2}$-stability by

$\gamma_{\texttt{L}_{2},N}=2G^{2}\sqrt{\frac{1}{N}\sum_{t_{0}=1}^{N}\sum_{t=t_{0}}^{N}\eta^{2}_{t}}.$

The results then follow immediately via invoking Theorem 1 with $\alpha=1/2$.
∎

######  Remark 9.

Specially for constant learning rates $\eta_{t}\equiv\eta$ and setting
$K\asymp\log\left(\frac{1}{\delta}\right)$, Corollary 5 admits a high-
probability generalization bound of scale

$\mathcal{O}\left(\eta\sqrt{N}+\sqrt{\frac{\log(1/\delta)}{N}}\right).$

For time decaying learning rates $\eta_{t}\propto\frac{1}{t}$, the
generalization bound scales as

$\mathcal{O}\left(\sqrt{\frac{\log(N)}{N}}+\sqrt{\frac{\log(1/\delta)}{N}}\right)$

with detail bound $\delta$.

######  Remark 10.

Regarding the excess risk bound, under the conditions of Corollary 5 and
$K\asymp\log\left(\frac{1}{\delta}\right)$, Theorem 2 combined with Lemma 13
yields that the modified output of Algorithm 1 as defined by (2.2) satisfies
the following bound with probability at least $1-\delta$:

$\left|R(A_{\texttt{SGD-w/o},k^{*}}(S_{k^{*}}))-R(w^{*})\right|\lesssim
G^{2}\sqrt{\frac{\log(1/\delta)}{N}\sum_{t_{0}=1}^{N}\sum_{t=t_{0}}^{N}\eta^{2}_{t}}+\Delta_{\text{opt}}+M\sqrt{\frac{\log(1/\delta)}{N}}.$

In the special case of bounded-norm generalized linear models, Shamir [2016]
established an in-expectation empirical risk sub-optimality bound
$\Delta_{\text{opt}}\lesssim\frac{1}{\sqrt{N}}$ under suitable learning rates.
For generic convex and non-smooth losses, however, it still remains unclear to
us if similar sub-optimality bounds are available for SGD under without-
replacement sampling.

###  D.3 Results for Non-convex and Smooth Loss

Finally, we study the performance of Algorithm 1 for $A_{\texttt{SGD-w/o}}$ on
smooth but not necessarily convex loss functions. We first establish the
following lemma on the mean(-square)-uniform stability of
$A_{\texttt{SGD-w/o}}$ in the considered non-convex regime.

######  Lemma 14.

Suppose that the loss function $\ell(\cdot;\cdot)$ is $G$-Lipschitz and
$L$-smooth with respect to its first argument. Consider $T\leq N$. Then
$A_{\texttt{SGD-w/o}}$ has $L_{2}$-stability by

$\gamma_{\texttt{L}_{2},N}=2G^{2}\sqrt{\frac{1}{N}\sum_{t=1}^{T}\exp\left(2L\sum_{\tau=t+1}^{T}\eta_{\tau}\right)\eta^{2}_{t}}.$

###### Proof.

Let us define the sequences $\\{w_{t}\\}_{t\in[T]}$ and
$\\{w^{\prime}_{t}\\}_{t\in[T]}$ that are respectively generated over $S$ and
$S^{\prime}$ via $A_{\texttt{SGD-w/o}}$ via sample path
$\xi=\\{\xi_{t}\\}_{t\in[T]}$. Suppose that $S\doteq S^{\prime}$. Recall that
$T\leq N$. Let us define a stopping time variable $t_{0}$ such that
$z_{\xi_{t_{0}}}\neq z^{\prime}_{\xi_{t_{0}}}$. Since $S\doteq S^{\prime}$,
the without-replacement sampling implies that

$\mathbb{P}\left(t_{0}=j\right)=\frac{1}{N},\quad j\in[N].$

In view of Lemma 2 we know that
$\|w_{t}-w^{\prime}_{t}\|\leq(1+\eta_{t}L)\|w_{t-1}-w^{\prime}_{t-1}\|$ if
$Z_{\xi_{t}}=Z^{\prime}_{\xi_{t}}$, and $\|w_{t_{0}}-w^{\prime}_{t_{0}}\|\leq
2G\eta_{t_{0}}$ otherwise due to the assumption that the loss is
$G$-Lipschitz. Therefore, it can be directly verified that the following holds
for any $t_{0}\leq t\leq T$:

$\left\|w_{t}-w^{\prime}_{t}\right\|^{2}\leq
4G^{2}\prod_{\tau=t_{0}+1}^{t}(1+\eta_{\tau}L)^{2}\eta^{2}_{t_{0}},$

where we have used $\prod_{\tau=t_{0}+1}^{t}(1+\eta_{\tau}L)^{2}=1$ for
$t=t_{0}$. For $t<t_{0}$, it is trivial that $\|w_{t}-w^{\prime}_{t}\|=0$.
Therefore the law of total expectation yields

$\displaystyle\mathbb{E}_{\xi_{[t]}}\left[\|w_{t}-w^{\prime}_{t}\|^{2}\right]\leq$
$\displaystyle\frac{4G^{2}}{N}\sum_{t_{0}=1}^{t}\prod_{\tau=t_{0}+1}^{t}(1+\eta_{\tau}L)^{2}\eta^{2}_{t_{0}}$
$\displaystyle\leq$
$\displaystyle\frac{4G^{2}}{N}\sum_{t_{0}=1}^{t}\prod_{\tau=t_{0}+1}^{t}\exp\left(2\eta_{\tau}L\right)\eta^{2}_{t_{0}}$
$\displaystyle\leq$
$\displaystyle\frac{4G^{2}}{N}\sum_{t_{0}=1}^{T}\exp\left(2L\sum_{\tau=t_{0}+1}^{T}\eta_{\tau}\right)\eta^{2}_{t_{0}},$

where we have used $1+x\leq\exp(x)$. The convexity of Euclidean norm leads to

$\mathbb{E}_{\xi_{[T]}}\left[\|\bar{w}_{T}-\bar{w}^{\prime}_{T}\|\right]\leq\frac{\sum_{t=1}^{T}\eta_{t}\mathbb{E}_{\xi_{[t]}}\left[\|w_{t}-w^{\prime}_{t}\|\right]}{\sum_{t_{0}=1}^{T}\eta_{t}}\leq\frac{4G^{2}}{N}\sum_{t_{0}=1}^{T}\exp\left(2L\sum_{\tau=t_{0}+1}^{T}\eta_{\tau}\right)\eta^{2}_{t_{0}}.$

Since the loss is $G$-Lipschitz, it follows from the above that for all
$i\in[N]$,

$\left\|\ell(\bar{w}_{T};Z)-\ell(\bar{w}^{(i)}_{T};Z)\right\|_{2}\leq
G\left\|\bar{w}_{T}-\bar{w}^{(i)}_{T}\right\|_{2}\leq
2G^{2}\sqrt{\frac{1}{N}\sum_{t_{0}=1}^{T}\exp\left(2L\sum_{\tau=t_{0}+1}^{T}\eta_{\tau}\right)\eta^{2}_{t_{0}}}.$

This proves the desired $L_{2}$-stability bound. ∎

With Lemma 14 in place, we can derive the following result as a direct
application of Theorem 1 to $A_{\texttt{SGD-w/o}}$ with Lipschitz and smooth
losses.

######  Corollary 6.

Suppose that the loss function $\ell(\cdot;\cdot)$ is $G$-Lipschitz and
$L$-smooth with respect to its first argument, and is bounded in the range of
$[0,M]$. Consider Algorithm 1 specified to $A_{\texttt{SGD-w/o}}$ with $T=N$.
Then for any $\delta\in(0,1)$ and $K\geq 2\log(\frac{4}{\delta})$, with
probability at least $1-\delta$ over the randomness of $S$ and
$\\{A_{\texttt{SGD-w/o},k}\\}_{k\in[K]}$, the output satisfies

$\left|R(A_{\texttt{SGD-w/o},k^{*}}(S_{k^{*}}))-R_{S}(A_{\texttt{SGD-w/o},k^{*}}(S_{k^{*}}))\right|\lesssim
G^{2}\sqrt{\frac{1}{N}\sum_{t=1}^{N}\exp\left(L\sum_{\tau=t+1}^{N}\eta_{\tau}\right)\eta^{2}_{t}}+M\sqrt{\frac{\log(K/\delta)}{N}}.$

###### Proof.

For the considered smooth and Lipschitz loss functions, from Lemma 14 we know
that $A_{\texttt{SGD-w/o}}$ with $T=N$ rounds of iteration has
$L_{2}$-stability by

$\gamma_{\texttt{L}_{2},N}=2G^{2}\sqrt{\frac{1}{N}\sum_{t=1}^{T}\exp\left(2L\sum_{\tau=t+1}^{T}\eta_{\tau}\right)\eta^{2}_{t}}.$

The desired results then follow immediately via invoking Theorem 1 with
$\alpha=1/2$. ∎

######  Remark 11.

For $K\asymp\log\left(\frac{1}{\delta}\right)$ and the choice of constant
learning rates $\eta_{t}\equiv\frac{1}{LN}$, Corollary 6 admits high-
probability generalization bounds of scale
$\mathcal{O}\left(\frac{1}{N}+\sqrt{\frac{\log(1/\delta)}{N}}\right)$. For the
choice of time decaying learning rates $\eta_{t}=\frac{1}{L\nu t}$ with
arbitrary $\nu>2$, it can be verified that the corresponding generalization
bound is of scale

$\mathcal{O}\left(\frac{1}{\nu
N^{1/2-1/\nu}}+\sqrt{\frac{\log(1/\delta)}{N}}\right).$