Year: 2021

Abstract:
High probability generalization bounds of uniformly stable learning algorithms have recently been actively studied with a series of near-tight results established by Feldman & Vondrak (2019); Bousquet et al. (2020). However, for randomized algorithms with on-average uniform stability, such as stochastic gradient descent (SGD) with time decaying learning rates, it still remains less well understood if these deviation bounds still hold with high confidence over the internal randomness of algorithm. This paper addresses this open question and makes progress towards answering it inside a classic framework of confidence-boosting. To this end, we first establish an in-expectation first moment generalization error bound for randomized learning algorithm with on-average uniform stability, based on which we then show that a properly designed subbagging process leads to near-tight high probability generalization bounds over the randomness of data and algorithm. We further substantialize these generic results to SGD to derive improved high probability generalization bounds for convex or non-convex optimization with natural time decaying learning rates, which have not been possible to prove with the existing uniform stability results. Specially for deterministic uniformly stable algorithms, our confidence-boosting results improve upon the best known generalization bounds in terms of a logarithmic factor on sample size, which moves a step forward towards resolving an open question raised by Bousquet et al. (2020).

heading: 1 INTRODUCTION
text: In many statistical machine learning problems, the ultimate goal is to design a suitable algorithm A : ZN 7→ W that maps a training data set S = {zi}i∈[N ] ∈ ZN to a modelA(S) in a closed subset W of an Euclidean space such that the following population risk function evaluated at the model is as small as possible: R(A(S)) := EZ∼D[`(A(S);Z)], where ` : W × Z 7→ R+ is a non-negative bounded loss function whose value `(w; z) measures the loss evaluated at z with parameter w, and D represents a distribution over 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 i.i.d.∼ DN . Then, a natural alternative measurement that mimics the computationally intractable population risk is the empirical risk defined by
RS(A(S)) := EZ∼Unif(S)[`(A(S);Z)] = 1
N N∑ i=1 `(A(S); zi).
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 bN such that the generalization bound |RS(A(S))−R(A(S))| . bN 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 RS , say RS(A(S)) . minw∈W RS(w) + bN , the generalization bound immediately implies an excess risk bound R(A(S)) −minw∈W R(w) . bN + 1√N due to 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.
The generalization bounds can be naturally implied by uniform bounds on supw∈W |R(w) − RS(w)| (Bartlett et al., 2006; Bottou & Bousquet, 2008). While broadly applicable (e.g., to nonconvex problems) and leading to tight generalization in some specific regimes (e.g., margin-based learning (Kakade et al., 2009)), uniform convergence bounds in general cases might suffer from the polynomial dependence on dimensionality and thus are not suitable for high-dimensional models which are ubiquitous in modern machine learning. Alternatively, 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 & 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 notion of uniform stability (Feldman & Vondrak, 2018; 2019; Bousquet et al., 2020). Inspired by these recent breakthrough results, we seek to derive sharper high-probability generalization bounds for randomized learning algorithms with on-average uniform 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 ≥ 1 with learning rate ηt > 0:
wt := ΠW (wt−1 − ηt∇w`(wt−1; zξt)) , (1) where ξt ∈ [N ] is a uniform random index of data under with or without replacement sampling, and ΠW is the Euclidean projection operator associated withW . Despite its popularity in the study of stability theory (Hardt et al., 2016; Zhou et al., 2019; Lei & Ying, 2020), the high probability generalization bounds of SGD are still relatively under explored through the lens of uniform stability.

