Sharper Generalization Bounds for Learning with Gradient-dominated Objective Functions
Authors: Yunwen Lei
Yiming Ying
Venue: ICLR 2021 Poster (2021)
Keywords: generalization bounds
non-convex learning

Abstract: Stochastic optimization has become the workhorse behind many successful machine learning applications, which motivates a lot of theoretical analysis to understand its empirical behavior. As a comparison, there is far less work to study the generalization behavior especially in a non-convex learning setting. In this paper, we study the generalization behavior of stochastic optimization by leveraging the algorithmic stability for learning with $\beta$-gradient-dominated objective functions. We develop generalization bounds of the order $O(1/(n\beta))$ plus the convergence rate of the optimization algorithm, where $n$ is the sample size. Our stability analysis significantly improves the existing non-convex analysis by removing the bounded gradient assumption and implying better generalization bounds. We achieve this improvement by exploiting the smoothness of loss functions instead of the Lipschitz condition in Charles & Papailiopoulos (2018). We apply our general results to various stochastic optimization algorithms, which show clearly how the variance-reduction techniques improve not only training but also generalization. Furthermore, our discussion explains how interpolation helps generalization for highly expressive models.

Published as a conference paper at ICLR 2021
SHARPER GENERALIZATION BOUNDS FOR LEARNING WITH GRADIENT-DOMINATE OBJECTIVE FUNCTIONS
Yunwen Lei Yiming Ying
School of Computer Science, University of Birmingham, Birmingham B15 2TT, United Kingdom DDpaatmeent of Computer Science, TU Kaiserslautern, Kaiserslautern 67653, Germany
3 DDepartment of Mathematics and Statistics, State University of New York Albany, USA y. .eleei @whambhhhh....... ac. uk yyingealbany. edu
ABSTRACT
Stochastic optimization has become the workhorse behind many successful ma- chine learning applications, which motivates a lot of theoretical analysis to un- derstand its empirical behavior. As comparison, there is far less work study the generalization behavior especially in a non-convex learning setting. In this pa- per, we study the generalization behavior of stochastic optimization by leveraging the algorithmic stability for learning with B-gradient- grrddeen-dommnntee objective func- tions. We develop generalization bounds of the order ((1((n5) plus the conver- gence rate of the optimization algorithm, where is the sample size. Our stabil- ity analysis significantly improves the existing non-convex analysis by removing the bounded gradient assumption and implying better generalization bounds. We achieve this improvement by exploiting the smoothness of loss functions instead of the Lipschitz condition in Charles & Papailiopoulos (2018). We apply gen- eral results to various stochastic optimization algorithms, which show clearly how the raruutce-rdduction techniques improve not only training but also generaliza- tion. Furthermore, our discussion explains how interpolation helps generalization for highly expressive models.
INTRODUCTION
Stochastic optimization has found tremendous applications in training highly expressive machine learning models including deep neural networks (DNNs) (Bottou et al. which are ubiquitous in modern learning architectures (LeCun et al.) 2015). Oftentimes, the models trained in this way have not only very small training errors or even interpolate the training examples, but also surpris- ingly generalize well to testing examples (Zhang et al. 2017). While the low training error can be well explained by the over- wver-parametrization of models and the efficiency of the optimization algo- rithm in identifying local minimizer (Bassily et al.) 2018 Vaswani et al. 2019 Ma et al. 2018) it is still unclear how the highly expressive models also achieve a low testing error (Ma et al. 2018)) With the recent theoretical and empirical study, it is believed that a joint consideration of the in- teraction among the optimization algorithm. learning models and training examples is necessary to understand the generalization behavior (Neyshabur et al. 2017 Hardt et al. 2016 Lin al. 2016).
The generalization error for stochastic optimization typically consists of an optimization error and an estimation error (see e.g. [Bousquet & Bottou| (2008)). Optimization errors arise from the sub- optimality of the output of the chosen optimization algorithms, while estimation errors refer to discrepancy between the testing error and training error at the output model. There a large studying the optimization error (convergence) of stochastic optimization al-
amount of literature gorithms (Bottou et al., 2018 Orabona 2014, Karimi et al.) 2016 Ying Zhou, 2017] Liu et al,, 2018). In particular, the power of interpolation clearly justified in boosting the convergence rate of stochastic gradient descent (SGD) (Bassily et al.) 20188, Vaswani et al., 2019; Ma et al. 2018). In contrast, there is far less work studying estimation errors of optimization algorithms. In seminal paper (Hardt et al. (0166). the fundamental concept of algorithmic stability was used to study the generalization behavior of SGD, which was further improved and extended in Charles & Papailiopoulos (2018); Zhou et al. (2018b): Yuan et al. (2019): Kuzborskij & Lampert (0018).
"Corresponding author; Yiming Ying

---

Published as a conference paper at ICLR 2021
However, these results are still not quite satisfactory in the following three aspects. Firstly, the
isting stability bounds in non-convex learning require very small step sizes (Hardt et al. 2016) and
yield suboptimal generalization bounds (Yuan et al.] 2019 Charles & Papailiopoulos 2018 Zhou
et al., 2018b). Secondly, majority of the existing work has focused on functions with a uniform Lipschitz constant which can be very large in practical models if not infinite (Bousquet & Elisse- eif 22002 Hardt et al. 2016] Charles & Papailiopoulos 2018; Kuzborskij & Lampert] (018)) c.g., DNNs. Thirdly, the existing stability analysis fails to explain how the highly expressive models still generalize in an interpolation setting, which is observed for overparameterized DNNs (Arora et al.,
2019 Brutzkus et al. 2017: Bassily et al., [018 [Bllin et al.) 2019).
In this paper, we make attempts to address the above three issues using novel stability analysis approaches. Our main contributions are summarized as follows.
1. We develop general stability and generalization bounds for any learning algorithm to optimize (non-convex) --gradient-dominated objectives. Specifically, we show that the excess generalization error is bounded by (1)()))) plus the convergence rate of the algorithm, where is the sample size. This general theorem implies that overfitting will never happen in this case, and generalization would always improve as we increase the training accuracy, which is due to an implicit regularization effect of gradient dominance condition. In particular, we show that interpolation actually improves generalization for highly expressive models. In contrast to the existing discussions based either hypothesis stability or uniform stability which imply at best a bound of O(1 / Vn.3), the main idea is to consider weaker on-average stability measure which allows replace the uniform Lipschitz constant in Hardt et al. (2016); Kuzborskij & Lampert (2018); Charles & Papailiopoulos (0018) with the training error of the best model.
2. We apply our general results to various stochastic optimization algorithms, and highlight the ad- vantage over existing generalization analysis. For example, we derive an exponential convergence of testing errors for SGD in an interpolation setting, which complements the exponential convergence of optimization errors (Bassily al., 2018, Vaswani et al., 2019, Ma al., 2018) and extends the existing results (Pillaud- Vivien et al. ( & Suzuki (019) from a strongly-conver setting to a non-convex setting.
particular, we show that stochastic auriance-reduced optimization out- performs SGD by achieving significantly faster convergence of testing errors, while this advantage is only shown in terms of optimization errors in the literature (Reddi et al., 2016 Lei et al. 2017
Nguyen et al. 2017 Zhou et al. 2018a Wang et al. 2019)
2 RELATED WORK
Algorithmic Stability. We first review the related work on stability and generalization. Algorith- mic stability is a fundamental concept in statistical learning theory (Bousquet & Elisseefi 2002
Elisseeff et al. 2005), which has a deep connection with learnability (Shalev-Shwartz et al. 2010
Rakhlin et al. 2005). The important uniform stability was introduced in Bousquee & Elisseeff (2002), where the authors showed that empirical risk minimization (ERM) enjoys the uniform sta- bility if the objective function is strongly convex. This concept was extended to study randomized algorithms such as bagging and bootstrap (Elisseeff et al. 2005). An interesting trade-off between uniform stability and convergence was developed for iterative optimization algorithms, which was then used to study convergence lower bounds of different algorithms (Chen et al.) 2018). While gen- eralization bounds based on stability are often stated in expectation, uniform stability was recently shown to guarantee almost optimal high-probability bounds based on elegant concentration inequal- ities for weakly-dependent random variables (Maurer 2017 Feldman & Vondrak 2019 Bousquet et al. 2020). Other than the standard classification and regression setting, uniform stability was very successfully to study transfer learning (Kuzborskij Lampert, 2018). PAC-Bayesian bounds (Lon-) don] 2017). other stability measures include the uniform argument stability (Liu et al.] 2017). hypothesis sta- bility (Bousquet & Elisseeff 2002). hypothesis set stability (Foster et al.] 2019) and on-average stability (Shalev-Shwartz et al. (2110). An advantage of on-average stability is that it is weaker than the uniform stability and can imply better generalization by exploiting either the strong convexity of the objective function (Shalev-Shwal Shwartt & Ben- David 2014 Corollary 13.7) or the more relaxed exp-concavity of loss functions (Koren & Levy] 2015 Gonen & Shalev-Shwartz 2017). Since condition is another relaxed extension of strong convexity, we use on-average stability to study generalization bounds.
2017) privacy learning (Bassily et al.] (019) and pairwise learning (Lei et al. 2020b). Some
2

---

