Stability and Deviation Optimal Risk Bounds with Convergence Rate $O(1/n)$
Authors: Yegor Klochkov
Nikita Zhivotovskiy
Venue: NeurIPS 2021 Oral (2021)
Keywords: algorithmic stability
generalization bounds
concentration inequalities
stochastic convex optimization

Abstract: The sharpest known high probability generalization bounds for uniformly stable algorithms (Feldman, Vondrak, NeurIPS 2018, COLT, 2019), (Bousquet, Klochkov, Zhivotovskiy, COLT, 2020) contain a generally inevitable sampling error term of order $\Theta(1/\sqrt{n})$. When applied to excess risk bounds, this leads to suboptimal results in several standard stochastic convex optimization problems. We show that if the so-called Bernstein condition is satisfied, the term $\Theta(1/\sqrt{n})$ can be avoided, and high probability excess risk bounds of order up to $O(1/n)$ are possible via uniform stability. Using this result, we show a high probability excess risk bound with the rate $O(\log n/n)$ for strongly convex and Lipschitz losses valid for \emph{any} empirical risk minimization method. This resolves a question of Shalev-Shwartz, Shamir, Srebro, and Sridharan (COLT, 2009). We discuss how $O(\log n/n)$ high probability excess risk bounds are possible for projected gradient descent in the case of strongly convex and Lipschitz losses without the usual smoothness assumption.