heading: 1.1 PRIOR RESULTS
text: Let us now briefly review some state-of-the-art generalization bounds for uniformly stable algorithms and their randomized variants. We denote by S .= S′ if a pair of data sets S and S′ differ in a single data point. A randomized learning algorithm A is said to have on-average γN -uniform stability if it satisfies the following uniform bound
sup S . =S′,z∈Z
|EA[`(A(S); z)]− EA[`(A(S′); z)]| ≤ γN .
This definition is equivalent to the concept of uniform stability defined over the on-average loss EA[`(A(S); z)]. Suppose that the loss function is Lipschitz and bounded in the interval (0, 1]. Then essentially it has been shown in Feldman & Vondrak (2019) that for any δ ∈ (0, 1), with probability at least 1− δ over S, the on-average generalization error is upper bounded by
|EA [R(A(S))−RS(A(S))]| . γN log(N) log ( N
δ
) + √ log (1/δ)
N . (2)
Recently, Bousquet et al. (2020) derived a slightly improved uniform stability bound that implies |EA [R(A(S))−RS(A(S))]| . γN log(N) log ( 1
δ
) + √ log (1/δ)
N . (3)
These generalization bounds are near-tight (up to a logarithmic factor log(N)) in the sense of a lower bound on sum of random functions provided in that paper. 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 γN -uniform stability with probability at least 1− δ′ for some δ′ ∈ (0, 1) over the randomness of A, i.e.,
PA { sup
S . =S′,z∈Z
|`(A(S); z)− `(A(S′); z)| ≤ γN } ≥ 1− δ′. (4)
Suppose that the randomness of A is independent of the training set S. Then with probability at least 1− δ − δ′ over S and A, the bound of Bousquet et al. (2020) naturally implies
|R(A(S))−RS(A(S))| . γN log(N) log ( 1
δ
) + √ log (1/δ)
N . (5)
Algorithm 1: Confidence-Boosting for Randomized Learning
Input : A randomized learning algorithm A and a training data set S = {zi}i∈[N ] i.i.d.∼ DN . Output: Ak∗(Sk∗). Uniformly divide S into K disjoint subsets such that S = ⋃ k∈[K] Sk and |Sk| = N K , ∀k ∈ [K]. for k = 1, 2, ...,K do Estimate Ak(Sk) as an output of the randomized algorithm A over subset Sk. end Compute k∗ = arg mink∈[K]
∣∣RS\Sk(Ak(Sk))−RSk(Ak(Sk))∣∣. 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 highprobability uniform stability condition expressed in equation 4. For the SGD (see equation 1) with fixed learning rate ηt ≡ η, it is possible to show that γN . η √ T + ηTN and δ
′ = N exp(−N2 ) in equation 4 (Bassily et al., 2020). For SGD with time decaying learning rate that has been widely studied in theory Harvey et al. (2019); Rakhlin et al. (2012) 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 equation 4 is still valid for γN and δ′ of interest. On the other hand, it is possible to show (see the proofs of Corollary 1 and 2) that SGD with time decaying learning rate has desirable on-average uniform stability.
More specially for randomized learning methods such as bagging (Breiman, 1996) and SGD equation 1, the randomness of algorithm can be precisely characterized by a vector of i.i.d. parameters ξ = {ξ1, ..., ξT } which are independent on data S. In such cases, suppose that A(S; ξ) has uniform stability with respect to ξ at any given S, i.e., supξ .=ξ′ |`(A(S; ξ)) − `(A(S; ξ′))| ≤ ρT . Then the high probability bound established in Elisseeff et al. (2005) shows that with probability at least 1−δ,
|R(A(S))−RS(A(S))| . γN + (
1 +NγN√ N
+ √ TρT )√ log ( 1
δ
) . (6)
Provided that γN . 1N and ρT . 1 T , the above bound shows that the generalization bound scales as O( 1√ N + 1√ T
) with high probability. However, the above bound will show no guarantee on convergence if γN & 1√N and/or ρT & 1√ T . For example, this is actually the case for SGD with time decaying learning rate ηt = O( 1t ) on non-convex loss functions in which γN . √ T N and ρT can scale as large as O(1). Open problem and motication. Keeping the merits and deficiencies of above recalled prior results in mind, it still remains an open issue if the existing deviation bounds can hold with high confidence for randomized algorithms with on-average uniform stability (such as SGD with decaying learning rates). The goal of the present study is to derive sharper high-probability generalization bounds for randomized algorithms that hold jointly over the randomness of data and algorithm, based on the relatively weaker notion of on-average uniform stability rather than its high probability counterpart.

heading: 1.2 OVERVIEW OF OUR RESULTS
text: The confidence-boosting technique of Schapire (1990) is a classical meta approach that allows us to boost the dependence of a learning algorithm on the failure probability δ from 1/δ to log(1/δ), at a certain cost of computational complexity. The fundamental contribution of our work is to reveal that the confidence-boosting trick yields near-tight high probability generalization bounds for uniformly 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 onaverage uniform stability, which leads to improved high-probability generalization bounds over the randomness of data and algorithm via confidence-boosting. More specifically, given a randomized learning algorithm A, we consider the following subbagging process over training set:
Boosting the Confidence via Subbagging. We independently run A over K disjoint and uniformly divided training subsets {Sk}k∈[K] to obtain solutions {Ak(Sk)}k∈[K]. Then we e-
valuate the validation error of each candidate solution over its complementary training subset, and output Ak∗(Sk∗) that has the smallest gap between training error and validation error, i.e., k∗ = arg mink∈[K] ∣∣RS\Sk(Ak(Sk))−RSk(Ak(Sk))∣∣. 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. Here we have assumed 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.
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 and deterministic algorithms:
• General results. Suppose that the loss is Lipschitz and bounded in the range of (0, 1]. Our main result in Theorem 1 show that for any δ ∈ (0, 1), setting K log( 1δ ) yields the following generalization bound of the output of Algorithm 1 that holds with probability at least 1 − δ over S and {Ak}k∈[K]:
|R(Ak∗(Sk∗))−RS(Ak∗(Sk∗))| . 1
K
(√ γm2,NK + γm,NK + √ K
N
) + √ log(K/δ)
N ,
where γm,N and γm2,N are respectively mean-uniform stability and mean-square-uniform stability bounds introduced in Definition 1. In contrast to the bound in equation 6, our bound is not relying on the uniform stability with respect to the random bits of algorithm.
• Stronger generalization 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 loss, and smooth non-convex loss functions (Corollary 3). For an instance, our result in Corollary 1 showcases that when invoked to SGD-w on smooth convex loss with learning rates ηt = O( 1√t ), the generalization bound of the output of Algorithm 1 with K log( 1 δ ) is
upper bounded by |R(ASGD-w,k∗(Sk∗))−RS(ASGD-w,k∗(Sk∗))| . √ log(T )
N +
√ T + √ N log(1/δ)
N .
Compared with theO( √ T N ) in-expectation bound of smooth convex SGD (Hardt et al., 2016), our
above bound is competitive in order while it holds with high confidence. • Sharper bounds for uniformly stable algorithms via confidence-boosting. Specially for a deter-
ministic learning algorithm A that has γN -uniform stability for each data set size N ≥ 1, we further show through Corollary 4 that the following bound holds for the output of Algorithm 1 with K = log(1δ ):
|R(A(Sk∗))−RS(A(Sk∗))| . γN K +
√ log(K/δ)
N .
In the case of γN . 1√N which holds in some popular learning paradigms such as regularized ERM, the above bound implies (recall K log( 1δ ))
|R(A(Sk∗))−RS(A(Sk∗))| . √ log(1/δ)
N ,
which is sharper than the best known result in equation 5 (under δ′ = 0) in the sense of the removal of a log(N) factor. This is a side contribution of our work that might be of independent interest towards answering an open question raised by Bousquet et al. (2020).
In addition to the generalization bounds, we have also derived a high probability excess risk bound for uniformly 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 − δ over S and {Ak}k∈[K]:
R(Ak∗(Sk∗))− min w∈W R(w) . γm,NK + ∆opt +
√ log(K/δ)
N ,
where ∆opt is the in-expectation empirical risk optimization error as given by equation 7.

heading: 2 GENERALIZATION ANALYSIS WITH CONFIDENCE-BOOSTING
text: 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.

heading: 2.1 PRELIMINARIES AND A KEY LEMMA
text: We first introduce the following concept of mean-uniform stability that serves as a powerful tool for analyzing the generalization bounds of randomized learning algorithms (Hardt et al., 2016; Elisseeff et al., 2005; Bassily et al., 2020). Definition 1 (Mean and Mean-Square Uniform Stability of Randomized Algorithms). Let A : ZN 7→ W be a randomized learning algorithm that maps a data set S ∈ ZN to a modelA(S) ∈ W . Then A is said to have γm,N -mean-uniform stability if for every N ≥ 1,
sup S . =S′
EA [‖A(S)−A(S′)‖] ≤ γm,N .
Moreover, A is said to have γm2,N -mean-square-uniform stability if for every N ≥ 1, sup S . =S′ EA [ ‖A(S)−A(S′)‖2 ] ≤ γm2,N .
Here the algorithm outputs A(S) and A(S′) share the same random bits associated with the algorithm. The above defined notion of mean-uniform stability is also known as Uniform Argument Stability (UAS) (Bassily et al., 2020), which was originally introduced by Liu et al. (2017) for nonparametric hypotheses. The notion of mean-square uniform stability is stronger than mean-uniform stability in the sense that the former naturally implies the latter such that γm,N ≤ √ γm2,N . Moreover, we say a function f is G-Lipschitz continuous overW if |f(w)− f(w′)| ≤ G‖w−w′‖ for all w,w′ ∈ W , and it is L-smooth if ‖∇f(w)−∇f(w′)‖ ≤ L‖w − w′‖ for all w,w′ ∈ W . 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 γm,N -mean-uniform stability, then its on-average first moment generalization error bound will be as small as O(γm,N + √ γm2,N +
1√ N ) when the loss function is Lipschitz continuous. This result is an adaptation of the second moment bound derived by Bousquet et al. (2020) to on-average uniform stable randomized algorithms, and that bound is also the source of γm2,N entering into play. For completeness, we provide a proof for this result in Appendix B.1. Lemma 1. Suppose that a randomized learning algorithm A : ZN 7→ W has γm,N -mean-uniform stability and γm2,N -mean-square-uniform stability. Assume that the loss function ` is G-Lipschitz with respect to its first argument and is bounded in the range of [0,M ]. Then we have
EA,S [|R(A(S))−RS(A(S))|] ≤ G √ γm2,N +Gγm,N + M√ N .
Remark 1. In comparison to the on-average bound |EA,S [R(A(S))−RS(A(S))]| ≤ Gγm,N (see, e.g., Hardt et al., 2016, Theorem 2.2), our on-average first moment bound in Lemma 1 is substantially stronger and it 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 & Vondrak, 2018; Bousquet et al., 2020) which is tighter in logarithmic factors than the one implied by the p-th moment inequality of (Bousquet et al., 2020, Theorem 4). In this case, our bound is stronger than the bound from Bousquet & Elisseeff (2002, Lemma 9) which essentially scales as 1√
N + √ γm,N in our notation.