Published as a conference paper at ICLR 2021
Generalization analysis. We now review related work generalization analysis for stochastic op- timization. In a seminal paper (Hardt et al. 2016), the authors used the nonexpansiveness of gradient mapping to develop uniform stability bounds for SGD to optimize convex, strongly convex and even non-convex objective functions. This inspired some interesting work on stochastic optimization. An interesting data-dependent stability bound was developed for SGD, nice property of which is that it shows how the initialization would affect generalization (Kuzborskij & Lampert, 20188) These sta- bility bounds were integrated into a PAC-Bayesian analysis of SGD, yielding generalization bounds for arbitrary posterior distributions [London 2017). Almost optimal generalization bounds were developed for differentially private stochastic convex optimization (Bassily et al. 2019). The on- average variance of stochastic gradients was used to refine the generalization analysis of SGD (Hardi
jet al. 2016) non-convex optimization (Zhou et al. 201 The uniform stability was also studied for SGD implemented in stagewise manner Yuan et al.] (019) and stochastic gradient Langevin dynamics in a non-convex setting (Li et al. 2020; Mou et al. 20188) Very recently, the discussions in
Hardt et al. (2016) were extended to tackle non soooth (Lei & Ying 2020, Bassily et al. (2020) and
non-Lipsethiz functions (Lei & Ying 2020). The most related work is [Charles & Papailiopoulos 2018), where some general hypothesis stability bounds were developed for learning algorithms that converge to optima. A very interesting point is that their bounds depend only on the convergence of the algorithm to global minimum and the geometry of loss functions around the global minimum. However, their discussion imply at best the slow generalization bounds ([1/vn3) for 3-gradient- dominated objective functions, and can not explain the benefit of low optimization errors in helping generalization. The underlying reason is that they used the pointwise hypothesis stability and did not consider the smoothness of loss functions. We aim to improve these results by leveraging the weaker on-average stability and smoothness of loss functions.
Other than the stability approach, there is interesting generalization analysis of SGD based on either uniform convergence approach (Lin et al. 20166), an integral operator approach (Lin & Rosasco
2017 Ving & Pontil 2008) Dieuleveut & Bach| 2016 Dieuleveut et al./ 2017 Mücke et al. 2019) or information-theone approach (Xu & Raginsky 2017.N et al. 2019 Bu et al. 2020).
MAIN RESULTS
Let p be a probability measure defined on a sample space 2 = X'x with X' C Rd and y C RR from which a training dataset S { [1,, (......,2 Zn) is drawn independently and identically. The aim find a good model w from a model parameter space W based on the training dataset S. The performance of a prescribed model w on single example z can be measured by a nonnegative loss function f(w 2w: where f W x 2 + Rt. In machine learning we often apply an (randomized) algorithm A: : U + W to S to produce an output model A(S) E W. Oftentimes, the constructed model w would have small empirical risk (w)
Σ [(w; 2,). However, we are mostly interested in the generalization performance of model w on testing examples measured by the population (Irue) risk F(w) = E, [f(; 2)]. where Egg denotes the expectation with respect to (w.I.t) 2. The gap between the population risk and empirical risk is called the estimation
Es (F((())))) error, which is due to the approximation of by sampling. Here EA denotes the expectation w.r.t. the randomness of the algorithm A. For example, if A is SGD, then EA denotes the expectation w.r.t. the random indices of training examples selected for the gradient computation. A powerful tool study the estimation error is the algorithmic stability (Bousquet & Elissceff. [002] Elisseeff et al. 2005, Shalev-Shwartz et al., 2010 Hardt et al. 2016). which measures the sensitivity of the algorithm's 's output w.r.t. the perturbation of training dataset. Below we give formal definitions of stability measures, whose connection to generalization is established in Theorem A.I
Definition 1 (Uniform Stability). A randomized algorithm A has uniform stability e if for all datasets S,S E 2d that differ by at most one example, we have sup, (x - f(A(S)):) I
The following on-average stability is similar to the average-RO stability in Shalev-Shwaal et al. 2010). The differrnce is we do not use an absolute value. For m E N, we denote [m] = [l..... m).
Definition 2 (On-average Stability). Let S = {21,..., }n} and Š = { ... ,,, be drawn in- dependently from p. For each [n], denote 5t1) {21, ži-1, 1,,,,.,,,-1,,,, E., 1,..,.... }. We say an algorithm A has on-average stability e if _ Σn_ L (S((S S(A()) Se.
3

---

Published as a conference paper at ICLR 2021
In this paper, we are interested in the excess generalization error F(A(S)) F(w"), where w' arg minwew F F(w) ) is the best model with the least testing error (population risk). For this purpose, we introduce some basic assumptions. A basic assumption in non-convex learning is the smoothness of loss functions (Ghadimi & Lan 2013 Karimi et al. 2016). meaning the gradients are Lipschitz continuous. Let 1/2 denote the Fuclidean norm and denote the gradient operator.
Assumption 1 (Smoothness Assumption), We assume for all = E 2, the differentiable function + [w; z) is I-smooth, i.e., [V/[(;;)) V L/| w'll2 for all w, w' E W.
Another assumption is the Polyak-Lojjasiewic (PL) condition on the objective function, which is
common in non-convex optimization (Zhou et al., 2018h Reddi et al.] 2016; Karimi et al. 2016 Wang et al. 2019; Lei et al. 2017), and was shown to hold true for deep (linear) and shallow neural networks (Hardt Ma 2016 Charles & Papailiopoulos 2018 Li & Yuan 2017).
Lojasiewicz Condition). Denote Fss infw'ew (sww"). We assume Fs satisfies PL or pradient-dominated condition (in expectation) with parameter 3 > 0, i.c.
Assumption 2
1 Es [w)]], Vw W.
Es [F((w)
Fs] s 2,3
(3.1)
is worthy of mentioning that our results in this section continue to hold if the global PL condition is relaxed to local PL condition, i.e., (3.1 holds for w in a neighborhood of the minimizer of Fs.
The existing stability analysis often imposes a bounded gradient assumption below (Bousquet & Elisseeff 2002; Hardt et al.] 2016: Charles & Papailiopoulos] 2018:) Yuan et al., 2019 Kuzborskij Lampert 2018). Indeed, the resulting stability bounds depend on the uniform Lipschitz constant G (see eq. (344). which can be prohibitively large in practical models, e.g., DNNs, even infinite,
e.g. least squares regression in an unbounded domain.
Assumption 3 (Bounded Gradient Assumption). We assume [|V/(w;; 2)12 S G for all w E W,
2 E Z and a constant G > O.
Our main result to be proved in Appendix B removes Assumption 3 and replaces the uniform Lips- chitz constant G by the minimal empirical risk Fs. which is significantly smaller than the Lipschitz constant. Note the assumption L n3/4 is mild, and the previous generalization bounds become vacuous as (1)) Yuaan et al. 2019 Charles & Papailiopoulos 2018 if this assumption is violated. hold and ws A(S). If L S nB/4, then
Theorem (Main Theorem). Let Assumptions
7
16LE[Fs]
LE (ws) - Fs]
B[F(ws) Fs]
(3.2)
nz,3
2
An important implication is as follows. Since E[ss] S ((Fs(w")) F(w*) and L'g Fs(Ws)) Eq. (32) implies upper bound the excess generalization error F(F(ws)] F(w""" and
E ((((ws) - Fs(ws)) = =0 1 +
(Wss) Fs]
(3.3)
8 The above two terms can be explained as follows. The term ((1((n,3) reflects the intrinsic com- plexity of the problem, while E (Ws)) - Fs] is called the optimization error. An interesting observation is that the overfitting phenomenon would never happen for learning under the Pl. condi- tion (analogous to learning with strongly convex objectives where the global minimizer generalizes well (Bousquet & Elisseeff) 2002)). Indeed, if the optimization algorithm finds more and more curate solutions, it achieves the limiting generalization bound ((n)))))). This shows an important message that optimization can be beneficial to generalization. This seemingly counterintuitive phe- nomenon is due to the implicit regularization enforced by the PL condition (analogous to the strong convexity condition). Another notable property is that Theorem applies to any algorithm. We can plug any known optimization error bounds into it to immediately get generalization bounds.
n3
Remark 1. We show that our result significantly improves the existing stability analysis. The work (Charles & Papailiopoulos/ 2018) showed the pointwise hypothesis stability is controlled
by 2G 13 + 2/2G [[Fs(wss) fs)/B, which together with the connection between stability and generalization (cf. (A.I) implies with probability 1 that
M2
24MG²
24MG 2E FE - Fs] 1o
F(ws) & Fs(ws) +
(3.4)
nd
n338
V88
4

---

Published as a conference paper at ICLR 2021
The above bound requires the bounded gradient assumption [V; G and the bounded loss assumption 0 S f(;;2) 2) I M for all w E W and E Z, which are successfully removed in our generalization analysis. Furthermore,
generalization bound significantly improves (3.4)
Indeed, assume ((F)( Fs] S 2 for some > 0, then (3.3) implies
[[F(ws)] B [[ss(ws)] + 0
(3.5)
n2
while 3.4 becomes F(ws) = (ws))) + o Vn3 + Vt). To achieve the generalization guarantee
( (LL///3) /n3), the above bound requires the optimization accuracy c (L8() while our bound 3.5) only requires the accuracy 6 = O(1/ vn.3) but gets the significantly better generalization bound 1/(33). We actually develop better stability bound. Specifically, the pointwise hypothesis stability is bounded by 0( m <) in Charles & Papailiopoulos/ (2018) while we show that the on-
n2 I <<> (ignoring average stability is bounded by O na +) which is significantly tighter if 1
constant factors). It should be mentioned that [Chrlles & Papailiopoolos (2018) did not impose a smoothness assumption. However, the smoothness assumption is widely used in non-convex opti- mization to derive meaningful rates (Ghadimi & Lan| 2013). As compared to probabilistic bounds in Charles & Papailiopoulos (2018). our bounds are stated in expectation. The extension to high- probability bounds will lead to additional O(1/ /2) term (Feldman & Vondrak, Vo11r.
Remark (Bounded gradient assumption). Very recently, the bounded gradient assumption was also removed for the stability analysis (Lei & Ying. 2020). However, their analysis considered SGD applicd to convex loss functions. As a comparison, we study stability and generalization in a non- convex learning setting, and our analysis applies to any stochastic optimization algorithms.
Remark 3. If A is ERM, Theorem immediately implies E ([F(ws) Fs] < 162 E
[[ If Fs
ng
is 3-strongly convex and L < n,/2, it was shown for ERM that E F - Fs] <
48L ng
E [s]
(Shalev-Shwartz& & Ben- 2014 Corollary 13.7). Their result is extended here from strongly convex setting to a gradient-dominatee setting, and from the particular ERM to any algorithm.
As direct corollary, can derive the following optimistic bound in the interpolation setting, which is the most intriguing case for over-parameterized or highly expressive DNN models.
Corollary 2. Let Assumptions
1 hold and ws = A(S). If [[fs] 0 and L < &n3/2, then
[[F(ws)) < 28 F [Fs(ww))]-
Remark 4. Corollary 2 shows benefit of interpolation in boosting the generalization by achieving a generalization bound O(c) for any <> if we minimize Fs sufficiently well. This benefit can not be explained by the existing discussions (Hardt et al., (016)] Charles & P'apaliopoulos] (0018) as they imply the same generalization bound O(1/vn5) in the interpolation setting. Although it was observed that interpolation helps in training (Bassily et al. [2018] Vaswani et al.) 2019: Ma et al.)
2018 Oymak & Soltanolkotabi 2020 Allen-Zhu et al. 2019; Zou et al.) 2018). it is still largely unclear, as indicated in Ma et al. (2018), that how interpolation helps in generalization. Corollary shows new insights on how interpolation from highly expressive models helps generalization.
We now move to the discussion the critical assumption in Corollary 2 i.c. L n3/2. According to the proof, the two parameters L and |3 can be replaced by their local counterparts, i.e., the smoothness and PL condition related particular minimizer w' of Fgc (Eqs. (B.6). (B.7) For example, 3 can be replaced by F/ w') /1// (w') P9)), which can be larger than 3. Below are some examples on explaining L/3 < n/2. As we will see, the quantity L/3 reflects the complexity of the problem (related to condition number as shown in Examples 2). Therefore, the condition T./3- < n// imposes implicitly constraint on the complexity of the problems. This explains why the optimization algorithm would never overfit when applied to gradient-dominated objective functions if L/3 3 < n/2, as shown in Theorem
Example Let Φ _R_ + R be a feature map, and f: RxR+ R,, be a loss function which is Le- smooth and -t-stongyyy convex w.r.t. the first argument. Consider f(w; 2) = (((w, o(z,)), y1) with (5-) being an inner product. Then, Fs satisfies the PL condition with the parameter d (Es)ot, where Σg =
is the empirical covariance matrix, AT denotes the transpose of matrix A and P (A) means the minimal zero singular value of A. The empirical counterpart (we have an expectation w.r.t. S in PL condition) of L/B is of the order of o m / (Es), where mmax (A) means the maximal singular value (we give details in Appendix E.
(A)
5

---

Published as a conference paper at ICLR 2021
Example 2. Consider neural networks with single hidden layer with d inputs, m hidden neu- rons and a single output neuron, for which the prediction function takes the form hy,w = Σx=1 2 2)). Here Wa E g2 and Uk E R denote the weight of the edges connecting the k-th hidden node the imput and output node, respectively, while á R + R is the activation function. Analogous to Arora et al. (2019); Oymak & Soltanolkotabi (2020), we fix V = (V1...., Vun) with |ux| = a for some a and train w (W1, W Wm. Rnxd from S. The loss function then takes the form z(w; = (v σ( (w)) -y) If we consider the identity activation function, i.e., <(t) = t, then Fs satisfies the PL condition with the parameter m (Es), where m (A)) denotes the minimal singular value of A and Σg Σ== ",,;" The empirical counterpart of L/B is of the order of mmx (Eg) (Es) (we give details in Appendix E.2 for a general activation function).
is possible to get generalization bounds under some other conditions. Since one-point strong convexity condition together with smoothness assumption implies the PL condition (Yuan et al. 2019). all our results upply one-point strongly convex functions. We can also get generalization bounds for objective functions satisfying the quadratic growth condition (Necoara et al. 2018), which is weaker than the PL. condition. However, we need to impose a realizability condition which The proof of Theorem is given in Section Let (S5) denote the Euclidean projection of w onto the set of global minimizers of Fss in W.
was also imposed in Charles & Papailiopoulos (2018). (2018)
Definition 3 (Quadratic Growth Condition). We say Fs : W + R satisfies the quadratic growth condition (in expectation) with parameter (3 if TE [F[([[[[)-))) Ps] 2 [F[[[ww(99 Theorem 3. Let Assumption Tarioom@Tholl Thold and Fs satisfy the quadratic growth condition with parameter 3. If the problem realizable, ie., [[ss]] = 0 and S n3/4, then E.. [F(ws)] S (Fs3B
for all w E W.
Finally, we consider any optimization algorithms applied to pradient-dominated and Lipschitz con- tinuous functions. We do not require loss functions to be smooth here. It shows that the excess generalization bound can decay as fast as ((1/(n.8) if we solve the optimization problem to suf- ficient accuracy, which is much better than the generalization bound (11 /1/vvl n, in Charles & Pa- pailiopoulos (2018). Recall the analysis in Charles & Papailiopoulos (2018) requires Assumptions
2 and a further assumption on boundedness of loss functions. The proof is given in Section
Theorem 4. Let Assumptions
hold and ws = A(S). Then the following inequality holds
2G
G FFs(sF(()) - FFs))*
EE [[F(ws)- Fs] S
nB
22
4 APPLICATIONS
In this section, we apply Theorem I different stochastic optimization algorithms such as stochastic gradient descent, randomized coordinate descent, and stochastic variance- reduced optimization. In particular, we study the number of stochastic gradient evaluations required to achieve a prescribed generalization bound, which is summarized in Table
We always assume I. < n.3 in this section.
4.1 STOCHASTIC GRADIENT DESCENT
We need some notations to state results on SGD. Specifically, denote by W1 E W an initial point of SGD. At the t-th iteration, we first randomly select an index it unif(n), and then update (wele by
W++1 W; n) V VVf.awww f(W,;
(4.1)
where he is sequence of positive step sizes and unif[m] denotes the uniform distribution over [n]. The proof of Theorem iis given in Appendix [D.]
Theorem 5. Let Assumptions
2 hold with L < n.3 44 Let A be SGD with the step size sequence 23(1+1)2- Then E[F(Wr+1)] F(w*) O ng
26+1
+ 1
TB3 We can take O 0(
(²2 stochastic
gradient evaluations to get excess generalization bounds ((1/(n))).
Remark 5. We compare Theorem 5 with the recent generalization analysis of SGD under the PI. condition. Based on pointwise hypothesis stability analysis and the optimization error bound in
Karimi et al. 2016), it was shown with probability at least - (Charles & Papailiopoulos/ 2018
F(Wr+1) - F(w") = 0( 1
1
(4.2)
Vn.8
T43

---

Published as a conference paper at ICLR 2021
Algorithm
Complexity for 1/(33)
Complexity for if E
[[]ss 0
SGD
gz log
RCD
dlng m
d log
0
Be
SVRG, SCSG
(n + n /3) logn n
(n + n
log Bc
SARAH, SpiderBoost
(n 1/8²) log n
(n + 1/82) log
SNVRG
nn + vn/B (3) log*
(n + /n/3 log"
De
Table I: Iteration complexity for different optimization algorithms to achieve a stated generalization bound under Assumptions 1 2 In the second column, we present the number of stochastic gradient evaluations to achieve excess generalization bounds ((1/(n8)). In the third column, we present the number of stochastic gradient evaluations to achieve generalization bounds O(e) if B[Fs] 0. We ignore constant factors. is known that variance-reduction techniques improve the iteration complexity to achieve small training errors. Our stability analysis shows that such an improvement is also achieved for testing errors. Note that the stability analysis in Charles & Papailiopoulos (2018) can at most imply an excess generalization bound (L1/vn3) for these algorithms.
The above bound indicates that ( 0n2²/3) stochastic gradient evaluations are needed to get the excess generalization bounds ((1/ y /n3). Based on the uniform stability bound in Hardt et al. (2016) and the optimization error bound in Karimi et al. (2016), it was shown in Yuan et al. (019)) that
L/B F(w") = 0 n (n 14
B[F(wr-1)
+ O
(4.3)
TB2
By taking an optimal T = n n113273 5 2431/22 (ignoring a constant factor) to balance the above
142/8
B T#2173 ). If L/3 is moderately large, then this bound quickly becomes E ([F(wr+1) - F(w") = 0(1 vn.).. With high proba- bility at least - 5, it was shown that SGD with the step size 17c (1+2) log(t+2) gets the bound
two terms, we derive [[[((T++)] - F(w*) = =O(n 1+2/3
F(WY+1)- - Fs (1 = ((Clogg Vno) (Zhou et al. 2018b). However, is not clear how the optimization errors decay with such step sizes. Typically, should be of the order 011/3) as shown in Karimi et al. (2016) and therefore the stability analysis in Zhou et al. (2018)) can at best achieve the generalization bounds (VVlog T / Vnz) To summarize, the existing stability analysis generally implies the generalization bound 0(1 nB for SGD in learning with gradient-dominated objec- tives (Charles& & Papailiopoulos) 2018 Zhou et al. [20 8b Yuan et al. 2019). which is significantly improved to ([1((n5)) in our paper by the refined stability analysis. It worth mentioning that, in this comparison, we have used the same optimization error bounds in Karimi et al. (2016), and the analysis in Charles & Papailiopoulos (2018); Zhou et al. (2018b); Yuan et al. (2019) requires a bounded gradient assumption and bounded loss assumption, which are removed in our analysis.
The above iteration complexity in Theorem 5 can be further improved if we impose restricted secant inequality (Karimi et al. 2016) on Fs, which has been considered for non-convex optimiza- tion, e.g., optimizing neural networks (Li & Yuan 2017). This is slightly stronger assumption than the PL condition as shown in Karimi et (2016).
Definition 4 (Restricted Secant Inequality). We say Fs : W + R satisfies the restricted secant inequality with parameter /3 if E [[((ww - w(5), - Fss(w)) 2 [T[|| [5) for all w E W.
Theorem 6. Assume F' satisfies the restricted secant inequality with parameter B. Let Assumption 7 hold with L < n33 /4. Let A be SGD with 1)+- 11(3((++1) Then one can take (n/B) stochastic gradient evaluations to achieve the excess generalization bounds ((1(n))).
Below we apply Theorem I to establish fast generalization bounds in an interpolation setting. Our analysis shows that interpolation actually boosts SGD by achieving exponential convergence of testing errors, which can not be derived from the bound (3.4) in Charles & Papailiopoulos/ (2018).
Theorem 7. Let Assumptions 1 1 hold with L < n.3/4 44 and E| = 0. Let A be SGD with N = 3/13. Then [[F(W1+1)] < L(1-82 [[Fs(wi)]] We can take ( 1og-2log(//// log(1/(Be))) stochastic gradient evaluations to achieve the generalization bound O(c) for any 6. > 0.
23
The above linear convergence does not contradict existing minimax lower bounds where the benefit of interpolation is not considered. The proofs for Theorems 6
7 are given in Appendix D.
7

---

Published as a conference paper at ICLR 2021
Remark 6. We discuss some recent work error bounds in low-noise conditions. Optimization errors of SGD were studied for general non-conves objectives (Vaswani et al. 2019 Ma 2018) and gradient- mominnnt-dmmiatee objectives (Bassily et al. 2018). For binary classification problems with the specific squared loss, it was shown SGD achieves an exponential convergence of testing classifica- tion errors under margin condition, i.e., positive and negative classes separated by margin that is strictly positive (Pillaud- -Viiinn et al.1/2018). This was extended to general convex loss functions under the same margin condition (Nitanda & Suzuki, 2019). These discussions consider regular- ized objective functions (Pillaud- Vivien et al., 2018]] Nitanda & Suzuki, 2019), which are strongly convex. The exponential convergence in [Pillaud- Vivien et al. 2018): Nitanda & Suzuki (2019) was established for the testing classification errors, i.e., 0-1 loss. As a comparison, we establish an expo- nential convergence for the testing errors measured by loss functions used in training. In addition, the exponential convergence in PPlllaud Vivien et al. (2018); Nitanda & Suzuki (2019) comes into effect only after a sufficiently large number of iterations, which is not required in Theorem 7
4.2 RANDOMIZED COORDINATE DESCENT
Randomized coordinate descent (RCD) is an efficient optimization algorithm particularly useful for high-ding aigh-dimensional learning problems (Nettervv 2012). At each iteration it firstly randomly selects a single coordinate is E {1....,dl dd}, and then performs the update along the iş-th coordinate as W++1 = W T/e Vi, Fs(We))., where V,Fs denotes the derivative of Fs w.r.t. the i-th coordinate and e; is a vector in IR with the i-th coordinate being 1 and other coordinates being 0.
Theorem 8. Let Assumptions
| and 2 hold with I n3/44. Let A be RCD with n = L/L. Then 4) ) We take (((dlogn)// stochastic gradient eval- uations to get excess generalization bounds ((1((n))). [f]] = O, we take dl 13(e)) stochastic gradient evaluations to get generalization bounds (ct) any > O.
- 0 1 +
The detailed proof for the above theorem is given in Appendix D.2 As indicated in Remark [ the discussion in Charles & Papailiopoulos/ (2018) can only imply the generalization bound O(1/ Vn3).
4.3 STOCHASTIC VARIANCE- BARIANCE-REDUCEI REDUCED OPTIMIZATION
SGD needs a diminishing step size due to the inherent variance of stochastic gradients, which gen- erally yields a sublinear convergence rate (Bottou al. 2018). Recently, there is large amount of work to accelcrate SGD by using some different gradient estimates with a reduced variance (Johnson & Zhang] 2013 Xiao & Zhang 2014 Zhang et al. 2013 Allen-Zhu & Hazan 2016 Fang et al. Wang et al. Nguyen et al. 2hou et al.) 20188a] Schmidt et 2l.]2011/ et al.,
2018
2014 Reddi et al. 2016). This class of algorithms proceeds in epochs. Let Wo be an initialization
point. At the beginning of s-th epoch, we set reference point We W,-1, draw a batch I, S [n]
and compute vo = VJz, (Wo), where we denote f7 IT Eie [(w; z;) for T C [v)] and [T]
is the cardinality of I. The batch I, can be equal to [m]] Johnson & Zhang 2013 Xiao & Zhang, 2014 Wang et al.) 2019 Reddi et al. (016) or drawn with replacement according to the uniform distribution over [>] (Lei et al.) 2017 Fang et al. 2018). Then we proceed with m, inner iterations by using some gradient estimators with reduced variances. At the f-th inner iteration, we first draw a batch 1, C [n] from the uniform distribution over [rz). The original SVRG (Johnson & Zhang 2013
Reddi et al. 2016 Xiao & Zhang 2014) uses the gradient estimator (we omit the dependency on s)
Ve Vf,, (w:) - Vfz, (wo)
Vo-
(4.4)
Recently different update of gradient estimator is proposed Nguyen al. 2017 Fang al.
2018
Vi = Vi,((w))
V.f.. (w--1)
Vi-1-
(4.5)
An important observation is that the variance of va diminishes to zero as we are approaching the
minimum, which allows us update the iterate with a constant step size W++1 w. - (John-
son & Zhang] 2001).. The framework of stochastic variance-reduced optimization is described in Algorithm Appendix [D.3 The following theorem gives generalization bounds ((1((n,)) for stochastic variance-reduced optimization, which significantly improves the bound ( 1///3)) based
on B.4. The proof is given in Appendix [.3]
Theorem 9. Let Assumptions
7 and 2 hold with L < n.3/4. Let A be either the SARAH in Nguyen
el al. 2017) or the SpiderBoost in Wang et al. (2019). We can take O(1 + 1/3²) logn) stochastic
gradient evaluations to get excess generalization bounds ((1(n33). IfE[is] = 0, we take O ((n+ 1/32) log 1/ (3e)) stochastic gradient evaluations to get generalization bounds (c)) for any e 0.
8

---

Published as a conference paper at ICLR 2021
0225
0175
100
0150
10a
10
0100
0075
300
800
2000
5000
20000
50000
Numbbe of Training Examples
Figure 1: Ky versus [T]
Figure 2: Testing error versus number of passes
As compared to SGD (Section 4.1 Theorem shows SARAH/SpiderBoost requires significantly fewer iterations achieve the same testing errors. This shows clear advantage of stochastic variance-reduced optimization over SGD in generalization other than training. Other than SARAH and SpoderBoost, also develop generalization bounds for SVRG in Reddi et al. (2016). SCSG in Lei et al. (2017) (Theorem D.3) and SNVRG-PL. in Zhou et al. (201 8a)
(Theorem D.4).
5 SIMULATIONS AND CONCLUSIONS
Simulations. We report some preliminary experiments to support our theory. We consider the dataset IJCNN available from the LIBSVM website (Chang Lin 201T) and report the average of experimental results from 25 repetitions. In our first experiment, max (/ss)/ (2ig) (Mis) S n would be satisfied in practice. To this aim, we randomly pick a subset ... n (1, and build an empirical covariance matrix En
aim to check how the condition
I (1,
M7 Eiez z.J, where |/| denotes
the cardinality of I. Then we compute the term K₃ == Gue (ma((E)) Tnie (E:)) Figure plots the K₃ as a function of I]. It is clear that the condition Ky S 1/4 is violated if [7] small. As 7 increases, Ky decreases and can be small 10-3 Then, the condition Ky S 1/4 holds trivially for sufficiently large n.
Theorem implies that overfitting would never happen for learning with gradient-dominated func- tions. Our second experiment aims verify this phenomenon. We consider generalized linear model for binary classification with the loss function f(w; = (f(w x) - y)² where is the logistic link function ((a) = (1 + (exppa)))))))
It was shown that the corresponding objective func- tion gradient-dominated (Foster et al., 2018). We use 80 percents of the dataset for training and reserve the remaining 20 percents for testing. We apply SGD with the step size = 1/(1 0.001t) and compute the testing error of [w,] on the testing dataset. Figure 2 we plot the testing errors versus the number of passes (iteration number divided by sample size). It is clear that the testing er- ror continue to decrease along the learning process, and there is no overfitting even after 100 passes of the dataset. This is well consistent with Theorem
Conclusions. We study stochastic optimization under the PL condition. We show that the general- ization errors can be bounded by (11((1))) plus the convergence rate of algorithms. An observation that the optimization always helps in generalization under the PL condition. Our analysis based on weak on-average stability measure removes the bounded gradient assumption in the literature, and can imply significantly better bounds. In particular, we show how the interpolation accelerates the generalization. Our study relies this assumption is widely used in the non-convex learning setting, it would be very interesting to extend the discussions here general non-convex objective functions.
essential PL condition the objective function. While
ACKNOWLEDGMENTS
The work of Yunwen Lei is supported by the National Natural Science Foundation of China (Grant No. 61806091) and the Alexander von Humboldt Foundation. The work of Yiming Ying is sup- ported by NSF grants IIS-1816227 and I1S-2008532.

---

Published as a conference paper at ICLR 2021
REFERENCES
Zeyuan Allen-Zht and Elad Hazan. Variance reduction for faster non-convex optimization. In International Conference Machine Learning, pp. 699-707, 2016.
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparameter- ized neural networks, going beyond two layers. Advances neural information processing systems. pp. 6155-6166, 2019.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of op- timization and generalization for overparameterized two-layer neural networks. In International Conference Machine Learning, pp. 322-2222222 2019.
Raef Bassily, Mikhail Belkin, and Siyuan Ma. On exponential convergence of sgd in non-convex 2018.
over-parametrized learning. arXiv preprint
Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Guha Thakurta. Private stochastic convex optimization with optimal rates. In Advances in Neural Information Processing Systems, pp. 11179-112288 2019.
Raef Bassily, Vitaly Feldman, Cristóbal Guzmán, and Kunal Talwar. Stability of stochastic gradient descent on nonsmooth convex losses. In Advances in Neural Information Processing Systems, 2020.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine- learning practice and the classical barinnar trade-off. Proceedings of the National Academy of Sciences, 1 (5849)):5549-18855555 11554, 2019.
Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM Review, 60(2):223-311, 2018.
Olivier Bousquet and Léon Bottou. 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-522 2002.
Olivier Bousquet, Yegor Klochkov, and Nikita Zhivotovskiy. Sharper bounds for uniformly stable algorithms. In Conference on Learning Theory, pp. 610-626 626, 2020.
Alon Brutzkus, Amir Globerson, Eran Malach, and Shai parameterized networks that provably generalize on linearly separable data. arXiv preprint arXiv: 1701v:1710.10174.
Sgd learns over-
Yuheng Bu, Shaofeng Zou, and Venugopal V Veeravalli. Tightening mutual information based bounds on generalization error. IEEE Journal on Selected Areas in Information Theory, 2020.
Chih-Chung Chang and Chih-Jen Lin. Libsvm: a library for support vector machines. ACM Trans-
actions on Intelligent Systems and Technology, 2(3):27, 2011.
Zachary Charles and Dimitris Papailiopoulos. Stability and generalization of learning algorithms that converge to global optima. In International Conference on Machine Learning, pp. 744-753, 2018
Yuansi Chen, Chi Jin, and Bin Yu. Stability and convergence trade-off of iterative optimization algorithms. arXiv preprint arXiv: 2018
Aaron Defazio, Francis Bach, and Simon Lacoste-Julien, SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives. In Advances in Neural Infor- mation Processing Systems, pp. 1646-1654, 2014.
Aymeric Dieuleveut and Francis Bach. Nonparametric stochastic approximation with large step- sizes. Annals of Statistics, 44(4): 363-1399,, 2016.
Aymeric Dieuleveut, Nicolas Flammarion, and Francis Bach. Harder, better, faster, stronger con- vergence rates for least-squares regression. The Journal of Machine Learning Research, 18(1): 3570-3570, 2017.
Andre Elisseeff, Theodoros Evgeniou, and Massimiliano Pontil. Stability of randomized learning algorithms. Journal of Machine Learning Research, 6(Jan):55-79, 2005.
10

---

Published as a conference paper at ICLR 2021
Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider:
Near- Mear-oltimal non-convex op-
timization via stochastic path-integratee differential estimator. In Advances Neural Information Processing Systems, pp. 689-699, 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.
Dylan Foster, Ayush Sekhari, and Karthik Sridharan. Uniform convergence of gradients for non- convex learning and optimization. In Advances in Neural Information Processing Systems, pp- 8759-8770, 2018.
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, pp. 6726-6736. 2019.
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochas- tic programming. SIAM Journal on Optimization, 23(4):2341-255 -2368, 2013.
Alon Gonen and Shai Shalev-Shwartz Average stability is invariant to data preconditioning: Impli- cations to exp-concave empirical risk minimization. The Journal of Machine Learning Research, 18(1):8245-8257, 2017.
Moritz Hardt and Tengyu Ma. Identity matters in deep learning. arXiv preprint urXiv:1611.0423 2016.
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.
Ric Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Advances in Neural Information Processing Systems, pp- 315-323, 2013.
Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the polyak-tojssiewicz condition. European Conference on Machine Learning, pp. 795-811, 2016.
Tomer Koren and Kfir Levy. Fast rates for exp-concave empirical risk minimization. In Advances in Neural Information Processing Systems, pp. 1477-1485, 2015.
Ilja Kuzborskij and Christoph Lampert. Data-dependent stability of stochastic gradient descent. In International Conference on Machine Learning, pp. 2820-2829, 2018.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. Nature, 521((553):436 444, 2015.
Lihua Lei, Cheng Ju, Jianbo Chen, and Michael Jordan. Non-convex finite-sum optimization via scsg methods. In Advances in Neural Information Processing Systems 30, pp. 2348-2358. 2017.
Yunwen Lei and Yiming Ying. Fine-grained analysis of stability and generalization for stochastic gradient descent. In International Conference on Machine Learning, pp. 5809-5819. PMIR, 2020.
Yunwen Lei, Ting Hu, Guiying Li, and Ke Tang. Stochastic gradient descent for nonconvex learning without bounded gradient assumptions. IEEE Transactions Neural Networks and Learning Systems, 31(110:439444400 2020a.
Yunwen Lei, Antoine Ledent, and Marius Kloft. Sharper generalization bounds for pairwise learn- ing. Advances in Neural Information Processing Systems, 33, 2020b.
Jian Li, Xuanyuan Luo, and Mingda Qiao. On generalization error bounds of noisy gradient methods for non-convex learning. In International Conference on Learning Representations, 2020.
Yuanzhi Li and Yang Yuan. Convergence analysis two-layer neural networks with relu activation. In Advances Neural Information Processing Systems, pp. 597-607, 2017.
Junhong Lin and Lorenzo Rosasco. Optimal rates for multi-pass stochastic gradient methods. Jour- nal of Machine Learning Research, 18(1):33753441, 2017.
Junhong Lin, Raffaello Camoriano, and Lorenzo Rosasco. Generalization properties and implicit
regularization for multiple passes SGM. International Conference on Machine Learning, pp- 2340-2348, 2016.
11

---

Published as a conference paper at ICLR 2021
Mingrui Liu, Xiaoxuan Zhang, Lijun Zhang, Jing Rong, and Tianbao Yang. Fast rates of ERM and stochastic approximation: Adaptive to error bound conditions. Advances in Neural Information Processing Systems, pp. 4683-4694, 2018.
Tongliang Liu, Gábor Lugosi, Gergely Neu, and Dacheng Tao. Algorithmic stability and hypothesis complexity. In International Conference on Machine Learning, pp- 2159-2167, 2017.
Ben London. PAC-hayesian analysis of randomized learning with application to stochastic gradi- ent descent. In Advances in Neural Information Processing Systems, pp. 2931-2940, 2017.
Siyuan Ma, Raef Bassily, and Mikhail Belkin. The power of interpolation: Understanding the effec-
tiveness of sgd in modern over-parametrized learning. In International Conference on Machine Learning, pp. 3325-3334, 2018.
Andreas Maurer. A second-order look at stability and generalization. In Conference on Learning Theory, pp. 1461-1475, 2017.
Wenlong Mou, Liwei Wang, Xiyu Zhai, and Kai Zheng, Generalization bounds of sgld for non- convex learning: Two theoretical viewpoints. Conference on Learning Theory, pp. 605 638, 2018.
Nicole Mücke, Gergely Neu, and Lorenzo Rosasco. Beating sgd saturation with tail-averaging and minibatching. In Advances Neural Information Processing Systems, pp. 12568-12577, 2019.
Ion Necoara, Yu Nesterov, and Francois Glineur. Linear convergence of first order methods for non-strongly convex optimization. Mathematical Programming, pp. 1-39, 2018.
Jeffrey Negrea, Mahdi Haghifam, Gintare Karolina Dziugaite, Ashish Khisti, and Daniel M Roy. information-thhcortiic generalization bounds for sgld via data-dependent estimates. In Advances in Neural Information Processing Systems, pp. 11015-11025, 2019.
Yu Nesterov. Efficiency of coordinate descent methods huge-scale optimization problems. SIAM Journal on Optimization, 22(2):341-362, 2012.
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nati Srebro. Exploring general- ization in deep learning. In Advances in Neural Information Processing Systems, pp. 5947-5956,
2017.
Lam M Nguyen, Jie Liu, Katya Scheinberg, and Martin Takáč. SARAH: A novel method for ma- chine learning problems using stochastic recursive gradient. International Conference on Ma- chine Learning, pp. 2613-2621, 2017.
Atsushi Nitanda and Taiji Suzuki. Stochastic gradient descent with exponential convergence rates of expected classification errors. In Kamalika Chaudhuri and Masashi Sugiyama (eds.), Interna- tional Conference on Artificial Intelligence and Statistics, pp. 1417-1426, 2019.
Francesco Orabona. Simultaneous model selection and optimization through parameter-free free stochastic learning. Advances in Neural Information Processing Systems, pp. 1116-1124, 2014.
Samet Oymak and Mahdi Soltanolkotabi. Towards moderate overparamettrivaaton:: global con- vergence guarantees for training shallow neural networks. IEEE Journal on Selected Areas in Information Theory, 2020.
Loucas Pillaud-Vivien. Alessandro Rudi, and Francis Bach. Exponential convergence of testing error for stochastic gradient methods. In Conference On Learning Theory, pp. 250-296, 2018.
Alexander Rakhlin, Sayan Mukherjee, and Tomaso Poggio. Stability results in learning theory.
Analysis and Applications, 3(04)3377417,, 2005.
Sashank Reddi, Ahmed Hefny, Suvrit Sra, Barnabas Poczos, and Alex Smola. Stochastic variance reduction for nonconvex optimization. In International Conference on Machine Learning, pp. 314-323, 2016.
Mark Schmidt, Nicolas Le Roux, and Francis Bach. Minimizing finite sums with the stochastic average gradient. Mathematical Programming, 162((-2):83-112 2017.
Shai Shaley-Shwartz and Shai Ben-David Understanding machine learning: From theory algo- rithms. Cambridge university press, 2014.
12

---

Published as a conference paper at ICLR 2021
Shai Shalev-Shward Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Learnability, stability and uniform convergence. Journal of Machine Learning Research, 11(0ct):2635-222) 2670, 2010.
Mahdi Soltanolkotabi, Adel Javanmard, and Jason D Lee. Theoretical insights into the optimization landscape of wver-parameterized shallow neural networks. IEEE Transactions Information Theory, 65(2):742-769, 2019.
Nathan Srebro, Karthik Sridharan, and Ambuj Tewari. Smoothness, low noise and fast rates. In Advances in Neural Information Processing Systems, pp. 2199-2207, 2010.
Sharan Vaswani, Francis Bach, and Mark Schmidt. Fast and faster convergence of sgd for over- parameterized models and an accelerated perceptron. In International Conference on Artificial Intelligence and Statistics, pp. 1195-1204, 2019.
Zhe Wang, Kaiyi Ji, Zhou, Yingbin Liang, and Vahid Tarokh. Spiderboost and momentum: Faster variance reduction algorithms. In Advances in Neural Information Processing Systems, pp- 2403 2413-2413.210 2019.
Lin Xiao and Tong Zhang. A proximal stochastic gradient method with progressive variance reduc- tion. SIAM Journal on Optimization, 24(4):2057-2075, 2014.
Aolin Xu and Maxim Raginsky, Information-theored analysis of generalization capability of learn- ing algorithms. Advances in Neural Information Processing Systems, pp. 2524-2533, 2017.
Yiming Ying and Massimiliano Pontil. Online gradient descent learning algorithms. Foundations of Computational Mathematics, 8(5):561-596 2008
Yiming Ying and Ding-Xuan Zhou. Unregularized online learning algorithms with general loss functions. Applied and Computational Harmonic Analysis, 42(2):224-244, 2017.
Zhuoning Yuan, Yan Yan, Rong Jin, and Tianbao Yang. Stagewise training accelerates convergence of testing over sgd. In Advances in Neural Information Processing Systems, pp. 2604 2614, 2019.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. International Conference on Learning Rep- resentations, 2017.
Lijun Zhang, Mehrdad Mahdavi, and Rong Jin. Linear convergence with condition number inde- pendent access of full gradients. In Advances in Neural Information Processing Systems, pp- 980-988, 2013.
Dongruo Zhou, Pan Xu, and Quanquan Gu. Stochastic nested variance reduced gradient descent for nonconvex optimization. In Advances in Neural Information Processing Systems, pp. 3921-3932.
2018: 8a.
Yi Zhou, Yingbin Liang, and Huishuai Zhang. Generalization enror bounds with probabilistic guar- antee for SGD in nonconvex optimization. arXiv preprint arXiv: 1802:8800000 06903, 2018b.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes over-parameterized deep relu networks. arXiv preprint arXiv:1811.08888 2018.
A STABILITY AND GENERALIZATION
We first give the definition of pointwise hypothesis stability. For any i E [n]. denote S1 {Z 2i-1, Zi41,..., }.
Definition 5 (Pointwise Hypothesis Stability). We say a randomized algorithm A has pointwise hypothesis stability e if for all E [n]] there holds Es Es. (AA(S)
(((S)==))2)) S e.
Theorem A.I establishes the key connection between the generalization and various stability mea- sures. Part (a) and part (b) show that the algorithm with either uniform stability or pointwise hypoth- esis stability generalizes well to testing examples (Bousquet & Elisseeff 2002). Initially, they were developed for deterministic algorithms (Bousquet & Elisseeff, 2002), which were then extended to the setting of randomized algorithms (Elisseeff et a2.55 Part (c) shows the connection between the generalization and the on-average stability Shally-Shwartz et al. 2010). Note part (b) involves square root of 1 1/ instead of a log(1
13

---

Published as a conference paper at ICLR 2021
Theorem A.1 (Generalization by Stability). Let A be randomized algorithm.
(a) If A has uniform stability c, then Es,A (Fs(A(S) - F(A(S))) S.
(b) Let M If A has pointwise hypothesis stability and < f(w;2) S M for all w W and 2. Then for all E (0, 10.1) with probability al least - 0
F(A(S)) & Fs(A(8)) + M + 12M
(A.1)
no
(c) If A has on-average stability 6, then Es,A [F(A(S)) (s(A(S)) S.
Proof. The proof of Part (a) can be found in Hardt et al. 2016
Theorem 2.2). Part (b) was first
proved for deterministic algorithms (Bousquet & Elisseeff 2002
Theorem 11), and then extended
to randomized algorithms (Elisseeff et al. 2005] Theorem 12). We prove Part (c) here due to its simplicity. Since 2, and 2 are drawn from the same distribution, we know
n Σ S. (F((((O) Fs(A(S))]
Es,A (F((S)) Fs(A(S))
= n
E S.S.A [S(A(S ););) [(A(S);
where the last identity holds since 2; is independent of A(S(O). The proof is complete by noting the definition of on-average stability.
B PROOF OF THEOREM
In this section, we prove Theorem We begin our analysis with some useful properties of smooth functions. If g is L-smooth, we have the following self- bofndonnding property (Srebro et al. 2010
[Vg(w)] s 2L (g(w) inf g(w))) Vw W
(B.1)
w'
and the following elementary inequality for all w, E W (Nestervv 2012)
g (w) S g( + (Vg(w). w) L|[ wlB In particular, if is further nonnegative, then
(B.2)
VV((w < 2Lg(w), Vw W.
(B.3)
The following lemma follows directly from the self-bounding property of smooth loss functions. Lemma B.1. Assume F is L-smooth. Then (w depend on S)
B[I[VF(()) 2LE F(w) Fss.
Proof. Recall w = arg min F(w). According to the self-bounding property B. and the
definition of w we know
B[]]F(())13 [|
< 2LE F(w) F(w")] = 2LE(F(w) FF(ww))
22LE Fs].
where we have used E[Fs(w")) [] = F(w*) since w is independent of S, and Fs S Fs(w") due to the definition of Fs. The proof is complete.
In the following lemma, derive the on-average stability bounds under the PI. condition. Recall for any denote by wS) the Euclidean projection of onto the set of global minimizers of Fs in W.
Lemma B.2. If Asssmpptioss
hold, then A has on-average stability satisfying
2L
E E + E ((W(()))))) (3))) + E(F(ws) - F(w + E[fs Fs(ws)).
<
ng
14

---

Published as a conference paper at ICLR 2021
Proof. Let S {21 { 2,] be drawn independently from p. For each i E [nl, let St be defined ( the projection of Wgo in Definition 2 For each E [n], we denote st = A((())) and w sto)
onto the set of global minimizer of Fgos. We decompose f fW 2,) f(ws; 24) follows
= (J(W - f(w (( ( ;2))) [( [(
sit
+ (f(w (860) 24) f(w] 3 24) + (f(ws (5) (2) f(Wss:z)) (B.4)
(S)
We now address the above three terms separately. We first address f(w (1)) ;2,)) f(ww] ((w ; 24). According to the definition of Fs; S, sti), we know
(9)
f( (S ) SG3 ; 2.) = nFs (w 56) - nF
(55)))
(
(8()) 863
(5(1) (
+ f(w
5( 22)
Since 2; and & follow from the same distribution, we know E[f further get
(5(9)
; :1)] = Eff(w (8)
5 ; and
S(0)
B[f(w (s sto [ = n1E n (9(1))
}] - nE Esto (w
(8(1))
)] + B Bf(((ws (9) 21)
5(0)
s(o
It then follows that
E B[f(w (8(9) 24) f(w! (5)
:2)]] nE Fs (w (555)))
Fsto (w (8(9))
}
= nE Fis (w (5
F'((W] WEW
inf
(B.5)
50
where we have used the following identity due to the symmetry between 2, and &;
B[F
(w (()))) 5t9
)]
F[Fs] E. inf Fs(w)]. weW
By the PL condition of Fs, it then follows from B.5) that (in our assumption of PL condition, w may depend on S. This was also imposed in the literature (Yuan al.j [201 Charles Papalliopoulos 2018
Zhou et al. 2018b). Indeed, the PI. condition was often shown for empirical functions Fs)
E
f(w (stt),
2.) - f(w
s (5); x)] S
n
E [[
(8()) g(0) >|(]
(B.6)
s(y)
2B
According to the definition of w s(t) we know V.s (F (5())))) 0 and therefore ((a + 6)2 < 2a² + 2
(8())
[VV (9111)
(w(tt)))
)11 =
(801))
1
(st1)
f (w (w()))) s(0) 22)
(8
S(1)
112
F
(w
V
f(w
S00
2x)
+ n
72
2
w
(8(9)
12 +
2
V
(w se0
(9(1))
2 )1
n²
n
2,)
4L
s(w
(5
sto ; z4,,
(B.7)
sto
no
where we have used the self-bounding property of smooth loss functions B.3 follow from the same distribution, we know
Since z; and 2,
[[ (5(B) 2 = [[[((w
(5) s (5)
12)
[[S(w
(5S) 56
=;::]== = Bls(w 5 2-)-
560
It then follows that
E [
(8
|1
4L Bls(w
(S)
=i) +
4L
Bis w (5) ;.)],
s(a
n
n
which, combined with (B.6), gives
E [[ (sta)
24) f(w ]
2L
E E[f(w! 3 24) Elf( (S) :2)).
(5)
sto
n3
Taking a summation of the above inequality for i 1, l,..., n, we get
Σ
[[( (g(9)) x
s(o) );20)= f(w [2)]] (8);
2L
[E[ + B[F (8) 11)) EEFFs\
(B.8)
3
(8t)) We then address (WWg() 24) - f(w sin ; 2:). Since Wg and w stn are independent of 2;, we know
(8(09)
[f 25) - f(w (8())
g(o [ = E F(Wg:)) - F F(w s00 } = E F((s) - F(w (5) )] (B.9)
(5(9)
where we have used the symmetry between 2; and E..
15

---

Published as a conference paper at ICLR 2021
Finally, address [(w (S) 24) f(ws; 2.). By the definition of w S
(S)
know
Σ (f(ws (8)
(2, (2) - f(w3:2)) n r - Fs(ws)).
(B.10)
Plugging B.8 B.9 and the above inequality back into (B.4). we derive
B f(W 2,) s(ws:
21.
(I (w)))) )
F(ws) - F(ws + +n [Fss - Fs(ws)].
The proof complete by recalling the definition of on-average stability and ([F3(W5))) (5))
B[F(wW (w3 ()
We further require lemma relating the convergence in terms of function values to the convergence terms of models. This shows that the PL condition is stronger than a quadratic growth condi- tion (Karimi et al.] (016))
Lemma B.3 (Karimi et al. 2016). If Fss satisfies the PL condition with parameter 3 > 0. Then for all w W have
E (sFs(w)- - Fs( 2 23B w w 13)))
(B.11)
We are now position to prove Theorem T
Proof of Theorem ! Plugging the on-average stability established in Lemma B.2 back into Part (c) of Theorem
A.I we derive
2L n5
E (w)) Fs(ws)]
B(F(ws) F(w ) + FE Fs(ws)], (B.12)
from which we derive
2L E F[((W) (9) Fs] S nB
[[] + [[F
(B.13)
By B.2 we know the following inequality for all 7 >
F(ws) F(w (5) - (VF( ws w
(S)
L
Ws (
+
IVF(w3 ||a||WS
w
(8)
||2 +
L
|w w 1
VF )1
(
w. w (5) 112.
where we have used the Cauchy- Schwartz inequality. This together with Lemma B. with w w w(()
implies that
E(F(ws) F(w (9)
L [E(((W Es] + (7 Elllws -w w (11)
L
27
Plugging B.13) into the above inequality, we get
E(F(ws) F(w (9) ) -
T, 2T
(H[ (F(((W (3))s + (++
1 E[llws w (1)))
1.
2 nB
2
Taking 7 = I./2, we then get
[F(s(ss) - F(w! (5))
<
2L
[[ + ((F(w + LB ww (
E
n.
Plugging the above inequality back into
B. derive the following inequality
E ((ws) Fs(ws)) <
4L
[TAs
F
(5) }]} + LEIL|Ws - - (ss))))
113
then follows that
E(F(ws) Pss] <
AL
[
+ E F(F(( + LEI[|Ws - -
(B.14)
n3
16

---

Published as a conference paper at ICLR 2021
Since L S n3/4, follows from (B.13) that
[F[(ws (5)
Fs]
[[[Fs] + (((F(w())))
and therefore
E B[F(WW (8) I 3E Fs).
We can plug the above inequality back into BB 14 and derive
[[[(ws)- Fs]
16LE[Fs]
LE Ws
w/ 11
(B.15)
n,3
The stated bound then follows from B.
The proof is complete.
Our analysis in the proof of Theorem
1 actually gives
SLE n, 2L
LE Fs(Fs( Fs]
E F(w()) Fs]
+
23
Since we assume [[ss] 0 in Corollary
we only need the condition < .13/2 to get Corollary
2
C PROOF OF THEOREM 3 AND THEOREM
In this section, we present the proof of Theorem and Theorem
(St))
Proof of Theorem 3 Let w be the projection of w by quadratic growth condition, we know
onto the set of global minimizer of Fs. Then
8(0)
E Fs
(Stt)) S60
As]
E
(5t)) s0B
w w|13]
This together with B.5 and non-negativity of implles
n2.3
E
(stD)
[[J(Ww
(S(11) si0
=:]]
[F (8 1)] = =
B (9) ()),
(C.1)
2
where we have used the symmetry between and s(i). By the realizability condition, we know almost surely that
f(w 2) = f( 2) = 0
and V Vi(w; 2;) = O. It then follows from the smoothness assumption that
E [[s(w (w (Stt))
=;) )
S(w g (5)
=:] = E [ w
(8(1))
=1) [(w; =
sta)
SG3
< E w (g())
w. V Vf f(w; 24) + - l|w (s(e)
w
g(0
2
300
w LE (Ww (8))
(s
=
8(0)
n2
We can plug (B.9). 10.10) and the above inequality back into B.4 and derive the following bound on the on-average stability E
LIEF (S)
E(F(ws) ( + E[βs Fs(ws))
n.3
We then can analyze analogously to the proof of Theorem but using the above stability bound and get the stated generalization bound. The proof is complete.
Proof of Theorem Similar to B.7 but using the boundedness of gradients, we know
(ste)
4G
IVs
11 S
We can plug this inequality into B.6 and derive
4G2 -
2G2
B [ w
5(0
2,)
s(w
s
(9) =
233 n²
17

---

Published as a conference paper at ICLR 2021
Taking summation of the above inequality gives
f (w (9(9),
2x) f(ws (w) :2x)] S 2G /B.
(C.2)
St9
Plugging B.9
and 1.10
back into
B.4). we derive the following inequality
2G
[[(w 24)
f(ws: 2:)]
+ nl F((ws) - F(w$5)) + nE Fs Fs(ws))
B
km
2G
+ nGE |ws w " [|2] nB Fs(ws)]
3
where in the last step we have used the inequality F(ws) - F(ws) (8) S Gl|ws - the boundedness of gradients. According to the definition of on-average stability, we know that the on-average stability of A satisfies
w due to
2G
< n3
+
GE [
w w [12] + B[Fs Fs(ws)]
2G
G Fs(ws) - Fs]
+ E E Fs( (s(ws)]
n3
V23
where we have used Lemma
B.3
According to Part (c) of Theorem A.T it follows that
2G
(([(Fs(ws) - Fs])
B[F(ws) Fs Fs(ws)]
S
+
+ E E[fs Fs(ws)].
n3
V23
The stated bound then follows directly. The proof is complete.
D PROOFS ON APPLICATIONS
In this section, we prove generalization bounds for various stochastic optimization algorithms.
D.1 STOCHASTIC GRADIENT DESCENT
We consider here SGD. In the following proposition, establish the variance of stochastic gra- dients for SGD under the PL condition. The variance was also studied in a general nonconvex setting (Lei et al.) 2020a).
Proposition D.1. Let Assumptions Z hold. Let (Weha be the sequence produced by SGD with step size sequence {1) Jee. If there exists to such that tp. S B/L² for all 2 lo, then
)l < 2L max max (E(Fs(((,)))))) (F(ss)
Vt 2 to.
Proof. By B.2 and the update 4.. we know
Fs(We+1) S Fs(w:) + (Wr+1 Wa, VFs(w:)) + L|| We
2
= Fs((w,) nu (V f(w ).), Vl'((,))) + Loff | (.(
2
< Fs(,.)) n. (V (w:: 2,, VFs(w.)) + L f(w,; 2x), where we have used (B3). Taking expectations on both sides we get the following inequality for all t 2 to
B[Fs(w+11] < <
L Bf (w):,,))
< F(Fs(()))) 3T (w,) Fs] ne (FF((
(D.1)
where we have used the PL condition and 17, S B/LL² in the last step. then follows the following inequality for all
[F(s(W S (1- (11-),))ER (FFFs + n.3 2F[
} & max [E(Fs(w.)], 2k(
Applying this inequality recursively, we derive
E [F(we+1)) & max (FFFs )), f 14 2 lo-
This together with (B.3 implies the following inequality for all 2
z,, 1 < 2LE[/(ww; 2, S 2L max F3 w.. 23[
The proof is complete.
18

---

Published as a conference paper at ICLR 2021
We now prove generalization bounds in Theorem 5 We denote B x B if there exist some constants 61 and 02 such that 01 B S B S B.
Proof of Theorem 5 Let to = - It is clear that T I 8/L22 for all t 2 to- Let o
2L max [E[F' (wi) 1)] i.......
..... LE] ('sFssss,.)) )I, [[]Fs According to the self-bounding property (B.3) and Proposition D.1 we know that [[] 2, ]1 I o² for all t E N. The following optimization
error bound was established in Karimi al. (2016)
Lo²
E Fs (We+1) Fs]
(D.2)
21,32
We can plug the above inequality into (3.2 with A(S)
WT+1, I, and get
16LE Fs)
L²
E [[F(wr+1)
ps]
n,3
47
Since
E F[ S [[(Fs( = F(w"),
(D.3)
we further get
16T.F(w")
T.20²
[[ F(ww)
n1
4T
By taking T x n/32, we get E F(WT+1) Fs]
((1/((())) This corresponds to ((n/3²)
stochastic gradient evaluations. The proof is complete.
Lemma D.2. Assume Fs satisfies the restricted secant inequality with parameter B. Let A be SGD with the step size sequence the = 1/(((t+++ + 1)). Then there exists some a E IR such that
EE [[[[TT w. < o² /(2T)
Proof of Lemma D.2
Analogous to the proof of Theorem 5 we can find E R4 such that
B|[ f(w:; 2.) 2 S o² for all t E N. Since w is projection of wi+1 onto the set of global
minimizer of Fss know
|| #+1 < We+11 w(()
(9)
(9) 12 W. 7/ SWW:i
(
W: w
(9) 1/2 + 1 /V]
21/r (w: (S)
Wt, V/ (w2, 2)
Taking expectation and using [ (wr; ||3
0
we derive
E [[|11
(8) w
2
< E3 |w w; (5)
1 +1,00 2 (S) We, VFs(w:)))
< E w - w [3) -1:0 3R || ww (9)
= (1 - 2m [[[[]]]]]]]]]]]]]]]]] - w (9) [2 + n2
where we have used the restricted secant inequality. For the step size me
1 (B((t 1)), we have
EE [[[lwe-1 w (5) [ S -
 - w
(9)
1 + 3211 + 1)22
o²
Multiplying both sides by tlt + 1), we derive
+ 0²
(lL + 1) W++1 - w 4 [
< (1 - 1)4B [[]] w (8)
|22
Taking a summation of the above inequality from = 1 to T gives
(T 1)TB w (5) [ S (T 1)/52
The proof is complete.
Proof of Theorem 0 It was shown that functions satisfying restricted secant inequality with parame-
ter also satisfies the PL condition with parameter 3/ L Karimi et al.
2016 Therefore (B.15) holds
with 3 there replaced by 3/ T.. According to Lemma D.2
we know E
WT
WT 12 < (39T)
(8)
We can plug this inequality back into (B.15) with A(S)
WT+11 and
get
F(w")
E [(F((T+1) )] F(w*) = 0
n/
32T
where we have used (D3). By taking T x n/3, we get EE F(Wr+1) =(w')=((1/mm3)) This
corresponds to O(n/3 (m) stochastic gradient evaluations. The proof is complete.
19

---

Published as a conference paper at ICLR 2021
Proof of Theorem Let 1 3/L2. According to the assumption E[Fs] = 0 and D. know
([FFs < [[[Fs(we)] 2m55E (www) 1
(1- n/ n ww)]. (D.4)
Applying this inequality recursively, we get [[(+((T++1)) - (1 "
We can plug
the above inequality back into (3.2) with A Wr+1 and get
(E(Fs(Wr++)
L(1 8 )
L Lexp(-8TT/L)
([F(W++1)]
E (w(()))]
E
Fs Fs((w))
299 where we have used the elementary inequality - S exp(-a).
2/3
23
(D.5)
To achieve [[F((T+1)] S e, we can take T such that
exp 3T//1² =B
T log
The proof is complete.
D.2 RANDOMIZED COORDINATE DESCENT
We prove here the generalization bounds for randomized coordinate descent. We further assume that the gradient coordinate- wise Lipschitz continuous in the sense that
Fs + ac;) < Fs(w) aV,Fs(() La /2, Va E R. w E R [d].
Proof of Theorem
8 According Theorem 3 in Karimi et al. 2016), we know
E[('s(Wr+2) Fs] S
EE
(s()))) Fs).
(D.6)
dL
Plugging the above inequality back into (3.2) and using (D33).
we get
16LE
Fs]
L
B
T
B[F(WT+1)] F(w*)
E[Fs(w11]]
n²
23
dT.
0
F(w")
8T
n2
+
exp
dL
where we have used (D.5). To achieve the excess generalization bounds ( (1])) we require T satisfying
3T
T dlogn
exp
If E[ss] = 0, then it follows from 3.2
D.6 and D.5) that
TB 2,3 exp dt.
B[F(WT+1))
BlFs(wi))
To achieve the generalization bound e, we require T satisfying
T3
exp
x Be
= T B dlog 1/(8e).
dL
The proof is complete.
D.3 STOCHASTIC VARIANCE-REDUCHH OPTIMIZATION
We prove here generalization bounds for various stochastic auriancereduccd optimization algo- rithms. We formulate the framework Algorithm
Algorithm 1: Stochastic Variance Reduced Optimization
Input: step size n, initialization Wo. {m.)
for s = 1,2, 2, do
Wo W draw a batch I, [n] compute Vo = Vi (W))
update w Wo 7/Vo
for f. = 1,...,,, m. do
draw batch 4, S [n]]
compute v, by either (4.4) or 4.5
update W W, 1/v,
set W. as W,,, where i, is drawn according to a distribution on [m.]
choose the output from { [w,] according to some strategy
20

---

Published as a conference paper at ICLR 2021
We now consider the stochastic variance-reducee gradient descent (SVRG) (Reddi et al. 2016) and stochastically controlled stochastic gradient (SCSG) (Lei et al. 2017).
Theorem D.3. Let Assumptions 7 and 2 hold with L n3 Let A be either the SVRG in Reddi al. (016)) or the SCSG in Lei al. (2017). Then we can take O(n+ n3/3) log n) stochastic gradient evaluations to get excess generalization bounds ((1/(n8)). Furthermore, if E[ssl o. then we can take ( nă /B) log 1/ (Bc)) stochastic gradient evaluations to achieve the gener- alization bound O(e) for any 0.
Proof. To achieve B[Fs(A(S)) - Fsl s 2/n, it shown that SVRG and SCSG requires O((n
n /B) log n) stochastic gradient evaluations (Reddi et al. 2016 Lei et al. 2017). We plug this optimization error bound into Theorem [ and get (E((((()))))))))))))))((()
(w") O (()())))).
We now consider the case [[ = According to 3.2p. to achieve generalization bound O(c), suffices that (E((((())) - = (3B). This can be achieved by taking O ((n+n3 (0(++///)) / log 1/(3e)
stochastic gradient evaluations (Reddi al. 2016 Lei al. 2017). The proof is complete.
We now present the proof of Theorem 9 on the behavior of the stochastic recursive gradient algo- rithm (SARAH) (Nguyen et al. 2017) and SpiderBoost (Wang et al. 2019).
Proof of Theorem 9 To achieve E[Fs(A(S)) - Fs] s 2/n, it was shown that SARAH and Spi-
derBoost requires ((n++ 1/3²) log n) stochastic gradient evaluations (Nguyen et 2017 Wang
al. 2019). We plug this optimization error bound into Theorem and g(t F
0(1 (n3)).
We now consider the case B[ss] = 0. According
3.2). to achieve generalization bound O it
suffices that E ({F(A(S)) Fs] (Be). This can be achieved by taking (( log 1/ 1((3))
stochastic gradient evaluations (gguyen et al. 2017 Wang et al. 2019). The proof is complete.
Finally, we consider SNVRG-PL (Zhou al.
2018a).
Theorem D.4. Let Assumptions 7 and 2 hold with L I n4. Let A be the SNVRG-PL in Zhou n + vn/3) log' n) stochastic gradient evaluations to get
et al. (018a). Then we can take ((In+ excess generalization bounds ((1/(nB)). Furthermore, E[Fs] 0, then we can take O + vn/3) log" }.) stochastic gradient evaluations to achieve the generalization bound O()) for any <> 0.
Proof. To achieve ({Fs(A(S)) - Fsl S 2/n. n, it was shown that SNVRG-PL requires O((n + vn/3) log" n) stochastic gradient evaluations (hou et al. 2018a). We plug this optimization error bound into Theorem and get B. B[F((A5)) F(w) O (1)5))).
We now consider the case E[ = 0. According to (3.2). to achieve generalization bound O(e), it suffices that ([F(A(S)) - Fs] = O(ße). This can be achieved by taking O(1z + vn/3) log" 1/(Be)) stochastic gradient evaluations (Zhou et al. 2018a). The proof is com- plete.
E DISCUSSIONS OF EXAMPLES
In this section, we present some discussions on understanding the assumption L/B n/2 Theo- rem 2
E. DISCUSSION OF EXAMPLE
We first give the definition of strong convexity. For any differentiable function g W + R, we say g is o-strongly convex if for any w, w' E W there holds
g(w') 2 g(w) + (w' w, Vg(w)) + -- 5/w -w'13
2
21

---

Published as a conference paper at ICLR 2021
Introduce g: R + RR by g(v)
1. n
Then the function Fs can be written as Ei=1 l(ve, Vi).
Fs(w)=
Σ (((w, ((xx)) = g(Aw), T
1
=
where A= = is -t-sonoy convex, then F's satisfies the PL condition (Karimi et al. 2016 Necoara et al. 2018
E RRu is the matrix formed from the data. It is known that if
Fs(w) - Ps S
V FFs(w)) (w)
(E.1)
20 ( min (A))
Since l is Je-strongly convex we know for any V, v' E R
g(v') =
U.) 2 (vr vi) +
Σ (v - -;) 11)+
oF
(0) - 2/)²
2n
at v112.
= =(v) (Vg(v), +
(E.2)
2n
That is, g is a a
-stongll convex. This together with EI shows that Fs(w)= F's 5
n
VFs(
/FF(())l3
(E.3)
2 (A))
20r0 min (Es)
where we have used
(d'min (A)) 1 J'inn (A A) = d'in (Es).
(E.4)
n2
For any v R". follows from the Le-strong smoothness of l that
1 1/2 Σ (vr.)))) E' ('(,,,)))
1
n
12
VV((v- - Vo(v')1
1/12
1| v'112.
n
n
n²
That is, g Lu smooth. It then follows "
[VFs(w) VFs(ww)ll [[ATVg(AN)) A ATVo(w))l6 S Fmax (A)]l (g(Aw)))l>
T (A) ||A(W - w')l Te max (A) w w w'll..
This together with (E.4) shows (o replaced by mmax)
(E.5) It is reasonable to assume that L is of the order of the smoothness of Fs. In this case, it follows from (E.3 and (E.5) that empirical counterpart of L/ /3 is of the order of maa (Es)/or minn (Es).
[VF((w) F's(w')lla S Leo (is)) (is)ll w'll2.
E.2 DISCUSSION OF EXAMPLE
We recall some notations in Example Consider single-hidden-layer neural networks with d inputs, m hidden neurons and a single output, for which the prediction function takes the form fy, = Exs ugo(( x)), Here Wy E Rdd and Us E IR denote the weight of the edges connecting the k-th hidden node to the input and output node, respectively, while
IR + IR is the activation
function. We fix v with |uy| = a for some a > O and train w = (W1, W2, w.
E Rmxd from
S. Note we only use the PL condition Fs(w) - F S 28 V [ for w w s64) in the proof (8()) of Theorem (only in B.6)). We fix w sto)
(8())
here. Analogous to Soltanokkotabi et al. 2019
we define the Jacobian matrix J = (J1, Jz...., Jn) E Mddx at w w (S
with
st0
J =
Um (w Jay
and r, w.z) yj for j [n)] was shown that (Soltanolkotabi et al. 2019
v VFs(w)= = Jr, for r= TT)
(E.6)
and therefore
[Fss 1 JJ Jr TTTTJ r.
n² (1
n2
22

---

Published as a conference paper at ICLR 2021
According to the definition Jy. know
Jz Jz = (110' (ww 2z)0, ..... Um un moo''ww (mmm)) (113))
U (w (wmetz))a )ags)
m
a²
(w
vy.
It then follows that
J = d" Σ (d(xw))(((xmm)) o (
(E.7)
where X = (#1...... TT) Rexd is the data matrix and @ denotes the Hadamard (entry-wise)
product matrices. According to the definition of we know Fs(w) = -11r112 Then, it follows from E.6 and E..
that
V FFs(w))
(w)
a²
(((Xw)((((xwz)) o (XxT))
n
a
(d(xw)((((xwa)) (xxx)) (xxX)) |||
n2
min
a²
(d(xa)) ) (x(T)))F(()) Fs(w).
0 min
That is, we can take the parameter of the PL condition as
Σ (d((x))(((Xxwa)
o (XXT))
8
Omiin
2n.
It is reasonable to assume that L is of the order of a² max Ex (o (d(xxa)(d(Xww))
(XXT) Soltanolkotabi al. 2019). In this case, we have the empirical counterpart of L/ is of the order of
0 max
Σ m Æ=
(d(xw)))((Xw.))
@ (XXT))
min
Σ
(d
@ (XXT)
If we consider the identify activation function, i.e., Φ(t) t, then it follows from the definition of
Eg that
Omax [XX
max (Es)
L/3
m (XXT)
Tmin Ex}
23


Reviews:
[{"review_id": "mMmvQmkBWqz", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the generalization performance of stochastic algorithms in nonconvex optimization with gradient dominance condition. In detail, the authors suggest that for any algorithm, its generalization error can be bounded by $O(1/(n\\beta))$ plus the optimization error of the algorithm, where $\\beta$ is the gradient dominance parameter. The main idea for the authors to obtain such an improved bound is an advanced analysis based on a weaker on-average stability measure. \n\nHere are my detailed comments. \n- It seems that to do a comparison, the authors need to ‘translate’ previous complexity results such as stability results (Charles & Papailiopoulos, 2018) to generalization results, considered in this paper. To do such a translation, Theorem A.1 is proposed. However, I did not find the proof to Theorem A.1 except its part c. Since the translation is crucial for a fair comparison, the authors may want to complete the proof to Theorem A.1 or point out some relevant references about that. \n- Assumption 1 and 2 suggest that $L$ and $\\beta$ are two parameters about $F$ itself, in other words, independent of any specific data set $S$. However, in Example 1 and 2, the authors suggest that $L/\\beta$ is in the order of $\\sigma_{max}(\\Sigma_S)/\\sigma_{min}(\\Sigma_S)$, which depends on the random data $S$. Can the authors explain more about that? Shall we need some more assumptions about the data distribution (for instance, the support set of $x$ is finite) to support such a claim?\n- $O(1/(n\\beta))$ generalization gap is standard for the case where $F$ is convex, and this work tries to extend it from convex to nonconvex with PL condition, just as the authors suggest in Remark 3. Does the $O(1/(n\\beta))$ gap still hold under other nonconvex relaxing conditions such as one-point strongly convexity or quadratic growth [1]? \n\n[1] Necoara, Ion, Yu Nesterov, and Francois Glineur. \"Linear convergence of first order methods for non-strongly convex optimization.\" Mathematical Programming 175.1-2 (2019): 69-107.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "mJ6AkX1Srwq", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper mainly studies the generalization performance of stochastic algorithms. Compared with previous results which rely on Lipschitz condition, this paper assumes smoothness condition and Polyak-Lojasiewicz Condition, and then prove the excess generalization bound that is a summation of $\\frac{1}{n\\beta}$ and empirical optimization error. This result looks impressive, not only because the first term looks shaper than previous $\\frac{1}{\\sqrt{n}}$ of generalization bound , but also it implies optimization benefits generalization, which may help understand some empirical observations in modern machine learning. What's more, authors analyze some common stochastic algorithms as concrete examples to show the corresponding theoretical guarantee.  Besides, the whole paper is well-written and easy to follow. \n\nThough results in this paper look stronger than previous results, authors use different assumptions (say smoothness instead of Lipschitz condition) compared with previous paper, and it would be better if authors could make these comparisons more clear (say in abstract etc.). Besides, though there is a $\\frac{1}{n\\beta}$ term in the generalization bound, it holds in expecation, and I think an extension to high probability bound will lead to an additional $\\frac{1}{\\sqrt{n}}$ term, which should also be stated clear when comparing with previous results. Finally, I wonder whether it is possible to extend the results to non-smooth loss function, at least for some special case, such as DNN with ReLU activation unit.", "extra_scores": {}, "extra_text": {}}, {"review_id": "__bzGDVijzr", "reviewer": "AnonReviewer4", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "One of the main contributions of this paper lies in the generalization error of O(1/n) under the P-L condition given by Theorem 1. It provides a generalization bound instead of the hypothesis stability or uniform stability in previous discussions. The result explains generalization even under overparameterized model.\n\n\nStrength:\n+ The theoretical result is novel, according to the authors this is the first paper to model the generalization bound in terms of a $O(1/n\\beta)$ term plus the convergence rate of the optimization algorithm\n+ The authors applies the main theorem on practical algorithms and derive convergence rate on generalization error while previous literature on those algorithms are mainly on  training error.\n\n\nWeakness:\n- Some of the background description and preliminaries are vague, for example the $E_{S, A}$ concerning taking an expectation over an algorithm A are not explained.\n- The relation of related works with this work is not clear enough. The two paragraphs, \"Algorithmic Stability\" and \"Generalization Analysis\" all ends up with areas that stability/generalization is applicable, while I care more about how previous literature shed lights on this work.\n- I see no experimental results to support their theory\n\nI think it is a good paper that provides novel aspects of understanding. It provides new insights in understanding important phenomenons in training deep neural networks whose Lipchitz constant might be very large. The bound removes the Lipchitz constant and uses training error of the best model instead. It explains why interpolation does not lead to overfitting. However the first part of this paper is a little bit rash while the experimental support is insufficient.\n\nQuestion:\n\nHow widely is the PL condition applicable? Are there any examples when the PL condition does not hold?\n\nIn Theorem 1 the assumption is $L \\leq n\\beta/4$, while in Corollary 2 the assumption becomes $L < n\\beta/2$, what makes the difference?", "extra_scores": {}, "extra_text": {}}, {"review_id": "SDqHvHtnhNL", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\n\nThe whole paper is focused on the theoretical part. I am missing the important experiment part to back up the theory. I could not vote for acceptance without the experiments, and I will increase the score if satisfying experiment results can be included.\n\nIt is also important to verify the condition $L \\leq n\\beta/4$ in the experiment, i.e. how large the sample size needs to be. In terms of this constraint, I saw that the authors tried to investigate and interpret it. But I still have some questions on them. Please correct me if any of my understanding is wrong:\n\nBoth $L$ and $\\beta$ seem to depend on $n$ and are not absolute constants here. For example $L/\\beta$ is about $\\sigma_{\\max}(\\Sigma_S) / \\sigma_{\\min}(\\Sigma_S)$ in the examples. Here my understanding is that $L/\\beta$ could be large if $n$ is small. When $n$ becomes super large then $L/\\beta$ would be close to some constant\n\n- if n is super large, then the constraint $L \\leq n\\beta/4$ would be satisfied. But since n is super large, this constraint is also very trivial and seems not imposing any \"implicit constraint\" on the complexity of the problem.\n- if n is moderate, then this constraint $L \\leq n\\beta/4$ might not be satisfied", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: In this work, the authors develop an improved generalization bound for stochastic optimization algorithms. Reviewers agree that the theoretial results are significant. Several reviewers had concerns about the lack of experimental validation, which the authors addressed during the discussion phase. Other more minor concerns were also adequately addressed by the authors. The final recommendation is therefore to accept.
Decision: Accept (Poster)