$L_2$-Uniform Stability of Randomized Learning Algorithms: Sharper Generalization Bounds and Confidence Boosting
Authors: Xiaotong Yuan
Ping Li
Venue: NeurIPS 2023 poster (2023)
Keywords: Uniform stability
Randomized learning algorithms
Confidence boosting
Generalization bounds
Stochastic gradient methods
TL;DR: We introduce a novel concept of $L_2$-uniform stability and prove a set of sharper exponential generalization bounds for randomized learning algorithms using confidence boosting techniques.

Abstract: Exponential generalization bounds with near-optimal rates have recently been established for uniformly stable algorithms~\citep{feldman2019high,bousquet2020sharper}. We seek to extend these best known high probability bounds from deterministic learning algorithms to the regime of randomized learning. One simple approach for achieving this goal is to define the stability for the expectation over the algorithm's randomness, which may result in sharper parameter but only leads to guarantees regarding the on-average generalization error. Another natural option is to consider the stability conditioned on the algorithm's randomness, which is way more stringent but may lead to generalization with high probability jointly over the randomness of sample and algorithm. The present paper addresses such a tension between these two alternatives and makes progress towards relaxing it inside a classic framework of confidence-boosting. To this end, we first introduce a novel concept of $L_2$-uniform stability that holds uniformly over data but in second-moment over the algorithm's randomness. Then as a core contribution of this work, we prove a strong exponential bound on the first-moment of generalization error under the notion of $L_2$-uniform stability. As an interesting consequence of the bound, we show that a bagging-based meta algorithm leads to near-optimal generalization with high probability jointly over the randomness of data and algorithm. We further substantialize these generic results to stochastic gradient descent (SGD) to derive sharper exponential bounds for convex or non-convex optimization with natural time-decaying learning rates, which have not been possible to prove with the existing stability-based generalization guarantees.