heading: 2.2 MAIN RESULTS ON GENERALIZATION BOUND
text: Let us recall the subbagging process as described in Algorithm 1: we independently run A over K even and disjoint training subsets {Sk}k∈[K] to obtain solutions {Ak(Sk)}k∈[K], and then pick Ak∗(Sk∗) that has the smallest difference between training error and validation error (over the complementary training subset S \ Sk∗ ). The following theorem is our main result about the high probability generalization bound of the output Ak∗(Sk∗) 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 : ZN 7→ W has γm,N -mean-uniform stability and γm2,N -mean-square-uniform stability as well. Assume that the loss function ` is GLipschitz with respect to its first argument and is bounded in the range of [0,M ]. Then for any α, δ ∈ (0, 1) and K ≥ 11−α log( 4 δ ), with probability at least 1 − δ over the randomness of S and {Ak}k∈[K], the output of Algorithm 1 satisfies
|R(Ak∗(Sk∗))−RS(Ak∗(Sk∗))| . 1
αK
( G √ γm2,NK +Gγm,NK +M √ K
N
) +M √ log(K/δ)
N .
Remark 2. To gain some intuition on the superiority of our bound in Theorem 1, let us consider K log ( 1 δ ) as allowed in the conditions. If γm,N . 1√N and γm2,N . 1 N , then our high-probability
bound in Theorem 1 roughly scales as √
log(1/δ) N which is sharper than the on-average bounds
in equation 2 and equation 3 with γN . 1√N . More precise consequences of these general results on SGD and deterministic uniformly stable estimators such as ERMs and full gradient descent method will be discussed shortly in the sections to follow.
Remark 3. In sharp contrast to the bound in equation 5 that requires high probability uniform stability and the bound in equation 6 that assumes uniform stability over the random bits of algorithm, our bound in Theorem 1 holds under a substantially milder notion of mean(-square)-uniform
stability over data. In terms of the tightness of bound, note that the confidence term √
log(1/δ) N is
necessary even for an algorithm with fixed output. The uniform stability terms γm,NK and γm2,NK are also near-tight as the the algorithm output can change arbitrarily with respect to these quantities.

heading: 2.3 ON EXCESS RISK BOUNDS
text: To understand the optimization performance of a randomized learning algorithmA with confidenceboosting, 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∗ := arg min w∈W
R(w) and ∆opt := EA,S [ RS(A(S))− min
w∈W RS(w)
] . (7)
In order to derive the excess risk guarantees, we first need to slightly modify the output of Algorithm 1 as Ak∗(Sk∗) where k∗ = arg mink∈[K]RS\Sk(Ak(Sk)). The following theorem is our main result about the high probability excess risk bounds of such a modified output of confidenceboosting. See Appendix B.3 for its proof.
Theorem 2. Suppose that a randomized learning algorithm A : ZN 7→ W has γm,N -mean-uniform stability. Assume that the loss function ` is G-Lipschitz with respect to its first argument and is bounded in the range of [0,M ]. Then for any α, δ ∈ (0, 1) and K ≥ 11−α log( 4 δ ), with probability at least 1− δ over the randomness of S and {Ak}k∈[K], the modified output of Algorithm 1 satisfies
R(Ak∗(Sk∗))−R(w∗) . 1
α
( Gγm,NK + ∆opt ) +M √ log(K/δ) N .
Remark 4. Unlike the generalization error bounds, the excess risk bounds established in Theorem 2 are not relying on the mean-square uniform stability of the algorithm, but with an additional term of in-expectation optimization error for minimizing the empirical risk. For deterministic optimization algorithms such as ERMs with ∆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.
Remark 5. Consider K log ( 1 δ ) and γm,N . 1√N . Then the bound in Theorem 2 roughly scales
as O( √
log(1/δ) N + ∆opt).
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 non-negative and
Algorithm 2: SGD via With-Replacement Sampling (ASGD-w)
Input : Data set S = {zi}i∈[N ] i.i.d.∼ DN , step-sizes {ηt}t≥1, #iterations T , initialization w0. Output: w̄T = 1T ∑ t∈[T ] wt. for t = 1, 2, ..., T do Uniformly randomly sample an index ξt ∈ [N ] with replacement; Compute wt = ΠW (wt−1 − ηt∇w`(wt−1; zξt)). end
its in-expectation bound is standardly known for uniformly stable learning algorithms, the highconfidence 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 way more challenging in the sense that establishing tight in-expectation first moment generalization bound (see Lemma 1) for uniformly stable randomized algorithms is by itself highly non-trivial.

heading: 3 IMPLICATIONS FOR STOCHASTIC GRADIENT DESCENT
text: In this section we demonstrate the applications of the generic bound in Theorem 1 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 ASGD-w. In what follows, we denote by {ASGD-w,k}k∈K the outputs of ASGD-w over subsets {Sk}k∈K when applied with Algorithm 1. Our results readily extend to the without-replacement variant of SGD and the corresponding results can be found in Appendix D.

heading: 3.1 CONVEX OPTIMIZATION WITH SMOOTH LOSS
text: For smooth and convex losses such as logistic loss, we can derive the following result as a direct consequence of Theorem 1 with α = 1/2 to ASGD-w. See Appendix C.1 for its proof. Corollary 1. Suppose that the loss function is `(·; ·) 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 ASGD-w with learning rate ηt ≤ 2/L for all t ≥ 1. Then for any δ ∈ (0, 1) and K log( 4δ ), with probability at least 1 − δ over the randomness of S and {ASGD-w,k}k∈[K], the generalization error is upper bounded as |R(ASGD-w,k∗(Sk∗))−RS(ASGD-w,k∗(Sk∗))| .
G2 √√√√√ 1 N  T∑ t=1 η2t + 1 N ( T∑ t=1 ηt )2+ G2 N T∑ t=1 ηt +M √ log(1/δ) N .
Remark 6. For the conventional step-size choice of ηt = 2L√t , the high probability generalization bound in Corollary 1 is dominated by O( √
log(T ) N +
√ T+ √ N log(1/δ)
N ), which matches the corre-
sponding O( √ T N ) in-expectation bound for SGD with smooth convex losses (Hardt et al., 2016).

heading: 3.2 CONVEX OPTIMIZATION WITH NON-SMOOTH LOSS
text: 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 ASGD-w with non-smooth convex loss and time varying learning rate {ηt}t≥1. Its proof is provided in Appendix C.2. Corollary 2. Suppose that the loss function is `(·; ·) is convex andG-Lipschitz with respect to its first argument, and is bounded in the range of [0,M ]. Consider Algorithm 1 specified to ASGD-w. Then for any δ ∈ (0, 1) and K log( 4δ ), with probability at least 1 − δ over the randomness of S and {ASGD-w,k}k∈[K], the generalization error satisfies |R(ASGD-w,k∗(Sk∗))−RS(ASGD-w,k∗(Sk∗))| .
G2 √√√√ T∑ t=1 η2t + 1 N2 ( T∑ t=1 ηt )2 +G2 √√√√ T∑ t=1 η2t + G2 N T∑ t=1 ηt +M √ log(1/δ) N .
Remark 7. For constant rates ηt ≡ η, Corollary 2 admits a high probability generalization bound of scale O(η √ T + η TN +
√ log(1/δ)
N ) which matches the near-optimal rate by Bassily et al. (2020, Theorem 3.3). More importantly, our deviation bound in Corollary 2 still holds for time varying learning rates.

heading: 3.3 NON-CONVEX OPTIMIZATION WITH SMOOTH LOSS
text: 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 ASGD-w with smooth non-convex loss. See Appendix C.3 for its proof. Corollary 3. Suppose that the loss function is `(·; ·) 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 ASGD-w with ηt ≤ 1L . Let ut := η 2 t + 2ηt ∑t−1 τ=1 exp(L ∑t−1 i=τ+1 ηi)ητ for all t ≥ 1. Then for any δ ∈ (0, 1) and K log( 4δ ), with probability at least 1− δ over the randomness of S and {ASGD-w,k}k∈[K], the generalization error is upper bounded as |R(ASGD-w,k∗(Sk∗))−RS(ASGD-w,k∗(Sk∗))| .
G2 √√√√ 1 N T∑ t=1 exp ( L T∑ τ=t+1 ητ ) ut + G2 N T∑ t=1 exp ( L T∑ τ=t+1 ητ ) ηt +M √ log(1/δ) N .
Remark 8. For the constant learning rates ηt ≡ 1LT , Corollary 3 admits high probability generalization bound of scale O( √
log(1/δ) N ). For time decaying learning rates ηt = 1 Lνt with arbitrary ν ≥ 1, it can be verified that the corresponding bound is of scale O( √
T 1/ν log(T ) νN +
√ log(1/δ)
N ).

heading: 4 IMPLICATIONS FOR DETERMINISTIC UNIFORMLY STABLE ALGORITHMS
text: This section is devoted to showing that confidence-boosting is also beneficial for deriving stronger generalization bounds for uniformly stable deterministic learning algorithms. First we note that when there is no internal randomness inA, the definition of mean(-square)-uniform stability reduces to the conventional concept of γN -uniform stability for deterministic algorithms given by
sup S . =S′ ‖A(S)−A(S′)‖ ≤ γN = γm,N =
√ γm2,N .
Let us now consider a specification of Algorithm 1 to a uniformly stable deterministic algorithm A. Since there is no randomness contained in A, we have that Ak(Sk) = A(Sk) for all k ∈ [K] in such a deterministic case. Then the following result is a direct consequence of Theorem 1 when applied to the considered deterministic learning regime. Corollary 4. Suppose that a deterministic learning algorithm A : ZN 7→ W has γN -uniform stability. Assume that the loss function ` is G-Lipschitz with respect to its first argument and is bounded in [0,M ]. Then for any α, δ ∈ (0, 1) and K ≥ log(4/δ)1−α , with probability at least 1− δ over the randomness of S, the output of Algorithm 1 satisfies
|R(A(Sk∗))−RS(A(Sk∗))| . 1
αK
( GγN
K +M
√ K
N
) +M √ log(K/δ)
N .
To demonstrate the superiority of our bound over prior ones, let us consider α = 0.5 andK log( 1δ ) in the above corollary. In the regime γN . 1√N which is of interest in many popular deterministic learning paradigms/algorithms such as regularized ERM (Shalev-Shwartz et al., 2009) and full gradient descent (Feldman & Vondrak, 2019), Corollary 4 implies a generalization bound for A(Sk∗)
over the data set S that scales as |R(A(Sk∗))−RS(A(Sk∗))| . √ log(1/δ) N . In comparison, the best known bound in equation 5 essentially from Bousquet et al. (2020) gives (keep in mind that δ′ = 0 in the deterministic case) |R(A(S))−RS(A(S))| . log(N)√N log( 1 δ ). As we can see that inside the carefully designed framework of confidence-bossting 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 sample. We expect this result will fuel future research towards fully resolving the corresponding open question raised in Bousquet et al. (2020).

