Boosting the Confidence of Near-Tight Generalization Bounds for Uniformly Stable Randomized Algorithms
Authors: Xiaotong Yuan
Ping Li
Venue: ICLR 2022 Submitted (2022)
Keywords: Uniform stability
Randomized learning algorithms
Bagging
Generalization bounds
Stochastic gradient methods

Abstract: High probability generalization bounds of uniformly stable learning algorithms have recently been actively studied with a series of near-tight results established by~\citet{feldman2019high,bousquet2020sharper}. 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~\citet{bousquet2020sharper}.

Under review as a conference paper at ICLR 2022
BOOSTING THE CONFIDENCE OF NEAR-TIGHT GEN- ERALIZATION BOUNDS FOR UNIFORMLY STABLE RANDOMIZED ALGORITHMS
Anonymous authors Paper under double-bling review
ABSTRACT
High probability generalization bounds of uniformly stable learning algorithms have recently been actively studied with series of near-tight results established by [Feldman & Vondrak (2019): Bouuquee et al. (020). 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 random- ness of algorithm. This paper addresses this open question and makes progress to- wards answering it inside classic framework of confidence-boosee boosting. To this end, we first establish an in-expectation first moment generalization eгror bound for randomized learning algorithm with on-average uniform stability, based on which we then show that 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 prob- ability generalization bounds for convex or non-convex optimization with natural time decaying learning rates, which have not been possible to prove with the ex- isting uniform stability results. Specially for deterministic uniformly stable algo- rithms, our maniiencce-oossing results improve upon the best known generaliza- tion bounds terms of a logarithmic factor on sample size, which moves a step forward towards resolving an open question raised by Bousquet et al. (2020).
INTRODUCTION
In many statistical machine learning problems, the ultimate goal is to design a suitable algorithm A z - W that maps training data set S <i 2 model A(S) in a closed subset W of an Euclidean space such that the following population risk function evaluated at the model is small as possible:
R(A(S)) == Ez=D(((A(S); 2)},
where E : W x 2 + IR+ is a non-negative bounded loss function whose value E(w; 2) measures the loss evaluated
with parameter w, and D represents 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 be an i.i.d. set, i.e., S iid. DV, Then, a natural alternative measurement that mimics the computationally intractable population risk is the empirical risk defined by
N Σ ((A(S);2)) Rs(A(S)) == | (((): 2)] = N 1=1
The bound on the difference between population and empirical risks is of central interest in under- standing the generalization performance of learning algorithm A. Particularly, we hope to derive suitable law of large numbers, i.e., sample size vanishing rate by such that the generalization bound (s() - R(A(S)) S by holds with high probability over the randomness of S and po- tentially the randomness of A as well. Provided that A(S) is an almost minimizer of the empirical risk function Rs. say Rs(AA (A(S)) < minwew Rs(w) (w) + bN. the generalization bound immediately implies an excess risk bound R(A(S)) min R(w)= S by + 1 due to the standard risk de- composition and Hoeffding's s inequality. Therefore, generalization bounds also play a crucial role in understanding the stochastic optimization performance of a learning algorithm.
V

---

Under review as a conference paper at ICLR 2022
The generalization bounds can be naturally implied by uniform bounds su |R(w) [s(w)] (Bartlett et al. 2006 Bottou & Bousquet) 2008). While broadly applicable (e.g., to non- convex 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 not suitable for high-dimensional models which are ubiquitous in modern machine learning. Alternatively, a powerful proxy for analyzing the generalization bounds the stability of learning algorithms to changes in the training dataset. Since the seminal work of [Bousquet & Elisseefi (2002), stability has been extensively demonstrated to beget dimension-ing independent generalization bounds for deterministic learning algorithms (Mukher- jee et al., 2006] Shalev- -Swarrz et al. 2010)) as well as for randomized learning algorithms (such as bagging and SGD) (Elisseeff et al. 2005 (ardd et al. (0166) 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 2 with learning rate T)t >> 0:
dimension-independenn
Wyy == Ulw (wt-1- T/s -1k (w)
(I)
where & [N] is a uniform random index of data under with or without replacement sampling, and 1w is the Euclidean projection operator associated with W. Despite its popularity in the study of stability theory (Hardt al. 2016, Zhou et al.] [219 Lei & Ying 2020). the high probability
generalization bounds of SGD are still relatively under explored through the lens of uniform stability.
1.1 PRIOR RESULTS
Let us now briefly review some state-of-the-art generalization bounds for uniformly stable algo- rithms 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 -nn-urrf stability if it satisfies the following uniform bound
sup
[BA|{(A(S):=)) - EA!((A(S"); 2)]l YN.
8=8'
This definition is equivalent to the concept of uniform stability defined over the on-average loss EA(((A(S); 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 ò E (0, 1), with probability least 1 d over S, the on-average generalization error is upper bounded by
NN σ
log (1/5) N
E [R(A(S)) (s(A))) & 7N log(N) log L
(2)
Recently, Bousquet et al. (2000) derived a slightly improved uniform stability bound that implies
log (1/6)
EA (R(A(S)) - Rs Rs{(A(S)) S YN log(N) log
5
+
N
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 hugh-probability results only hold expectation with respect to the internal randomness of algorithm.
Further suppose that A has 7N -N-uuiform stability with probability at least 1 8' for some 8' e E(,,1) over the randomness of A, i.e.,
- -(A(S)):)) YN } 2 8-
PA
sup
(4)
SES' 2EEZ
Suppose that the randomness of A is independent of the training set S. Then with probability at least 1 d- - 8' over S and A, the bound of Bousquet et al. (2020) naturally implies
(R(A(S)) - Rs(A(5)) & YN log(N) log 1
log (1/5)
(5)
N
2

---

Under review as a conference paper at ICLR 2022
Algorithm 1: Con
for Randomi zed Learning
Input : :A randomized learning algorithm A and training data set S = (Zilie(N) lid DM Output: (s-(S)))
Uniformly divide 5 into K disjoint subsets such that 5 UkEiK] Sk and |Sx| = N AA E [K].
for k = 2,.,.... K do
Estimate (5&) as an output of the randomized algorithm over subset Sg. end Compute K- [kj] Rsy, (Ax(S)) Rs, (Ax(S)))
This is by far the best known generalization bound of randomized stable algorithms that hold with high probability jointly over data and algorithm. The result, however, relies heavily on the high- probability uniform stability condition expressed in equation For the SGD (see equation I with
fixed learning rate 7): = 17. it is possible to show that YN X TTT + aT
"N" and 8' = N exp(
in equation 4 (Bassily et af., 20.0), For SGD with time decaying learning rate that has been widely studied in theory HHavvey 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 IN and ò' of interest. On the other hand, it is possible to show (see the proofs of Corollary andd] 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 equa- tion T the randomness of algorithm can be precisely characterized by a vector of i.i.d. parameters <= ,1...., which are independent on data S. In such cases, suppose that A(S;E) has uniform stability with respect to any given S, i.e., supe [E{A(S;; E)) {{A(S: E')) S Pr- Then the high probability bound established in Elisseeff al. (2005) shows that with probability at least 1 6,
(R(ASS) - (((RR(((SSSS))) TN + (
[ (1+N NYn vTOT) VN
log (5}
Provided that YN S N and PT S 1. the above bound shows that the generalization bound scales O vT) with high probability. However, the above bound will show no guarantee on convergence if IN Z VN and/or pr 2 v For example, this is actually the case for SGD with time decaying learning rate 1)t ( on non-convex loss functions in which YN S YT can scale as large as ((1)
and pr
N
Open problem and motication. Keeping the merits and deficiencies of above recalled prior results in mind, it still remains 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.
1.2 OVERVIEW OF OUR RESULTS
The confidence-boosting technique of (Schapire (1990) is classical meta approach that allows us to boost the dependence of learning algorithm on the failure probability 5 from 1/8 to log(1/6), at a certain cost of computational complexity. The fundamental contribution of our work is to reveal that the confidence-boosse for uniformly stable randomized learning algorithms. The novelty lies in refined analysis of the in-expectation first moment generalization error bound for a randomized learning algorithm with on- average uniform stability, which leads to improved high-probability generalization bounds over the randomness of data and algorithm via confidence- -boosiing. More specifically, given a randomized learning algorithm A, we consider the following subbagging process over training set:
trick yields near-tight high probability generalization bounds
Boosting the Confidence via Subbagging. We independently run A over K disjoint and u- niformly divided training subsets {S*] to obtain solutions (As(S=))ue(k) Then e-
3

---

Under review as a conference paper at ICLR 2022
valuate the validation error of each candidate solution over its complementary training subset, and output Ax- (Sk-) that has the smallest gap between training error and validation error, i.., k* = arg min] Rsy., (A=(Sz)) Rs. (A+))) Specially when A is deterministic, this re- duces 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 subbagging procedure with greedy model selection for randomized algorithms over multiple dis- joint subsets. Here we have assumed without loss of generality that N is multiplier of K. The considered procedure of confidence-boostine for randomized learning outlined in Algorithm |
Main Results. In what follows, we highlight our main results on the generalization bounds of the output of A aalong with the implications for SGD and deterministic algorithms:
General results. Suppose that the loss is Lipschitz and bounded the range of (0, 1]. Our main
result in Theorem show that for any 5 E (0, 1), setting K = log( ())) yields the following generalization bound of the output of Algorithm [ that holds with probability at least - ô over S and } )
1 K Mn 7 +
K N
log(K/9/ K/o) N
[R( (R (S (A (..A--(())) (Sk
where N and "/2..N are respectively mean-uniform stability and mean-square-uniiomm stability bounds introduced in Definition] I In contrast to the bound in equation our bound is not relying on the uniform stability with respect to the random bits of algorithm.
Stronger generalization bounds for SGD via onffience-boostingg We then use our general result- anfiidence-bosstinn on the generalization bounds of SCD-w (SGD via with-replacement sampling as outlined in Algorithm 2). The main results
s to study the benefit
series of corollar- ies of Theorem [ when substantialized to SGD with smooth (Corollary [T or non-smooth (Corol- lary
2 convex Toss, and smooth non-convex loss functions (Corollary 3) For an instance, our result in Corollary [
showcases that when invoked to SGD-w on smooth convex loss with learn- ing rates 7e O Vi ). the generalization bound of the output of Algorithm with K log( is
upper bounded by
V (og(T) N
VT + VN log (1/6)
R(AsCD-w.A- (8k-)) Rs( (tssAACD-w.A (Sx-))
N
Compared with the O O in-expectation bound of smooth convex SGD HHrdd et al. 2016 our above bound is competitive in order while holds with high confidence.
Sharper bounds for uniformly stable algorithms via confidence-boostie ministic learning algorithm A that has 7nn-uniform stability for each data set size N 2 1, we further show through Corollary 4 that the following bound holds for the output of Algorithm with K- log(
Specially for a deter-
log(K/8)
R(A(S=+)) - Rs(A S
N
In the case of IN E VN which holds in some popular learning paradigms such regularized ERM, the above bound implies (recall K log(}) (3))
log(1/6)
IR(A(S))) )) Rs (s(A(S))))
N
which is sharper than the best known result in equation 5 (under 8' = 0) in the sense of the
removal of log(N) factor. This is side contribution of 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 high probability excess risk bound for uniformly stable randomized learning with manidence-boosting More specifically, with proper modification of the output of Algorithm I and [As)eE(Ke
show that with probability at least d over S
logí K/0)
R(AA-(Sk))) min R(w) S ST. upp +
WEW
N
where App is the in-expectation empirical risk optimization error given by equation 7
4

---

Under review as a conference paper at ICLR 2022
2 GENERALIZATION ANALYSIS WITH CONFIDENCE-BOOSTING
In this section, we present a set of generic results on the generalization bounds of randomized learn- ing algorithms with confidence-boosting as described in Algorithm
2.1 PRELIMINARIES AND A KEY LEMMA
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
ct al. 2005 Bassily et al. 2020).
Definition 1 (Mean and Mean-Square Uniform Stability of Randomized Algorithms), Let A 2 + W be a randomized learning algorithm that maps a data set 2N to model A(S) E W.
Then A is said to have No, Ta,N-mean mean-unifone stability if for every N 2 1,
sup EA [I]A(S) - A(S S Ys.N-
s=s'
Moreover, is said to have No? ---maa--suuree uniforr stability ifr every N 2 1.
sup EA [1A(5) - A(5)) S 7--
$=S"
Here the algorithm outputs A(S) and A(S") share the same random bits associated with the algo- rithm. 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. (2117) for non- parametric hypotheses. The notion mean-square uniform stability is stronger than mean-uniform stability in the sense that the former naturally implies the latter such that Y,.N I /Tm,,N More- over, say function f is G-Lipschitz continuous over W if f(w) f(w") I G'llw w'll for all w, w E W, and it is L-smooth if [[V](w) - ff('')ll s L|W w'll for all w, w' E W.
Inspired by second moment bound for generalization error of uniformly stable algorithms from Bousqqet et al. 2220 Section 5), we first establish the following lemma which states that randomized learning algorithm has Yn,N ---mm---nnnnnnne stability, then its on-average first moment generalization error bound will be as small as O(in,N V + A when the loss function is Lipschitz continuous. This result an adaptation of the second moment bound derived by Bouuqueet et al. (2200) to on-average uniform stable randomized algorithms, and that bound is also the source of 7nP N entering into play. For completeness, we provide proof for this result in Appendix B.
Lemma 1. Suppose that a randomized learning algorithm A : NN + W has NJ..N-mean-nnee mean--niform stability and "n="N N-eean- saaaaan--u-----a- uniforr stability. Assume that the loss function E is G-Lipschitz with respect to its first argument and bounded in the range of [0,, A1). Then we have
M
EASS [R(A(S)) - Rs(A())) S GV/SA,N + GYn.N +
VN
In comparison to the on-average bound TE (R(A(S)) - Rs(A(S)) S G.m,, (see, e.g.. H.rdi et al. 2016, Theorem 2.2), our on-average first moment bound in Lemma Tis substantial- ly 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 the explicitly or implicitly known first moment bound for uniformly stable algorithms (see, e.g., Feldman & Vondrak, [2018 Bousquet et al. 2020) which is righter in logarithmic factors than the one implied by the p-th moment in- equality of Bousquet et al. 2020 Theorem 4). In this case, our bound is stronger than the bound from Bousquet& & Elisseef (002 Lemma 9) which essentially scales as VN + VY,,N in our notation.
Remark 1.
2.2 MAIN RESULTS ON GENERALIZATION BOUND
Let us recall the subbagging process as described in Algorithm I we independently run over K even and disjoint training subsets { ke(k] to obtain solutions (Ac(5)) and then pick A&- (Sx-) that has the smallest difference between training error and validation error (over the com- plementary training subset S \ S..). The following theorem is our main result about the high prob- ability generalization bound of the output Aç- (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 I and the fact that at least one of the solutions generated by subbagging generalizes well with high probability.
5

---

Under review as a conference paper at ICLR 2022
Theorem 1. Suppose that randomized learning algorithm A 2 4 W has "I=,N --a---aannniiia mean-uniiorm stability and "hp "n N-mean-ssaee saaunn---re----- mnuare-uniform stability as well. Assume that the loss function G- Lipschitz with respect its first argument and is bounded in the range of [0, M... Then for any o, E (0,1) and 2 1 log(5) with probability at least over the randomness of S and (E(K)) the output of Algorithm| satisfies
I-a
1 [R(Ax-(Sx-)) (As-AAAAA-SAA (Sxx aK (o
K N
log(K/o)
M
+ M
N
Remark 2. To gain some intuition on the superiority of bound in Theorem let consider
K x log (+) as allowed in the conditions. Ti, S VN and "i S N. then our high-probability
bound in Theorem L roughly scales
1oR(1/5) which is sharper than the on-average bounds in equation 2 and equation 3 "IN S VN More precise consequences of these general results on SGD and deterministic uniformly stuble estimators such as ERMs and full grudient descent method will be discussed shortly in the sections to follow.
Remark 3. sharp contrast to the bound equation 5 that requires high probability uniform stability and the bound in equation ② that assumes uniform stability over the random bits of algo- rithm, our bound in Theorem Tholds under a substantially milder notion of meanl -square )annarrm-
stability over data. In terms of the tightness of bound, note that the confidence term V VN N is necessary even for an algorithm with fixed output. The uniform stability terms Yma & and 7 are also near-tight the the algorithm output can change arbitrarily with respect to these quantities.
[og(1/88
2.3 ON EXCESS RISK BOUNDS
To understand the optimization performance of randomized learning algorithm A with confidence- boosting, we further study here the excess risk bounds of Algorithm 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 R(w) and Appi : EAS Rs(A(S)) - min Rs(w) weW
WEW
In order derive the excess risk guarantees, first need slightly modify the output of Algo- rithm [ as A&- (Sk.) where K* = arg minke]K] Rsys, (As(Sa)). The following theorem is our main result about the high probability excess risk bounds of such a modified output of confidence-
boosting. See Appendix B.3 for its proof.
Suppose that randomized learning algorithm A 2N + W has "Jm,N-mean- -ea--ennnttie uninou 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 a, (0,1) and K > T-a log( with probability least over the randomness of S and {Ak] AkJKK] the modified output of Algorittmm 7 satisfies
Theorem 2.
1 (G +opp
log K/8)
R(Ax-(Sk-) - R(w*)(()))) S
M
N
Remark 4. Unlike the generalization error bounds, the excess risk bounds established in Theorem are not relying on the mean-square uniform stability of the algorithm, but with an additional term of in- in-expectation optimization error for minimizing the empirical risk. For deterministic optimization algorithms such as ERMs with Dap O, similar excess risk bounds can be implied by the generic results of Shalev-Shwarnd et al. 2010 Theorem 26) developed for the confidence-buosiie
approach.
Remark 5. Consider K = log (1) and "m.,N E }_ Then the bound in Theorem roughly scales
O [ug(1/6) + A.p)).
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

---

Under review as a conference paper at ICLR 2022
Algorithm 2: SGD via With with-Replaccemnts Sampling (Asco-w)
lid. ~ DN, step-sizes (21,, #iterations T, initialization wip. Input Data set S = [Zi)eIN]
Output: uy 1 Σ1e[T] W/.
for to 1art=122..... do
Uniformly randomly sample an index & E [M] with replacement;
Compute w,- Ilw (w:-1 The (
end
its in-expectation bound standardly known for uniformly stable learning algorithms, the high- confidence bound in Theorem [ can be easily derived via invoking Markov inequality the inde- pendent 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 for uniformly stable randomized algorithms is by itself highly non-trivial.
3 IMPLICATIONS FOR STOCHASTIC GRADIENT DESCENT
In this section we demonstrate the applications of the generic bound in Theorem [ to the widely used SGD algorithm. We focus on variant of SGD under with-replacement sampling outlined Algorithm 2 which we call Asso-y- w. what follows, we denote by (AsaD-v.k) k the outputs of Asso over subsets {Sk &ek when applied with Algorithm I Our results readily extend to the without-replacemmen variant of SGD and the corresponding results can be found Appendix D
3.1 CONVEX OPTIMIZATION WITH SMOOTH LOSS
For smooth and convex losses such as logistic loss, we can derive the following result direct consequence of Theorem [
with a = 1/2 to Asen-g. See Appendix C.1 for its proof.
Corollary 1. Suppose that the loss function is E(::-) is convex, G-Lipschitz and L-smooth with respect to its first argument, and is bounded in the range of [0, MM. Consider Algorithm 7 specified Asep-w with learning rate nh S L for all t 2 1. Then for any å (0, and K x log( ). with probability at least
over the randomness of S and {Asep - [K([K). the generalization error is upper bounded as R[Asso n.x (Sx-)) RRsAAso w.k (Sk-))
T
log(1/8)
G2
m
Σ
+ M V
N
N
N
Remark 6. For the conventional step-size choice of 1/. =
LV the high probability generalization
2
bound in Corollary is dominated by O(V log(T")
VT+y/ /o
(6)) which matches the corre-
sponding ( IT) in in-expectation bound for SGD with smooth convex losses Hardt al. 2016).
3.2 CONVEX OPTIMIZATION WITH NON-SMOOTH Loss
Now we turn to study the case where the loss is convex but not necessarily smooth, such as the hinge loss and absolute loss. The following result as a direct consequence of Theorem [ for the specification of Algorithm to Aseo with non-smooth convex loss and time varying learning rate (n1 Its proof is provided in Appendix C.2
Corollary 2. Suppose that the loss function is ((::)) is convex and G-Lipschitz with respect to its first argument, and is bounded the range of [0, M). Consider Algorithm ! specified to Ageo Then for any d (0, 1) and K x log(?). ). with probability at least 1 - 8 over the randomness of and {Aseo n.k [.])))])) the generalization error satisfies [R(A RR(ASED - (Sxx)) - Rs(Asco w,k- w.k (Sx.) )) S
T
2
T
G
T
T + M 1og(1/5)
2
Σ
+
m
Σ
N2
N
N
7

---

Under review as a conference paper at ICLR 2022
Remark 7. For constant rates Ni 7) Corollary 2 admits high probability generalization bound of scale OnnVT + n + V 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.
3.3 NON-CONVEX OPTIMIZATION WITH SMOOTH LOss
We further study the performance of Algorithm T for SGD on smooth but not necessarily convex loss functions, such normalized sigmoid loss (Mason al. 1999). The following result is direct application of Theorem to AscD with smooth non-convex loss. See Appendix for its proof. Corollary 3. Suppose that the loss function is ((55)) is G-Lipschitz and L-smooth with respect to its first argument, and is bounded in the range of [0, M). Consider Algorithm specified to AseD with Q)e S +. Let ut == Tf + 21); Ex=1 exp(L Limr+1 7h)rr for all t 2 1. Then for any E (0, 1) and K x log( with probability at least - over the randomness of S and {As6o w.k w.k)RE(K]. the generalization error is upper bounded as R(Agso-NA (S Rs(AAso (S DI
G²
1
T
exp
L
L
I
T/
T Ut + G E exp 1
T "t + M
log(1/8)
N
T=H+1
T=1+1
Remark 8. For the constant learning rates Th LT. Corollary
3 admits high probability gener-
/Log(//6) For time decaying learning rates The = Lvt with arbitrary
alization bound of scale O(V
2 1, it can be verified that the corresponding bound is of scale Oly /TM log(T)
log(2/0)
VN
N
4 IMPLICATIONS FOR DETERMINISTIC UNIFORMLY STABLE ALGORITTMM
This section is devoted to showing that confidence- confidence-boostingg is also beneficial for deriving stronger generalization bounds for uniformly stable deterministic learning algorithms. First we note that when there no internal randomness in A, the definition of mean( (qquare)-unifee stability reduces to the conventional concept of 7NN -uniforr stability for deterministic algorithms given by
sup ||A(S)) A(S')I S TN "n,N T=a,N S
Let us now consider a specification of Algorithm to uniformly stable deterministic algorithm A. Since there no randomness contained in A, we have that A& (Si) = A(S₂) for all k E [K] in such a deterministic case. Then the following result is direct consequence of Theorem I when applied to the considered deterministic learning regime.
Corollary 4. Suppose that a deterministic learning algorithm A : Z + W has YN- stability. Assume that the loss function is G-Lipschitz with respect to its first argument and is log(2/6) with probability at least 1 8 over
bounded [0, M). Then for any a, 8 E (0, 1) and K 2 I-a
the randomness of S, the output of Algorithm 7 satisfies
1 [((AS=-)) - -Rs(A(S aK
K N
log(K/0) K/8)
G
+ M
+
M
N
To demonstrate the superiority of our bound over prior ones, let consider a 0.5 and K log( (
in the above corollary. In the regime 7N S -π which of interest in many popular deterministic learning paridigss/algorithmss such as regularized ERM (Shalev-Shwartz et al. 2009) and full gra- iiplies a generalization bound for A(Sa-)
dient descent (Feldman & Vondrak 2019), Corollary 4
2020 gives (keep in mind that 8' = 0 over the data set S that scales as |R(A(S.)) )) - Rs (A(s))) E
log(1/6)
In comparison, the best N
known bound in equation 5 essentially from Bousquet et al.
log(H) As we can see that inside the in the deterministic case) R((AS)) - Rs(A(S)) S V'V
lng(
carefully designed framework of confidence- bossting via subbagging, our generalization bound gets rid of the logarithmic factor (Ng 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).
8

---

Under review as a conference paper at ICLR 2022
5 OTHER RELATED WORK
The idea of using stability of a learning algorithm, namely the sensitivity of estimated model to the
changes in training data, for generalization performance analysis dates back the seventies (Vap-) nik & 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 I--N and regularized ERMs (Bousquet& & Elisseeff 2002 Zhang 2003; Klochkov & Zhivotovskiyl (2021), The stability theory for randomized learning algorithms was formally introduced and investigated by Elisseetf 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 devia- tion (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 & Papailiopoolos/ (2018); Lei & Ying (202T). For non-convex sparse learning, algorithmic stabili- ty theory has been applied to derive the generalization bounds of the popularly used iterative hard thresholding (IHT) algorithm (Yuan & Li 202I). The uniform stability bounds on SGD have also been extensively used for designing differential privacy stochastic optimization algorithms (Bassily Feldman et al. 2020).
ct al. 2019
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 without- replacement sampling (Bühlmann) 2012). The stability and generalization bounds of bagging have been analyzed for both uniform (Elisseeff' et al., 2005) and non-uniform (Foster et al., 2019) av- eraging schemes. Unlike these prror results for bagging with averaging aggregation, our bounds are obtained based on a soffidence-boostine greedy aggregation scheme which turns out yield sharper dependence on the uniform stability parameter.
The munfidence-boostiin technique has long been applied for obtaining sharp high-probabblity ex- cess risk bounds from the corresponding strong in in-expectation bounds (Shalev-Shwartz et al.) 2010) Mehta 2017). For generic statistical learning problems, confidence-boostingg has been used to con- vert any low-confidence learning algorithm with linear dependence 1/0 to high-confidence algorithm with logarithmic factor log) For learning with exp-concave losses, a relevant ERM estimator with in in-expectation fast rate of convergence algorithm with an almost identical fast rate of convergence up to a logarithmic factor on 1/5 (Mehta) 2017). While sharing similar spirit of boosting the confidence, our generalization analysis is sub- stantially more challenging than those prior excess risk analysis in terms of tightly deriving in- expectation first moment generalization bound for uniformly stable randomized algorithms.
converted to high-confidence learning
6 CONCLUSIONS
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 nut- shell, our main results in Theorem | and Theorem 2 reveal that a carefully designed subbagging process in Algorithm [ can yield high-confidence generalization and risk bounds under the notion of mean(- -esss-uuueeuuitttooi
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 logarith- mie factor on sample size from the best known bounds. While sharper in the dependence on sample size, our confidence-boostin A over K disjoint training subsets of equal size with K x log (t). 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 al. (2020) for future investigation.
results are only applicable to one of the independent runs of algorithm
9

---

Under review as a conference paper at ICLR 2022
REFERENCES
Savina Andonova, Andre Elisseeff, Theodoros Evgeniou, and Massimiliano Pontil. A simple algo- rithm for learning stable machines. In ECAL, pp. 513-517, 2002.
Peter L Bartlett, Michael I Jordan, and Jon D McAuliffe. Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101(473):138 136.118886666, 2006.
Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Thakurta. Private stochastic convex optimization with optimal rates. arXiv preprint arXiv:/908.099
2019.
Raef Bassily, Vitaly Feldman, Cristobal Guzman, and Kunal Talwar. Stability of stochastic gradient descent on nonsmooth convex losses. Advances in Neural Information Processing Systems, pp. 1-10, 2020.
Yoshua Bengio, Ian Goodfellow, and Aaron Courville. Deep learning, volume 1. MIT press Mas- sachusetts, USA:, 2017.
Léon Bottou and Olivier Bousquet. The tradeoffs of large scale learning. In Advances in Neural Information Processing Systems, pp. 161-168, 2008.
Olivier Bousquet and André Elisseeff. Stability and generalization. Journal of Machine Learning Research. 2(Mar):499-555) 2002.
Olivier Bousquet, Yegor Klochkov, and Nikita Zhivotovskiy. Sharper bounds for uniformly stable algorithms. In Conference on Learning Theory, pp. (10-626, 2020.
Leo Breiman. Bagging predictors. Machine learning, 24(2):123-144, 1996.
Peter Bühlmann. Bagging, boosting and ensemble methods. In Handbook of computational statis- tics, pp. 1022. Springer, 2012.
Zachary Charles and Dimitris Papailiopoulos. Stability and generalization of learning algorithms that converge to global optima. In International Conference on Machine Learning, pp. 453, 2018.
Luc Devroye and Terry Wagner. Distribution-free inequalities for the deleted and holdout error estimates. IEEE Transactions on Information Theory, 25(2):202-2077 1979.
Andre Elissefff, Theodoros Evgeniou, and Massimiliano Pontil. Stability of randomized learning algorithms. Journal of Machine Learning Research, 6(Jan):55-79, 2005.
Vitaly Feldman and Jan Vondrak. Generalization bounds for uniformly stable algorithms. In Ad- vances Neural Information Processing Systems, pp. 9747-9757. 2018.
Vitaly Feldman and Jan Vondrak. High probability generalization bounds for uniformly stable algo- rithms with nearly optimal rate. In Conference on Learning Theory, pp. 1270-1279, 2019.
Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: optimal rates in linear time. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pp. 439-449, 2020.
Dylan J Foster, Spencer Greenberg, Satyen Kale, Haipeng Luo, Mehryar Mohri, and Karthik Srid- haran. Hypothesis set stability and generalization. In Advances in Neural Information Processing Systems, 2019.
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International Conference on Machine Learning, pp. 1225-1234, 2016.
Nicholas JA Harvey, Christopher Liaw, Yaniv Plan, and Sikander Randhawa. Tight analyses for non- smooth stochastic gradient descent. In Conference on Learning Theory, pp. 1579-1613. PMLR, 2019.
Sham M Kakade, Karthik Sridharan, and Ambuj Tewari. On the complexity of linear prediction: Risk bounds, margin bounds, and regularization. In Advances in Neural Information Processing Systems, pp. 793-800, 2009.
10

---

Under review as a conference paper at ICLR 2022
Yegor Klochkov and Nikita Zhivotovskiy. Stability and deviation optimal risk bounds with conver- gence rate o(1/n). In Advances in Neural Information Processing Systems, 2021.
Ilja Kuzborskij and Christoph Lampert. Data-dependent stability of stochastic gradient descent. In International Conference Machine Learning, pp. 2820-2829, 2018.
Yunwen Lei and Yiming Ying. Fine-grained analysis of stability and generalization for sgd. In International Conference Machine Learning, 2020.
Yunwen Lei and Yiming Ying. Sharper generalization bounds for learning with gradient-dominate objective functions. International Conference on Learning Representations, 2021.
Tongliang Liu, Gábor Lugosi, Gergely Neu, and Dacheng Tao. Algorithmic stability and hypothesis complexity. In International Conference Machine Learning, pp. 2159-2167. PMLR, 2017.
Llew Mason, Jonathan Baxter, Peter Bartlett, and Marcus Frean. Boosting algorithms gradient descent in function space. In Advances in Neural Information Processing Systems, pp. 512-518, 1999.
Nishant Mchta. Fast rates with high probability exp-concave statistical learning. Artificial Intelligence and Statistics, pp. 1085-1093, PMLR, 2017.
Sayan Mukherjee, Partha Niyogi, Tomaso Poggio, and Ryan Rifkin. Learning theory: stability is sufficient for gencralization and necessary and sufficient for consistency of empirical risk mini- mization. Advances in Computational Mathematics, 151--3) 2006.
David Opitz and Richard Maclin. Popular ensemble methods: An empirical study. Journal of Artificial Intelligence Research, 11:169-198, 1999.
Alexander Rakhlin, Ohad Shamir, and Karthik Sridharan. Making gradient descent optimal for strongly convex stochastic optimization. In International Conference on Machine Learning, pp- 1571-1578, 2012.
William H Rogers and Terry J Wagner. A finite sample distribution-free performance bound for local discrimination rules. The Annals of Statistics, pp. 506-514, 1978.
Robert E Schapire. The strength of weak learnability. Machine learning, 5(2):197-227) 1990.
Mark Schmidt, Nicolas Roux, and Francis R Bach. Convergence rates of inexact mooximal-gradien methods for convex optimization. In Advances in Neural Information Processing Systems, pp. 1458 1466, 2011.
Shai Shalev-Shwarzz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Stochastic convex opti- mization. In Conference on Learning Theory, 2009.
Shai Shalev-Shwarz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Learnability, stability and uniform convergence. Journal of Machine Learning Research, 11(0ct):2635-266 2670, 2010.
Giorgio Valentini and Thomas Dietterich. Low bias bagged support vector machines. Interna- tional Conference on Machine Learning, pp. 752-759, 2003.
V.N. Vapnik and A. Ya. Chervonenkis. Theory of Pattern Recognition [in Russian]. Nauka, 1974.
Kiao-Tong Yuan and Ping Li. Stability and risk bounds iterative hard thresholding. Interna- tional Conference on Artificial Intelligence and Statistics, 1702-1710, PMLR, 2021.
Tong Zhang. Leave-one-out bounds for kernel methods. Neural Computation, 1 1377-133711437 2003.
Yi Zhou, Huishuai Zhang, and Yingbin Liang. Understanding generalization enror of sgd in non- convex optimization. In International Conference Acoustics, Speech, and Signal Processing (ICASSP), 2019.
11

---

Under review as a conference paper at ICLR 2022
A AUXILIARY LEMMAS
We need the following lemma from Hardt et al. (2016) which shows that SGD iteration is non- expansive convex and smooth loss.
Lemma 2 (Hardt et al. (2016)). Assume that f is convex and L-smooth. Then for any w, w/ E W and a & 2/L, we have the following bound holds
IC aV aV)(w) - (w' - aVV((w))) < I|w w'll
The following lemma, which 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 (ur1r21 satisfies the following recursion for all t 2 1:
u S S + Σ U
1=1
with {S+) (5+1r21 an increasing sequence, So 2 ug and a, 2 Offor all T. Then, the following inequality holds for all 2 1:
u S / S Σ a,
B PROOFS FOR THE RESULTS IN SECTION
In this section, we present the technical proofs for the main results stated in Section
B. PROOF OF LEMMA 1
We need the following lemma essentially from Bousquet et al. (2020) that provides first moment bound for the sum of random functions.
Lemma 4. Let S 121, Zz.... IN3 be set of i.idd. random variables valued in Z. Let 91..... IN be a set of measurable functions gi z + E that satisfy Es (8)] < M² and Ez, [g. (S)] for all i E [N.. Then we have
Es
Σ 9.(
Σ itj
Es Es,so) ((o(S)-9.(S()))) ((( MVN,
where {(3 = 25-1, Bi Lst1, from the same distribution that of S.
IN} and S' {21 B2.... E'y is another i..d. sample
Proof. We reproduce the proof in view of the argument in Bousquet et al. (2020 Section 5) showing that {g.} are weakly correlated. For any # j, since Ez, (S)) and Ez, E2,19,(5 [S)] O, we can verify that
Es ( Esyz Ez, (S( (S) | S 23] = Esiz, (a:((()) Ez, (o)(S) S 2i] 0,
where we have used the independence of the elements in S [Z Similarly, can show that
Es ( = Es (Q(S)))), 0.
Then it follows that for any i + j.
Es (g, (S)] = Es, [g(()))
Es.st, (u)
(ax(5) - (((55)) - ()(())))]]
[(:(S) ((S()))((s(s)) (S
Eg
12

---

Under review as a conference paper at ICLR 2022
Based on the above bound and Jensen's 's inequality we get
N
Es
Σ
(5)
Σ (:(5) )
N
Es (S)gg Es [S]
Σ
t=1
Es ,60 [[()(()) - -() -) + MVN
[(0((5) (((S)))) + (gr(5) ()( MMN
E ,00)
(a:(5)) - (.()))) o + MVN.
This proves the desired bound.
Now we are ready to prove the result in Lemma I
Proof of Lemmal 7 Let us consider (s(S) R(A(S)) ((A(S); Z,) and g:(S) h:(S)
Ez, (S)) for E [N]. Then by assumption we have
Eg, (S)] = 0, L9 (8) S M
For each E [N], let 5(() denote a random data set that is identical to S except that one of the 7; is replaced by another random sample Z For any + j. since the loss is non-negative and G-Lipschitz, can be verified that
(g:(S) (5) ((((5))) S &max| max
[M((S) h2( (B2 (2, ni(sunn)1 [||A(S)- A(S Ez, [G]IA(S) - A(SU))))}
which readily implies
(a(()) - -.(s()))))
Eg,st) [G9|AA(S) A(S6i\113]
Eg
Then invoking Lemma
to {gi) yields
Es
(c)
Es, (0.(()) - 9:())) MVN
(A.1)
SG
E Eg,s [I|A(S) A(S6))|1) MVN.
Further, it can be verified that
N
Es
Ez, [s{
= EEs
Bz ((A(S)))
(A.2)
-Es
Ez, ( 2,)1
N
=Es
Ez, [2]1((A(S); 2) - (22((())))) |7)1
G[IA(() - A(S |
<Es,s0
13

---

Under review as a conference paper at ICLR 2022
By combining equation A.1 and equation A.2 obtain
EAS [R(A(S)) - Rs(A()))
1
EA,S
Σ (0: B2, (M))))
N
G
EA
S - A(S
+
G - N
E A,s,st [IAA(S)
A(S(i)I|
M
N
VN
G
E A.S [[A(S) - A
BAS,SS
[IA(S)) - A
M
VN
itj
M IG /G G/,,N
VN'
where in the last inequality we have used the stability conditions on A. The proof is completed.
B.2 PROOF THEOREM
We first establish the following intermediate result that captures the effects of subbagging ran- domized algorithms: it basically tells that with K x (og()), at least one the solutions generated by subbagging generalizes well with high probability.
Lemma 5. Suppose that randomized learning algorithm A ZN W has "n. N mean--niform stability and "im .N mean-squar uniuuor stability as well. Assume that the loss function is G- Lipschitz with respect to its first argument and is bounded in the range [0, M). Then for any a, over the randomness of {(Ar, 3x))K)(
(0, 1) and K 2 1-a
log(2/6), with probability at least
the sequence (Sx) TMEKK generated by Algorithm 7 satisfies
K N
min (SA) - Rss (Ac(S))) & kE[K]
G G + GYa + M
Proof. From Lemma we have that randomized algorithm A and data S with |Š|
N
k
K EAS ( R3(A())) S / + M N
Since {Ae, So SKEEK independent to each other, by Markov inequality we know that
K
))
P(A
min (SA)) - Rs. (Ax(5))) G Tn. N + + + M
N
S K 28
KE(K]
which implies the desired bound.
Next we proceed to prove the main result in Theorem
Proof of Theorem
7 Let consider the following three events:
K M
K log(K/5)
E
(R(AA-(Sx))) Rs(AA aK
G THP + G. xxx
MM
N
(K - IKN
Klog(K/8)
3 := max (S{A)(s)) - Rsys, (Au(S))) & MV
kE[K]
(K 1
=2:= min
IR(A (Sx)) - (An S
G G + G.m. x + M
kE[A]
N
14

---

Under review as a conference paper at ICLR 2022
We can show that 3 2 & Azg Indeed, suppose that & and & simultaneously occur. Consequently the following inequality is valid:
R( Ax- (Sk.))
(s(A (St+))l
1
K-1
R(A (Sk-))
Rsy (Ag- (SL-))
s (A (Sx-))
K
K
K-
$
|R(A (Sk-)) RS (Sk-(Sk=))
(RAAx((Sk-) - Re (A (Ak-(5k-)
K
K
[RSYSL (Ax- (Sk-)) RS (Ak- (Sa-) )) + R(Ax- (Sk= Resss (A (5k- ))
K
G
1
min
(Ax(s)) RS, (Ax + R(A (Sk-)) REY.E (Ak- (Sk-)
K
KE[K]
min K KE[K]
|Rss (A&(SW) R(AN(S)) + R(A+(S))) Rs. (Au(SA))
+ |[(A= (Sk-)) R (At- (Sx-))
$ K KE[K]
min (R(AA((E)) Rs. (Sa)) + max KE(K)
Rays (Ax(S)) R(A+(5)))
K
+ | (St-)) R. (A (Sx-))
min (R(AA(SE)) Rs. (Su()))) KE[K]
max [(()(Ss)) (Au RE[K]
K
K
1 aK
(G/TuRx
K
K log((//)
G + M
+ M
N
(K 1)N
where in "Si we have used the definition of k", and "Ç2" follows from &g, E2. With leading terms preserved in the above we can see that & occurs.
Next we can show that TP (( (E1) S ./ Toward this end, us consider the following events for all [K]:
E - (-IIIAAA(SA)) Rey. (A&(S))) & M
K (o)((K/)) (K - 1)N 1IN
Clearly, is true that & -K E is sufficient to prove that PS,At Ek
S 5 holds for each
2K
A E [K]. Indeed, consider the random indication function (SS, ;= 1 gx associated with the event E/. Then we have the following holds for each k E [K]:
PS.AL E
A,S,A, [B(S, Ax)1
-EA..S Sa
ES [3(S, A&) Ak, Sx]l
2 ARAs Ak.
Esvs. (B(S,AR) AR, SR]
K log(K/8) [K 1)N
(R())((k)) Rsys. (Av(Sa)) M
Ak, Sp.
5
LBA. S
|k, Sk
2K
2K'
where in "Si" we have used the independence between {Ax, Sk} and S \ Hoeffding's 's inequality conditioned on {Ak, Sx), keeping in mind that A (Sx) is independent the data set S S₁ of size (1 -1-1/11 L/KKNN It follows by union probability that
Sr. and "C2" is due to
K
K
5
Ps.(A)) EE = -Ss(AA)
U k=l
<
PS.AA
E3
<
2
15

---

Under review as a conference paper at ICLR 2022
Further, from the part(b) of Lemma we have Ps, (s. (E2) s Combining this and the preceding bound yields
8
(s.(AA) (E) S.(A)) (& (2)) 21 - (..(AA)) (E)) -P,,(A,) ( (6
1 5.
2
This implies the desired result in part(b) K/(K 1) S f K 2 2.
B.3 PROOF OF THEOREM 2
We first present the following simple lemma about the in-expectation risk bounds of randomized algorithm which will be used in our analysis.
Lemma 6. Suppose that randomized learning algorithm A zN W has "In,N te.x-meennuniffon 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") S GT + Dopr
Proof. By risk decomposition we can show that
EA.S [R(A(S) ((is)))R(w"") R(w")]
-ASS [R(A(S)) - Rs(A(S)) + Rs(A(S)) Rs(w") + Rs(w") [R(w")]
< EASS (R(A(S)) Rs(A(S))] Aopt
SG7,,N + Dopt:
where in the last inequality have used the on-average generalization bound by Hardt al. (2016) Theorem 2.2).
Lemma 7. Suppose that a randomized learning algorithm A ZN + W has "nn no.x-mean-uniform stability. Assume that the loss function is G-Lipschitz with respect to its first argument. Then over the randomness of
for any a, 10, and K 2 1-a
(2g(2/8) with probability at least
{(AR, S4)]ME(K] the sequence (Sk)SR) generated by Algorithm 7 with the modified output satisfies
min ((A)(Sk)) R((w" S (( kE(K]
1 (Grin + Anp
Proof. Recall the modified output A&- (Skx) where het arg minke[k] (Ac((e))()))) From Lemma 6 we have that over randomized algorithm A and data Š with (S| K
E A. R(A(S)) R(w") < GYm, & + Appt-
Since (Ac, are independent to each other, by Markov inequality we know that
((A..Sa) min R(A,(S)) R((")()))))))))))))())) 1 (Grmm + Aox sak 5
kE[K]
which implies the desired bound in part(b).
Next we proceed to prove the main result Theorem
Proof of Theorem
Let consider the following three events:
1 (Sx-) Rs(AA (St. (11)))) a (0% Aup)) M
K log( K/0)
3
(K - 1)N
(log(K/))
Σ1 = max (SA)) - (ssss((A & MV (K 1)N
kElK]
R(Ax(S))) - R(ww) (rrm + A
& = min
kE[K]
16

---

Under review as a conference paper at ICLR 2022
Similarly, we show that 3 2 & n &g. Indeed, suppose that &1 and &g simultaneously occur. Conse-
quently the following inequality is valid:
R(AA (Sx=)) R(w=)
= -R(AA (5 RS (Ax- (Sk=)) + Re (Ak (Sxx)) R(w")
2 R(AA (8k-)) R (Ax-(Sk-)) min Rsys, (Ax(5)) R(w") kE[K]
=R(A -Rx))=(Sx))) RSV (Ap-(Sk-)
min kE[K]
(R - ((AA(SE)) + R(AA(SE) R(w*)}
- min (R(AA(())) R(w")) + max Rsv.. (As(Sk)) - R(AR(S))) k
kE|K]
K log (K/5)
Gmm, + Dop) M
(K 1IN
where in "CI" we have used the definition of k", and "G2" follows from & &2. With leading terms preserved in the above we can see that occurs.
Based on the same proof argument as that of the part(b) of Theorem I we can show that
(. ) (E1) S 3. Further, from the part(b) of Lemma we have PSSAA)) ε2) ing this and the preceding bound yields
Combin-
8
(.A)))) (E) 2 (s (&1 N& 21 - -Ps.AA) (E) - P..(AA)(()) 21
2
2
This implies the desired result in part(b) as K/(K - 2 K 2 2.
C PROOFS FOR THE RESULTS IN SECTION
In this section, we present the technical proofs for the main results stated in Section
C.I PROOF OF COROLLARY
We begin with presenting and proving the following lemma that gives the mean(-square)-unifoo stability bounds for Agac v on convex and smooth loss functions such as logistic loss.
Lemma 8. Suppose that the loss function is E(:5.) is convex, G-Lipschitz and L-smooth with respect its first argument. Assume that T) < 2/ L for all 2 1. Then A gGD has mean-uniform stability
such that
sup E Am AlA vSS) - Aoeo (S))ll < S
2G N
Σ nt
EE(T)
and has mean-square-umffom stability such that
40G²
T
T
sup Esssor (eAsso-((S) - Asco Asco--(S'))1
Σ
N
N
$
Proof. The first mean-uniform stability bound can be straightforwarddy derived based on the argu- ment of Hardt et al. (016)) Theorem 3.7). We focus on proving the second mean-square mean-square-uniform stability bound. For any pair of S, S', let us define the sequences {w, he(()) and (w/he(rr that are respectively generated over S and S' via AseD-z via sample path & = (E, hee()- Note by assumption that wp = w/- We distinguish the following two complementary cases.
Case I: zg, = In this case, by invoking Lemma 2 we immediately get
||w w1 [[ (w; nh Vnll( (g.)) - -w n =
10:+11 - 7/8 V (w 25.) (w/_1 - m1 V (
(A.3)
|1:1 - 12
17

---

Under review as a conference paper at ICLR 2022
Case II: 2g. # z In this case, we have
| w/ll? ||llw (1-- T/ V.())) -a
aV
[ - 176 V ( 24.) (w/_11 7/1 V V (w ))
(1|u=11 - w/-1ll + 7/ V (o((wrr1: zt,) + w C( (w/ [
(A.4)
[1 - w/-1ll + 2G11)
W1-1 - w/-111 4G1/, |t-1 - w/-1ll + 4G vf
where in the last but inequality we have used ((::) is G-Lipschitz with respect to its first argument.
Let Bg = (S, == 1 { + be the random indication function associated with event "g. *
" Based on the recursion forms equation A.3 and equation A.4 and the condition wo = wó we
can show that for all t 1,
| wfll 12 S Σ AGB-nrll-- - wi-1ll +
Σ 4G 1G3
Then applying Lemma with simple algebraic manipulation yields
)
2
||w, w/ll2 s 8G2
Σ
3 +4
Σ 3
Since by assumption S and S' differ only in single element, under the scheme of uniform sampling without replacement, we can see that (e () ~ Bernoul (1/N((1))))))) and (B,(8, ()) is an i.idd sequence of Bernoulli random variables. It follows that
Ean [|we-=W('
-
Ee 18r)1/ + +4BEH1 Σ 3r01 (1)
<8G²
=8G2
Σ
Esny 18, + 4,62 + Σ
IEg 13. N=TT
ryttr
=8
5
+
Σ Dr
40G²
1
Σ
2
Σ
N
N
T=1
where we have used Eg, [B:]]
Ex, [88]]
N.
The convexity of squared Euclidean norm leads to
Σt"
Esn [| w[ll
1
T
Eg [1 1-
40G
Σ
T1
T
N
N
t=1
Note that the above holds for any S = S², i.c.
))
40G²
sup
Be -1
Σ
M
+ N
Σ
m1))
N
s
t=1
The proof is concluded.
With Lemma 8 in place, we are ready to prove Corollary
Proof of Corollary 7 From Lemma g we know that Asco-u has mean-uniform stability with param- eter
2G
No.N
N
EE[T]
18

---

Under review as a conference paper at ICLR 2022
and wwtssssuuurr-uooonnn stability with parameter
40G²
Σ
n
Σ
T
n
N
N
The desired results then follow immediately via invoking Theorem 1 with a = =1/2.
C.2 PROOF OF COROLLARY
We first establish the following lemma the mean(-square)--uiffmm stability of Agan-u in the of non-smooth convex loss.
Lemma 9. Suppose that the loss function is l(-:-) is convex and G-Lipschitz with respect its first argument. Then Agso-v has mean teaa-uniform stability such that
4G
T
sup A (1Asco-v(S)) - x S 2G $ig
nt
N
t=1
t=1
and has mean-square-unfoone stability such that
T
32G²
T
2
sup EA $=
[1-Aso-- - Asso (SS') < 40G 2
11
1/
N2
Proof. Let us define the sequences {wr her and {wt he(r] that are respectively generated over S and S' via AseD-w via sample path { = {Et hETT. Suppose that S' and consider a hitting time variable to = inf(t: ze, + F. Let Br = (s, == 1 (,,, be the random indication function associated with event zee + z Conditioned on lo. has been shown by Bassily et al. 2020 Lemma 3.1) that
|ml
w/ll s 2G
Σ
+ 4G
Σ r=fo+1
B S 2G,
Σ n
4G Σ
3r0r.
(A.5)
r=to
Then we can show the following for s
4G
Es
[||er w/ll - 2G
7
7
where we have used the fact that {.,}} an i.i.d. sequence of Bernoulli(I/N) random variables. The convexity of Euclidean norm leads to
Egg [|]e,
will
4G
ExT
[|] why |l]
2G,
Σ
which is the first desired bound. Similarly, based on the square of the bound equation A.5 show that
we can
EGg [l|w; - ww(l?
<BgH
SG Σ
11 +
326
Σ 8
-
17 T
Σ
8311 + Σ
88G
1/ 320²
1
7F
Σ
Tr
N
N2
T=1
TfTT!
2
320²
<40G2 2
1/r +
Σ
T/
N2
7=1
r=1
19

---

Under review as a conference paper at ICLR 2022
where we have used Bg, [B6]
Eg, [B]]
N. It follows directly from the convexity of loss that
T
32G
2
REm [1lØr - w1|19]] v 40G
1/1
+
Σ
7/1
N
The proof is concluded.
Equipped with Lemma we are now in the position to prove Corollary 2
Proof of Conollary From Lemma we know that Asco-e with non-smooth convex loss has saaan-ssurre--niioinn stability with parameters
T Σ 1=1
4G
T
32G
N 2G
11
Th
40G
11
2
N2
Σ
1/1
t=
t=
The desired results then follow immediately via invoking Theorem Twith a 1/2.
C.3 PROOF OF COROLLARY 3
We first establish the following lemma on the mean(ssquare)--uiffom stability of Asco-w in the considered non-convex regime.
Lemma 10. Suppose that the loss function is E(::)) is G-Lipschitz and L-smooth with respect its first argument. Consider nr I L/L. Let
2 + 11
27
exp
L
Tr
i=r+1
for all 1. Then Asea-w has mean- aeennuuiffom stability such that
2G
T
T Σ
sup EA [[AAsc-u(S)) Asco-v(S')ll
exp
L
177
nr:
N
$=S'
1=
and has mean-square-umifor stability such that
4G2 N
sup A (1 - Asco- S
exp
3L
Σ
7
ut-
SES'
T=t+1
Proof. Let us define the sequences {w: heee and {w/her that are respectively generated over S and S' via Asen-w via sample path & = (&heejz) Suppose that S = S'. Let us consider A. = Esμ [l], - w/ll. Then based on the arguments of Hardt et al. (2016) Theorem 3.8) we know that with probability 1 & over &.s l|w, - w/ll < (1+m.L)]lar
w/ and l|w, w/ll s
||:=1 - w/-1ll + 2GT, with probability 1. Therefore we have
A -
(1 + 11-1 N
(A.-1 + 2Gm)
N
(1
1
2Gm
(1+mLL) MLL)
(1 (1+
+ N
A +
N
N
2Gt
1+
1
1
MeL
A A--1+ +
N
N
(11 N
2GT
cxpp
M
A
N
2Gm
(exp(nLL)
A +
N
20

---

Under review as a conference paper at ICLR 2022
where we have used 1 + I exp(x). Then unwind the above recursion form to obtain that for all 2 1,
2G
2G
A
II exp (n.L)
exp
L
?
(A.6)
N
r=1
1=++1
i=++1
where we have used Do O. The convexity of Euclidean norm leads to
1= Eu I|
w/ll]
2G
T
BEm
U J4y
exp
L
Σ
T
r=t+1
which immediately implies the first desired bound as it holds for all S S
To show the mean-square-unifom stability bound, let us consider Å. := Eg [||00 - w/|l Then
verify that with probability x over &x. l| w/ll (1 77 I.) | w/-1 2 and
with probability N
||w - w/ll & (1lwe-1 w/-111 2Gr1)² 11 - w1-111 + 4Gm: - w/-1l1 + 4G2 n1:
Therefore we have
Á
1 1 1 N
(1
(1+
1
( 40m + 4G
N
(11-1)
1
4G P N
1-1
1-1
(1
1 + N
2 + 217
exp
L
nT
T=1
1
M5
1
4GPut
1+
1
(2 L2)
N
N
exp (1
1
(2 11-33)
Ac-1+ +
4G
N
N
4G2u
eexp (2n, + n 1.) A
N
where in the second inequality we have used the bound equation A.6 on A. Recall that Ån 0. Then we can unwind the above recursion form obtain
A 4G2
4G N
Σ II exp (2n,. + 1, ur 1=T-1
Σ
exp
3L.
Σ
Di
Ur:
r=1
(=++1
where we have used 7) S 1/L. follows immediately from the convexity that
Benny [| - 11 Σ B [lle w|ll?]
4G
T
T
exp
3L
Σ
Ur
uss
N
r=t+1
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 Asco-w with smooth non-convex loss has
mnean(ssquare--unifon stability with parameters
2G
4G2
Nn
exp
L
Σ
Tr
mp-
N
exp 3L
Σ 7r
Us.
T=f+1
r=1+1
The desired results then follow immediately via invoking Theorem
i with 1/2.
21

---

Under review as a conference paper at ICLR 2022
Algorithm 3: SGD via Without-RReplacement Sampling (AsCD-wo)
lid. ~ DD, step-sizes (m #iterations T, initialization wip. Input Data set S = [ZikeIN]
Output: Uy + Σ W/.
for t= 1....... do
Uniformly randomly sample an index & E [M] with or without replacement;
Compute w/ Ilw (w:-1 The 1i
end
D AUGMENTED RESULTS FOR SGD UNDER WITHOUT-REPLACEMENT SAMPLING
In this section, we further consider applying our main results in Theorem to the variant of SGD under without-replacement sampling (Asep-wo), is outlined in Algorithm 3 For the sake of sim- plicity and readability, we only consider single-epoch processing with T < N, and we focus on the case where the loss convex but non-smooth. The extensions of our analysis to multi-epoch pro- cessing, i.e., T < rN for some integer 2 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 the micann-square)-niiie stability of Asco-wo which can be easily proved based on the result from Bassily al. 2020 Lemma 3.1).
Lemma 11. Suppose that the loss function is E(33) is convex and G- G-piscchizz with respect to its first argument. Consider T S. N. Then Asso wo has mean- rrean-unifom stability such that
2G N
T Σ
sup As [llAggo-wolf (S) As6o- no (S') S=S'
2
m
fo=1
t=to
and has waassssuuaar-uffffrn stability such that
4G
T
T
sup E EAS [l w S s=ga
m
Proof. Let (T and WT(S', {) respectively be the output generated over S = [ziie and S' = (=(]ie[N) by Asac-v via sample path & = hEhee()) Recall that T & N. Let us define a hitting time variable to = inf(t: ze, & Z Since S the uniform randomness of & implics that
P (to j]
je [N]
N
Given E (T), it follows from Bassily et al.
2020
Lemma 3.1) that
w|w, w/ll
< 4G2
n
T
T=t0
Then we have
402
4G
Egg [llwe] w/
Σ
Σ
T
N
N
t0=1==to
10=1 r=to
The convexity of squared Euclidean norm leads to
Σ
will?
T
Bam [| - w'y [12] <
T
N
=
tatto
Similarly we can show
T
2G
Egn 11]TT
w -
T
N
t=to
The proof is completed.
22

---

Under review as a conference paper at ICLR 2022
The following result is direct consequence of Theorem | when invoking Algorithm AseD-wo with non-smooth convex loss.
Corollary 5. Suppose that the loss function is E(-;)) )) is corvex and G-Lipschitz with respect to its first argument, and is bounded in the range of [0, M). Consider Algorithm D specified to Ascr-wo
with T S N. Then for any E (0,1) 1) and K 2 2 log(()) with probability at least å over the randomness of S and {Aseo wo,k so,k)k the output of ASeD we satisfies
IR(Asco-wo, (Sk-)) Rs(Ascc-woot (Sk= ))1
T +
G
T
T
logí K/8)
SC2
M
Th
m
M
N
to=1t=to
f0=1
t=to
Proof. From Lemma 11
we know that Asec wo has mean-ssquare)--nifom stability with parameters
2G
4G2
No
m
n
The results then follow immediately via invoking Theorem ! with 1/2.
Remark 9. Specially for constant learning rates = 17 Corollary S admits high probability generalization bound of scale O
+
1og(1/6)
For general time varying learning
VN
N
N
rates, our bound in Corollary 5 still holds with high probability. For example, when ny x 1. the
generalization bound scales as
(v
/og((T) N
log(1/8) with high probability.
N
23


Reviews:
[{"review_id": "hM2Ygyg4M3_", "reviewer": "Reviewer_Ufmg", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Comments:  \n\n1. In Corollary 1 2 and 3, Consider Algorithm 1 specified to $A_{\\text{SGD-w}}$ is unclear to me, and $\\{A_{\\text{SGD-w},k}\\}$ is not defined. In my understanding, $A_{\\text{SGD-w}, k^*} (S_{ k^* } )$ is the output of SGD with subbagging process in Algorithm 1, and Algorithm 2 is seems to redundant here. Did I imiss something ?\n\n2.  In the proof of Corollary 1 2 and 3, the authors should clearly state that they put $\\gamma_{m,N/K}$ and $\\gamma_{m^2,N/K}$ instead of $\\gamma_{m,N}$ and $\\gamma_{m^2,N}$ back into Theorem 1, and the bounds are related to $K$ which cannot be ignored. In addition, in the statements of corollaries, setting $\\alpha=1/2$â should be added. \n\n3. In Remark 6, choosing $K\\asymp\\log{(1/\\delta)}$ and $\\eta_t=1/\\sqrt t$, the high probability generalization bound should be dominated by $O\\left(\\sqrt{\\frac{\\log{(T)}}{N}}+\\frac{\\sqrt T+\\sqrt{N\\log{(1/\\delta)}}}{N}\\right)$. \n\n4. In Remark 8, the stepsize is chosen to be $\\eta_t = O({1\\over t^{1+\\nu}})$ which seems not right, since the stepsize should satisfy $\\sum_{t=1}^\\infty \\eta_t =\\infty$. Is this the artifact of the proof in the nonconvex case? \n\n\nMirror comments: Page 4 paragraph 3, $\\gamma_{m,N/K}$ and $\\gamma_{m^2,N/K}$ have not been defined before. Page 12, in Lemma 4, $h_i$ should be $g_i$.\n \n", "summary_of_the_paper": " 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. ", "summary_of_the_review": " The paper proposed to use the confidence-boosting/bagging techniques to boost the dependence of learning algorithm from $1/\\delta$ to $\\log (1/\\delta)$.  Specific applications to SGD are derived.   Overall, the paper is well written and the results are new and interesting. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "gZDYrGOKqyx", "reviewer": "Reviewer_LQgS", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "strengths :\n(1.) This paper has nice writing and a clear organization.\n\n(2.) Existing generalization bounds of randomized algorithms are often derived in expectation. Although some work uses the Chernoff bound of Bernoulli random variables to derive the high probability bound, the authors provide improved ones in this paper. \n\n(3.) I checked the proof, which seems to be solid.\n\nConcerns:\n(1.) The subbaging process requires an enormous computational complexity. When the authors apply it to SGD, it occurs to me that the high probability generalization bounds are derived for a variant of SGD, not the vanilla SGD. \n\n(2.) Some proof steps in Page 15 between $\\mathbb{P}_{S,A_k}(\\bar{(\\mathcal{E}_1^k)})$ and $\\frac{\\delta}{2K}$ are confused. The authors can make a detailed explanation to improve their paper’s impact.\n\n(3.) The authors discussed that Lemma 1 is inspired by (Bousquet et al,. 2020). In the proof of Lemma 1, Lemma 4, a basic lemma, is a first moment bound for a summation of random functions, while Theorem 4 in (Bousquet et al,. 2020) are derived for $p$-th moment bound with $p \\geq 2$. I do hope the authors can explain why they derive the first moment bound. Is it an essential step to the proof? In my opinion, the $p$-th moment bound can be employed to derive $1/n$-type bound (Klochkov and Zhivotovskiy, 2021). The first moment bound may limit its application to derive sharper bounds.\n", "summary_of_the_paper": "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.", "summary_of_the_review": "Overall, the authors proposed an interesting idea to improve the stability-based generalization bound for randomized algorithms. I thus tend to comment for acceptance.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "fMAy3TQEdEU", "reviewer": "Reviewer_F7yX", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\n1. The problem of showing tighter generalization bounds for uniformly stable algorithms has seen exciting work recently, and the paper makes solid contributions to this directions.\n\n2. The paper is quite well-written. It discusses the prior work properly in context, provides sufficient intuition for their results and is generally quite easy to read.\n\n3. It's nice that even thought the framework is developed for randomized algorithms, it yields some tighter bounds for previous deterministic settings as well. This makes it seem a bit less specialized.\n\nWeaknesses:\n\n1. Continuing from the previous point, one could argue that the results in the paper are a little bit specialized. They hold for a specific regime of SGD, and though the authors do provide context about the importance of the results, perhaps a bit more discussion, discussion of the open problem from previous work and how the paper is concretely making substantial progress on it would be helpful.\n\n2. It's a bit unsatisfying that the bounds don't hold for SGD itself, but instead for the confidence boosted procedure which Alg. 1 develops. Do the authors believe that this is necessary? Is it possible to show the high-probability results for SGD itself?", "summary_of_the_paper": "The paper considers the problem of showing tight generalization bounds for randomized uniformly stable algorithms. The key contributions are the following:\n\n1. 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.\n\n2. 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.\n\n3. Finally, the paper shows that though the framework is developed for randomized algorithms it obtains tighter bounds for deterministic algorithms as well.", "summary_of_the_review": "Overall, this is a well-written paper which uses interesting techniques and makes decent progress on an interesting problem, and hence I am in favor of acceptance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "c3g5-ee-JlK", "reviewer": "Reviewer_jM1w", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper makes progress towards answering, for randomized\nalgorithms with on-average uniform stability, such as stochastic gradient descent\n(SGD) with time decaying learning rates, wheter\nthese deviation bounds still hold with high confidence over the internal randomness of algorithm.\n\nHowever clarity can be improved in showing how far paper's results are from lower bounds.", "summary_of_the_paper": "The paper first establishes an in-expectation first moment generalization error bound for\nrandomized learning algorithm with on-average uniform stability, based on which\nit then shows that a properly designed subbagging process leads to near-tight high\nprobability generalization bounds over the randomness of data and algorithm. It\nfurther substantializes these generic results to SGD to derive improved high probability generalization bounds for convex or non-convex optimization with natural\ntime decaying learning rates, which have not been possible to prove with the existing uniform stability results.", "summary_of_the_review": "The paper makes progress towards answering, for randomized\nalgorithms with on-average uniform stability, such as stochastic gradient descent\n(SGD) with time decaying learning rates, wheter\nthese deviation bounds still hold with high confidence over the internal randomness of algorithm.\n\nHowever clarity can be improved in showing how far paper's results are from lower bounds.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Confidence boosting via aggregating multiple run of algorithms has been used before. The main result of the paper relies on a generic confidence boosting trick. The authors for instance cite Shalev-Schwartz et al 2010 theorem 26 in remark 4 of their paper and correctly point out that for deterministic algorithms like ERM one can use that for confidence boosting. While that theorem there is proved for excess risk and for deterministic algorithms, the main idea there to me seems like what is used in the authors paper as well. 

The basic idea: 
Property A holds in expectation, Hence use Markov inequality to get a low grade probability version of it in each of the K pieces
Now probability that at least one of the pieces is good is high since each piece is independent of the other
Finally aggregate with simple concentration with union bound.

In Shalev-Schwartz et al 2010 this is done with property being excess risk, here it is done with generalization error.

(Oh and I should add, the fact that the algorithm is randomized does not affect this line of reasoning as long as we use fresh randomness for each of the K blocks).

Now the missing piece covered is that on-average stability implies generalization in expectation. But isn’t this already known to be true in the stability literature? 

To me it seems like the main technical contribution of the paper is not as novel. Further, as one of the reviewers points out, the main goal should be to prove high probability guarantee for the algorithm popularly used like SGD not the confidence boosted version of it.

None the less, it seems like the application of the result to SGD seems interesting and somewhat new. 

I am reluctant to propose an accept here.
Decision: Reject