L2-Uniform Stability of Randomized Learning Algorithms: Sharper Generalization Bounds and Confidence Boosting
Xiao-Tong Yuan
Ping Li VecML Inc. www vecml. com Bellevue, WA 98004, USA
School of Intelligence Science and Technology Nanjing University Suzhou, 215163, China
pingl1960gmiil.cmm
xtyuan1980@gmail.c com
Abstract
Exponential generalization bounds with near-optimal rates have recently been established for uniformly stable algorithms (Feldman and Vondrák, 2019; Bousquet et al., 2020). We seek to extend these best known high probability bounds from deterministic learning algorithms to the regime of randomized learning. One simple approach for achieving this goal is to define the stability for the expectation over the algorithm's 's randomness, which may result in sharper parameter but only leads guarantees regarding the on-average generalization error. Another natural option is to consider the stability conditioned on the algorithm's randomness, which is way more stringent but may lead generalization with high probability jointly over the randomness of sample and algorithm. The present paper addresses such tension between these two alternatives and makes progress towards relaxing it inside a classic framework of seffidence-boosting To this end, we first introduce a novel concept of Lz-uniform stability that holds uniformly over data but second- moment over the algorithm's 's randomness. Then we prove strong exponential bound on the first-moment of generalization error under the notion of L22-uniform stability. As an interesting consequence of the bound, we show that a bagging- meta algorithm leads to near-optimal gener- alization with high probability jointly over the randomness of data and algorithm. We further substantialize these generic results to stochastic gradient descent (SGD) to derive sharper exponential bounds for convex or non-convex optimization with natural time- decaying learning rates, which have not been possible to prove with the existing stability-basee based generalization guarantees.
core contribution of this work,
Introduction
In many statistical learning problems,
interested in designing randomized algorithm A N R + W that maps training data sample S = {2.) E z with an algorithm's 's random parameter & E R to a model A(S.E) E W. Here Z and R are some measurable sets, and W is a closed subset of Euclidean space. The ultimate goal is to find suitable algorithm such that the following population risk evaluated at the model should be as small as possible:
R R(A(S,)) E)) == Ez((A(SS 2)},
where 7 E 2 and (:W> x 2 ~ + is non-negative bounded loss function whose value f(w:; 2) measures the loss evaluated with parameter w. generally the case that the underlying data distribution is unknown, and in this case the data points Z, are usually assumed to be independent.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Then, a natural alternative measurement that mimics the computationally intractable population risk the empirical risk given by
Rs(A(S) == -= 1
N Σ (AA(S.))
The bound on the difference between the population and empirical risks is of central interest in understanding the generalization performance of a learning algorithm. In particular, we hope to derive a suitable law of large numbers, i.e., a sample size vanishing rate by such that the generalization bound [A(S, E)) R(A(S, (()) E)) X by holds with high probability over the randomness of S and hopefully the randomness of & as well. Let Rt == min R(w) be the optimal value of the population risk. Conditioned on S, suppose that A(S,E) is an almost minimizer of the empirical risk Rs such that Rs (s(A(S,E) ()) - minwew Rs(w) I E, then the generalization bound immediately implies an excess risk bound R()(S.E)) R R bN + VN + E based on the standard risk decomposition and Hoeffding's 's inequality. Therefore, generalization guarantees also play a crucial role in understanding the stochastic optimization performance of learning algorithm.
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 cetenniionnindendddenn generalization bounds for deter- ministic learning algorithms (Mukherjee et al., 2006; Shalev-Shwarts 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 and Vondrák, 2018, 2019; Bousquet et al., 2020; Klochkov and Zhivotovskiy, 2021) which is independent to the underlying distribution of data. For randomized algorithms, the definition of uniform stability can be extended in two natural ways by respectively considering 1) the stability averaged over the algorithm's 's randomness (Hardt al., 2016) and 2) the stability conditioned on the algorithm's 's randomness (Feldman and Vondrák, 2019). The former simpler show but typically leads on-average generalization bounds, while the latter is rela- tively more stringent but may yield deviation bounds given that the conditional stability holds with high probability over the algorithm's 's randomness. Between these two extreme cases, however, the generalization behavior of randomized learning algorithm still remains largely under explored.
To address the above mentioned theoretical gap between the current lines of results, we explore the opportunities of deriving exponential generalization bounds for randomized learning algorithmss beyond the notions of on-average stability and conditional 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 2 1 with learning rate π) 0:
Wi := 1lw (w,-1
T/t V. (: Z,,))
(I)
where i, E [N] is random index of data under with or without replacement sampling, and TT is the Euclidean projection operator associated with W. The in-expectation generalization of SGD has been studied under on-average stability (Hardt et al., 2016; 6; Zhou et al., 2022; Lei and Ying, 2020), while the exponential bounds have recently been established given that the stability holds with high probability over the sampling path of SGD (Feldman and Vondrák, 2019; Bassily et al., 2020).
1.1 Prior results
Let us start by briefly reviewing some sfate-of-the-art exponential generalization bounds under the notion of uniform stability and its randomized variants. We denote by S = $ if a pair of data sets S and is differ in a single element. A randomized learning algorithm A is said to have on-average "N uniform stability (Elisseeff et al., 2005) if satisfies the following uniform bound:
Eg ((A((S))): 2) - ((A(S))): ((A()S:):22)(((((SS)))))) < YNN
sup 5=,,ZZZ
This definition is equivalent to the concept of uniform stability defined for the expectation of loss Ee[e(A(S, {); 2).. Suppose that the loss function is bounded in the interval [0. MM. Then essentially it has been shown in Feldman and Vondrák (2019) that for any 5 E (0, 1). with probability at least
1 8 over S, the on-average generalization error is upper bounded by
N 8
log (1/8)
[Eg [R(A(S,)) E)) Rs(A(S,E)) S YN log(NN) (N) log
+
M
(3)
N

---

Bousquet et al. (2020) later derived slightly improved exponential bound that implies
[ (R(A(S)E) - (s((() & YN (og(())log) log (1) + My
log (1/0)
These bounds are near-tight (up to logarithmic factors) in the sense of an (1w log (1) + log
N
lower deviation bound on sum of random functions with "N-uuiform stability (Bousquet et al., 2020, Proposition 9). Concerning the excess risk bound, Klochkov and Zhivotovskiy (2021) essentially derived the following result using the sample-spliting techniques of Bousquet et al. (2020):
(M + B) log
BEg [R(A(S,E)) R S opt [p[ + 7N log log(N) log
(5)
N
where Aap :- Bg [s(AAS)))) - min Rs(w) represents the in-expectation empirical risk sub- optimality, and B is the constant of the generalized Bernstein condition (Koltchinskii, 2006). While sharp in the dependence generalization and risk bounds lies in that these eroobbrobybylity results only hold expectation with respect to ç, the internal randomness of algorithm.
sample size,
common limitation of the above uniform stability implicd
Alternatively, consider that has "N -Nnuuiffomm stability with probability at least 1 8' for some 8' E (0, 1) over the random draw of E, i.e.,
P
((A(S) 2) - SE
sup
S 7N
2 1 21-8 8'.
(6)
Suppose that the randomness of A is independent of the training set S. Then the bound of Bousquet et al. (2020) naturally implies that with probability at least 1 - 8 8' over S and &.
log (1/6)
(((((SE)) - (s(A(S S Tv ()) log
MY
This is by far the best known generalization bound of randomized stable algorithms that hold with high probability jointly over the randomness of data and algorithm. The result, however, relies heavily the high-probabillity uniform stability as expressed in (6). For the SGD recursion (1) YN with fixed learning rate n 17. it is possible show that YN S TVT + aT and 0' = N exx((-9) N)
NN
in (6) (Bassily et al., 2020). For SGD with time decaying learning rates, which has been widely studied in theory (Harvey al., 2019; Rakhlin 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 (6) is still valid for 7N and 8' of interest. Madden et al. (2020) indeed have established a high-probability uniform stability bound for minibatch SGD with learning rates nt S NE. However, such fairly conservative choice of learning rates tends to impair the empirical minimization performance of SGD and thus is of limited interest from the perspective of risk minimization.
1.
More specially for randomized learning methods such as bagging (Breiman, 1996) and SGD, the randomness of algorithm can be precisely characterized by a vector of i.i.d. parameters & {f1,..., iz} which are independent on data S. In such cases, assume additionally that A(S, {) has uniform stability with respect to conditioned on S, i.e., sup (((AS,)) {)) - (AASS, E) s pr- Then the following exponential bound has been derived by Elisseeff al. (2005):
1 11 NYN xTPr)) (1+N (*+ VNN
R(A(S)) Rs(A(S)) YN tw++
log
(8)
Provided that yN S and PT S J. the above bound shows that the generalization bound scales as 0 / ) with high probability. However, the rate of the above bound is sub-optimal and will
show no guarantee convergence if 7N 2 JN and/or PT 2 AT As example, for non-convex
SGD with learning rate 7) = = it can be shown that 7N 2
and pr scales as large as O()).
Open problem. So far, it still remains open if the exponential generalization bounds for deterministic uniformly stable algorithms might be extended to randomized learning algorithms under the variants of uniform stability tighter than the on-average version (2) but less restrictive than the bigb-brobability
3

---

version (6). Particularly, we are interested in the following notion of Lg-uniform stability (as formally introduced in Definition 1) with parameter Ni,
sup 2
S '.
which represents a second-momen variant of the uniform stability for randomized learning algorithms. For example, as we will shortly show in Section 4 that SGD with practical time-decaying learning rates has Ln-uniform stability with favorable parameters. The main goal of the present work is to derive sharper exponential generalization bounds for randomized learning algorithms under the notion of Ln-uniform stability.
1.2 Overview of our contribution
The fundamental contribution of this work is near-optimal first-moment generalization error bound for Lu-uniformly stable algorithms, which is summarized Theorem and highlighted below:
B& (IR(A(S, Rs (A(S,)))) & N4 (og((N) log { g )
log (1/6) N
+MV
While our first first-moment bound above has an identical convergence rate to that of the on-average bound in (4), the former is stronger in the sense that the expectation is taken outside the generalization gap and thus implies the latter where the expectation is taken inside. The key ingredients of our analysis set of fine- fine-grained concentration inequalities for randomized functions (Proposition 1) and sums of randomized functions (Proposition 2), which respectively generalize the classic bounded-differene inequalities and prior result of Bousquet al. (2020) under the considered Lz-uniform bounded difference conditions. These generalized concentration inequalities and their proof arguments are novel to our knowledge and should be of independent interests in analyzing randomized functions.
As an important consequence of our main result, we reveal that a bagging-based meta procedure (see Algorithm 1) can be used to boost the confidence of generalization for Lz-uniformly stable algorithms. More specifically, in the presented bagging procedure we independently run a randomized algorithm A multiple K times over fraction of the training set to obtain K solutions. Then we evaluate the validation error of these candidate solutions over a holdout training subset, and output the solution that has the smallest training- validdtion gap. Our result in Theorem 2 shows that for any confidence level E (0. 1), setting K x log(3 (3) yields a near-optimal generalization bound for the selected solution that holds with high probability jointly over the randomness of data and algorithm.
We have substantialized our results 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 shows that when invoked to SGD with smooth convex loss and learning rates f/- = O 7
the generalization bound of the output of Algorithm I may scale as O( (N) log (t) V
(og(T) /T
N
( in-expectation bound of smooth convex SGD (Hardt al., 2016), our To compare with the O bound above for the boosted SGD is comparable in convergence rate while it holds with high probability jointly over the randomness of data and sampling path.
2
L LzUUniform Stability and Generalization
2.1 Notation and definitions
Let us introduce some notation to be used in our analysis. We abbreviate [M] := (1...., N). Recall that S {Z,} hej is set of i...d. training data. Denote by S' [Z]Te[N] an independent copy
of 5 and we write 5(i) = [Z1- .... Z;-1, 1, Z!, Z,41; Z }. For a real-valued random variable Y, its norm for q 2 1 is given by ||l,, (B[[>]9)) 2/4 By definition it can be verified that Vig 2 2,
|| (B] 2/4 = (Bll 2/4 = =|| 1l./2-
(10)
Let h N + R be some measurable function and consider the random variable h(S) h(Z,,... ZN). For h(S) and any index set I S [N], we define the following abbreviations:
h(St)= == E (h(S) Si], (Sr] = (E [I((S)1 S,)) /9

---

We say function f to be G-Lipschitz continuous over W if [f(w) f(m) - Gl|l أاا for all
w, E W. and is Lmsohoth ( - S L E x || For a pair of functions f. f 2 we use f S f" (or J" ž f') to denote f S cf' for some universal constant e > 0.
In the following definition, we formally introduce the concept of L---nnformm stability for randomized learning algorithms to be investigated in this work.
Definition 1 (L2- -n--Unifomm stability of randomized learning algorithms). We say randomized learning algorithm A IN x R +
W to have 12-uniform stability with parameter V22,N 2 0 if
sup BE (E(AA(S,)) - ((A(S (()()))))))))) 9,2,,2
S <
Remark 1. By definition the Lz-uniform stability has a second-momens dependence on the internal randommess of algorithm conditioned on data, while it is invariant to the data distribution. This justifies the name of such a notion of mixed algorithmic stability.
Remark 2. On one hand, by Jensen's 's inequality the L2-uniform stability implies the on-average uniform stability defined in (2). On the other hand, the second-order form of Lz-uniform stability is by defimition weaker than the ligh-probability uniform stability in (6). If the algorithm's 's randomness É can be expressed as set of i.i.d. random bits, then the Le- Le-uniform stability is also weaker than the conditional uniform stability conditioned on data S (Elisseeff et al., 2005).
Throughout this paper, we assume for simplicity that the output models A(S(), .)) and A(S,E) share the same internal random bit & which is invariant data. With similar analysis techniques, it is indeed possible to extend Definition and our main results to the general setting where the randomness of algorithm is allowed to be dependent on data, such as in posterior sampling for Bayesian learning.
2.2 Concentration inequalities for randomized functions
We begin by establishing in the following result a group of first- and second-order concentration inequalities (in moments) for randomized functions of independent random variables.
Proposition 1. Let 1 Zz,,.. ZN} } be set of independent random variables valued in Z and & be random variable valued in R. Let g 2N R + R be a measurable function that satisfies the following Lz-bounded differreece condition:
,s)) 53.
sup EEg 9
Then for any q 2 2.
E [l)(S, Es (0(S, S <33 /
(11)
and
Eg ((((,))- Es -ss (o(s
< 9
68NN39..
(12)
Proof in sketch. Let consider h(S) E& - - E)]]]- The given Lo-bounded- difference condition implies that h(S) has bounded-differrnce property. Then the desired first-order bound in (11) can be obtained by respectively invoking a moment Efron-Stein inequality (Boucheron et al., 2005, Theorem 2) to upper bound (S) - (()(l)) and a slightly modified Efron-Stein in- equality to bound the mean B[ To prove the second-order concentration bound, we consider the function h((()= == Egg (o( IE (g( (S, {)}] which can be shown to be weakly self-bounding (see Definition 2) under the L2- Mhounded-differemee
condition. Then the desired bound (12) can be derived by applying the upper tail bound of Boucheron et al. (2005, Theorem 6.19) and lower tail bound of Klochkov and Zhivotovskiy (2021, Proposition 3.1) for weakly saff-boundig functions. See Appendix A.2 for a detailed proof of this result.
The moment bound in (11) extends the McDiarmid's (bounded difference) inequality (McDiarmid et al., 1989) to randomized functions with the Lg-bounded -ouudedddifferecce property. The second-order concentration bound in (12) is crucial for proving the moment bound of sums in Proposition 2, as can be used to sharply control some second-order components involved in the arguments. These generic inequalities are expected to be of independent interests for understanding the first/sseonn-oorer concentration behavior of randomized functions.
5

---

2.3 A moment inequality for sums of randomized functions
As key intermediate result, we further establish in the following proposition a moment concentration inequality for sums of randomized functions that satisfy the L2- s--bounded-diffen difffereffceeeee condition. This result extends the moment bound for sums of functions (Bousquet al., 2020, Theorem 4) sums of randomized functions.
Proposition 2. Let S = Zz,....... I be set of independent random variables valued in 2 and & be a random variable valued in R. Let 91, .... 9N be a set of m that satisfy the following conditions for any [N]:
2 N x xR + R
E (g)( 5\ Z = 0 and (S 1 Z, S M, almost surely;
9x(S.E) )) has the following L2 ba-boouned-ddiffeennee property with respect to all variables in except 74 Le., Vj +
sup Be (a(5.)) a000) $ 5
Then for all q 2 2.
N
Be
Σ 9 (5
s 3M /3Ng 3-N N N18g.
Proof in sketch. The main idea is inspired by the sample-splitingg arguments of Feldman and Vondrák (2019); Bousquet et al. (2020), with some new ingredients developed to handle the first-moment operator taken over the internal randomness of functions. Here we just highlight a fundamental differ- ence, which arises from using a newly developed moment inequality (Lemma 9) for bounding the sums of conditionally independent randomized functions inside each individual data splits. Different from the version of parrinniewicz--yygmme al. (2020), our new bound in Lemma 9 relies on some second-order (over the function's 's random- ness) components which might be tightly bounded by the second-order concentration inequality in Proposition I. A full proof is provided in Appendix A.3.
inequality used in the original analysis of Bousquet
Remark 3. For sums of deterministic functions, our result in Proposition 2 reduces to the existing moment bound of Bousquet et al. (2020, Theorem 4) which is known to be near-tight up to logarithmic factors. We comment in passing that the tightness analysis of Bousquet et al. (2020, Proposition 9) for deterministic functions can be more or less straightforvardly extended to randomized functions. Remark 4. The bound of Proposition 2 would still be valid when the bounded-loss condition (S, Z E]] S M is relaxed to certain sub-Gu Gaussian or sub-exponential stochastic versions.
2.4 Main result on generalization bound
Consequently from Proposition 2, we can now establish our main result on the generalization bound of Lz-uniformly stable randomized learning algorithms.
Theorem 1. Let A 2 x R ~ W be a randomized learning algorithm that has Lz-uniform stability with parameter NN,,NN Assume that the loss function & is valued in [0, M). Then for any 5 E (0, 1), the following bound holds with probability at least 1 8 over the draw of S:
Eg [IR(A(SEE) Rs(A(S,,)) & ", (og(N) log (:) + M
log (1/8)
N
Proof. See Appendix A.4 for proof of this result.
Remark 5. The first-moment bound in Theorem naturally implies the on-average bound in (4) with an identical rate of convergence, though the former obtained under the relatively stronger notion of L2 Lz-uniform stability. As we will see shortly that the L2 stability can indeed be fulfilled by the popularly upplied SGD algorithm and thus Theorem 1 of practical importance for showcusing sharper generalization performance of SGD. When A is deterministic, our bound reduces to the neur-optimal (up logarithmic factors on sample size and failure tail) generalization bound for uniformly stable algorithms (Bousquet et al,, 2020).

---

Algorithm 1: Confidence-Boosting for Randomized Learning Algorithms
Input :Randomized learning algorithm A, data set S = (2i)eeN) μ E (0,1) and E zt.
Output: A(5, Ex-).
Uniformly divide S into two disjoint subsets Si and Sn with |S (1 HnN, [S21 uN.
for = 1,, K do
Estimate A(Si, Ex) an output of A over the subset S with random bit &x.
end
Select the random bit k* according to k* = arg [ej]] (A,(( Rs, ((51),))))
In view of the standard risk decomposition, the following excess risk tail bound can be readily obtained via applying Theorem and Hoeffding's inequality:
1 +
log (1/8)
Eg (R(A(SSE)) RR Dopt + N,N, log( log
MV
(13)
Here recall that Am == EEg (Rs(A()) risk minimization. Since the excess risk is by definition non-negative, the above bound can also be obtained under the weaker notion of on-average uniform stability (2) via applying (4). In this sense, the first-moment generalization eтror bound in Theorem 1 is substantially more challenging derive than the excess risk bound. Additionally, under the generalized Bernstein condition (Koltchinskii, 2006), the risk bound (13) can be readily improved to (5) by directly applying the corresponding deviation optimal risk bound of Klochkov and Zhivotovskiy (2021) to the on-average loss function under on-average uniform stability condition.
min Rs(w) is the sub-optimality of empirical
Eg (&(L(A(S,E); )
3 Boosting the Confidence of Generalization
The confidence-boosting technique of Schapire (1990) a classic meta approach that allows one to boost the dependence of a learning algorithm on the failure probability 5 from 1/8 to log(1/8), at certain cost of computational complexity. In this section, we show an implication of our first-moment bound in Theorem for achieving high-pue high-probbbility generalization jointly over the randomness of data and algorithm, inside natural framework of sonfidence-bosstngg
3.1 Confidence boosting via bagging
Given a randomized learning algorithm A, we propose to study a bagging based seriidence-boosttng procedure outlined in Algorithm 1. In this meta procedure, independently run the algorithm A for K times over S1, a fraction of the training set, to obtain K different candidate solutions {A(S), [ ke(K) Then holdout training subset S2, and cherry pick A(Si, Eu-) that has the smallest gap between the training error and validation error, i.e., h'' arg min Ris, (A(SI, - Rs, (A(S). Ex))]. Particularly, consider that the internal randomness of A arises from random sampling with replacement of data points, such as SGD under with-replacement sampling. Then in this setting, the procedure can be regarded as a version of bagging (Breiman, 1996) with a greedy model ensemble scheme, which is invoked to the deterministic counterpart of A with fixed random bits (e.g., SGD with identity permutation) over the training subset Sj.
evaluate the validation error of these candidate solutions over the
3.2 Jointly exponential bounds
The following theorem is our main result about the generalization error bound the output A(Si, Ck-) that holds with high probability over the entire training set and the random seeds (Ex [Es]E]]]]
Theorem 2. Suppose that a randomized learning algorithm A N R. W has Lz-uniform stability with parameter "I2,N- Assume that the loss function & is valued in [0, M). Then for any least 1 8 over the randomness of S and (EKTEEjK)
8 E (0, 1) and K 2 2 log( (3),, ), with probability at the output of Algorithm satisfies
(R(A(S), Rs( Rs(A(SI, ))1 S (22,(1-4) log( log(N))lo log (1)
M
log (K/8)
Vp(1 - P)
N
7

---

Algorithm 2: Asco-v: SGD under With-Replacement Sampling
Input :aata set = (ZN) step-sizes (121, #iterations T, initialization wig-
Output : W2 = T ΣiE(Ty W/.
for [ 1,2,...... ...,, do
Uniformly randomly sample an index it E [N] with replacement; Compute = IIw (w--1 N/ V (w: Z2,).
end
Proof in sketch. Based on Theorem 1, we first prove an intermediate result to show that the mini- mal generalization error of the K outputs satisfies [in (((((S),, Rs, (A(Si, Ek)) S
(1,((1=)) log(N) log (3) +
M
log(1/6) N
provided that K 2 log( Next we show that the
Va(1-R)
used greedy model selection strategy guarantees that the selected (()) mimics the generalization behavior of that best performer among the candidates, with a slightly expanded log( (k/ō) factor representing the overhead of simultaneously bounding the generalization performance of K different candidate solutions over the holdout validation set. Finally the desired bound follows from the union probability argument. See Appendix B.1 for its full proof.
D
The bound in Theorem 2 holds with high probability jointly over the randonness of sample and algorithm. Different from the bound in (7) that requires high probability uniform stability, Theorem 2 is valid under substantially milder notion of Lz-uniform stability, though at the cost of multiple running of algorithm for confidence boosting. Compared to the bound in (8) that requires certuin conditional uniform stability over the random bits of algorithm, our bound has sharper dependence on the uniform stability parameter yet under a weaker notion of stability.
Remark 6.
Remark 7. Regarding the scale of the factor 1/ 1/V/(1 -
p)) the bound of Theorem 2, if setting 0.01 (i.e., 99% of S are used as for training), then the factor is around 10.05.
Concerning the excess risk of Algorithm 1, we consider a slightly modified output A(S1, Ek-) such that k- arg min Rs, (A(S1, (((,,x)). (x)). Then based on the in-expectation risk bound (13), we can derive the following excess risk bound under the conditions of Theorem using similar arguments:
R(A(S1,Ex.) R S Aopt + 12.(1=uNN log((V) log +
M
log (K/5) N
(14)
VM(1
1)
Again, the above risk bound is still valid under the weaker notion of on-average uniform stability (2).
4 Implications for SGD
This section devoted to demonstrating the implications Theorem and Theorem 2 for the widely used SGD algorithm and its confidence-booster versions as well. We focus variant of SGD under with-replaacmment sampling as outlined in Algorithm 2, which we call ASaD In what follows, substantialize {ie frejj the sample path of Asao., K independent copies of when implemented with bagging as shown in Algorithm 1. Our results can also be extended the without-replacemmnt variant of SGD and the corresponding results provided in Appendix D for the sake of completeness.
given data set, and {Ex [((K] the
4.1 Convex optimization with smooth loss
We first present the following lemma that establishes the Lz-uniform stability of AscD-v with convex and smooth loss functions, such as logistic loss. See Appendix C.2 for its proof.
Lemma 1. Suppose that the loss function E(:; .) is convex, G-Lipschitz and L-smooth with respect to its first argument. Assume that Ttt S 2/T. T/ for all 2 Then Ascr has Lz-uniform stability with parameter
T N
T
2
N2 = 262
10
N2
Σ f=l
11
t=1
8

---

Given Lemma 1, we can apply Theorem 1 and Theorem 2 to immediately obtain the following generalization result for AsaD-u and its confidence-booster version with smooth and convex losses. Corollary 1. Suppose that the loss function ((:;-) E [0, M] is convex, G-Lipschitz and L-smooth with respect its first argument. Then for any (0, 1), it holds with probability least 1 ò over the randomness of S that [ (S {))
Rs (Sssss---o ())I S
log)(NV) log (6)
T
2
log(1/6) N
Σ
2
+
Σ
+ MM
N
N
Moreover, consider Algorithm specified to Asco-w with learning rate tt S 2 and K x log()). Then with probability at least ò over the randomness of S and {Ek)kE]K] holds that (R(AAccou((S, Ex-)) (sscA Ex=
Golo((NV) (og(N))ogg)) log (5)
T
T Σ 1
M
log(1/8)
Σ
n +
(1 N)N
(1 22
Vp(1
p)
N
Remark 8. For the conventional choice of tht = LVf the high-probability (w.r.. data) general- ization bounds in Corollary for SGD and its confidence boosted version are roughly of scale
O( Iog(N) log (t)
log(T) N
) which matches the corresponding O T N
in-expectation bound
of SGD with smooth and convex losses (Hardt 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 of (modified) Algorithm 1 as direct consequence the generic bound (14) to AsED-v with convex and smooth losses:
((1.o--(S1..fx)) - R² SG2 log (N) (N) log
th Σ t=1
+ (1 (1- 22
Σ
(1
H)N
M
log(1 (g/()))
D² W*)
+ GO Ei=
VI(1 - 11)
N
Et=1
where W := Argmin R(w) and D(w, W*) = min w|l w With learning rate =
T.Ti. the right hand side of the above roughly scales as V log (1) leg(T)
2
/T
log(T) vT
which matches the prior high-probability excess risk bounds of SGD with convex losses (Harvey et al., 2019, Remark 3.7).
4.2 Convex optimization with non-smooth loss
Now turn to study the case where the loss is convex but not necessarily smooth, such as the hinge loss and absolute loss. We first establish the following lemma about the Lz-uniform stability parameter of Asco-v in the considered setting. See Appendix C.3 for its proof.
Lemma Suppose that the loss function E(::)) convex and G-Lipschitz with respect to its first argument. Then A so has T-z-uniforo stability with parameter
T
32
N2,N G2
40
Σ
1/t
N2
With Lemma 2 in place, readily apply Theorem and Theorem 2 to establish the following corollary about the generalization bounds of AgeD-v and its iafidence-boosterd version with convex and non-smooth loss functions.
Corollary 2. Suppose that the loss function E(::-) E [0, M) is convex and G-Lipschitz with respect to its first argument. Then for any å E (0, 1), it holds with probability at least 1 1- ô over the randomness of S that Eg [[[(Asoo-(S.EE)
Rg ( (Ssss-sss E)DI x
G² (ogg(NN) log ())
T
log(1/8)
Σ
Th
n
+ M
N2

---

Moreover, consider Algorithm specified to Asco- with K x log 3). Then with probability at least 1 over S and (ERKK)) it holds that |R( RR(Ason-of (S 1x.xx))))))))
Rs(Ason (S Ex.
G (o) log (
Σ t=1
mh +
22
1
Σ
T
111
11 -
M
log(1/0)
N
1=1
Remark 9. For SGD with decaying learning rates 1/1
Corollary 2 admits high-probability
VNN'
generalization bounds of scale O ((log(N))o log (3) (3)
(og(T)
+ N3
1og(1/5)
With fixed rates
Y), Corollary 2 yields deviation bounds of scale (n log (VT f)+
log
N
which matches the near-optimal rate by Bassily et al. (2020, Theorem 3.3).
4.3 Non-convex optimization with smooth loss
We further study the performance of Algorithm for Ascn-u with smooth but not necessarily convex loss functions, such as normalized sigmoid loss (Mason et al., 1999). The following lemma estimates the T22uniform stability of AsaD-u in the considered setting. See Appendix C.4 for its proof.
Lemma 3. Suppose that the loss function ((:;-) is G-Lipschitz and L-smooth with respect its first argument. Consider 1b. S 1/L. Then Asco.u has L2-unifore stability with parameter
T
T
N2.N 2G2
exp
3L
Th
Ut:
N
1=1
7 7=1+1
where
--1
Ut == 1/2 + 2m
exp
L
17i
T/--
i=
Based on Lemma 3, we can invoke Theorem and Theorem 2 to show the following generalization result for Ascr.u and its confidence-boostee version with non-convex and smooth loss functions. Corollary Suppose that the loss function f(:: E [0. M) G-Lipschitz and L-smooth with respect to its first argument. Then for any ō (0, 1), it holds with probability at least 1 over the randomness of S that Eg []R[ [[((Asco- E)) Rs ((, X
T
log(1/6)
G2 (o) log
8
Σ exp Σ T=
ur M
where Ut = TÍ + 2Th D exp(L Lisr+1 M. for all 2 Moreover consider Algorithm 1 specified to Asar-w with T/, < 1 and K (log( Then with probability at least over and
[Ex]KE[K]. it holds that [R(Asoo-uS1,, (S1, Rs (Asco
G² Golog(NVlos log ( (
Σ exp L
Σ r=t+1
M
log (1/8)
ur
VM(1
11)
Remark 10. For the decaying learning rates th
Lut with arbitrary
I.
2 1,
the generalization
bounds in Corollary 3 are of scale O log(NN ) log (1)
V
(TVe log(T)
+
log(1/8)
For the constant
N
learning rates = TT. the bounds are of scale O log(N) log (t) 1oR(1/6)
N
Conclusion
In this paper, we have introduced novel concept of Le-uniform stability for randomized learning algorithms and proved a strong first-mone mesttmoment generalization bound that holds with high probability over training sample. Equipped with this result, we have further developed bagging based confidence- boosting procedure and shown that yields near-optimal generalization bounds with high confidence jointly over the randomness of sample and algorithm. The power of our theory has been demonstrated through an application to SGD with time-decaying learning rates, where sharper generalization bounds have been obtained for both convex and non-convex loss functions.
10

---

Acknowledgments and Disclosure of Funding
The authors sincerely thank the anonymous reviewers and area chairs for their insightful comments on this paper. The research was conducted while XTY worked for Nanjing University of Information Science and Technology and both authors worked for Baidu Cognitive Computing Lab. The work of XTY is also funded in part by the National Key Research and Development Program of China under Grant No. 2018AAA0100400 and in part by the Natural Science Foundation of China (NSFC) under Grant No. U21B2049, 61936005.
References
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-1 1288, Vancouver, Canada, 2019.
Raef Bassily, Vitaly Feldman, Cristóbal Guzmán, and Kunal Talwar. Stability of stochastic gradient descent nonsmooth convex losses. In Advances in Neural Information Processing Systems (NeurIPS), virtual, 2020.
Yoshua Bengio, Ian Goodfellow, and Aaron Courville. Deep learning, volume 1. MIT press Cambridge, MA, USA, 2017.
Stéphane Boucheron, Olivier Bousquet, Gábor Lugosi, and Pascal Massart. Moment inequalities for functions of independent random variables. The Annals of Probability. 33(2):114-660, 2005.
Olivier Bousquet and André Elisseeff. Stability and generalization. Mach. Learn. Res., 2:499-522 2002.
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.
Leo Breiman. Bagging predictors. Mach. Learn., 24(2):123-144 1996.
Peter Bühlmann. Bagging, boosting and ensemble methods. In Handbook of computational statistics, pages 985-1022, Springer, 2012.
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.
Yuan Shih Chow and Henry Teicher. Probability theory: independence, interchangeability, martin- gales. Springer Science & Business Media, 2003.
Luc Devroye and Terry J. Wagner. Distribution- free inequalities for the deleted and holdout error estimates. IEEE Trans. Inf. Theory, (5(2):202-200) 1979.
André Elisseeff, Theodoros Evgeniou, and Massimiliano Pontil. Stability of randomized learning algorithms. J. Mach. Learn. Res., 6:55-79, 2005.
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.
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.
Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: optimal rates in linear time. Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 439-449, Chicago, IL, 2020.
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.

---

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.
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, A7., 2019.
Matthew Holland. Robustness and scalability under heavy tails, without strong convexity. In Proceedings of the 24th International Conference Artificial Intelligence and Statistics (AISTATS), pages 865-873 Virtual Event, 2021.
Yegor Klochkov and Nikita Zhivotovskiy. Stability and deviation optimal risk bounds with con- vergence rate of o(1/n). In Advances in Neural Information Processing Systems (NeurIPS), pages 5065-5076, virtual, 2021.
Vladimir Koltchinskii. Local rademacher complexities and oracle inequalities in risk minimization. The Annals of Statistics, 34(6):2593-2656, 2006.
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.
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 1809-5819 Virtual Event, 2020.
Yunwen Lei and Yiming Ying. Sharper generalization bounds for learning with gradient- objective functions. In Proceedings of the 9th International Conference Learning Representa- tions (ICLR), Virtual Event, Austria, 2021.
Liam Madden, Emiliano DallAnese, and Stephen Becker. High probability convergence and uniform stability bounds for nonconvex stochastic gradient descent. arXiv preprint #rXiv:2006.05610 2020.
Llew Mason, Jonathan Baxter, Peter L. Bartlett, and Marcus Frean. Boosting algorithms as gradient descent. In Advances in Neural Information Processing Systems (NIPS), pages 512-518, Denver, CO, 1999.
Colin McDiarmid et al. On the method bounded differences. Surveys in Combinatorics, 141(1): 148-188, 1989.
Nishant Mehta. Fast rates with high probability in exp-concave statistical learning. Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS), pages 1085-1093, Fort Lauderdale, FL. 2017.
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.
Dheeraj Nagaraj. Prateck 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.
David W. Opitz and Richard Maclin. Popular ensemble methods: An empirical study. J. Artif. Intell. Res., 11:169-198, 1999.
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.
William Rogers and Terry J Wagner. A finite sample distribution-fre free performance bound for local discrimination rules. The Annals of Statistics, pages 506-514, 1978.
12

---

Robert E. Schapire. The strength of weak learnability. Mach. Learn., 5:197-227, 1990.
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.
Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Learnabllity, stability and uniform convergence. J. Mach. Learn. Res., 11: 11::2635-2777 2010.
2010.
Ohad Shamir. Without-replacemmet sampling for stochastic gradient methods. In Advances in Neural Information Processing Systems (NIPS), pages 46-54, Barcelona, Spain, 2016.
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 (ICMI.), pages 71-79, Atlanta, GA, 2013.
Giorgio Valentini and Thomas G. Dietterich. Low bias bagged support vector machines. Pro- ceedings the Twentieth International Conference (ICML), pages 752-759 Washington, DC, 2003.
V. N. Vapnik and A. Ya. Chervonenkis. Theory of Pattern Recognition [in Russian]. Nauka, 1974.
Xiao-Tong Yuan and Ping Li. Stability and risk bounds of iterative hard thresholding. IEEE Trans. Inf. Theory, 68(10))66336661, 2022.
Xiao-Tome Tong Yuan and Ping Li. Exponential generalization bounds with near-optimal rates for stable algorithms. In Proceedings of the Eleventh International Conference on Learning Representations (ICLR), Kigali, Rwanda, 2023.
Tong Zhang. Leave-one-out bounds for kernel methods. Neural Comput., 15()):197-11477 2003.
Yi Zhou, Yingbin Liang, and Huishuai Zhang. Understanding generalization error SGD in nonconvex optimization. Mach. Learn., 111(1):345-377 2022.
13


Reviews:
[{"review_id": "NIBjiP8Tqe", "reviewer": "Reviewer_3pL8", "summary": "A new notion of algorithmic stability is introduced for randomized algorithms, which is intermediate to previously studied notions and leads to new strong generalization bounds. The need for a new notion is justified due to known lower bounds under previously studied notions by related to on-average stability, and practical limitations of stronger notions like uniform stability with high probability when applied to SGD. A new intermediate L2-uniform stability is introduced with a goal to fill this gap, and generalization guarantees are obtained under this notion improving over on-average stability bounds. Also boosting is used to give high probability generalization error bounds. Remarkably, the stability of SGD is bounded under this new notion for convex and/or smooth loss functions and the stability constants are derived. ", "questions": "- How does $\\gamma_{L_2,N}$ compare to $\\gamma_N$ for SGD?\n- Line 75: Should it be $[0,M]$ instead of $(0,M]$?\n- Line 187: Typo: McDiamid’s", "limitations": "Limitations of results could be discussed in more detail. For example, in Remark 6, are there terms where the proposed bounds are worse than the in-expectation bounds of Hardt et al. 2016?", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper considers a novel and interesting notion of stability, and establishes strong generalization bounds for algorithms that are stable under the defined sense of stability.\n- High probability risk bounds are obtained via boosting.\n- The proposed notion of stability is shown to be satisfied for the popular SGD (stochastic gradient descent) algorithm when the loss function is convex and/or smooth.", "weaknesses": "- No lower bounds are provided, so tightness of the results is not clear. The upper bounds are tighter, but under a stronger assumption than previously studied in Bousquet et al. 2020.\n- The presentation of Section 4 could be improved. What are the novel insights in establishing the bounds on the L2-uniform stability parameters? For implications to SGD, it might be better to present/discuss the lemmas on the L2-uniform stability parameters in the main body, possibly replacing the corresponding corollaries obtained by combination with Theorem 2. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful review and appreciation of our work. \n\n> **Your comment:** No lower bounds are provided, so tightness of the results is not clear. \n> \n**Our response:** Per your comment, we plan to provide some additional analysis regarding tightness of our bounds in the next version. Since the main result of Theorem 1 is implied by the the moment bound for sums of randomized functions in Proposition 2, it is natural to ask if that latter bound can be improved in general. Inspired by the lower bound analysis of Bousquet et al. [2020, Proposition 9], we indeed believe that similar results and analysis could be extended to sum of randomized functions of Rademacher signs that satisfy the L2-bounded-difference property. A potential way to construt such randomized functions is to consider $g_i(S,\\xi)=MZ_i + \\frac{\\beta}{2}Z_i\\left(\\sum_{j\\neq i}Z_j + \\xi_1\\right)\\xi_2$ where $Z_i$, $\\xi_1$, $\\xi_2$ are all Rademacher signs. It can be verified that these functions have L2-bounded-difference property, and the arguments of Bousquet et al. [2020, Proposition 9] can be naturally adapted to the sum of $g_i(S,\\xi)$ to get the desired lower bound that matches the upper bound presented in Proposition 2.\n\n> **Your comment:** The presentation of Section 4 could be improved. What are the novel insights in establishing the bounds on the L2-uniform stability parameters? \n\n**Our response:**  We appreciate your suggestions about improving the exposition of results in Section 4. To compare with the on-average uniform stability analysis of SGD by Hardt et al. [2016], a non-trivial technical contribution of our L2-uniform stability analysis is using Lemma 10 to handle a key recurssion appeared in Equation (32) for smooth and convex losses. \n\n\n> **Your comment:** How does $\\gamma_{L_2,N}$ compare to $\\gamma_N$ for SGD?\n\n**Our response:** In the following, we compare $\\gamma_{L_2,N}$ to $\\gamma_N$ for SGD with smooth or non-smooth convex losses: \n\n1. For smooth and convex losses, $\\gamma_{L_2,N}\\le \\sqrt{\\frac{1}{N}\\sum_{t=1}^T \\eta^2_t + \\frac{1}{N^2} \\left(\\sum_{t=1}^T \\eta_t\\right)^2}$ (see Lemma 12). In comparson, $\\gamma_N$ is known to be of the scale $\\frac{1}{N}\\sum_{t=1}^T\\eta_t$ [Hardt et al., 2016, Theorem 3.7].\n \n2. For non-smooth and convex losses, $\\gamma_{L_2,N}\\le \\sqrt{\\sum_{t=1}^{T}\\eta^2_t + \\frac{1}{N^2} \\left(\\sum_{t=1}^T \\eta_t\\right)^2}$ (see Lemma 13), while $\\gamma_N$ scales similarly as $\\sqrt{\\sum_{t=1}^{T}\\eta^2_t} + \\frac{1}{N}\\sum_{t=1}^T\\eta_t$ accroding to Bassily et al. [2020, Theorem 3.2].   \n\n\n> **Your comment:** Line 75: Should it be $[0,M]$ instead of $(0,M]$? Line 187: Typo: McDiamid’s\n\n**Our response:** Yes, the range of loss value should be $[0,M]$. Thanks for catching the typos!\n\n\n## References:\n\nOlivier Bousquet, Yegor Klochkov, and Nikita Zhivotovskiy. Sharper bounds for uniformly stable\nalgorithms. *COLT*, pp. 610–626, 2020.\n\nMoritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic\n373 gradient descent. *ICML*, 1225–1234, 2016.\n\nRaef Bassily, Vitaly Feldman, Cristobal Guzman, and Kunal Talwar. Stability of stochastic gradient descent on nonsmooth convex losses. *NeurIPS*, 1–10, 2020."}, {"review_id": "eGv6WbRlao", "reviewer": "Reviewer_ZVGG", "summary": "Algorithmic stability refers to the sensitivity of learning algorithms to the training set. Roughly speaking, if a learning algorithm is more stable, then its generalization gap (i.e., its training loss is highly indicative of its population loss) can be better controlled. In the literature, various notions of algorithmic stability have been proposed for *randomized* learning algorithms. Two most prominent ones are *on-average uniform stability*, which says that the averaged (over its internal randomness) algorithm is uniformly stable, and *high probability uniform stability,* which says that the algorithm is uniformly stable with high probability over its internal randomness.\n\nThis paper puts forth a new notion of algorithmic stability called *L2-uniform stability*, which can be seen as a second moment version of on-average stability. This notion sits naturally between on-average stability, which is rather weak and thus leads to weaker generalization bounds, and high probability stability, which can be too stringent to satisfy. To demonstrate the utility of this novel notion, the authors show that L2-stability can be used to derive generalization bounds with (exponentially) high confidence, where the randomness is over *both* the training samples and the algorithm’s internal randomness. This is in contrast to the generalization bound derived from on-average stability which only holds *in expectation* with respect to the algorithm’s internal randomness. The authors provide applications of their novel technique by showing qualitatively stronger generalization bounds for SGD with respect to convex loss functions.", "questions": "- Is it possible, perhaps under additional assumptions, to get exponentially high probability generalization bounds from on-average uniform stability? What are some technical barriers that stand in the way of boosting the confidence of generalization bounds from on-average stability?\n\n**Minor comments**\n- Typo in line 56: \"deviatin\"", "limitations": "Yes.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- **Simple and novel notion with useful applications.** L2-uniform stability is a natural strengthening of on-average uniform stability. Though the modification may seem minor, this novel notion leads to significantly stronger generalization bounds. As mentioned previously, a key deficiency of generalization bounds from on-average stability is that they only hold *in expectation* with respect to the algorithm's randomness. Certainly, generalization bounds that hold *with high probability* over the algorithm's randomness (and also randomness of training samples) are preferable. The first-moment generalization bound from L2-stability, combined with bagging [Breiman, 1996], yields such high probability bounds. The authors further show that SGD in various settings (e.g., for smooth/non-smooth convex losses) is sufficiently L2-stable, leading to sharper generalization bounds.\n\n- **Clear exposition.** The ideas in the paper are presented with great clarity and the overall text, including the technical proof sections, flows seamlessly.", "weaknesses": "N/A", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful review and appreciation of our work.\n\n> **Your comment:** Is it possible, perhaps under additional assumptions, to get exponentially high probability generalization bounds from on-average uniform stability? What are some technical barriers that stand in the way of boosting the confidence of generalization bounds from on-average stability?\n\n**Our response:** Thanks for the interesting questions which we hope can be addressed by the following replies:\n\n1. In general, it still remains open, if not impossible, to derive near-tight exponential generalizations bounds via confidence-boosting technique under the notion of on-average uniform stability. A substantial challenge faced here is that from on-average stability, it seems only possible to get exponetial generalization bounds w.r.t the on-average loss like in Equation (4), to which the confidence-boosting trick is not directly applicable.    \n\n2. It is however possible to get exponential bounds on *excess risk* under the weaker notion of on-average uniform stability. Indeed, as discussed in the last paragrah of Section 3 that the exponential excess risk bound in Equation (14) can be obtained by applying the confidence-boosting technique to the in-expectation excess risk bound in Equation (13), keeping in mind that excess risk is always non-negative. \n\n3. If we are willing to modify the confidence-boosting procedure using *subbagging*, i.e., we repeat the algorithm on independent subsets and take the best one on the holdout, then it is indeed possible obtain the desirable near-optimal generalization bounds under on-average stability. However, such a kind of subbagging procedure needs to run the randomized algorithm over $\\log(1/\\delta)$ independent subsets instead of the full dataset. In contrast, our bagging-style strategy repeatedly executes the randomized algorithm over the entire sample (except the holdout) with $\\log(1/\\delta)$ independent random seeds, which is expected to be more favorable for practical implementation."}, {"review_id": "1lJJhR1pih", "reviewer": "Reviewer_Yv2V", "summary": "Stability is a useful tool for obtaining sharper generalization bounds in learning theory. In prior work, the notion of \"on-average\" stability is as follows. A randomized learning algorithm is stable if for all datasets $S$, adjacent datasets $S'$ (i.e. differing by a single point), and all data points $Z$, the expected difference (taken over the randomness of the algorithm) between the loss incurred by the algorithm at Z when trained on $S$ and $S'$ is bounded.\n\nOn-average stability can be used to provide \"on-average\" risk bounds, where the population risk and the empirical risk of the trained classifier have low expected difference. Note here that this does not guarantee that the empirical risk is close to the population risk -- it rather guarantees that the empirical risk is close to an unbiased estimator of the population risk. Specifically, the quantity $$|\\mathbb{E}_{\\xi}[R(A(S), \\xi) - R_n(A(S), \\xi)]|,$$ is bounded, where the absolute values occur outside the expectation. \n\nThe goal of this is work to, under tighter assumptions, create tighter risk estimation bounds where we can instead bound the absolute difference between the two risks (i.e. proving accuracy) rather than simply providing a \"close-to-unbiased\" estimator. \n\nTo do so, they begin with a tighter notion of stability, where they bound the expected squared difference between the loss incurred at Z when trained on $S$ and $S'$. By simply adding a square here, this eliminates the possibility of \"large differences\" cancelling each other out when the expectation taken, and thus is a much stronger notion of stability. Under this assumption, their main result is a risk estimation bound on $$\\mathbb{E}_{\\xi}|R(A(S), \\xi) - R_n(A(S), \\xi)|.$$ Here the absolute value appears inside the expectation, and this is the crucial difference.", "questions": "Can you argue more explicitly why your bound is \"sharper than its on-average counterpart?\" I had to read through the algebra for this to become clear to me, and I generally don't like relying on algebra alone due to its sensitivity to typos. \n\nEdit: these concerns have been addressed in the rebuttal.", "limitations": "None.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This paper appears to be a significant technical development over prior work. While the notion of stability has been known to lead to better generalization bounds, this paper greatly strengthens the type of generalization bounds that can be obtained for _randomized_ learning algorithms (my understanding is that this paper offers no new insight into deterministic algorithms as their bound essentially reduces to existing bounds).", "weaknesses": "I think that the subtly of the contribution of this paper needs to be spelled out more clearly. As far as I can tell, the crucial difference between this bound and prior bounds is literally upon the placement of the absolute value signs. The quantities $|\\mathbb{E}[R-R_n]|$ and $\\mathbb{E}|R-R_n|$ are substantially different meaning that this difference is important, but nevertheless they visually look very similar to the reader. If my understanding of this paper is correct, then highlighting this difference could be helpful.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful review and positive evaluation of our work. \n\n> **Your comment:** I think that the subtly of the contribution of this paper needs to be spelled out more clearly. \n\n**Our response:** Thanks for your concise summary of the crucial differences between our first-moment generalization bound (under $L_2$-stability) and the prior on-average generalization bounds (under on-average stability). Per your suggestion, we will more explicitly highlight the mentioned subtle differences in Section 1.2 and Section 2.4.  \n\n> **Your comment:** Can you argue more explicitly why your bound is \"sharper than its on-average counterpart?\" I had to read through the algebra for this to become clear to me, and I generally don't like relying on algebra alone due to its sensitivity to typos. \n\n**Our response:**  While our bound in Theorem 1 has identical convergence rate to that of the on-average bound in Equation (4), the former is stronger in the sense that the expectation is taken outside the absolute generalization gap and thus implies the latter. We will more precisely elaborate on this difference in the updated draft. \n\n> **Minor comments** on typos. \n\n**Our response:** Thanks for catching the typos! "}, {"review_id": "uzZhcSRosZ", "reviewer": "Reviewer_RTFd", "summary": "This paper develops new and potentially sharper (as compared to the state of the art) data and randomness dependent (high probability type) generalization bounds using a kind of new and more restrictive notion of algorithmic stability, which the authors call L2-uniform stability. The focus is in particular on generalization analysis for randomized algorithms.\n\nThe main results of the paper are then leveraged to derive very detailed high probability generalization bounds for a certain bagging-based meta algorithmic framework. Those results are subsequently instantiated for SGD, in the same boosting-type scheme. ", "questions": "Line 126: What \"sharper\" means here? The bound is the same but with different constants, and with the \"Jensen\" version of the estimation error.\n\nIn Remark 3, although I understand the point, I believe that the word \"tighter\" is not really applicable, because of the different type of stabilities in Theorem 1 and in (4). Maybe you could rephrase. I see, however, that in the appendix the L2 stability of SGD (for instance) is established. I think that the relevant result could be highlighted more explicitly, even if Theorem 1 is in-expectation relative to \\xi.\n\nTitle of Section 4 is misleading, and all algorithms considered are boosted. I would suggest that the authors rephrase, and also state more clearly throughout the paper that the bounds derived for specific algorithms are not for standard schemes such as SGD, but for the boosted versions. \n\nIt seems that Remark 6 has a technical issue: If I am not mistaken, the rate of Hardt et al. in the smooth , Lipschitz, convex case is of order $\\sqrt{T}/N$ for a stepsize equal to $2/(L\\sqrt{T})$, that is for a constant stepsize. In contrast, Remark 6 refers to a decaying root stepsize, which when summed from 1 to T gives a subharmonic number which is strictly larger that $\\sqrt{T}$. If I am correct in the above, please make an effort to revise the results in Section 4 accordingly. See also lines 141-147, where a similar statement is made.\n\n", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is well-written and considers an important and challenging question, namely, that of characterizing the generalization performance of randomized algorithms in a \"high-probability\" scheme, which is very much attractive especially from a practical/application perspective.\n\nSection 1 (Intro) are particularly well-written and generally a pleasure to read, and well-suited even for people who are not very familiar with algorithmic generalization.\n\nPropositions 1 and 2 are interesting, and could be potentially of independent interest. This is a plus.\n\nTheorem 1, one of the main and \"backbone\" results, is interesting though somewhat expected, especially because it provides an upper bound on the L1 norm of the estimation error (averaged over algo randomness), rather than the expected estimation error commonly studied in the literature.  However, as pointed out below, the real usefulness of the L2 stability which introduced in the paper might be a bit questionable.\n\nThe results presented in Section 3 for the particular class of meta-algorithms are also interesting and useful. By the way, are the results presented in Sections 3/4 the first ones on the generalization of that type of algorithms? ", "weaknesses": "The L2-type notion stability may be considered \"new\", although it is a reasonable and natural \"norm-Jensenized\" generalization of (2). In terms of contribution, this is probably sufficient, although it may also be considered derivative relative to prior works, at least conceptually.\n\nAll the results presented are for boosted algorithms, which is interesting on the one hand, but it is unclear if the results and the respective techniques produce non-trivial or improved results for standard algorithms, such as (mini-batch) SGD. Maybe the authors would like to elaborate more on this. Also see my comment about Remark 3, below.\n\nAlso, the results in Section 4 are quite weak. In particular, although the bounds are indeed decaying, the decays are extremely slow, like $\\ log{(N)} / \\sqrt{N}$, which is almost constant (so to say). I therefore doubt that such bounds could be of actual interest, apart from strictly theoretical. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful review and encouranging comments. \n\n> **Your comment:**  By the way, are the results presented in Sections 3/4 the first ones on the generalization of that type of algorithms?\n\n**Our response:** Yes, we for the first time establish in Theorem 2 a generalization bound for confidence-boosted randomized algorithms with $L_2$-uniform stability, which has not been possible to get under the weaker notion of on-average stability. The implications of Theorem 2 for the boosted SGD with decaying learning rates are also new to our knowledge.\n\n\n> **Your comment:** All the results presented are for boosted algorithms, which is interesting on the one hand, but it is unclear if the results and the respective techniques produce non-trivial or improved results for standard algorithms, such as (mini-batch) SGD. Maybe the authors would like to elaborate more on this.\n\n**Our response:** Regarding the exponential generalization bounds for the original randomized algorithms with $L_2$-uniform stability, it is a thrilling question yet so far our confidence-boosting technique does not allow us to resolve this open problem completely. We believe that developing tighter martingale concentration inequalities for randomized algorithms with conditional uniform stability (conditioned on the algorithm random bits), if possible, would be a vital step towards fully resolving this challenging problem. \n\n\n>**Your comment:** In particular, although the bounds are indeed decaying, the decays are extremely slow, like \n$\\log(N)/\\sqrt{N}$, which is almost constant (so to say).\n \n**Our response:** We would like to highlight that in view of the lower bound of Bousquet et al. [2020, Proposition 9], up to logrithmic factors, the $\\log(N)/\\sqrt{N}$ rate is actually almost the best we can hope in general for *high-probability* generalization bounds.\n\n\n>**Your comment:** Line 126: What \"sharper\" means here? The bound is the same but with different constants, and with the \"Jensen\" version of the estimation error.\n\n>In Remark 3, although I understand the point, I believe that the word \"tighter\" is not really applicable, because of the different type of stabilities in Theorem 1 and in (4). Maybe you could rephrase. \n \n**Our response:** By saying that our result is sharper, what we really want to express is that our first-moment generalization bound in Theorem 1 implies the on-average bound in Equation (4), though they are obtained under different notions of stability while the rates are identical. We will rephrase the statement to more accurately reflect the strength of our results in future version. \n\n\n> **Your comment:** I see, however, that in the appendix the L2 stability of SGD (for instance) is established. I think that the relevant result could be highlighted more explicitly, even if Theorem 1 is in-expectation relative to \\xi.\n\n\n**Our response:** We appreciate your suggestion about highlighting the implications of Theorem 1 for vanilla SGD with decaying learning rates, in addition to those of Theorem 2 for boosted SGD.  \n\n\n> **Your comment:** Title of Section 4 is misleading, and all algorithms considered are boosted. I would suggest that the authors rephrase, and also state more clearly throughout the paper that the bounds derived for specific algorithms are not for standard schemes such as SGD, but for the boosted versions.\n\n**Our response:** Per your suggestion, we will modify the title of Section 4 and rephrase the texts to more accurately state that the results are custermized for confidence-boosted versions of SGD. \n\n\n> **Your comment:** In contrast, Remark 6 refers to a decaying root stepsize, which when summed from 1 to T gives a subharmonic number which is strictly larger that $\\sqrt{T}$.\n\n**Our response:** There might be a misunderstanding with regard to this technical issue. Indeed, under the considered $\\mathcal{O}(\\frac{1}{\\sqrt{t}})$ stepsizes in Remark 6, the rate of Hardt et al. [2016] is still of scale $\\frac{\\sqrt{T}}{N}$ due to the fact $\\sum_{t=1}^T \\frac{1}{\\sqrt{t}} \\le 2\\sqrt{T}$. \n\n\n\n## References:\n\nOlivier Bousquet, Yegor Klochkov, and Nikita Zhivotovskiy. Sharper bounds for uniformly stable\nalgorithms. *COLT*, pp. 610–626, 2020.\n\nMoritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic\n373 gradient descent. *ICML*, 1225–1234, 2016."}, {"review_id": "gekumz33pT", "reviewer": "Reviewer_7EkU", "summary": "This paper considers generalization bounds for SGD with a notion of randomization on learning algorithms. The paper considers a $L_2$-uniform stability framework and establishes generalization inequalities under such a framework. Additional algorithms and analysis using confidence-boosting are discussed.", "questions": "Please refer to the questions listed or implied in the above sections. Additional questions / comments are:\n\n1. Why is the upper bound in Theorem 2 increasing as $K$ increases? One would think that running an algorithm multiple times and selecting the \"best\" output would yield a \"tighter\" result. Can this be elaborated?\n\n2. Theorems 1 and 2 appear to be \"sub-exponential\" bounds with respect to dependency of $\\log(1/\\delta)$. Is it possible to derive with similar methodologies a \"sub-gaussian\" type bound? \n\n3. Are there matching lower bounds (perhaps up to logarithmic factors) under the $L_2$ uniform stability assumption?\n\nBelow are some typos that may need revision:\n\n- the statement in Theorem 2 has an additional period in line 262.\n- \"Jensen's ineuqality\" in line 164", "limitations": "Limitations are not addressed in detail.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The paper's strengths are summarized in the following criteria.\n\nOriginality: The main comparisons made within the paper focus on comparisons against prior literature established for \"on-average\" uniform stability and \"high probability\" uniform stability. While SGD's under these two forms of uniform stability have been studied extensively, the authors identify an interesting gap in the literature by looking at \"$L_2$\" uniform stability.\n\nQuality and clarity: The paper covers a good amount of motivation and background of SGD theory. Some additional comments regarding quality and clarity can be found in latter sections.\n\nSignificance: Considering that SGD is broadly used in many areas of ML, understanding more about the theory of SGD is quite important. From this perspective, this paper is relevant to the NeurIPS community.", "weaknesses": "While the paper covers good amount of material, one of the weaknesses of the paper is its clarity and structure. There were certain parts of the paper that were not easily readable and confusing. It may be helpful to add in formal definitions and clear up typos/confusions:\n\n-  For example, it may be helpful to elaborate in the paper more on specific definitions such as $\\mathcal{Z}$, $\\mathcal{R}$, etc.\n- Another example is the definition of the parameter $\\gamma_{L_2,N}$ in lines 162-164; the words \"for every $N\\geq 1$\" is likely redundant and adds confusion for the reader.\n\nRegarding the main results, considering that an $L_2$ assumption is stronger than an $L_1$ assumption, it does not necessarily make sense to compare Theorem 1 and (4) directly. A better \"comparison\" may be to derive the optimal ordering for the $L_2$ case, i.e., the corresponding lower bound. It is not immediately clear if the known lower bounds from earlier works with different assumptions can be applied to show that Theorem 1 is tight up to a logarithmic factor apart for some special cases (such as when $A$ is deterministic). Is this analysis available?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful review and detailed comments for improvement. We sincerely hope that the main concerns raised in the review can be clarified by the following responses.  \n\n> **Your comment:** It may be helpful to add in formal definitions and clear up typos/confusions.\n\n**Our response:** Thanks for your very careful inspection of our manuscript. Per your suggestion, we will further clarify notation and fix typos/confusions to improve readability. \n\n> **Your comment:** It is not immediately clear if the known lower bounds from earlier works with different assumptions can be applied to show that Theorem 1 is tight up to a logarithmic factor apart for some special cases (such as when $A$  is deterministic). Is this analysis available?\n\n**Our response:** Yes, we indeed believe that the lower bound analysis of Bousquet et al. [2020, Proposition 9] for sum of functions of Rademacher signs could be extended to sum of functions of Rademacher signs with auxiliary random bits. As an initial thought, one may consider to construct randomized functions of form $g_i(S,\\xi)=MZ_i + \\frac{\\beta}{2}Z_i\\left(\\sum_{j\\neq i}Z_j + \\xi_1\\right)\\xi_2$ where $Z_i$ and $\\xi_1$, $\\xi_2$ are all Rademacher signs. It can be verified that these $g_i(S,\\xi)$ satisfy the L2-bounded-difference property. Consequently, the arguments of Bousquet et al. [2020, Proposition 9] can be naturally adapted to the considered randomized functions to get the desired lower bound that matches the upper bound presented in Proposition 2 (which then implies the main result in Theorem 1). Once ready, we will add the lower bound analysis to the next version. \n\n\n> **Your comment:** Why is the upper bound in Theorem 2 increasing as $K$ increases? One would think that running an algorithm multiple times and selecting the \"best\" output would yield a \"tighter\" result. Can this be elaborated?\n\n**Our response:** We would like to clarify that the $\\log (K/\\delta)$ factor in the bound of Theorem 2 originally arises from the the uniform  generalization bound defined in $\\mathcal{E_1}$ (Line #600 of the supplement file), which represents the overhead of simultaneously bounding the generalization performance of $K$ different candidate solutions $\\{A(S_1,\\xi_k)\\}_{k\\in [K]}$ over the holdout validation set $S_2$. We will add some remarks on this point in the updated draft.\n\n\n> **Your comment:**  Theorems 1 and 2 appear to be \"sub-exponential\" bounds with respect to dependency of $\\log(1/\\delta)$. Is it possible to derive with similar methodologies a \"sub-gaussian\" type bound? \n\n**Our response:** It is an interesting direction to explore the possibility of deriving exponential generalization bounds of sub-gaussian form. The current sample-splitting technique based on moments concentration inequalities seems not allowing us to remove the sub-exponential terms. We conjecture that a potential workaround is using the the exponential versions of Efron-Stein inequality [Boucheron et al., 2003] instead of the moments counterpart inside the sample-splitting framework. We leave the improvement over poly-logarithmic terms for future investigation. \n\n\n## References:\n\nOlivier Bousquet, Yegor Klochkov, and Nikita Zhivotovskiy. Sharper bounds for uniformly stable\nalgorithms. *Conference on Learning Theory*, pp. 610–626, 2020.\n\nStephane Boucheron, Gabor Lugosi, and Pascal Massart. Concentration inequalities using the entropy\nmethod. *Annals of Probability*, 31(3):1583–1614, 2003."}]

Author rebuttal:

Meta-review: This meta review is based on the reviews, the authors rebuttal and the discussions with the reviewers, discussions with the SAC, and ultimately my own judgement on the paper. There was a consensus that the paper contributes sound and interesting contributions to generalization theory. I feel this work deserves to be featured at NeurIPS and will attract interest from the community. I would like to personally invite the authors to carefully revise their manuscript to take into account the remarks and suggestions made by reviewers in their camera-ready. Congratulations!
Decision: Accept (poster)