heading: 5 OTHER RELATED WORK
text: 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 & Chervonenkis, 1974; Rogers & Wagner, 1978; Devroye & 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 & Elisseeff, 2002; Zhang, 2003; Klochkov & 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 & Ying, 2020) or deviation (Bassily et al., 2020). In Kuzborskij & 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 & Papailiopoulos (2018); Lei & 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 & 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 and 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 & Maclin, 1999), and sometimes stable algorithms such as SVMs (Valentini & Dietterich, 2003). As an important variant of bagging, subbagging has been proposed to reduce the computational cost of bagging via training base models under withoutreplacement sampling (Bü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/δ to a high-confidence algorithm with logarithmic factor log(1/δ). 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/δ (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 inexpectation first moment generalization bound for uniformly stable randomized algorithms.

heading: 6 CONCLUSIONS
text: In this paper we presented a generic confidence-boosting method for deriving near-optimal high probability generalization bounds for uniformly 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 notion of mean(-square)-uniform 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. While sharper in the dependence on sample size, 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 log ( 1 δ ) . 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 sample. We leave the full understanding of such an open issue raised by Bousquet et al. (2020) for future investigation.

heading: A AUXILIARY LEMMAS
text: We need the following lemma from Hardt et al. (2016) which shows that SGD iteration is nonexpansive on convex and smooth loss. Lemma 2 (Hardt et al. (2016)). Assume that f is convex and L-smooth. Then for any w,w′ ∈ W and α ≤ 2/L, we have the following bound holds
‖w − α∇f(w)− (w′ − α∇f(w′))‖ ≤ ‖w − w′‖.
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τ}τ≥1 satisfies the following recursion for all t ≥ 1:
u2t ≤ St + t∑
τ=1
ατuτ ,
with {Sτ}τ≥1 an increasing sequence, S0 ≥ u20 and ατ ≥ 0 for all τ . Then, the following inequality holds for all t ≥ 1:
ut ≤ √ St + t∑ τ=1 ατ .

heading: B PROOFS FOR THE RESULTS IN SECTION 2
text: 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 4. Let S = {Z1, Z2, ..., ZN} be a set of i.i.d. random variables valued in Z . Let g1, ..., gN be a set of measurable functions gi : ZN 7→ R that satisfy ES [g2i (S)] ≤ M2 and EZi [gi(S)] = 0 for all i ∈ [N ]. Then we have
ES [∣∣∣∣∣ N∑ i=1 gi(S) ∣∣∣∣∣ ] ≤ √∑ i6=j ES,S(j) [( gi(S)− gi(S(j)) )2] +M √ N,
where S(j) = {Z1, ..., Zj−1, Z ′j , Zj+1, ..., ZN} and S′ = {Z ′1, Z ′2, ..., Z ′N} is another i.i.d. sample from the same distribution as that of S.
Proof. We reproduce the proof in view of the argument in Bousquet et al. (2020, Section 5) showing that {gi} are weakly correlated. For any i 6= j, since EZi [gi(S)] = 0 and EZj [gj(S)] = 0, we can verify that
ES [ gi(S (j))gj(S) ] = ES\Zj [ EZj [ gi(S (j))gj(S) | S \ Zj ]] = ES\Zj [ gi(S (j))EZj [gj(S) | S \ Zj ] ] = 0,
where we have used the independence of the elements in S ∪ {Z ′j}. Similarly, we can show that ES [ gi(S)gj(S (i)) ] = ES [ gi(S (j))gj(S (i)) ] = 0.
Then it follows that for any i 6= j, |ES [gi(S)gj(S)]| = ∣∣ES,S(i),S(j) [gi(S)gj(S)]∣∣
= ∣∣∣ES,S(i),S(j) [(gi(S)− gi(S(j)))(gj(S)− gj(S(i)))]∣∣∣ ≤ES,S(i),S(j) [∣∣∣(gi(S)− gi(S(j)))(gj(S)− gj(S(i)))∣∣∣] .
Based on the above bound and Jensen’s inequality we get
ES [∣∣∣∣∣ N∑ i=1 gi(S) ∣∣∣∣∣ ]
≤ √√√√√ES ( N∑
i=1
gi(S)
)2 = √√√√∑
i 6=j ES [gi(S)gj(S)] + N∑ i=1 ES [g2i (S)]
≤ √∑
i 6=j
ES,S(i),S(j) [∣∣(gi(S)− gi(S(j)))(gj(S)− gj(S(i)))∣∣]+M√N
≤ √ 1
2 ∑ i6=j ES,S(i),S(j) [( gi(S)− gi(S(j)) )2 + ( gj(S)− gj(S(i)) )2] +M √ N
= √∑ i 6=j ES,S(j) [( gi(S)− gi(S(j)) )2] +M √ N.
This proves the desired bound.
Now we are ready to prove the result in Lemma 1.
Proof of Lemma 1. Let us consider hi(S) := R(A(S)) − `(A(S);Zi) and gi(S) = hi(S) − EZi [hi(S)] for i ∈ [N ]. Then by assumption we have EZi [gi(S)] = 0, ES [g2i (S)] ≤M2. For each i ∈ [N ], let S(i) denote a random data set that is identical to S except that one of the Zi is replaced by another random sample Z ′i. For any i 6= j, since the loss is non-negative and G-Lipschitz, it can be verified that
|gi(S)− gi(S(j))| ≤max {∣∣∣hi(S)− hi(S(j))∣∣∣ , ∣∣∣EZi [hi(S)− hi(S(j))]∣∣∣}
≤max { G‖A(S)−A(S(j))‖,EZi [ G‖A(S)−A(S(j))‖ ]}, which readily implies
ES,S(j) [( gi(S)− gi(S(j)) )2] ≤ ES,S(j) [ G2‖A(S)−A(S(j))‖2 ] .
Then invoking Lemma 4 to {gi} yields
ES [∣∣∣∣∣ N∑ i=1 gi(S) ∣∣∣∣∣ ] ≤ √∑ i6=j ES,S(j) [( gi(S)− gi(S(j)) )2] +M √ N
≤G √∑
i6=j
ES,S(j) [ ‖A(S)−A(S(j))‖2 ] +M √ N.
(A.1)
Further, it can be verified that
ES [∣∣∣∣∣ N∑ i=1 EZi [hi(S)] ∣∣∣∣∣ ]
=ES [∣∣∣∣∣ N∑ i=1 EZi [R(A(S))− `(A(S);Zi)] ∣∣∣∣∣ ]
=ES [∣∣∣∣∣ N∑ i=1 EZi [EZ′i [`(A(S);Z ′ i)]− `(A(S);Zi)] ∣∣∣∣∣ ]
=ES [∣∣∣∣∣ N∑ i=1 EZi [ EZ′i [`(A(S);Z ′ i)]− EZ′i [`(A(S (i));Z ′i)] ]∣∣∣∣∣ ]
≤ES,S(i) [ G‖A(S)−A(S(i))‖ ] .
(A.2)
By combining equation A.1 and equation A.2 we obtain
EA,S [|R(A(S))−RS(A(S))|]
= 1
N EA,S [∣∣∣∣∣ N∑ i=1 (gi(S) + EZi [hi(S)]) ∣∣∣∣∣ ]
≤G N EA √∑ i 6=j ES,S(j) [ ‖A(S)−A(S(j))‖2 ]+ G N EA,S,S(i) [ ‖A(S)−A(S(i))‖ ] + M√ N
≤G N √∑ i 6=j EA,S,S(j) [ ‖A(S)−A(S(j))‖2 ] + G N EA,S,S(i) [ ‖A(S)−A(S(i))‖ ] + M√ N
≤G√γm2,N +Gγm,N + M√ N ,
where in the last inequality we have used the stability conditions on A. 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 log( 1δ ), at least one of the solutions generated by subbagging generalizes well with high probability.
Lemma 5. Suppose that a randomized learning algorithm A : ZN 7→ W has γm,N -mean-uniform stability and γm2,N -mean-square-uniform stability as well. Assume that the loss function ` is GLipschitz with respect to its first argument and is bounded in the range of [0,M ]. Then for any α, δ ∈ (0, 1) and K ≥ log(2/δ)1−α , with probability at least 1 − δ over the randomness of {(Ak, Sk)}k∈[K], the sequence {Ak(Sk)}k∈[K] generated by Algorithm 1 satisfies
min k∈[K]
|R(Ak(Sk))−RSk(Ak(Sk))| . 1
α
( G √ γm2,NK +Gγm,NK +M √ K
N
) .
Proof. From Lemma 1 we have that over randomized algorithm A and data S̃ with |S̃| = NK ,
EA,S̃ [ |R(A(S̃))−RS̃(A(S̃))| ] ≤ G√γm2,NK +Gγm,NK +M √ K N .
Since {Ak, Sk}k∈[K] are independent to each other, by Markov inequality we know that
P{Ak,Sk} ( min k∈[K] |R(Ak(Sk))−RSk(Ak(Sk))| ≥ 1 α ( G √ γm2,NK +Gγm,NK +M √ K N )) ≤ αK ≤ δ,
which implies the desired bound.
Next we proceed to prove the main result in Theorem 1.
Proof of Theorem 1. Let us consider the following three events:
E := { |R(Ak∗(Sk∗))−RS(Ak∗(Sk∗))| . 1
αK
( G √ γm2,NK +Gγm,NK +M √ K
N
) +M √ K log(K/δ)
(K − 1)N
} ,
E1 := { max k∈[K] |R(Ak(Sk))−RS\Sk(Ak(Sk))| .M √ K log(K/δ) (K − 1)N } ,
E2 := { min k∈[K] |R(Ak(Sk))−RSk(Ak(Sk))| . 1 α ( G √ γm2,NK +Gγm,NK +M √ K N )} .
We can show that E ⊇ E1 ∩E2. Indeed, suppose that E1 and E2 simultaneously occur. Consequently the following inequality is valid:
|R(Ak∗(Sk∗))−RS(Ak∗(Sk∗))|
= ∣∣∣∣R(Ak∗(Sk∗))− 1KRSk∗ (Ak∗(Sk∗))− K − 1K RS\Sk∗ (Ak∗(Sk∗)) ∣∣∣∣
≤ 1 K |R(Ak∗(Sk∗))−RSk∗ (Ak∗(Sk∗))|+ K − 1 K ∣∣R(Ak∗(Sk∗))−RS\Sk∗ (Ak∗(Sk∗))∣∣ ≤ 1 K
∣∣RS\Sk∗ (Ak∗(Sk∗))−RSk∗ (Ak∗(Sk∗))∣∣+ ∣∣R(Ak∗(Sk∗))−RS\Sk∗ (Ak∗(Sk∗))∣∣ ζ1 = 1
K min k∈[K] ∣∣RS\Sk(Ak(Sk))−RSk(Ak(Sk))∣∣+ ∣∣R(Ak∗(Sk∗))−RS\Sk∗ (Ak∗(Sk∗))∣∣ = 1
K min k∈[K] ∣∣RS\Sk(Ak(Sk))−R(Ak(Sk)) +R(Ak(Sk))−RSk(Ak(Sk))∣∣ + ∣∣R(Ak∗(Sk∗))−RS\Sk∗ (Ak∗(Sk∗))∣∣
≤ 1 K min k∈[K] |R(Ak(Sk))−RSk(Ak(Sk))|+ 1 K max k∈[K] ∣∣RS\Sk(Ak(Sk))−R(Ak(Sk))∣∣ + ∣∣R(Ak∗(Sk∗))−RS\Sk∗ (Ak∗(Sk∗))∣∣
≤ 1 K min k∈[K] |R(Ak(Sk))−RSk(Ak(Sk))|+ K + 1 K max k∈[K] ∣∣R(Ak(Sk))−RS\Sk(Ak(Sk))∣∣ ζ2 . 1
αK
( G √ γm2,NK +Gγm,NK +M √ K
N
) +M √ K log(K/δ)
(K − 1)N ,
where in “ζ1” we have used the definition of k∗, and “ζ2” follows from E1, E2. With leading terms preserved in the above we can see that E occurs. Next we can show that PS,{Ak}(E1) ≤ δ2 . Toward this end, let us consider the following events for all k ∈ [K]:
Ek1 := { |R(Ak(Sk))−RS\Sk(Ak(Sk))| .M √ K log(K/δ)
(K − 1)N
} .
Clearly, it is true that E1 = ⋂K k=1 Ek1 . It is sufficient to prove that PS,Ak ( Ek1 ) ≤ δ2K holds for each k ∈ [K]. Indeed, consider the random indication function β(S,Ak) := 1Ek1 associated with the event Ek1 . Then we have the following holds for each k ∈ [K]:
PS,Ak ( Ek1 )
=ES,Ak [β(S,Ak)] =EAk,Sk [ ES\Sk|Ak,Sk [β(S,Ak) | Ak, Sk] ] ζ1 =EAk,Sk [ ES\Sk [β(S,Ak) | Ak, Sk]
] =EAk,Sk [ PS\Sk ( |R(Ak(Sk))−RS\Sk(Ak(Sk))| &M √ K log(K/δ)
(K − 1)N
) | Ak, Sk ] ζ2 ≤EAk,Sk [ δ
2K | Ak, Sk
] = δ
2K ,
where in “ζ1” we have used the independence between {Ak, Sk} and S \ Sk, and “ζ2” is due to Hoeffding’s inequality conditioned on {Ak, Sk}, keeping in mind that Ak(Sk) is independent on the data set S \ Sk of size (1− 1/K)N . It follows by union probability that
PS,{Ak} ( E1 ) = PS,{Ak} ( K⋃ k=1 Ek1 ) ≤ K∑ k=1 PS,Ak ( Ek1 ) ≤ δ 2 .
Further, from the part(b) of Lemma 5 we have PS,{Ak}(Ē2) ≤ δ2 . Combining this and the preceding bound yields
PS,{Ak} (E) ≥ PS,{Ak} (E1 ∩ E2) ≥ 1− PS,{Ak} ( Ē1 ) − PS,{Ak}(Ē2) ≥ 1− δ
2 − δ 2 = 1− δ.
This implies the desired result in part(b) as K/(K − 1) ≤ 2 for K ≥ 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 6. Suppose that a randomized learning algorithm A : ZN 7→ W has γm,N -mean-uniform stability. Assume that the loss function ` is G-Lipschitz with respect to its first argument. Then we have
EA,S [R(A(S))−R(w∗)] ≤ Gγm,N + ∆opt.
Proof. By risk decomposition we can show that
EA,S [R(A(S))−R(w∗)] =EA,S [R(A(S))−RS(A(S)) +RS(A(S))−RS(w∗) +RS(w∗)−R(w∗)] ≤ |EA,S [R(A(S))−RS(A(S))]|+ ∆opt ≤Gγm,N + ∆opt,
where in the last inequality we have used the on-average generalization bound by Hardt et al. (2016, Theorem 2.2).
Lemma 7. Suppose that a randomized learning algorithm A : ZN 7→ W has γm,N -mean-uniform stability. Assume that the loss function ` is G-Lipschitz with respect to its first argument. Then for any α, δ ∈ (0, 1) and K ≥ log(2/δ)1−α , with probability at least 1 − δ over the randomness of {(Ak, Sk)}k∈[K], the sequence {Ak(Sk)}k∈[K] generated by Algorithm 1 with the modified output satisfies
min k∈[K]
R(Ak(Sk))−R(w∗) . 1
α
( Gγm,NK + ∆opt ) .
Proof. Recall the modified output Ak∗(Sk∗) where k∗ = arg mink∈[K]RS\Sk(Ak(Sk)). From Lemma 6 we have that over randomized algorithm A and data S̃ with |S̃| = NK ,
EA,S̃ [ R(A(S̃))−R(w∗) ] ≤ Gγm,NK + ∆opt.
Since {Ak, Sk}k∈[K] are independent to each other, by Markov inequality we know that P{Ak,Sk} (
min k∈[K]
R(Ak(Sk))−R(w∗) ≥ 1
α
( Gγm,NK + ∆opt )) ≤ αK ≤ δ,
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:
E := { |R(Ak∗(Sk∗))−RS(Ak∗(Sk∗))| . 1
α
( Gγm,NK + ∆opt ) +M
√ K log(K/δ)
(K − 1)N
} ,
E1 := { max k∈[K] |R(Ak(Sk))−RS\Sk(Ak(Sk))| .M √ K log(K/δ) (K − 1)N } ,
E2 := {
min k∈[K]
R(Ak(Sk))−R(w∗) . 1
α
( Gγm,NK + ∆opt )} .
Similarly, we show that E ⊇ E1 ∩ E2. Indeed, suppose that E1 and E2 simultaneously occur. Consequently the following inequality is valid:
R(Ak∗(Sk∗))−R(w∗) =R(Ak∗(Sk∗))−RS\Sk∗ (Ak∗(Sk∗)) +RS\Sk∗ (Ak∗(Sk∗))−R(w ∗)
ζ1 =R(Ak∗(Sk∗))−RS\Sk∗ (Ak∗(Sk∗)) + min
k∈[K] RS\Sk(Ak(Sk))−R(w
∗)
=R(Ak∗(Sk∗))−RS\Sk∗ (Ak∗(Sk∗)) + min k∈[K]
{ RS\Sk(Ak(Sk))−R(Ak(Sk)) +R(Ak(Sk))−R(w ∗) }
≤ min k∈[K] (R(Ak(Sk))−R(w∗)) + 2 max k∈[K] ∣∣RS\Sk(Ak(Sk))−R(Ak(Sk))∣∣ ζ2 . 1
α
( Gγm,NK + ∆opt ) +M
√ K log(K/δ)
(K − 1)N ,
where in “ζ1” we have used the definition of k∗, and “ζ2” follows from E1, E2. With leading terms preserved in the above we can see that E occurs. Based on the same proof argument as that of the part(b) of Theorem 1 we can show that PS,{Ak}(E1) ≤ δ2 . Further, from the part(b) of Lemma 7 we have PS,{Ak}(Ē2) ≤ δ 2 . Combining this and the preceding bound yields
PS,{Ak} (E) ≥ PS,{Ak} (E1 ∩ E2) ≥ 1− PS,{Ak} ( Ē1 ) − PS,{Ak}(Ē2) ≥ 1− δ
2 − δ 2 = 1− δ.
This implies the desired result in part(b) as K/(K − 1) ≤ 2 for K ≥ 2.

heading: C PROOFS FOR THE RESULTS IN SECTION 3
text: 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 mean(-square)-uniform stability bounds for ASGD-w on convex and smooth loss functions such as logistic loss.
Lemma 8. Suppose that the loss function is `(·; ·) is convex, G-Lipschitz and L-smooth with respect to its first argument. Assume that ηt ≤ 2/L for all t ≥ 1. Then ASGD-w has mean-uniform stability such that
sup S . =S′
EASGD-w [‖ASGD-w(S)−ASGD-w(S′)‖] ≤ 2G
N ∑ t∈[T ] ηt,
and has mean-square-uniform stability such that
sup S . =S′
EASGD-w [ ‖ASGD-w(S)−ASGD-w(S′)‖2 ] ≤ 40G 2
N  T∑ t=1 η2t + 1 N ( T∑ t=1 ηt )2 . Proof. The first mean-uniform stability bound can be straightforwardly derived based on the argument of Hardt et al. (2016, Theorem 3.7). We focus on proving the second mean-square-uniform stability bound. For any pair of S, S′, let us define the sequences {wt}t∈[T ] and {w′t}t∈[T ] that are respectively generated over S and S′ viaASGD-w via sample path ξ = {ξt}t∈[T ]. Note by assumption that w0 = w′0. We distinguish the following two complementary cases.
Case I: zξt = z′ξt . In this case, by invoking Lemma 2 we immediately get
‖wt − w′t‖2 =‖ΠW(wt−1 − ηt∇w`(wt−1; zξt))−ΠW(w′t−1 − ηt∇w`(w′t−1; z′ξt))‖ 2
≤‖wt−1 − ηt∇w`(wt−1; zξt)− (w′t−1 − ηt∇w`(w′t−1; z′ξt))‖ 2
≤‖wt−1 − w′t−1‖2. (A.3)
Case II: zξt 6= z′ξt . In this case, we have
‖wt − w′t‖2 =‖ΠW(wt−1 − ηt∇f(w))−ΠW(w′ − α∇f(w′))‖2
≤‖wt−1 − ηt∇w`(wt−1; zξt)− (w′t−1 − ηt∇w`(w′t−1; z′ξt))‖ 2 ≤ ( ‖wt−1 − w′t−1‖+ ηt(‖∇w`(wt−1; zξt)‖+ ‖∇w`(w′t−1; z′ξt)‖) )2 ≤ ( ‖wt−1 − w′t−1‖+ 2Gηt
)2 =‖wt−1 − w′t−1‖2 + 4Gηt‖wt−1 − w′t−1‖+ 4G2η2t ,
(A.4)
where in the last but inequality we have used `(·; ·) is G-Lipschitz with respect to its first argument. Let βt = βt(S, S′, ξ) := 1{zξt 6=z′ξt}
be the random indication function associated with event zξt 6= z′ξt . Based on the recursion forms equation A.3 and equation A.4 and the condition w0 = w ′ 0 we can show that for all t ≥ 1,
‖wt − w′t‖2 ≤ t∑
τ=1
4Gβτητ‖wτ−1 − w′τ−1‖+ t∑
τ=1
4G2βτη 2 τ .
Then applying Lemma 3 with simple algebraic manipulation yields ‖wt − w′t‖2 ≤ 8G2  t∑ τ=1 βτη 2 τ + 4 ( t∑ τ=1 βτητ )2 . Since by assumption S and S′ differ only in a single element, under the scheme of uniform sampling without replacement, we can see that βt(S, S′, ξ) ∼ Bernoulli(1/N) and {βt(S, S′, ξ)} is an i.i.d. sequence of Bernoulli random variables. It follows that
Eξ[t] [ ‖wt − w′t‖2 ] ≤8G2
 t∑ τ=1 Eξ[t] [βτ ]η 2 τ + 4Eξ[t] ( t∑ τ=1 βτητ )2 =8G2
 t∑ τ=1 Eξ[t] [βτ + 4β 2 τ ]η 2 τ + 4 ∑ τ 6=τ ′ 1Eξ[t] [βτβτ ′ ] ητητ ′  =8G2  5 N t∑ τ=1 η2τ + 4 N2 ( t∑ τ=1 ητ )2 ≤ 40G2  1 N T∑ τ=1 η2τ + 1 N2 ( T∑ τ=1 ητ
)2 , where we have used Eξt [βt] = Eξt [β2t ] = 1N . The convexity of squared Euclidean norm leads to
Eξ [ ‖w̄T − w̄′T ‖2 ] ≤ ∑T t=1 Eξ[t] [ ‖wt − w′t‖2 ] T ≤ 40G2  1 N T∑ t=1 η2t + 1 N2 ( T∑ t=1 ηt )2 . Note that the above holds for any S .= S′, i.e.,
sup S . =S′
Eξ [ ‖w̄T − w̄′T ‖2 ] ≤ 40G 2
N  T∑ t=1 η2t + 1 N ( T∑ t=1 ηt )2 . The proof is concluded.
With Lemma 8 in place, we are ready to prove Corollary 1.
Proof of Corollary 1. From Lemma 8 we know thatASGD-w has mean-uniform stability with parameter
γm,N = 2G
N ∑ t∈[T ] ηt,
and mean-square-uniform stability with parameter
γm2,N = 40G2
N  T∑ t=1 η2t + 1 N ( T∑ t=1 ηt )2 . The desired results then follow immediately via invoking Theorem 1 with α = 1/2.
C.2 PROOF OF COROLLARY 2
We first establish the following lemma on the mean(-square)-uniform stability of ASGD-w in the case of non-smooth convex loss. Lemma 9. Suppose that the loss function is `(·; ·) is convex and G-Lipschitz with respect to its first argument. Then ASGD-w has mean-uniform stability such that
sup S . =S′
EASGD-w [‖ASGD-w(S)−ASGD-w(S′)‖] ≤ 2G √√√√ T∑ t=1 η2t + 4G N T∑ t=1 ηt,
and has mean-square-uniform stability such that
sup S . =S′
EASGD-w [ ‖ASGD-w(S)−ASGD-w(S′)‖2 ] ≤ 40G2 T∑ t=1 η2t + 32G2 N2 ( T∑ t=1 ηt )2 .
Proof. Let us define the sequences {wt}t∈[T ] and {w′t}t∈[T ] that are respectively generated over S and S′ via ASGD-w via sample path ξ = {ξt}t∈[T ]. Suppose that S . = S′ and consider a hitting time variable t0 = inf{t : zξt 6= z′ξt}. Let βt = βt(S, S ′, ξ) := 1{zξt 6=z′ξt} be the random indication function associated with event zξt 6= z′ξt . Conditioned on t0, it has been shown by Bassily et al. (2020, Lemma 3.1) that
‖wt − w′t‖ ≤ 2G √√√√ t∑ τ=t0 η2τ + 4G t∑ τ=t0+1 βτητ ≤ 2G √√√√ t∑ τ=1 η2τ + 4G t∑ τ=1 βτητ . (A.5)
Then we can show the following for all t ≤ T
Eξ[t] [‖wt − w ′ t‖] ≤ 2G √√√√ t∑ τ=1 η2τ + 4G N t∑ τ=1 ητ ,
where we have used the fact that {βt} is an i.i.d. sequence of Bernoulli(1/N) random variables. The convexity of Euclidean norm leads to
Eξ[T ] [‖w̄T − w̄ ′ T ‖] ≤
∑T t=1 Eξ[t] [‖wt − w′t‖]
T ≤ 2G √√√√ T∑ t=1 η2t + 4G N T∑ t=1 ηt,
which is the first desired bound. Similarly, based on the square of the bound equation A.5 we can show that
Eξ[t] [ ‖wt − w′t‖2 ] ≤Eξ[t] 8G2 t∑ τ=1 η2τ + 32G 2 ( t∑ τ=1 βτητ )2 =8G2
t∑ τ=1 η2τ + 32G 2Eξ[t]  t∑ τ=1 β2τη 2 τ + ∑ τ 6=τ ′ βτβτ ′ητητ ′  =8G2
t∑ τ=1 η2τ + 32G 2  1 N t∑ τ=1 η2τ + 1 N2 ∑ τ 6=τ ′ ητητ ′  ≤40G2
t∑ τ=1 η2τ + 32G2 N2
( t∑
τ=1
ητ
)2 ,
where we have used Eξt [βt] = Eξt [β2t ] = 1N . It follows directly from the convexity of loss that
Eξ[T ] [ ‖w̄T − w̄′T ‖2 ] ≤ 40G2 T∑ t=1 η2t + 32G2 N2 ( T∑ t=1 ηt )2 .
The proof is concluded.
Equipped with Lemma 9, we are now in the position to prove Corollary 2.
Proof of Corollary 2. From Lemma 9 we know that ASGD-w with non-smooth convex loss has mean(-square)-uniform stability with parameters
γm,N = 2G √√√√ T∑ t=1 η2t + 4G N T∑ t=1 ηt, γm2,N = 40G 2 T∑ t=1 η2t + 32G2 N2 ( T∑ t=1 ηt )2 .
The desired results then follow immediately via invoking Theorem 1 with α = 1/2.
C.3 PROOF OF COROLLARY 3
We first establish the following lemma on the mean(-square)-uniform stability of ASGD-w in the considered non-convex regime.
Lemma 10. Suppose that the loss function is `(·; ·) is G-Lipschitz and L-smooth with respect to its first argument. Consider ηt ≤ 1/L. Let
ut := η 2 t + 2ηt t−1∑ τ=1 exp
( L
t−1∑ i=τ+1 ηi
) ητ
for all t ≥ 1. Then ASGD-w has mean-uniform stability such that
sup S . =S′
EASGD-w [‖ASGD-w(S)−ASGD-w(S′)‖] ≤ 2G
N T∑ t=1 exp
( L
T∑ τ=t+1 ητ
) ηt,
and has mean-square-uniform stability such that
sup S . =S′
EASGD-w [ ‖ASGD-w(S)−ASGD-w(S′)‖2 ] ≤ 4G 2
N T∑ t=1 exp
( 3L
T∑ τ=t+1 ητ
) ut.
Proof. Let us define the sequences {wt}t∈[T ] and {w′t}t∈[T ] that are respectively generated over S and S′ via ASGD-w via sample path ξ = {ξt}t∈[T ]. Suppose that S . = S′. Let us consider ∆t := Eξ[t] [‖wt − w′t‖]. Then based on the arguments of Hardt et al. (2016, Theorem 3.8) we know that with probability 1− 1N over ξt, ‖wt−w ′ t‖ ≤ (1+ηtL)‖wt−1−w′t−1‖, and ‖wt−w′t‖ ≤ ‖wt−1 − w′t−1‖+ 2Gηt with probability 1N . Therefore we have
∆t ≤ (
1− 1 N
) (1 + ηtL)∆t−1 + 1
N (∆t−1 + 2Gηt)
= (( 1− 1
N
) (1 + ηtL) + 1
N
) ∆t−1 +
2Gηt N
= ( 1 + ( 1− 1
N
) ηtL ) ∆t−1 +
2Gηt N
≤ exp ((
1− 1 N
) ηtL ) ∆t−1 +
2Gηt N
≤ exp (ηtL) ∆t−1 + 2Gηt N ,
where we have used 1 + x ≤ exp(x). Then we can unwind the above recursion form to obtain that for all t ≥ 1,
∆t ≤ t∑
τ=1
{ t∏
i=τ+1
exp (ηiL) } 2Gητ N = 2G N t∑ τ=1 exp ( L t∑ i=τ+1 ηi ) ητ , (A.6)
where we have used ∆0 = 0. The convexity of Euclidean norm leads to
Eξ[T ] [‖w̄T − w̄ ′ T ‖] ≤
∑T t=1 Eξ[t] [‖wt − w′t‖]
T ≤ 2G N T∑ t=1 exp
( L
T∑ τ=t+1 ητ
) ηt,
which immediately implies the first desired bound as it holds for all S .= S′.
To show the mean-square-uniform stability bound, let us consider ∆̃t := Eξ[t] [ ‖wt − w′t‖2 ] . Then we can verify that with probability 1− 1N over ξt, ‖wt − w ′ t‖2 ≤ (1 + ηtL)2‖wt−1 − w′t−1‖2, and with probability 1N ,
‖wt − w′t‖2 ≤ (‖wt−1 − w′t−1‖+ 2Gηt)2 = ‖wt−1 − w′t−1‖2 + 4Gηt‖wt−1 − w′t−1‖+ 4G2η2t . Therefore we have
∆̃t ≤ (
1− 1 N
) (1 + ηtL) 2∆̃t−1 + 1
N
( ∆̃t−1 + 4Gηt∆t−1 + 4G 2η2t )
≤ ((
1− 1 N
) (1 + ηtL) 2 + 1
N
) ∆̃t−1 + 4G2
N η2t + 2ηt t−1∑ τ=1 exp ( L t−1∑ i=τ+1 ηi ) ητ︸ ︷︷ ︸
ut  = ( 1 + ( 1− 1
N
) (2ηtL+ η 2 tL 2) ) ∆̃t−1 +
4G2ut N
≤ exp ((
1− 1 N
) (2ηtL+ η 2 tL 2) ) ∆̃t−1 +
4G2ut N
≤ exp ( 2ηtL+ η 2 tL 2 )
∆̃t−1 + 4G2ut N ,
where in the second inequality we have used the bound equation A.6 on ∆t. Recall that ∆̃0 = 0. Then we can unwind the above recursion form to obtain
∆̃t ≤ 4G2
N t∑ τ=1
{ t∏
i=τ+1
exp ( 2ηiL+ η 2 iL
2 )}
uτ ≤ 4G2
N t∑ τ=1 exp
( 3L
t∑ i=τ+1 ηi
) uτ ,
where we have used ηt ≤ 1/L. It follows immediately from the convexity that
Eξ[T ] [ ‖w̄T − w̄′T ‖2 ] ≤ ∑T t=1 Eξ[t] [ ‖wt − w′t‖2 ] T ≤ 4G 2 N T∑ t=1 exp ( 3L T∑ τ=t+1 ητ ) ut,
which is the second desired bound. The proof is completed.
With Lemma 10 in place, we proceed to prove the main result in Corollary 3.
Proof of Corollary 3. From Lemma 10 we know that ASGD-w with smooth non-convex loss has mean(-square)-uniform stability with parameters
γm,N = 2G
N T∑ t=1 exp
( L
T∑ τ=t+1 ητ
) ηt, γm2,N = 4G2
N T∑ t=1 exp
( 3L
T∑ τ=t+1 ητ
) ut.
The desired results then follow immediately via invoking Theorem 1 with α = 1/2.
Algorithm 3: SGD via Without-Replacement Sampling (ASGD-wo)
Input : Data set S = {zi}i∈[N ] i.i.d.∼ DN , step-sizes {ηt}t≥1, #iterations T , initialization w0. Output: w̄T = 1T ∑ t∈[T ] wt. for t = 1, 2, ..., T do Uniformly randomly sample an index ξt ∈ [N ] with or without replacement; Compute wt = ΠW (wt−1 − ηt∇w`(wt−1; zξt)). end