Stability and Deviation Optimal Risk Bounds with Convergence Rate O(1/n)
Yegor Klochkov
Nikita Zhivotovskiy Department of Mathematics
Cambridge-INET, Faculty of Economics University of Cambridge yk3760cam. uc.uk
ETH, Zürich wikita.zhivotovvsk.e @math. ethz. ch
Abstract
The sharpest known high probability generalization bounds for uniformly stable algorithms (Feldman, Vondrák, NeurIPS 2018, COLT, 2019), (Bousquet, Klochkov, Zhivotovskiy, COLT, 2020) contain a generally inevitable sampling error term order (n)/vn). When applied to excess risk bounds, this leads to suboptimal results several standard stochastic convex optimization problems. We show that if the so-called Bernstein condition is satisfied, the term (l//vn) and high probability excess risk bounds of order up to ((1/n) are possible via uniform stability. Using this result, we show high probability excess risk bound with the rate O(log //nn for strongly convex and Lipschitz losses valid for any empirical risk minimization method. This resolves a question of Shalev-Shwartz, Shamir, Srebro, and Sridharan (COLT, 2009). We discuss how Ollog n n) high probability excess risk bounds are possible for projected gradient descent in the case of strongly convex and Lipschitz losses without the usual smoothness assumption.
be avoided,
Introduction
Stability a standard method to analyze the generalization properties of learning algorithms. This approach can be traced back to the foundational works of Vapnik and Chervonenkis [46]. Using the sensitivity of the learning algorithms to the removal of one example in the learning sample, they proved optimal bounds (scaling O(1nn), where is the sample size) the average risk of hard margin SVM and of the Perceptron algorithm. The ideas of stability were further developed by Rogers and Wagner [40), Devroye and Wagner 113 [4] Lugosi and Pawlak (33), Kearns and Ron 226 and other authors. Stability arguments are notorious for only providing in-expectation error bounds. High probability guarantees require more effort and lead to several long-standing open problems in the
literature. For example, the classical stability analysis of Vapnik and Chervonenkis [46] (22 has only
recently been refined allow high probability guarantees with the optimal error rate (0 g 19
The widely used notion of stability allowing high probability upper bounds is called uniform stability. It was introduced in the seminal work of Bousquet and Elisseeff [7]. Let us introduce some standard notation. We have a set n i.id. observations S = (X...... Xx,} sampled according to some unknown distribution P defined instances with their labels. Our decision rules are indexed by set W that is always assumed to be closed subset of separable Hilbert space. Given the learning sample S, learning algorithm produces the decision rule Wn = (S) E W. For the loss function ? X x W - [0, 00), we define the risk and the empirical risk of W, respectively as
abstract set X. One may naturally think of X' as set of
1 72 R(w) Ep((X, (w)
wX)
n
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Following 77 an algorithm Wn (we always use the word algorithm both for the mapping and for the
1. ...... n, holds that decision rule) is uniformly y-staale, for any I, F1,............. . n E X' and
[0(x, wn (x(......, xx)) { wn (T 24-1, x', #++1, xn)) 5
The paper of Hardt, Recht, and Singer 20 on the stability of gradient descent methods has generated wave of interest in this direction. Recent works use various notions of stability in their analysis:
some authors are motivated by the analysis of gradient descent algorithms [32 30
16 5]. while
others the notion of average stability to obtain the in-expectation (1//n) rate for regularized
regression [29] 47] and some more specific improper learning procedures [7 3 One of the
key open questions left in [20] is related to the lack of high probability generalization bounds. Their question inspired a line of research focused on getting the sharpest possible generalization bounds for uniformly stable algorithms. Based on the recent progress by Feldman and Vondrák [16 17), the sharpest known high probability bound for uniformly stable algorithms was shown by Bousquet, Klochkov and Zhivotovskiy (9]. Their result states that for a y-uniformly stable algorithm w,, if the loss E(.,)) .) is bounded by M, then for any 8 E (0, 1). with probability at least 1 5, it holds that
R(w,) - RR,(w,) E y log n log
T
M
log
stability error
sampling error
One problem inherent to all high probability generalization bounds is that they are insensitive to the stability parameter 7 being smaller than M/vn. That is, in this favorable case the sampling error term scaling as (11 (n) controls the generalization error. The situation where y is smaller than M/ /ni happens in the literature on stochastic convex optimization where the strongly convex objectives are frequently considered 42 43 39 21 Unfortunately, there is no generic way to remove the (1///n) term in ① It appears even for the algorithms that always output the same decision rule (0-uniform stability). The problem is that generalization bounds compare the finite-sample risk R, with its non-empirical counterpart, namely, the population risk
A frequently used alternative to generalization bounds, which avoids the sampling error, are the excess risk bounds. That is, we are interested in upper bounding
R(w,) - infwew R(w).
Via a standard decomposition, the generalization bounds of the form I can be translated into the excess risk bounds for the empirical risk minimization algorithm (ERM). However, in this case the sampling error O / VT) is propagated in the excess risk bound leading to suboptimal results in the cases where we expect the (11/n) rate of convergence. Thus, are focusing on the following question:
Can uniform stability provide high probability excess risk bounds with the rate (up to) O(L/n)?
The main result of this paper answers this question positively and provides the first high probability bound based on uniform stability allowing the O(log n//n) rate of convergence. Similar questions appeared earlier in the literature on stochastic convex optimization, where optimal in en-execctation results usually follow from stability. In particular, Shalev-Shwartz, Shamir, Srebro, and Sridharan asked their pathbreaking paper 42 a high probability excess risk bound for strongly convex and I. Lipschitz losses with the rate ((1/n) is possible. As a corollary of our main result, we resolve their question by getting an almost optimal high probability bound with the rate Ollogn/n n/n).
1.1 Main results
It is well known that the O(1/n) rate of convergence for the excess risk cannot be achieved for free. So we need introduce additional assumption. We consider the following generalization of the so-called Bernstein condition allowing multiple global risk minimizers. The version below is originally due Koltchinskii (27)
Assumption 1.1 (Generalized Bernstein condition). Assume that W = Argmin R(w) is a set of risk minimizers in closed set W. We say that W together with the measure P and the loss satisfy the generalized Bernstein assumption if for some B > 0 for any w E W. there is wt e W such that
B(E( Z) -(ww, 2 B(R(w) R(w")).

---

Observe that the Bernstein assumption is independent of a specific learning algorithm. It is also not too restrictive and often accompanies uniform stability. In Section 2.1 we provide some examples and detailed discussion.
Suppose that loss Rn. We denote the optimization error of such an algorithm by
given uniformly stable algorithm wn that attempts minimize the empirical
Dopt (wn()) inf
Rn (w).
wEW
In particular, for ERM, we have Dopt = 0. The following theorem is our first main result.
Theorem 1.1. Assume that the loss E(:,)) )) is bounded by M. Suppose also that Assumption 1.1 is
satisfied with the parameter B. Let Wn be 7-stable algorithm that has the optimization error Dopt. There is an absolute constant e > 0 such that the following holds. Fix any 1j > 0. Then, with
probability least 6, it holds that
R(w,)= infwew R(w) S Aope + BBAopt + c(1 + 1/m) (7 moogg+++
M +
B
log 5
Our main application of this bound is an almost optimal high probability bound for ERM with strongly convex and Lipschitz losses. See Section 2.2 and Proposition[2.11 [2 more detail. Observe that the bound Theorem 1.1 contains the term corresponding to the expected optimization error Eoopt, where the expectation is taken with respect to the learning sample. This does not pose problem in applications known to us. particular, Theorem L.T limplies that our uniformly stable algorithm is ERM in W, then Aapt = 0 and, with probability at least 1 5,
M + B
R(wa) inf R(w)= S (ogg
<
log
Our second main result complements the generalization bound (1) and provides the variance-type bound, allowing us to completely remove the term O(1/vn) in ( whenever the empirical error Rm (w.) is small.
Theorem 1.2. There is an absolute constant с > such that the following holds. Let Wp. be st-bable algorithm and assume that the loss e(.,-) is bounded by M. Fix any rj > O. Then, with probability at least 8, it holds that
M n
1 5
R(w,)= S (1 + Rw + c(1 1/m) (7
log
This result has a clear motivation: in modern practice, learning algorithms achieve small or even zero empirical error the learning sample, and the analysis should take this into account. Note that there are several recent variance-type stability bounds in the literature (32 (3) but under significantly stronger assumptions.
particular, these papers, the loss is generalized linear function, whereas we are working in the canonical framework of Bousquet and Elisseeff [ It is also important note that in some examples, a small empirical error may lead to worse stability: this called the fitting-ssaabe stability tradeoff in the textbook [1). For instance. in ridge regression, regularization improves stability but the same time leads to an increased empirical error. And vice versa, by removing regularization, we may fit the data but lose stability.
Additional notation. For any two functions (or random variables) f. the symbol f g means that there an absolute constant c such that f < cg on the entire domain. The gradient and subgradient of function f at point Zy denoted by f=(z)) Vzf( and 0f(z)) 0₂ (ra). respectively. The notation (..)) stands for the inner product and by writing log x, we conventionally mean max (log
2 Stochastic convex optimization with strongly convex losses
Stochastic convex optimization a classical setup in which one minimizes a convex function based on some values or gradients at a given sequence of points. The most common setting is where at each round, the learner gets information on f through stochastic gradient oracle (see [39 and references therein). Another related setup that allows us to analyze generalization is when we observe the values
of the losses f(w, X,) for an i.i.d. sample X1,..., ., X,. Arguably the most well-studied case when the following properties of the loss hold for any X:
3

---

The loss f(z,-) )) is X-strongly convex. That is, for any W1, W2 E W. E (w, W2).
w1) faz, w2) 2 (g, W1 w2) + (A/2)llw3 w2 12?
The loss ((x,,) is L-Lipschitz. That is, for any æ E X and any w1, W2 E W,
[f(z, w1) f(x, w2)1 - L| well-
These assumptions on the loss are standard in the literature and have been studied in, e.g., [23 24
42 48 49] as well as the recent work on stability of gradient descent methods (00 One can
reasonably argue that both assumptions that, these assumptions are fundamental to the machine learning community and provide a clear illustration of our excess risk bounds.
rather restrictive (see the discussions in 44 2 Despite
In this setup, given convex and closed set W. we want to analyze the ERM strategy (also referred to as Sample Average Approximation (SAA)). That is, we are aiming to provide a high probability upper bound on the excess risk
R ( inf R(w),
where T
argmin R2 (wr)
The question of deviation optimal bounds in a closely related setup was recently revived by Harvey, Liaw, Plan, and Randhawa (2]. They proved generalization of Freedman's inequality for martingale differences to show high probability guarantees for stochastic gradient descent, resolving several open questions. In our case, high probability excess risk bounds are known for some specific algorithms but follow from the regret bounds in the online setting combined with martingale-basee based online to batch conversion techniques (4 (see also 42, Section 2.2[). Despite numerous attempts 44 43
48 49). the question of whether dimension-free free high probability bounds are achievable by any algorithm minimizing the empirical error remained open.
32
On the technical side, since ERM cannot be seen as a result of an online to batch conversion! ! the existing martingale-based techniques cannot be directly exploited. More importantly, uniform convergence, which is a standard tool for obtaining high probability bounds for ERM, fails in our case. This follows from an example in 43 Section 4.1 and page 2646] (see also [5]). One may
wonder if a more precise localized analysis (34] 27 3 should help in our setup. This is also not the
case, since according to [42. Section 5.3] there is no uniform convergence for an arbitrary localization radius. Fortunately, our stability-bans based method proves the desired upper bound.
2.1 Verifying the Bernstein assumption
When applying Theorem we first need check that the Bernstein assumption holds. Let us discuss this assumption in more detail. Assumption I.I appears first in a similar generality in the work of Massart 34 and under the name Bernstein class assumption in 4 This assumption used as one of the components for proving the rates of convergence faster than O (1/vn) (see the textbook (88 The Bernstein assumption is usually implied by the convexity of the underlying class and the convexity of the loss function. We refer to 45 for an extensive survey on related results.
For our purposes, verify Assumption I.] for strongly convex and Lipschitz losses. The following result is well-understood and appears (usually implicitly) in the literature. In our case, there is unique risk minimizer w" E WW that is, w" argmin R(w). From one perspective. the Lipschitz property implies for any w E W.
E(E(w, X) x))² < 12| - w" w
From another perspective, since the loss y-strongly convex and w" minimizes the risk in the convex set W, we have
R(w) - R(w*) 2 (A/2)]lw 11
Comparing the two inequalities, we have
B(l(w, X)- x))² < 1- w0 < (2L3 ( -R(()( R(w*)).
'The result in the textbook [1] Theorem 3. shows that the follow-the-leade the-ee strategy (an adaptation of ERM in the online setup) achieves the regret 4 (1 log n after rounds. However, after the online to batch conversion (24) only get high probability bound for an average of empirical risk minimizers.

---

This implies that X-strongly convex and L-Lipschitz losses satisfy Assumption 1.1 with B = 2L2/A
Our version of the Bernstein condition, namely Assumption 1.1 is due Koltchinskii (27 Page 2618]. The key difference from the standard Bernstein assumption is that we allow multiple minimizers but can still provide (1111) rates of convergence. Our motivation lies in the recent interest in relaxing the strong convexity assumption in (stochastic) optimization problems. One of such alternatives the -ojasi--oasseewicz condition (PL) (see (25)). In this context, the work [3I] extends the standard Bernstein assumption to go beyond the strong convexity assumptions allowing multiple risk minimizers. Likewise, [2] claims that uniform stability results hold when the strong convexity assumption on the losses is replaced by the (PL) assumption Thus, our general results can potentially be useful in this direction.
2.2 High probability bound for almost risk minimizers
In this section, we present the main application of Theorem In the strongly convex case, we provide a sharp high probability guarantee valid for any learning algorithm depending its optimization error.
Proposition 2.1. Ler W be convex closed set. Assume that the loss function is X-strongly convex and L-Lipschitz as defined above. Let an approximate empirical minimizer w have an optimization error opt bounded by deterministic A for any learning sample. Then, with probability 1 - 8.
L2 An
L2A A
log n log (
R(w)= - R(ww) 5
+
In particular, if ④ is ERM in W, then A = 0 and
L R(w) R(w") S An
log n log
The in-expectation version of 3
without an additional log n-factor is well-known and attributed to As we mentioned, the possibility of high probability bound with Discussion after Claim 6.2). Despite the recent progress, the term O (1/ is present in the sharpest known high probability bound [17 Corollary 4.2]. Proposition 2. settles this question up to logarithmic factor. We note that high-probability bounds are known ERM in the particular case where the loss is a generalized linear function with strongly convex penalty 44 The analysis in [44] is based on localized Rademacher complexities and exploits the linear structure of the loss. As we mentioned above, uniform convergence cannot help in our setup.
the foundational papers 7 42
the rate O (1/n) was asked in 42
2.3
Application to projected gradient descent without smoothness assumptions
Let us consider a simple illustration of Proposition 2.1 In what follows, we focus on the statistical rather than the computational part of the story. The method of Projected Gradient Descent (full-batch PGD) consists of iteration of the following update rules for t = I,...,T; T,
Y/ W/ Migt,
where St E ORn(w));
Wr++ = (y:),
where T is the total number of steps, Wi is an initial approximation, and Iy is the projection operator onto the convex closed set W. The choice of the number of iterations T and the step values v4 affects the optimization error, For instance, when the loss is X-strongly convex and L-Lipschitz, choosing Vt X(+IJ gives the following optimization error (see 10 Theorem 3.9).
Ra (ww) min RB (w) S <TT2/XT, wEW
where wy T[T+T] Eln tw, is the weighted average of iterations. Therefore, PGD achieves the optimization error O(1/n²) after T = 0(n²) steps. By Proposition 2.1 with probability at least
1 - 5, it holds that
I!² Xn
R(w - R(w") S log log (
(4)
'The bounds in 112 require that (PL) holds for the empirical error. To the best of our knowledge, no stability results are known if (PL) is satisfied only for individual losses.
5

---

This is the first high probability O/logn/n) excess risk bound for non-smooth PGD. Our techniques do not give an answer to the question whether a smaller number of iterations sufficient in the non-smooth case. Recent results suggest that full-batch PGD can indeed require significantly more steps than Stochastic Gradient Descent [0. However, the authors only consider convex objectives that correspond to slow convergence rates O(1/vn).
We note that stability of PGD can be analyzed regardless of the optimization error. Indeed, the derivations of Hardt, Recht, and Singer [20] Section 3.4] (see also [1Z] Section 4. 4.1.2]) imply that if the loss is B- 8-smooth addition to strong convexity and the Lipschitz property, that is,
V nn (r. w1) V (= w2)ll S Bl| w2l1: for all w1, W2 E W,
then PGD with the constant step size y = 1/3 is 21 2 -unifoonl stable for any number of steps. In addition, the optimization error of the final iterate satisfies [TO] Theorem 3.10).
31.
Rm, (wT)
min (w)
exp exp(-XT/3).
wEW
X2
As result, the smoothness assumption implies the same (previously unknown) high probability excess risk bound (4) after only T = Ollog n) steps.
3 Proofs
Throughout the proofs, we rely on the Lp norm. Denote the Ly-norm of a random variable as
|| = (EB (P) A moment bound can be translated into sish--robbbblity bound as follows (see, e.g.. 99] Section 2J). Assume that for some b >> 0 and all p 2 2, it holds that || S avp + bp. Then, there an absolute constant C such that for any 5 E (0, 1), with probability at least it holds that
Z C loylog (1/6) b log (1/8)
As mentioned, generalization bounds of form ( cannot provide excess risk bounds with the rate better than O(I/VT). The following lemma separates the sampling term from the generalization error.
Lemma 3.1. Let = ( Xn) be y-stable algorithm and let w/ = wx( X be its independent copy. Then, for any p z
RA (w,) R (w))
Σ (1 X1] ER(w.)
S ypllog.
Such decomposition is possible due to the following extension of the bounded differences inequality by Bousquet, Klochkov, and Zhivotovskiy 9 Theorem 4].
Theorem. Assume that XI,..., Xn are independent variables and the functions 9i X + R satisfy the following properties for I,...,
Ex,gi(X,..... X.) = almost surely;
gi has the bounded differences property with respect to all but the i-th variable: for all j +
and 21,... Zn, z.g. have (E1, (. 2/y, Tg+1s.... en)] 8;
EX X.)I X < K almost surely.
Then, the following moment bounds hold for all p 2 2,
Σ
9: p
- 12v22ppnoog logn + 4K vpn.
(6)
In addition, we will use the following version of the Bernstein inequality (6 Theorem 15.11]: if X1y..., .i....,, Xx, are zero mean, independent and bounded [X,] S M almost surely, then
| + ... + X.llp S 5o
EX?) p + 4pM, 1=1
Vp 2222. 2.

---

Our last tool is the concentration inequality for non non-negea negativee weakly self- bounded functions. Assume
that a. b 2 O. We say that the function : X - [0. +000 (a. bw-akky elf-bounded if there exist functions Si x > [0, +00) that satisfy for all x E X
(f(a)
+b.
The following concentration incquality is lower tail version of 6 Theorem 6.19]. which is originally
due to Maurer [35]. The difference is that their result it is assumed that fx) S f(r) for any X². The proof of the version below is standard. and we reproduce it below for the sake of completeness. Since we consider the lower tail, we remove the term at present in [6] Theorem 6.19].
Proposition 3.1. Suppose that XI...., Xn are independent random variables and the function f X" + 10, +00) is (a, b)-wakly self-bounded and the corresponding functions ft satisfy f((x) 2 f(x) 1...., n and any x E X Then, for any t O,
t²
I X,)) f(X1 Xx) + +t) exp
sex
(8)
2xEf(XI.... Xn) + 26
3.1
Proof of Lemma 3.1
For Wh = Wn (X1,
X1-1, ,., Xn), where X is an independent copy of X,, consider
the functions
9: 9; X,) = Ex; X, w/!) - Exy R(w!"))
One can immediately verify that these functions satisfy all three properties needed to apply @ with 27, It is standard to check that (see e.g.. (9] Lemma 7))
(w,,) R(w,,) - En n
i=1 S 2yn.
Let consider for i 1, ,...,,... n, the functions 1,, Xn)) 9: Elgg X,). where the functions
f; preserve the stability property (up to a factor of 2). Observe that E h// X,] 0 almost surely, which implies K Therefore, applying (6) to the functions h;, we have that for any p 2 2.
Si Eg/gl X.)
S 48y2 logn.
Notice that Elga X,) = E( A X. ER( (w,)) Our result follows.
3.2 Proof of Theorem 1.1
The proof starts with standard decomposition that turns the generalization bound into an excess risk bound. Denote Re inf R(w). We have for any w Arggmin R(w),
R(w,) R = R( w,)) Rn (w,) + (w,) - R,(w") + (x R
< Dopt (w,)) R(w,)) + (R,(w")
Here, the expression R2, (w,) R(w,) stands for the generalization error and is typically of order 1/ l/. To avoid this, we use the decomposition of Lemma 3.1
(w,) - R(ww) = E Σ E' ((,((, ER(w,),
where Ι![| S "yp log for any 2 2 and wo, is an independent copy of wn- We write E' to denote the expectation with respect to this independent copy. We now need to pair the remainder term with Rn, (w") R(w") to achieve the O(1/n) rate. Since ER(ww,) = E (((w,, then for any w" Argminn R(w), it holds that
R(w,) R" < Sopt -
Σ (E'((X, w,) - ((X,,w)) + E' (E'((W',) - R"
Since we are free to choose any wº, let us take the one corresponding to w/, Assumption 1.1 Notice that neither R(w,), & nor Dopt depend on this choice. In other words, w' Argmin R(w)
7

---

is random vector induced by w/, where we write w' instead of wt to point out this dependence. Therefore, we rewrite our last display as follows
R(w.)= - Re S Appt - 5
Σ (E'e(Xi, w/)) ) e(Xi, w')) + E R(w()) - Rº
Notice that here the only terms that depend on w/, are l(Xi, w'). Taking the expectation E'' both sides of this inequality, obtain
R(wn) R E opt -
Σ 71
1
n
E [((x; E(X,, + R
(9)
Here, EE'((X w') ('E w!)l
w E' F("(") = R", and as we have already noticed, EE' ((x, w,) E' R("" Moreover, by the Bernstein condition and Jensen's 's inequality.
EE (E'(e(X,, w(,) ((Xi, - E' E'B(L(X,, w/,) ((Xi, w/) w²2
E'E[(e(X,, w(,) e(X;, w' ('))?(w'n))
I B(E' -((())))R
Having this variance bound, we are ready to apply the moment Bernstein inequality 7 to the sum of independent random variables [' w²)) ((X,, w²)]. Since E' 3'R(w',) R is exactly the expectation of each of these summands, we have for all p 2 2,
B(ER(W)) - R ) 2 PM
E' [((X,,
-E'''' + Rº
S
(10)
n
Plugging this into p9, we obtain for each p 2 2 and some absolute constant C> 0,
PM
[[(w)) - 18" -Apelll S (pp hoplog=+ B(ER((E)) - 18*)
+
$ <<E((ww)) - R²) + (7plog +
B
+
M
(11)
17
where the second inequality holds since for any a, b, > holds that vab naa + b/1)-
Finally, we need an upper bound on (ER(w,,) R" Taking p (T and using the Cauchy- Schwarz inequality, have
ER(w,)) - EAopt S [R(ww,) - R² Aopall2
(ER((w,) R*) (27 logn + 2(Br M)/n).
Subtracting 77 (ER((w)) R*) from both sides and dividing by - 7), we obtain
C ER(w,) R S EA + I- (7 +
B
M
Plugging this bound back into assuming that 17 1/2, and translating the moment bound into the high-probability bound through (5). we obtain that, with probability at least 1 1 8,
(
17 Edgpt + log log (1)
B +
log log(1/5)
R(w,) R Dopt + C'
M
1-
12
where C² is absolute constant. By replacing 17 by max (ax (2(44))))))
finish the proof.
L
3.3 Proof of Theorem 1.2
We will show that under the conditions of the theorem, the following variance bound holds. For any E (0, 1), we have, with probability at least 1 85
R(w,) R, S log log (
M R((w))
(1)
M
5
+
log
log
(12)
8
8

---

The statement of the theorem follows immediately by applying the inequality vab S na + b/n to the middle term of the right-hand side and choosing the appropriate value 17.
The proof of 12 repeats the arguments of Theorem 1.1 with several important changes listed below. As in the proof of Theorem 1.1 use the generalization bound of Lemma and then apply the Bernstein inequality to the correcting term. Converting the moment bound into a high probability bound by (5). have, with probability 1 8/2.
R(w,)= (w,)))= S log n log ())+ + B(E(X', wn))
1
M log n
log
(13)
n
where we used that the variance of TE[((X, wy))l X] is bounded by (B(((X,, wn))² due to Jensen's inequality.
Our goal is replace the non-random term (E{((', w,))² with its empirical version EE E'(((X,, w. ))² where slightly abusing the notation, E'' denotes the integration only with respect to the independent copy X'. Unfortunately. naive application of the bounded difference inequality leads a suboptimal bound in our case. Instead, we use second order concentration through the weakly self- ooff-bounding property. Set
f = f(r.. x.,) = ['(('X,, Wn (TT))...,T.))))
and fs = supa f(r1..... En), so that ft 2 f for all = 1..... n. We show that f is (8n7?, 2ny ( J-weakly self-bounded. By the uniform stability and Jensen's inequality, we have
Σn ---)) (f
1
f1) 2 Σ (E'(I(X', wn))² - supmex E' ('(,', ?²
$ ny (2E' wa) + 7)²
$ 8mm?2 + 2mn²
Therefore, by the concentration inequality (8) we have that, with probability 1- 55/2.
[(((X', )² - E' (e(X', uw)))² S v (m)"E( w,))² + ( log(1/8).
Using Va S for all a, b 2 0 and ('('',', w²))² < MR MR(ww), obtain the same event E(e(X', w²)))² - 2M (( S nン log
Plugging this bound into 13 and using the union bound, we obtain 12) Hence, the theorem follows.
3.4 Proof of Proposition 2.1
We first check the uniform stability of W. For this we need to prove that for any x E X,
(xx @) [(x, x() S 4T. / /812//2
where @ ((11 ... ).,) and ( (x ( -;-1; 2/,, Ti+1, ... Fn ). Let also i be the mini-
mizer of R,, which denotes the empirical risk on the sample II...., nn and (1) is the minimizer of R!!) which denotes the empirical risk on the sample .I...., , .,,..., Fn. Then, by [42 Claim 6. I].
for any E X,
[((x, wi E(x, x0)) S 4I.2 / (Xn).
On the other hand, since R2 is A-strongly convex,
(A/2)]l - ق|| < Rn(w)) - ( (w) A
which implies ||00 ا||l < V 2A/A. A similar relation holds between ( and ( Using the L-Lipschitz property, we conclude that for x,
[((x, ( - E(x, o0()) S (e(r, w) - ((x, (() + 16(x, w()) - l(x, (((0) + 16(x, t) - b(x. ū)l
< 4T.2 (An) + /

---

Since w is stable, we apply Theorem 1.1 It is only left to check that the loss is bounded. This follows from the fact that it is both L-Lipschitz and A-strongly convex at the same time. Indeed, we have for any w E W and w² = argmin R(w), that
(A/2)ll- w01 < R(w) R(w") ) S LI[ - w'll.
so that the convex set Wi is bounded and contained in the ball {w || w*ll 2L/ Using again the Lipschitz property of f(z,)) :) we conclude that for any x E X, w E W,
10(x,,00 w) [(x, w* S 21.2/x.
Although the conditions of Theorem 1.1 require a uniform bound E(.,-) -) < M, it only enters in the proof in (TO) where we apply the Bernstein inequality 7 to the sum of independent random variables
[[ )nn) e(X;, w²) X.). Therefore, the inequality still holds with 2L / in place of M. The
rest of the proof of Theorem provides us with the required bound.
3.5 Proof of Proposition 3.1
Since the result is not presented in the literature in the form we need, we reproduce the standard argument. Let Z f(X,..... Xx,). Z; = f((,,..... X Xiti..... )x,) are such that Z < Z; almost surely, and the weakly self- bounding property holds, that is, Σi=1 (Z; - Z)² I aZ + b. Let
us first apply modified logarithmic Sobolev inequality [6 Theorem 6.6]. We have
- - - log E SE
A2 Σ
6 6- 2,11
where d(x) = e" x - 1. Since for x 2 0. oi -x) I x² / and Z 2, S for all = I,....,.. n, we
have for any À S 0,
X2
n
X2
XEIZE A2 - BBe log 22
v E
AZ Σ
zz -21²²
- 2 2 (aE[Ze Ze 1B( (EE(
2
i=1
Define G()) = log Ble so that G'(A) = BZ 1/B|e>2)
Dividing both sides of the last display
by AZ, we obtain
X² -G'(A)G((A) G(A) (aG'(A) +),
A5o.
For A < O, we have
(1)) = (0--01110 (
a G'(A)
G(A) b 2 S 2
Finally, we integrate this inequality. Observe that G(0) = 0 and we also have ('(0) EZ. Hence,
as x - -0, by Taylor's theorem (1/A a/2)G(A) = (1/A - (AEZ + +(A)) = EEZ + o(1).
Integrating the last display over the interval [>, 0J, we obtain
EZ - (1 - a G(M) s (
After some rearrangements this leads the following inequality (recall that À < 0),
log Ele G(A) - AEZ - (aT + b)
X²
< (aEZ + 6).
2(1 Xa/2)
2
It remains use the Markov inequality (recall again that X 0) show that
X2 P(Z < EZ -)) = P - EZ) > Xt) = IP (c (Z > 1) S exp [x+ + (aEZ + bb)
2
(F The latter exponent is minimized by À = -1/ + b) < implying the statement.
Acknowledgments. We thank Jaouad Mourtada for his comment on the and for providing several important references. We also thank Tomas Vaškevičius for valuable feedback. Nikita Zhivotovskiy is funded in part by ETH Foundations of Data Science (ETH-FDS).
strategy
10

---

References
[1] I. Amir, T. Koren, and R. Livni. SGD generalizes better than GD (and regularization doesn't help). arXiv preprint arXi::2102.01117 2021.
[2] F. Bach and E. Moulines. Non- con-strongly-conee smooth stochastic approximation with convergence rate (1/n). In Advances in Neural Information Processing Systems, volume 26, 2013.
[3] P. L.. Bartlett, O. Bousquet. and S. Mendelson. Local Rademacher complexities. The Annals of Statistics. 33(44:1497-1537. 2005.
[4] P. L.. Bartlett and S. Mendelson. Empirical minimization, Probability theory and related fields, 135(3):311-
334, 2006.
[5] R. Bassily, V. Feldman, C. Guzmán, and K. Talwar. Stability of stochastic gradient descent nonsmooth convex losses. Advances in Neural Information Processing Systems, volume 33, pages 4381 14391,, 2020.
[6] S. Boucheron, G. Lugosi, and P. Massart. Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, 2013.
[7] O. Bousquet and A. Elisseeff. Stability and generalization. The Journal of Machine Learning Research, 1:499-526, 2002.
[8] O. Bousquet, S. Hamneke, Moran, and N. Zhivotovskiy. Proper learning, Helly number, and optimal SVM bound. In Conference on Learning Theory, volume 125, pages 582-609, PMLR, 2020.
[9] O. Bousquet, Y. Klochkov, and N. Zhivotovskiy. Sharper bounds for uniformly stable algorithms. In Conference on Learning Theory, pages 610-626. PMLR, 2020.
[10] S. Bubeck. Convex Optimization: Algorithms and Complexity. Found. Trends Mach. Learn..
8(3 40:231):333333 2015.
[11] N. Cesa-Bianchi and G. Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006.
[12] Z. Charles and D. Papailiopoulos. Stability and generalization of learning algorithms that converge to global optima. In International Conference on Machine Learning, pages 745-754, PMLR, 2018.
[13] L. Devroye and T. Wagner. Distribution-ffee free inequalities for the deleted and holdout error estimates. IEEE Transactions Information Theory, 25(2):202-205 -07- 1979.
[14] L. Devroye and Wagner. Distribution-Fre free performance bounds for potential function rules. IECE Transactions on Information Theory, 25(5)6011604, 1979.
[15] V. Feldman. Generalization of ERM in stochastic convex optimization: The dimension strikes back. In Advances in Neural Information Processing Systems, volume 29, 2016.
[16] V. Feldman and J. Vondrák. Generalization bounds for uniformly stable algorithms. In Advances in Neural Information Processing Systems, volume 31, 2018.
[17] V. Feldman and J. Vondrák. High probability generalization bounds for uniformly stable algorithms with nearly optimal rate. Conference on Learning Theory and arXiv preprint UrXiv:1902.10740 pages 1270-1279. PMLR, 2019.
[18] A. Gonen and S. Shalev-Shwards Average stability is invariant to data preconditioning: Implications to exp-concave empirical risk minimization. The Journal of Machine Learning Research, 18(45:8245-8257 2017.
[19] S. Hanneke and A. Kontorovich. Stable sample compression schemes: New applications and an optimal SVM margin bound. In Conference on Algorithmic Learning Theory, volume 132, pages 697-721. PMIRR 2021.
[20] M. Hardt, B. Recht, and Y. Singer. Train faster, generalize better: Stability of stochastic gradient descent. 2420,, volume 48, pages
In International Conference on Machine Learning and arXiv preprint 1225-1234. PMLR, 2016.
[21] N. Harvey, C. Liaw, Y. Plan, and Randhawa. Tight analyses non- non-smooth stochastic gradient descent. Conference on Learning Theory, pages 1579-1613. PMIRR 2019.
[22] D. Haussler, N. Littlestone, and M. K. Warmuth. Predicting (0, 1) ffucciinns on randomly drawn points. Information and Computation, 115(2):248 292, 1994.
[23] E. Hazan, A. Agarwal, and S. Kale. Logarithmic regret algorithms for online convex optimization. Machine Learning, 696--9) 2007.
[24] S. M. Kakade and A. Tewari. On the generalization ability of online strongly convex programming algorithms. In Advances in Neural Information Processing Systems, pages 801-808, 2008
[25] H. Karimi, Nutini, and M. Schmidt. Linear convergence of gradient and proximal-gradient methods under condition. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 795-811. Springer, 2016.
the

---

[26] M. Kearns and D. Ron. Algorithmic stability and sanity-check bounds for leave-one-out cross- validatiio... Neural computation, 1166):4427-1533 1999.
[27] V. Koltchinskii. Local Rademacher complexities and oracle inequalities in risk minimization. Annals of Statistics, 34(6):2593 2656,,26666622 2006.
[28] V. Koltchinskii. Oracle Inequalities in Empirical Risk Minimization and Sparse Recovery Problems. volume 2033 of Ecole d' Eté de Probubilités de Saint-Flour XXXVIII-2008. Springer Science & Business Mcdia, 2011.
[29] T. Koren and Levy. Fast rates for exp-concave empirical risk minimization. In Advances in Neural Information Processing Systems, volume 28, 2015.
[30] I. Kuzborskij and C. Lampert. Data-dependent stability of stochastic gradient descent. In International Conference on Machine Learning, pages 281 2--4-824. PMIR, 2018.
[31] M. Liu, X. Zhang, L. Zhang, R. Jin, and T. Yang. Fast rates of ERM and stochastic approximation: Adaptive to error bound conditions. In Advances in Neural Information Processing Systems, volume 31, 2018.
[32] T. Liu, G. Lugosi, G. Neu, and D. Tao. Algorithmic stability and hypothesis complexity. In International Conference on Machine Learning, pages 2159-2167. PMLR, 2017.
[33] G. Lugosi and M. Pawlak. On the probbabii-y estimate classification rules. IEEE Transactions on Information Theory, 40(2):475 4811,,4811111 1994.
error rate of nonparametric
[34] P. Massart. Some applications of concentration inequalities to statistics. In Annales de la Faculté des sciences de Toulouse: Mathématiquex, volume 9. pages 245-303, 2000.
[35] A. Maurer. Concentration inequalities for functions of independent variables. Random Structures & Algorithmss, 29(2):121-133 2006.
[36] A. Maurer. A second-order look at stability and generalization. In Conference on Learning Theory, pages 1461-1475. PMLR, 2017.
[37] Mourtada and Gaiffas. An improper estimator with optimal excess risk in misspecified density estimation and logistic regression. arXiv preprint arXiv:19/2.1078, 2019.
[38] J. Mourtada, T. Vaškevičius, and N. Zhivotovskiy. Distribution-Fee free robust linear regression. arXiv preprint arXiv:2 102. 2021.
[39] A. Rakhlin, O. Shamir, and K. Sridharan. Making gradient descent optimal for strongly convex stochastic optimization. In Internationaa Conference on Machine Learning, page 1571-1578, 2012.
[40] H. Rogers and J. Wagner. finite sample distribution-free performance bound for local discrimination rules. The Annals of Statistics, pages 506-514, 1978.
[41] S. Shalev-Shwartz and S. Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014.
[42] S. Shalev-Shwartz, O. Shamir, N. Srebro, and K. Sridharan. Stochastic convex optimization. In Conference Learning Theory, 2009.
[43] S. Shalev-Shwartv, O. Shamir, N. Srebro, and K. Sridharan. Learnabllity, stability and uniform convergence. The Journal of Machine Learning Research, 11:2635-2666 2670, 2010.
[44] K. Sridharan, S. Shalev-Shwartz, and N. Srebro. Fast rates regularized objectives. Advances in Neural Information Processing Systems, 21:1545-1552, 2008
[45] T. Van Erven, P. Grunwald, N. A. Mehta, M. Reid, and R. Williamson. Fast rates in statistical and online learning. The Journal of Machine Learning Research, 16(1):1793- 11117799-1661,2000 2015.
[46] V. Vapuik and A. Chervonenkis. Theory of Pattern Recognition. Nauka. Moscow., 1974.
[47] T. Vaškevičius and N. Zhivotovskiy. Suboptimality of constrained least squares and improvements via non- non-linear predictors. arXiv preprint arXiv:2009,098. 00900, 2020.
[48] L. Zhang. T. Yang, and R. Jin, Empirical risk minimization for stochastic convex optimization: O(1/n)-and ((1/n))-typ of risk bounds. In Conference on Learning Theory, pages
PMLR, 2017. [49] I.. Zhang and Z. Zhou. Stochastic approximation of smooth and strongly convex functions: Beyond the O(1/T) convergence rate. In Conference on Learning Theory, volume 99, pages 3160-3179. PMIR,
2019.
[50] N. Zhivotovskiy. Optimal learning via local entropics and sample compression. In Conference on Learning Theory, pages 2023-2065. PMLR, 2017.
12


Reviews:
[{"review_id": "x7BqHnLrYha", "reviewer": "Reviewer_Bxnk", "summary": "This paper presents high probability bounds of O(1/n) for uniformly stable algorithms. The authors assume the generalized Bernstein condition due to Koltchinskii [26] as an additional assumption compared to related works in the literature. Under this assumption, they show that uniformly stable algorithms can achieve [optimization_error + O(1/n)] excess risk bound with a high probability. The authors show that optimization of stronlgy convex Lipschitz continuous objective functions satisfies the generalized Bernstein condition. This allows them to provide the first high probability O(log(n)/ n) risk bound for uniformly stable algorithms on a strongly convex Lipschitz continuous optimization problem.", "questions": "", "limitations": "", "rating": 7, "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": "The paper uses tools developed by Bousquet et al. [8] heavily to prove their results. It is rather difficult to find a strongly convex function that is Lipschitz continuous and bounded. An easy way to justify these conditions together is to assume that \\mathcal{X} is a compact set. The contribution is of good value from a theoretical point of view. As the authors pointed out, the generalized Bernstein assumption might be useful when considering optimization under PL-condition which is widely studied in recent years due to its usefulness for modern ML applications. Overall, the paper makes a good contribution and might serve as a first step to thoroughly explore the new assumption in different settings.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "One potential improvement is to consider the running time of the algorithm when trying to achieve high probability O(1/n) excess risk bounds. Currently, the algorithm requires n^2 iterations of full-batch which results in O(n^3) gradient-complexity which is significant. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hours"}, "extra_text": {}}, {"review_id": "pszu4479vVI", "reviewer": "Reviewer_3CZg", "summary": " The authors presented an improved variance-type excess risk analysis for uniformly stable learning algorithms. Particularly, it was proved that if the population risk satisfies the Bernstein condition, then a $\\gamma$-stable algorithm with optimization error $\\Delta_{opt}$ over a set of $n$ observations can achieve excess risk of order $\\gamma \\log(n) + \\frac{1}{n} + \\Delta_{opt}$ with high probability. This result implies $O(\\frac{\\log(n)}{\\lambda n})$ risk bounds for empirical risk minimization (ERM) and projected gradient descent (PGD) with $\\lambda$-strongly convex and Lipschitz loss functions. Also, a high-probability $\\eta$-approximated generalization error bound is provided which improves the $O(\\sqrt{\\frac{\\log(1/\\delta)}{n}})$ tail term in the best known generalization bounds to $O(\\frac{\\log(1/\\delta)}{\\eta n})$.\n\n", "questions": "", "limitations": "", "rating": 7, "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": "Strengths: \n+ The deviation analysis of uniformly stable algorithms as focused in this paper is an important and timely topic in learning theory.\n  \n+ I am particularly impressed with the strength and originality of the results obtained in this paper for strongly convex optimization problems. The main idea of proof is to make a smart use of an extended bounded difference inequality from Bousquet, et al. (2020) to separate the sampling term from the generalization error, so that the randomness of model and data sample can be decoupled in a way that the Bernstain inequality is applicable to get tighter bounds. While built largely upon the previous results, IMO the technical part still appears novel enough in the considered problem regime.  \n \n+ The paper is generally well organized and clearly presented, with all steps in the proofs very carefully explained. \n\nWeakness: \n  \n   My main concern is about the benefit of main results in Theorem 1.1 when substantialized to ERM and PGD with arbitrary convex losses. Basically, the improved $O(\\frac{\\log(n)}{n})$ rate of convergence seems only possible for strongly convex loss functions with zero optimization error achievable over training data. For generic convex losses which are of more interest in practice, we usually need to deal with regularized ERM of which the empirical risk error $\\Delta_{opt}$ is typically $O(\\frac{1}{\\sqrt{n}})$ due to a trade-off between optimization and generalization. In this case, while the population risk can still be assumed strongly convex so that Theorem 1.1 is applicable, the $O(\\frac{1}{\\sqrt{n}})$ optimization error term will dominate the risk bound which makes the  $O(\\frac{1}{n})$ term much less interesting. The authors have partially  addressed such a limitation for Theorem 1.2 with respect to the empirical risk. However, it looks like that similar or even more severe limitations exist for Theorem 1.1 as well in terms of optimization error.  \n\n\n=== Post rebuttal update ===\n\nThe major concern  on the limitation of results raised in my initial review has been properly addressed in author response. I would like to maintain my rating.   ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes,  the authors have partially addressed the limitations and potential negative societal impact of their work. ", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "oBHl0nZcTc", "reviewer": "Reviewer_1bRR", "summary": "This work provides improved generalization bounds for uniformly stable algorithms under the Bernstein condition. This condition bounds the variance of the loss with respect to a risk minimizer by the excess risk, and it has been widely used to derive faster rates in statistical learning. However, their use for high probability bounds in stochastic optimization was limited by the fact that all known high probability generalization bounds for stable algorithms incurred terms $\\Omega(1/\\sqrt{n})$. The main consequence of this result is a high probability excess risk bound for the Empirical Risk Minimizer in strongly convex stochastic optimization, resolving an open question by Shalev-Shwartz et al. (COLT 2009). Another consequence is an (optimal) high probability excess risk bound for (full-batch) gradient descent with O(n^2) iterations. \n\nUniform stability is a central tool for machine learning theory, and the results of this paper provide a clear contribution here. Technically, the paper does not include much innovation, but the methods used, particularly referring to the excess risk decomposition, are quite interesting, and may encounter further use. Finally, I am not sure about the \"deviation optimal\" part in the title: Is it clear that the bounds derived are sharp? No matching lower bounds are provided for Lemma 3.1 or Theorem 1.1. I believe existing results (like lower bounds in Bousquet, Klochkov & Zhivotovskiy (BKZ)) may already explain this to some extent, but I would suggest including a more detailed discussion on sharpness.\n", "questions": "", "limitations": "", "rating": 7, "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": "\n1. To achieve the main result, a useful Lemma 3.1 is shown (this is a minor variation of a Lemma from BKZ): this result avoids the sampling error term $O(1/\\sqrt{n})$ by showing a moment bound of a \"shifted\" generalization error. This shifting includes the risk of the algorithm output and an average conditional loss. It would be interesting if the authors would elaborate further about the intuition on this refinement, and what are its consequences for the excess risk bounds (the technical proofs are clear, but \nnevertheless it might be useful a brief discussion).\n\n2. The proof of the main result (Thm 1.1) is obtained nontrivially from Lemma 3.1. This involves a (seemingly novel) decomposition of the excess risk and the (shifted) generalization error, along with various estimates based on concentration by the Bernstein condition.\n\n3. Theorem 1.2 provides what they call a variance-type bound (not sure why is it called like this), which bounds the risk in terms of the empirical risk and a deviation bound which leverages faster rates by uniform stability. This bound seems useful in realizable settings, where the empirical risk can be made arbitrarily small.\n\n4. The consequences for strongly convex stochastic optimization appear in Proposition 2.1 and its following discussion. As mentioned above, this general bound for stable algorithms answers a question raised in Shalev-Shwartz et al (2009) which is quite interesting on its own. In this result, the most problematic term is $\\sqrt{L^2\\overline{\\Delta}/\\lambda}$, where $\\overline{\\Delta}$ is a bound on the empirical error: this leads to optimal excess risk in this case for GD with O(n^2) iterations. It is worth pointing out here that a similar iteration requirement appears in the nonsmooth case, as shown in Bassily, Feldman Guzman and Talwar (2020). That paper also includes a lower bound on stability, showing that for GD $\\Omega(n^2)$ steps needed to obtain optimal rates with uniform stability. It is reasonable to conjecture that a similar lower bound may hold in the strongly convex setting, and in fact some limitations of GD in terms of excess risk have already been shown in recent work by Amir, Koren and Livni (https://arxiv.org/pdf/2102.01117.pdf). The latter result is shown for GD on the regularized ERM, but I suspect ideas there might be useful for the strongly convex setting as well.\n\nFinally, I would suggest the authors to include a more detailed statement of the last paragraph before section 3 (lines 204-206 in page 6). Here it is claimed a new high-probability excess risk bound for GD on smooth and strongly convex losses. For future use of this result, it might be a good idea to have a proper statement.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This work is theoretical, so I agree with the authors there are no societal consequences of it.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns from this paper.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "UhYn9K_sbsv", "reviewer": "Reviewer_KWWB", "summary": "The article exhibit a way to bound the excess risk in a general risk minimization framework when the loss function is with bounded difference (or stable as they call it). They show that the rates $O(1/n)$ can be attained under some Bernstein condition. This is  often called \"fast rates\" of convergence in the literature and this article exhibit the first general inequality to get fast rates of convergence for stable loss function.", "questions": "", "limitations": "", "rating": 9, "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": "To my knowledge, this type of result was only proved in particular cases and this is the first general result on fast rates of convergence obtained via stability. The article is clear and well written and I think this is significant for the Neurips community. This article may generalize to a lot of learning problems and may become a tool to prove fast rates in  a lot of different settings, this may be an important step to assess the rate of convergence of algorithms and to have theoretical rates that match the rates that we witness in practice. The authors also illustrate this generalization capacity on the problem of stochastic convex optimization with strongly convex losses.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "None", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers are unanimous that this work provides a significant contribution in the area of uniform stability, which should interest the learning theory community as well as the wider NeurIPS community. A key consequence of the authors' results is the positive resolution of a long-standing open question of Shalev-Shwartz et al.'s COLT 2009 paper: this question is about whether ERM can obtain fast rates of convergence for Lipschitz, stochastic strongly convex optimization with high probability, where the dependence on the failure probability $\delta$ is logarithmic. While the authors do heavily draw from previous work, certain technical components like the novel excess risk decomposition are highly original, provide an important technical contribution, and might lead to progress in future works. In addition, the work is very well written and clear. This work would be a welcome contribution to NeurIPS.
Decision: Accept (Oral)