heading: D AUGMENTED RESULTS FOR SGD UNDER WITHOUT-REPLACEMENT SAMPLING
text: In this section, we further consider applying our main results in Theorem 1 to the variant of SGD under without-replacement sampling (ASGD-wo), as is outlined in Algorithm 3. For the sake of simplicity and readability, we only consider single-epoch processing with T ≤ 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 ≤ rN for some integer r ≥ 1, and to convex or non-convex smooth loss functions are more or less straightforward and thus are omit.
We start by establishing the following lemma on the mean(-square)-uniform stability of ASGD-wo which can be easily proved based on the result from Bassily et al. (2020, Lemma 3.1). Lemma 11. Suppose that the loss function is `(·; ·) is convex andG-Lipschitz with respect to its first argument. Consider T ≤ N . Then ASGD-wo has mean-uniform stability such that
sup S . =S′
EASGD-wo [‖ASGD-wo(S)−ASGD-wo(S′)‖] ≤ 2G
N T∑ t0=1 √√√√ T∑ t=t0 η2t ,
and has mean-square-uniform stability such that
sup S . =S′
EASGD-wo [ ‖ASGD-wo(S)−ASGD-wo(S′)‖2 ] ≤ 4G 2
N T∑ t0=1 T∑ t=t0 η2t .
Proof. Let w̄T (S, ξ) and w̄T (S′, ξ) respectively be the output generated over S = {zi}i∈[N ] and S′ = {z′i}i∈[N ] by ASGD-wo via sample path ξ = {ξt}t∈[T ]. Recall that T ≤ N . Let us define a hitting time variable t0 = inf{t : zξt 6= z′ξt}. Since S . = S′, the uniform randomness of ξt implies that P (t0 = j) = 1
N , j ∈ [N ].
Given t ∈ [T ], it follows from Bassily et al. (2020, Lemma 3.1) that
‖wt − w′t‖2 ≤ 4G2 t∑
τ=t0
η2τ .
Then we have
Eξ[t] [ ‖wt − w′t‖2 ] ≤ 4G 2
N t∑ t0=1 t∑ τ=t0 η2τ ≤ 4G2 N T∑ t0=1 T∑ τ=t0 η2τ .
The convexity of squared Euclidean norm leads to
Eξ[T ] [ ‖w̄T − w̄′T ‖2 ] ≤ ∑T t=1 Eξ[t] [ ‖wt − w′t‖2 ] T ≤ 4G 2 N T∑ t0=1 T∑ t=t0 η2t .
Similarly we can show
Eξ[T ] [‖w̄T − w̄ ′ T ‖] ≤
2G
N T∑ t0=1 √√√√ T∑ t=t0 η2t .
The proof is completed.
The following result is a direct consequence of Theorem 1 when invoking Algorithm 1 to ASGD-wo with non-smooth convex loss. Corollary 5. Suppose that the loss function is `(·; ·) 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 ASGD-wo with T ≤ N . Then for any δ ∈ (0, 1) and K ≥ 2 log(4δ ), with probability at least 1 − δ over the randomness of S and {ASGD-wo,k}k∈[K], the output of ASGD-wo satisfies
|R(ASGD-wo,k∗(Sk∗))−RS(ASGD-wo,k∗(Sk∗))|
.G2 √√√√ 1 N T∑ t0=1 T∑ t=t0 η2t + G2 N T∑ t0=1 √√√√ T∑ t=t0 η2t +M √ log(K/δ) N .
Proof. From Lemma 11 we know thatASGD-wo has mean(-square)-uniform stability with parameters
γm,N = 2G
N T∑ t0=1 √√√√ T∑ t=t0 η2t , γm2,N = 4G2 N T∑ t0=1 T∑ t=t0 η2t .
The results then follow immediately via invoking Theorem 1 with α = 1/2.
Remark 9. Specially for constant learning rates ηt ≡ η, Corollary 5 admits a high probability generalization bound of scale O ( ηT√ N + η T √ T N + √ log(1/δ) N ) . For general time varying learning
rates, our bound in Corollary 5 still holds with high probability. For example, when ηt ∝ 1t , the generalization bound scales as O (√
log(T ) N + √ T N +
√ log(1/δ)
N
) with high probability.

Review summaries:
The paper considers the problem of showing tight generalization bounds for randomized uniformly stable algorithms. The key contributions are the following:  1. The paper uses the framework of confidence-boosting to develop a generic procedure for amplifying the success probability in the generalization bound for a uniformly stable algorithm.  2. The paper then instantiates this bound for the important case of SGD, obtaining generalization bounds that hold in step sizes regime not covered by previous work.  3. Finally, the paper shows that though the framework is developed for randomized algorithms it obtains tighter bounds for deterministic algorithms as well.

This paper establishes near-optimal high probability bound for randomized algorithms with on-average uniform stability. To this end, the authors use a confidence-boosting technique via a subbaging process. The authors then apply the derived generalization bound to SGD and the deterministic uniformly stable algorithm. The results reveal that their bounds improve the results of SGD in (Hardt et al., 2016) and the results in (Bousquet et al,. 2020) up to a $\log (N)$ term.

 This paper derives near-optimal high probability generalization bounds for randomized learning algorithms. To be specific, the authors establish an improved high probability generalization error bounds over the randomness of data and algorithm via confidence boosting method. The main novelty is they establish the in-expectation first moment generalization bound with mean (square) uniform stability for the randomized algorithm and then use subbagging technique to obtain the high-confidence bounds. In particular, their results can handle time-varying stepsize cases when applied to SGD.  The ideas are motivated by the confidence-boosting/bagging ideas in the literature.