Beyond Lipschitz: Sharp Generalization and Excess Risk Bounds for Full-Batch GD
Authors: Konstantinos Nikolakakis
Farzin Haddadpour
Amin Karbasi
Dionysios Kalogerias
Venue: ICLR 2023 poster (2023)
Keywords: Gradient Descent
Generalization Error
Smooth Nonconvex/Convex Optimization

Abstract: We provide sharp path-dependent generalization and excess risk guarantees for the full-batch Gradient Descent (GD) algorithm on smooth losses (possibly non-Lipschitz, possibly nonconvex). At the heart of our analysis is an upper bound on the generalization error, which implies that average output stability and a bounded expected optimization error at termination lead to generalization. This result shows that a small generalization error occurs along the optimization path, and allows us to bypass Lipschitz or sub-Gaussian assumptions on the loss prevalent in previous works. For nonconvex, convex, and strongly convex losses, we show the explicit dependence of the generalization error in terms of the accumulated path-dependent optimization error, terminal optimization error, number of samples, and number of iterations. For nonconvex smooth losses, we prove that full-batch GD efficiently generalizes close to any stationary point at termination, and recovers the generalization error guarantees of stochastic algorithms with fewer assumptions. For smooth convex losses, we show that the generalization error is tighter than existing bounds for SGD (up to one order of error magnitude). Consequently the excess risk matches that of SGD for quadratically less iterations. Lastly, for strongly convex smooth losses, we show that full-batch GD achieves essentially the same excess risk rate as compared with the state of the art on SGD, but with an exponentially smaller number of iterations (logarithmic in the dataset size).

Published as a conference paper at ICLR 2023
BEYOND LIPSCHITZ: SHARP GENERALIZATION AND EXCESS RISK BOUNDS FOR FULL-BATCH GD
Konstantinos E. Nikolakakis', Farzin Haddadpour, Amin Karbasi' &Dionysios S. Kalogerias
Department of Electrical Engineering Yale University, Yale University & Google Research' ffirst. last f @yale.
ABSTRACT
We provide sharp path-dependent generalization and excess risk guarantees for the full-batch Gradient Descent (GD) algorithm on smooth losses (possibly non- Lipschitz, possibly nonconvex). At the heart of our analysis is upper bound on the generalization error, which implies that average output stability and a bounded expected optimization error termination lead generalization. This result shows that a small generalization error occurs along the optimization path, and allows bypass Lipschitz sub-Gaussian assumptions the loss prevalent in previous works. For nonconvex, convex, and strongly convex losses, we show the explicit dependence of the generalization error in terms of the accumulated path-dependent optimization error, terminal optimization error, number of samples, and number of iterations. For nonconvex smooth losses, we prove that full-batch GD efficiently generalizes close to any stationary point at termination, and recovers the generalization error guarantees of stochastic algorithms with fewer assumptions. For smooth convex losses, we show that the generalization error is tighter than existing bounds for SGD (up to one order of error magnitude). Consequently the excess risk matches that of SGD for quadratically less iterations. Lastly, for strongly convex smooth losses, we show that full-batch GD achieves essentially the same excess risk rate compared with the state of the SGD, but with exponentially smaller number of iterations (logarithmic in the dataset size).
INTRODUCTION
Gradient based learning (Lecun al., 1998) is a well established topic with a large body of literature on algorithmic generalization and optimization errors. For general smooth convex losses, optimization error guarantees have long been well-known (Nesterov, 1998). Similarly, Absil et (2005) and Lee et al. (2016) have showed convergence of Gradient Descent (GD) to minimizers and local minima for smooth nonconvex functions. More recently, Chatterjee (2022), Liu al. (2022) and Allen-Zit et al. (2019) established global convergence of GD for deep neural networks under appropriate conditions.
Generalization error analysis of stochastic training algorithms has recently gained increased attention. Hardt et al. (2016) showed uniform stability final-iterate bounds for vanilla Stochastic Gradient Descent (SGD). More recent works have developed alternative generalization error bounds with prob- abilistic guarantees (Feldman & Vondrak, 2018; 2019; Madden et al., 2020; Klochkov & Zhivotovskiy, 2021) and data-dependent variants (Kuzborskij & Lampert, 2018), or under weaker assumptions such strongly quasi-convex (Gower et al., 2019), non-smooth convex (Feldman, 2016; Bassily et al., 2020; Lei & Ying, 2020b; Lei et al., 2021a), and pairwise losses (Lei et al., 2021b; 2020). In the nonconvex case, Zhou et al. (2021b) provide bounds that involve the on-average variance of the stochastic gradients. Generalization performance of other algorithmic variants lately gain further attention, including SGD with early momentum KKamezani-Kebryy et al., 2021). randomized coordinate descent (Wang et al., 2021c), look-ahead approaches (Zhou et al., 2021a), noise injection methods (Xing et al., 2021), and stochastic gradient Langevin dynamics (Pensia et al., 2018; Mou et al., 2018; Li et al., 2020; Negrea et al., 2019; Zhang et al., 2021; Farghly & Rebeschini, 2021; Wang et al., a02),;
"Leadd & corresponding author

---

Published as a conference paper at ICLR 2023
Excess Risk Upper Bounds: GD vs SGD
Algorithm
Iterations
Interpolation
Bound
B-Smooth Loss
GD (this work) 1/: 1/28
T= vR
No
o
Convex
VTl
SGD
1 Vn
= 1/vT
=
No
o
Convex
(Lei & Ying, 2020b)
GD (this work)
1
T=n
Yes
o
Convex
Th 1/28
SGD
1) 1/22
=
Yes
o
Convex
(Lei & Ying, 2020b)
n2
GD (this work) ?t 2/ + +))
v /log(n)
Strongly Convex (Objective)
(logn)
No
n2
SGD 1/: 2/(1 + 10) (Lei & Ying, 2020b)
Strongly Convex (Objective)
T 0
No
n2
Table 1: Comparison of the excess risk bounds for the full-batch GD and SGD algorithms by Lei Ying (2020b, Corollary Theorem 11). We denote by n the number of samples, the total number iterations, f)t the step size time 4, and by ec. - E[Rs (W5)) the interpolation error.
Even though many previous works consider stochastic training algorithms and some even suggest that stochasticity may necessary (Hardt et al., 2016; Charles Papailiopoulos, 2018) for good generalization, recent empirical studies have demonstrated that deterministic algorithms generalize well; see, c.g., (Hoffer et al., 2017; Geiping et al., 2022). In fact, Hoffer et al. (2017) showed empirically that for large enough number of iterations full-batch GD generalizes comparably to SGD. Similarly, Geiping et al. (2022) experimentally showed that strong generalization behavior is still observed the absence of stochastic sampling. Such interesting empirical evidence reasonably raise the following question: "Are there problem classes for which deterministic training generalizes more efficiently than stochastic training?"
indeed
While prior works provide extensive analysis of the generalization error and excess risk of stochastic gradient methods, tight and path-dependent generalization error and excess risk guarantees in non- stochastic training (for general smooth losses) remain unexplored. Our main purpose in this work is theoretically establish that full-batch GD indeed generalizes efficiently for general smooth losses. While SGD appears to generalize better than full-batch GD for non-smooth and Lipschitz convex losses (Bassily et al., 2020; Amir et al., 2021), non-smoothness seems to be problematic for efficient algorithmic generalization. In fact, tightness analysis on non-smooth losses (Bassily et al., 2020) shows that the generalization error bounds become vacuous for standard step-size choices. Our work shows that for general smooth losses, full-batch GD achieves either tighter stability and excess error rates (convex case), or equivalent rates (compared to SGD the strongly convex setting) but with significantly shorter training horizon (strongly-comve objective).
RELATED WORK AND CONTRIBUTIONS
Let n denote the number of available training samples (examples). Recent results (Lei & Tang, 2021; Zhou et al., 2022) on SGD provided bounds order O(1/vn) for Lipschitz and smooth nonconvex losses. Neu et al. (2021) also provided generalization bounds of order O(r'I// / VT), with T= = vn and step-size 77 = 1/T to recover the rate ((1/V)). In contrast, we show that full-batch GD generalizes efficiently for appropriate choices of decreasing learning rate that guarantees faster convergence and smaller generalization eиror, simultaneously. Additionally, the generalization error involves intrinsic dependence the of the stationary points and the initial point. Specifically,
2

---

Published as a conference paper at ICLR 2023
Full-Batch Gradient Descent
Step Size
Excess Risk
Loss
To (To +1
Th S c/ VC
Nonconvex
+ Copt
n
Tep +1
112 1/23
+ T
Convex
n
= 1/23, T Vn
C vn
+ -
Convex
V
VT
-4T7 B+ 7
~-Strongly Convex
7t 2/(3+ + +2
+ eexp
+ +
n
1) 2/ + 7)
Vlog(n)
? Strongly Convex
T (8++) log 2y
CVEC n
n?
Table 2: A list of excess risk bounds for the full-batch GD up some constant factor C >> 0. We denote the number of samples by n. "cops" denotes the optimization error copt & ([ (A(S)) Rgg) T the total number of iterations and c A (W3)] the model capacity (interpolation) error.
we show that full-batch GD with the decreasing learning rate choice of T = 1/2,tt achieves tighter bounds of the order ((VTlog(TT) (since (T))/ S 1/vn) for any T' S n/ log(n). In fact, O DT (og(T)/n essentially matches the rates in prior works (Hardt et al., 2016) for smooth and Lipschitz (and often bounded) loss, however we assume only smoothness at the expense of the /Tog(T) term. Further, for convex losses we show that full-batch GD attains tighter generalization error and excess risk bounds than those of SGD in prior works (Lei & Ying, 2020b), similar rates in comparison with prior works that consider additional assumptions (Lipschitz or sub-Gaussian loss) (Hardt et al., 2016; Lugosi & Neu, 2022; Kozachkov et al., 2022). In fact, for convex losses and for a fixed step-size Th = 1/23, we show generalization error bounds of order (TT/n) for non-Lipschitz losses, while SGD bounds in prior work are of order O ((/T/n) (Lei & Ying, 2020b). As consequence, full-batch GD attains improved generalization error rates by one order of error magnitude and appears to be more stable in the non-Lipschitz case, however tightness guarantees for non-Lipschitz losses remains an open problem.
Our results also establish that full-batch GD provably achieves efficient excess error rates through fewer number of iterations, as compared with the state-of-the-art excess error guarantees for SGD, Specifically, for convex losses with limited model capacity non-interppolation) constant step size and T = /n, the excess risk is of the order O while the SGD algorithm requires T to achieve excess risk of the order O(1/ (n) (Lei & Ying, 2020b, Corollary 5.a).
show that with
For --strongly convex objectives, our analysis for full-batch GD relies on a leave-one-out Tol strong convexity of the objective instead of the full loss function being strongly-conver This property relaxes strong convexity, while it provides stability and generalization error guarantees that recover the convex loss setting when No.o + Prior work (Lei & Ying, 2020b, Section 6, Stability with Relaxed Strong Convexity) requires a Lipschitz loss, while the corresponding bound becomes infinity when Y -> 0, in contrast to the heave-one-on approach. Further, prior guarantees on SGD (Lei Ying, 2020b, Theorem 11 and Theorem 12) often achieve the same rate of (1/nn) however with = (n:) iterations (and a Lipschitz loss), in contrast with our full-batch GD bound that requires only T = @(lgg n)) iterations (at the expense of a Vlog(n) term)', Finally, our approach does not require projection step (in contrast to Hardt al. (2016); Lei & Ying (2020b)) in the update rule and consequently avoids dependencies on possibly large Lipschitz constants.
'SGD naturally requires less computation than GD. However, the directional step of GD can be evaluated in parallel. As consequence, for strongly-convex objective GD would be more efficient than SGD (in terms of running time) if some parallel computation is available.
3

---

Published as a conference paper at ICLR 2023
In summary, we show that for smooth nonconvex, convex and strongly convex losses, full-batch GD generalizes, which provides an explanation its good empirical performance in practice (Hoffer al., 2017; Geiping et al., 2022). We refer the reader to Table 1 for overview and comparison of our excess risk bounds and those of prior work (on SGD). A more detailed presentation the bounds appears in Table 2 (see also Appendix A, Table 3 and Table 4).
PROBLEM STATEMENT
Let f(w, 2) be the loss at the point _ for some example Z. Given dataset S 2 { of i..d samples 2; from an unknown distribution D, our goal is to find the parameters w" of learning model such that w E arg min R(w), where R(w) & Ef Z)] and R - R(w"). Since the distribution D is not known, consider the empirical risk
Rs(w)
72 Σ f(w;
(1)
The corresponding empirical risk minimization (HRM) problem is find W arg argmin, Rs(w) (assuming minimizers on data exist for simplicity) and we define R's - Rs(W)). For deterministic algorithm A with input S and output A(S), the excess risk Cexcess is bounded by the sum of the generalization error Egen and the optimization error Copt (Hardt al., 2016, Lemma 5.1), (Dentcheva & Lin, 2022)
Cexcesss E[R(A(S)) - R E(R(A(S)) - Rs(A(S)) +E (R)s()(S)) Rs (W3)
(2)
'gen
Popt
For the rest of the paper we assume that the loss smooth and non-negative. These are the only globally required assumptions the loss function.
Assumption (3-Smooth Loss) The gradient of the loss function is B-Lipschitz
| [ V.l =))22 S B|| ul|2, Vz Z.
Additionally, we define the interpolation error that will also appear in our results.
Definition (Model Capacity/nnterpolation Error) Define c - (W3))
In general éc (non-negative loss). If the model has sufficiently large capacity, then for almost every S E "", it is true that Rg (s())) O. Equivalently, it holds that c. = 0. In the next section we provide a general theorem for the generalization error that holds for any symmetric deterministic algorithm (e.g. full-batch gradient descent) and any smooth loss under memorization of the data-set.
4 SYMMETRIC ALGORITHM AND SMOOTH LOSS
Consider the i..d random variables 21, 22..... En 21, 26. 2n with respect to an unknown dis- tribution D. the sets S A (#1, 22, en)) and S(1) & (21, 2...... 2/,..., 2n) random element. Recall that an algorithm symmetric the output remains unchanged under permutations of the input vector. Then (Bousquet & Elisseeff, 2002, Lemma 7) shows that for any / E (l,..., n and any symmetric deterministic algorithm the generalization error is Egen = Est,,, (f((s(()) ( 21)]. Identically, we write Egen = E (A(S())))) 24) : f(A(S); where the expectation is over the random variables 21,..., Sn 2 2 for the rest of the paper. We define the model parameters W.. w((3) evaluated at time / with corresponding inputs S and s(i), For brevity, we also provide the next definition.
that differ at the zth
Definition We define the expected output stability as Estab(A) A B[IIA(S) A(S()) and the expected optimization error cpp A E{Rs(A(S)) (s5))
We continue by providing an upper bound that connects the generalization error with the expected output stability and the expected optimization error the final iterate of the algorithm.
4

---

Published as a conference paper at ICLR 2023
Theorem (Generalization Error) Let f(::2) ) be non-negative B-smooth loss for any Z. For any symmetric deterministic algorithm A(-) the generalization error is bounded as
Igenl S 2/ (.p(pp + (e)sstab(A) + stabbA)
(4)
where (stab(A) A [[I[A(S) ([)) In the limited model capacity case it is true that ce is positive (and independent of T. and T) and Egenl ( (atab(())))
We provide the proof of Theorem in Appendix B.1. The generalization error bound in equation holds for any symmetric algorithm and smooth loss. Theorem 3 consist the tightest variant of (Lei & Ying, 2020b. Theorem 2, b)) and shows that the expected output stability and a small expected optimization error at termination sufficiently provide smooth (possibly non-Lipschitz) losses. Further, the optimization error term Copt is always bounded (with specific known rates) in the cases of (strongly) convex losses. Under the interpolation condition the generalization error bound satisfies tighter bounds.
upper bound the generalization error for
and goes
Corollary (Generalization under Memorization) If memorization of the training set is feasible under sufficiently large model capacity, then c. = 0 and consequently (geell S (2t/2(cop(Sstab(())
( and Egenl = O maxx (tabb A); (sta((1))).
For a small number of iterations T' the above error rate is equivalent with Theorem 3. For sufficiently large T the optimization error rate matches the expected output stability and provides a tighter rate (with respect to that of Theorem 3) of (geeul = ((staa(A)).
Remark. As a byproduct of Theorem 3, one can show generalization and excess risk bounds for a uniformly μ-PL objective (Karimi et al., 2016) defined as ||| [[|VVss [ ( 2 2plE(Rs(w) R3] for all w E Rd. Let TT - T ((((S) be the projection of the point A(S) the set of the minimizers of (-(-). Further, define the constant غ & ([)s(T))) + R(Ts)]. Then bound on the excess risk (the proof appears in Appendix D)
8B
V Eopt + ce 8/
16252
45,3
Cexcess
Typ
v
n2p²
Copt. p
(5)
We note that closely related bound has been shown in (Lei & Ying, 2020a). In fact, (Lei & Ying, 2020a, Therem 7) requires simultaneously the interpolation error to be zero (ec = 0) and an additional assumption, namely the inequality 3 < n4/44, to hold. However, if 3 < n//44 and 6. 0 (interpolation assumption), then (Lei & Ying, 2020a, inequality (B.13), Proof of Theorem 1) implics that ([[[] I [TTR)( and) the expected population risk at T is zero i... [[R(ss)] 0. Such a situation is apparently trivial since the population risk is zero at the empirical minimizer Ts arg min (s(.). On the other hand, if / > m///4, these bounds become vacuous. A PL condition interesting under the interpolation regime and since the PL is not uniform (with respect the data-set) in practice (Liu al., 2022), it is reasonable to consider similar bounds that of 5 as trivial.
5 BULL-BATCH GD
In this section, we derive generalization error and excess risk bounds for the full-batch GD algorithm. We start by providing the definition of the expected path error fpath, in addition to the optimization error capt. These quantities will prominently appear in our analysis and results.
Definition (Path Error) For any 3-smooth (possibly) nonconvex loss, learning rate The and for any E (1)...,.), we define the expected path error as
Cath
F.ElV 2; 1
(6)
'In general. this occurs when n + oc, and the generalization error is zero. As a consequence, the excess risk hecomes equals to the optimization error (see also (I.ei & Ying, 2020a, Therem 7)), and the analysis becomes interesting from generalization error prospective.
5

---

Published as a conference paper at ICLR 2023
The Cpath term expresses the path-dependent quantity that appears in the generalization bounds in results'. Additionally, as show, the generalization enror also depends the average optimization eπrоr Copt (Theorem 3). A consequence of the dependence on Copt. is that full-batch GD generalizes when it reaches the neighborhoods of the loss minima. Essentially, the expected path error and optimization eтror replace bounds in prior works (Hardt et al., 2016; Kozachkov et al., 2022) that require a Lipschitz loss assumption to upper bound the gradients and substitute the Lipschitz constant with tighter quantities. Later we show the dependence of the expected output stability term in Theorem 3 with respect the expected path error. Then through explicit rates for both epath and Copt we characterize the generalization error and excess risk.
5.1 NONCONVEX LOss
We proceed with the average output stability and generalization error bounds for nonconvex smooth losses. Through a stability error bound, the next result connects Theorem with the expected path error and the corresponding learning rate. Then we use that expression derive generalization error bounds for the full-batch GD in the case of nonconvex losses.
Theorem 6 (Stability Error Pwvor-Nonconver Loss) Assume that the (possibly) noncorvex loss f(,,z) is B-smooth for all & E Z. Consider the full-batch GD where denotes the total number of iterates and nh. denotes the learning rate, for all T + 1. Then for the outputs of the algorithum
WT+1 = A(S), wi() T+1 = A(S(8) it is true that
T
46path n²
Σ
II (1+ 1n1)) j=t+1
(stab(A) S
The expected output stability in Theorem 6 is bounded by the product of the expected path error (Definition 5), a sum-produce term (E Va I[ (1 + +Bnn)²² that only depends on the step-size and the term 4/n² that provides the dependence on the sample complexity. In light of Theorem 3, and Theorem 6, we derive the generalization error of full-batch GD for smooth nonconvex losses.
Theorem (Generalization Error - Nonconvex Loss) Assume that the loss {( 2) is 3-smooth for all z Z. Consider the full-batch GD where T denotes the total number of iterates, and the learning rate is chosen Ne I C/t I 1/3, for all S T 1. Let & 3C < and C(e, T) A min {e + 1/2, e log(eT)). Then the generalization error of full-batch GD bounded by
4 n Av Av3(eTy V(Eape Ee)Epath + +12 (eT))²
V /(Cope + eath (eT)
Spath (eT)2=((e,,T) n²
Iggeal
Epath.
(8)
7
n12
Additionally, by the definition of the expected path and optimization error, and from the descent direction of algorithm, we evaluate upper bounds on the terms fpath and copt and derive the next bound as byproduct of Theorem 7.
Corollary The generalization error of full-batch GD Theorem can be further bounded as
8/3 n
48
|Egen| <
VloglTT)(eTT) + l log(e
26 ([R)(Wi)).
The inequality (8) Theorem 7 shows the explicit dependence of the generalization error bound on the path- aeth-dependent eиror fpath and the optimization error Copt- Note that during the training process the path-dependent error increases, and the optimization error decreases. Both terms path and copt may be upper bounded, to find the simplified (but potentially looser) bound appeared in Corollary
We prove Theorem 6, Theorem and Corollary in Appendix C. Finally, the generalization error in Corollary 8 matches bounds in prior work, including information theoretic bounds for the SGLD algorithm (Wang et al., 202 Corollary 1) (with fixed step-size), while our results do not require the sub- GoosGassiinn loss assumption and show that similar generalization is achievable through deterministic training.
Recall that the initial point W, may be chosen arbitrarily and uniformly over the dataset.

---

Published as a conference paper at ICLR 2023
Remark. (Dependence Stationary Points) Let W1 be arbitrary initial point (independent of S). Under mild assumptions (provided in (Lee et al., 2016)) GD convergences to (local) minimizers. Let WS, s,w, be the stationary point such lim A(S) - W s.w. Then through the smoothness of the loss, we derive an alternative form of the generalization error bound in Theorem 3 that expresses the dependence of the generalization error with respect to the quality of the set of stationary points,
i.c.,
Igenl I 4 (SEIIA(S)) W3,w, [2 + E (W,,,,), )1) (stab(a) + (SCctab(A))
(10)
Inequality (10) provides detailed bound that depends on the expected loss at the stationary point and the expected distance of the output from the stationary point, namely [[I[A(S) - W 12]
5.2 CONVEX LOss
In this section, we provide generalization error guarantees for GD smooth convex losses. Starting from the stability of the output of the algorithm, we show that the dependence on the learning rate is weaker than that of the nonconvex case. That dependence and the fast convergence to the minimum guarantee tighter generalization error bounds than the general case of nonconvex losses in Section 5.1. The generalization error and the corresponding optimization error bounds provide risk bound through the error decomposition (2). We refer the reader to Table 2 for a summary of the excess risk guarantees. We continue by providing the stability bound for convex losses
excess
Theorem (Stability Error - Convex Loss) Assume that the convex loss f(;;z) is B-smooth for all E Z. Consider the full-batch GD where T denotes the total number of iterates and nu. S 1/28
learning rate, for all t S T + 1. Then for outputs of the algorithm WT+1 A(S), ( = A(S it is true that
(stab(A) S
4épath n
Σ ne
S
323 12 21=1 7h n
E[[[W]
W + Ec Σ n
(11)
In the convex case, the expected output stability (inequality 11) is bounded by the product of the ex- pected path error, the number samples term 2/n²² and the accumulated learning rate. The inequality (II) gives Estab(A) = o(E nt/ )t/n)²) and through Theorem 3 we find Eggal = + t= n//n). In contrast, stability guarantees for the SGD and non-Lipschitz losses in prior work (Lei Ying,
2020b, Theorem 3, (4.4)) give (sta((A) = O [E ni/n)) and |ggenl = = ET n/: /n). As a
consequence, GD guarantees are tighter than existing bounds of the SGD for non-Lipschitz losses, variety of learning rates and T S For instance, for fixed 7) - 1/VT, the generalization error bound of GD Egeal = ((VT/n) /n) which tighter than the corresponding bound of SGD, namely Igenn (1/Vvn) Further, GD applies for much larger learning rates (n) =//3), which provide not only tighter generalization error bound but also tighter excess risk guarantees than SGD as we later show. By combining Theorem and Theorem 9, we show the next generalization error bound.
Theorem 10 (Generalization Error - Convex Loss) Let the loss function f(,,2) 2) be convex and 3-smooth for all Z. Consider the full-batch GD where T denotes the total number of iterates. We chose the learning rate such that πt S 1/2,, for all t < T + 1. Then the generalization error of full- hatchbathhhhe GD is bounded by
4/2.3 (Fopt + Ee) Epath
T
|ggenl
Σ nt + 88 Spath
Σ n
(12)
n
n2
We provide the proof of Theorem and Theorem 10 in Appendix E. Similar to the nonconvex case (Theorem 7), the bound in Theorem 10 shows the explicit dependence of the generalization error on the number of samples n, the path-dependent term Epath. and the optimization error Eopt, as well as the effect of the accumulated learning rate. From the inequality (12), we can proceed by deriving exact bounds on the optimization eтror and the accumulated learning rate, to find explicit expressions of the generalization error bound. Through Theorem 9, Theorem 10 (and Lemma 20 in Appendix E), we derive explicit generalization error bounds for certain choices of the learning rate. In fact, we consider the standard choice 7/- 1/2.3 in the next result.
7

---

Published as a conference paper at ICLR 2023
Theorem 11 (Generalization/Eeees Error Convex Loss) Let the loss function f(;, 2) be con- vex and B-smooth for all 2 E 2. 1f = 1//2, for all t E {l...., , T), then
1 + n2 (3 W1
27
1 gen
W + T(e),
(13)
and
1 27 n22
33E W1 W
Eexcess
<
(35E - w3l + Teo) +
(14)
T
As consequence, for T = n iterations the GD algorithm achieves Gexcess O /n). In contrast, SGD requires 7 n number of iterations to achieve fexcess O(1/vn) (Lei & Ying, 2020b, Corollary 5, a)). However, if e O, then both algorithms have the same excess risk rate of OL/nn) through longer training with I" = n iterations. Finally, observe that the term [B] W1 W should be (1) and independent of the parameters of interest (for instance n) derive the aforementioned rates.
5.3 STRONGLY- CONVVX OBJECTIVE
One common approach to enforce strong-convexity is through explicit regularization. such a case both the objective (s(.)) the individual losses f(; =) are strongly-convex. In other practical scenarios, the objective is often strongly-convex but the individual losses are not (Ma al., 2018, Section 3). In this section, the above cases by assuming a y-strongly convex objective. We also show a property of full- batch GD that requires only leave-one-out variant of the objective to be strongly-convex. If the objective Rs(.) is 7-strongly convex and the loss f(:; =) is 3-smooth, then the leave-one-out function Rg-i(w) - 2//2 is -troonly convex for all E {l,...,, na} for some "ooo- S 7. Although "Noo is slightly smaller than (Noo max 7 - B/n, 0}), our results reduce to the convex loss generalization and stability bounds when Nowo -> Further, the faster convergence also provides tighter bounds for the excess risk (see Table 2).
show stability and generalization error guarantees that include
Theorem 12 (Stability Error - Strongly Convex Loss) Assume that the loss f(; 2) is 9-smooth for all Z and that R-(-) is --strongly convex. Consider the full-batch GD where T denotes the total number of iterates and Tt < 2/ (3 + 7) denotes the learning rate, for all t S. T. Then outputs of the algorithm WT+1 = A(S). WT-1 = A(S())
) is true that
T
T
(stab(A) I
4Epath
Σ The
II j=t+1
(1o)))
(15)
n²
t=1
Specifically, if = 2/( + r). then
4e 4épath
2T
(stab(A)
min
(16)
n²
Nooo
B
By comparing the stability guarantee of Theorem 9 with Theorem 12, we observe that the learning rate dependent term (sum-product) is smaller than that of the convex case. While the dependence on expected path error (Cpath) is identical, we show (Appendix F) that the Epach term smaller in the strongly convex case. Additionally, Theorem 12 recovers the stability bounds of the convex loss case, when Yow 0 (and possibly y + 0). Similarly the nonconvex and convex loss cases, Theorem 3 and the stability error bound in Theorem 12 provide the generalization error bound for strongly convex losses.
Theorem 13 (Generalization E Strongly Convex Loss) Let the loss function J(, 2) B- smooth for all z Z and the objective Rs(-) be 7-strongly convex. Consider the full-hatch GD where T denotes the total number of iterates. Let set the learning rate q 2/ + 4). all < T. Then the generalization error of full- full-batch GD is bounded by
IEgen|
ACoptt + Ce Cpath
28
Σ
Th t=1
T
II
T
(1
Th Thoo) + 8.8 Spath n2
Spath
II (1 n) j=t-1
j=++1
1=1
8

---

Published as a conference paper at ICLR 2023
We prove Theorem 12 and Theorem 13 in Appendix F. Recall that the sum-product term in the inequality of Theorem 13 is smaller than the summation of the learning rates in Theorem 10. This fact together with the tighter optimization error bound provide smaller excess risk than those of the convex losses. Similar to the convex loss setting, we use known optimization error guarantees of full-batch GD for strongly convex losses to derive explicit expressions of the generalization and excess risk bounds. By combining Theorem 13 and optimization and path error bounds (Lemma 22, Lemma 23 in Appendix F, and Lemma 15 in Appendix B.2), we derive our generalization error bound for fixed step size as follows in the next result.
Theorem 14 (Generalization/Eccess - Strongly Convex Loss) Let the objective function Rg() be y-sttongly convex and B-smooth by choosing some B-smooth loss ((, necessarily
(strongly) convex for all Z. Define m(71oo; T) - 3TT min {B/ 2T) / 7) and
M( - max [ 111,,,,RR (WF)) (W.).}. and set the learning rate to tit 2/(3 + 7). Then the generalization error of the full-batch GD at the last iteration satisfies the inequality
8V6 n
(VM(W))+ - exp
22T
4v3
T Vm(TToo: T) M(Wi)
'gen| I
+
V Vm(Tioo: T).
B 3
Additionally the optimization error (Lemma 23 in Appendix and the inequality (2) give the following excess risk
8v6 V
-2Tg
4v3 Ar
] +Axx
(-477)
Cexceesss
exp
+ A Aexp exp
(8+7)
(17)
n
n
where AT A (TM(W1) min (3/ 2T) /(B + 7) and A - (B[[| /
Theorem 13 and Theorem 14 also recover the convex setting when 7 + 0 or Vine + O. Additionally,
for 7 > 0 and by setting the number of iterations as T = (3/> + 1) log(n)) and by defining the
sequence mn. G min { 1//o (3/7 1) log 1o /22, the last inequality gives
llgn
<M((W) + 1 1 4v 3m, M(Wi) Vmn.rw.
Igen $
(18)
n
n
Finally, for T -13/7 1) log(n)/2 iterations is true that
8/6log
1 443 nn
Eexcess
VT
+
(19)
n
n
n??
where r,, 3M(W)) min 33/Tioe: (8/7 + 1) log n) /2y and as a consequence the excess risk is of the order O / /llo(nn//) As comparison, the SGD algorithm (Lei & Ying, 2020b, Theorem 12) requires = n number of iterations to achieve an excess risk of the order ((1/n), while full-batch GD achieves essentially the same rate with T (8/7 + 1) (n) iterations.
CONCLUSION
In this paper we developed generalization error and excess risk guarantees for deterministic training on smooth losses via the the full-batch GD algorithm. At the heart of our analysis is sufficient condition for generalization. implying that, for every symmetric algorithm, average algorithmic output stability and a small expected optimization error at termination ensure generalization. By exploiting this sufficient condition, we explicitly characterized the generalization error in terms of the number of samples, the learning rate, the number of iterations, path-dependent quantity and the optimization error at termination, further exploring the generalization ability of full-batch GD for different types of loss functions. More specifically, we derived explicit rates the generalization error and excess risk for nonconvex, convex and strongly convex smooth (possibly non- non-Lipschitz) losses/objectives. Our theoretical results shed light recent empirical observations indicating that full- bull-batch gradient descent generalizes efficiently and that stochastic training procedures might not be necessary and in certain cases may even lead to higher generalization errors and excess risks.

---

Published as a conference paper at ICLR 2023
7 ACKNOWLEDGMENT AND DISCLOSURE OF FUNDING
We would like to thank the four anonymous reviewers for providing valuable comments and sugges- tions, which have improved the presentation of the results and the overall quality of our paper.
Amin Karbasi acknowledges funding in direct support of this work from NSF (IIS-1845032) ONR (N00014- 19-1-2406), and the Al Institute for Learning-Enan Enabled Optimization at Scale (TILOSS).
REFERENCES
P. A. Absil, R. Mahony, and B. Andrews. Convergence of the iterates of descent methods for analytic cost functions. SIAM Journal on Optimization, 16(2):531-547 2005, doi: 137/4406000 URL htthttts//doo..rg//11 http:///do..rr11.11133//////01// 050655555.
Zeyuan Alu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings th 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 242-252. PMLR, 09-15 Jun 2019. URL https:ttp/// /tt.ttpss//pprceeeeeee httpps////prrceenng.........mm. r.press v97/a a en - zhul 9a.html.
Idan Amir, Yair Carmon, Tomer Koren, and Roi Livni. Never go full batch (in stochastic convex optimization). In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 25033-25043. Curran Associates, Inc., 2021. URL http::://ppcceeeangggee/o/////ee d27b95cac4 c27 (000
http://pppr/2////1eee...
Raef Bassily, Vitaly Feldman, Cristóbal Guzmán, and Kunal Talwar. Stability of stochastic gradient descent nonsmooth convex losses. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and
H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 4381 4381-4391 Curran Associates, Inc., 2020. URL https: http://pcceeee.n...cccc httpg//nnw......./peeeeeeee pwtpppppppcpppp..//..222 #ile//2e2cbbfcceeed 471 42taeeaaeeelaaeeedeeeeeeee 36dc Padpe 2rraaeeeeeeeeeeceeeeeeeeeeeeeerr
Paperr.pdf.
Olivier Bousquet and André Elisseeff. Stability and generalization.
The Journal of Ma-
chine Learning Research, 2:499-526, 2002. URL https:://///ttt r.org/ w.org//aperr////a/.oo. /apers/v2/
bousquet 02a.hmll.
Zachary Charles and Dimitris Papailiopoulos. Stability and generalization of learning algorithms that converge to global optima. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 745-754. PMLR, 10-15 Jul 2018. URL https: #80/charles18a.htn.
Sourav Chatterjee. Convergence of gradient descent for deep neural networks. arXiv preprint arXiv:2203.16462. 2022. URL /ttppp///aax.voooo/////////////
Darinka Dentcheva and Yang Lin. Bias reduction in sample-based optimization. SIAM Journal on Optimization, 130-111,, 2022. doi: 10.1137/20M13224488. URL. pestps::/doi.ooo 11.1137/200112222
Tyler Farghly and Patrick Rebeschini. Time-independent generalization bounds for SGLD in non- convex settings. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances Neural Information Processing Systems, volume 34, pp. 19836-19846. Curran Associates, Inc., 2021. URL
a4ee59dd8 (a0ad6688b000 68 (eeeeeeedeed333eeeeeeeeeeee alles99aisaaeee1eeeeeee002022233 Paper.pdf.
Vitaly Feldman. Generalization of erm in stochastic convex optimization: The dimen- sion strikes back. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Gamett (eds.), Advances in Neural Information Processing Systems, volume 29. Curran Asso- ciates, Inc., 2016. URL http:///pppooeeeeigeeeeeee...oot
//
10

---

Published as a conference paper at ICLR 2023
Vitaly Feldman and Jan Vondrak. Generalization bounds for uniformly stable algorithms. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- cisa-Bianchi, and R. Gar- nett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Asso- ciates, Inc., 2018. URL 05a6241 (1662226668ee8273366666 656
Vitaly Feldman and Jan Vondrak. High probability generalization bounds for uniformly stable algo- rithms with nearly optimal rate. In Alina Beygelzimer and Daniel Hsu (eds.), Proceedings of the Thirly-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Re- search, pp- 1270-1279. PMLR, 25-28 Jun 2019. URL htw.t: /ttp:///rroeeee /proceee//////oooeeoeoooo ngs.ml r.press/ v99 fe 1 dmann 9a.html.
Jonas Geiping, Micah Goldblum, Phil Pope, Michael Moeller, and Tom Goldstein. Stochastic training is not necessary for generalization. In International Conference on Learning Representations, 2022. URL htwps:ttt///cc..ct http:///pppeeeeeeeeeeeeoe www.://wwwwww...............t..t forum? d=
Robert Mansel Gower, Nicolas Loizou, Xun Qian, Alibek Sailanbayev, Egor Shulgin, and Peter Richtárik. SGD: General analysis and improved rates. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 5200-5209, PMLR, 09-15 Jun 2019. URL https: / /prpceedodeeeeeeeee www.dinngmllm.mmmm.......mm.. r.press/ v9/ qi an 9b.html.
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In Maria Florina Balcan and Kilian Q. Weinberger (eds.), Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pp. 1225-1234, New York, New York, USA, 20-22 Jun 2016. PMLR. URL https: http:///pooeeddeeeeeeeee
Elad Hoffer, Itay Hubara, and Daniel Soudry. Train longer, generalize better: clos- ing the generalization gap in large batch training of neural networks. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Asso- ciates, Inc., 2017. URL https::/proceeedd/ www.inniii.nncnceeeoo.o... httppp.cc///pppe////////.ee
Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the Polyak-Lojasiewin condition. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 795-811. 7.5-ne1, 2016. URL
https: /tttp::/ddoioorg//000 wttp://////...0000/// 110.-00779773--333---66------2--
Yegor Klochkov and Nikita Zhivotovskiy. Stability and deviation optimal risk bounds with con- vergence rate o( ((1/n). In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 5065-5076. Curran Associates, Inc., 2021. URL httpst://prcceediiniie www.riinnnnnnnnnniiie.e.ee...eie www.snneuiiicc...m wttp:r.p....pppppe/220..... -at.aaab222277.01111aaapp......
Leo Kozachkov, Patrick M Wensing, and Jean-Jacques Slotine. Generalization in supervised learning through Riemannian contraction. arXiv preprint wwXiv:2201.06633 2022. URL https://
arxiv..rg//bbs/220..00
Iiaa Kuzborskij and Christoph Lampert. Data-dependent stability of stochastic gradient descent. In Jen- nifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 2815-2824, PMLR, 10-15 Jul 2018. URL https:://///ccccc http:///pooeeeeen...... www.pppesssse00 www.kkuubbaakakaee jiikiiijlle jaliiilBaaa. 8a.html.
Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):222))) (1:211):27222333 2324, 1998. doi: 10. 17995977767...
Jason D. Lee, Max Simchowitz, Michael I. Jordan, and Benjamin Recht. Gradient descent only converges to minimizers. In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir (eds.), 29th Annual Conference on Learning Theory, volume 49 of Proceedings of Machine Learning Research, pp. 1257, Columbia University, New York, New York, USA, 23-26 Jun 2016. PMLR. URL https: / ptw.c//cceedeeooooooooooooooceeo mgs.ml www.m.r.ppeas.. r.press/ v eeell 6.html.
11

---

Published as a conference paper at ICLR 2023
Yunwen Lei and Ke Tang. Learning rates for stochastic gradient descent with nonconvex objectives. IEEE Transactions on Pattern Analysis and Machine Intelligence, 43(12):4500-45 4511, 2021. doi: 10.1109/TPAMM.2021..000
Yunwen Lei and Yiming Ying. Sharper generalization bounds for learning with gradient-dominated objective functions. In International Conference on Learning Representations. 2020a. URL
https: wtt.:eccc/virtuaa//2111..
Yunwen Lei and Yiming Ying. Fine-gra Fine-grained analysis of stability and generalization for stochastic gradient descent. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference Machine Learning. volume 119 of Proceedings of Machine Learning Research, pp. 5809-5819. PMLR, 13-18 Jul 2020b. URL https: http://poooeeeen.....e wtw.inngs......./s.i....m.. lei20c.html.
Yunwen Lei, Antoine Ledent, and Marius Kloft. Sharper generalization bounds for pairwise learning. H. Larochelle, M. Ranzato, Hadsell, M. F. Balcan, and H. Lin (eds.), Ad- vances in Neural Information Processing Systems, volume 33, pp. 21236-21246. Curran As- sociates, Inc., 2020. URL https: http:::://pppceednnggeeeeeeee http:ppps..pppppp/////////////// Paperp...
Paper.pdf.
Yunwen Lei, Ting Hu, and Ke Tang. Generalization performance of multi-pas stochastic gradient descent with convex loss functions. The Journal of Machine Learning Research, 22(25):1 2021a. URL http::tt////. http://mm.oorrrr..eee wwwporrg//ppp///aaaaaaeeeeeeeeee waarrrs/v22// 111//19777 6.html.
Yunwen Lei, Mingrui Liu, and Yiming Ying. Generalization guarantee of sgd for pairwise learn- ing. In M. Ranzato, A. Beygelzimer, Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 21216-21228. Curran As- sociates, Inc., 2021b. URL https: http:////eeoeeeeegngcceeece wwwp:/ewwpp..cppppr////e/e. 1.5011411eeffaac44555 2olpaaeeee00000000000000------- 4400
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. URL
https: http://////eeeeeeee.eeeee www.weeeeeet.urrrre/eeeeeee forum? 1d=skxxt.gHKP..
Chaoyue Liu, Libin Zhu, and Mikhail Belkin. Loss landscapes and optimization in over weer-parametrrieed non-linear systems and neural networks. Applied and Computationnal Harmonic Analysis, 59:85- 116, 2022. ISSN 1063-5203. doi: https://doi.orge wtt.o/ooo//...01/.aaa.....oooo actpa 12.009. URL https: :ttpss// www.sciencen
wwreet.ccm.. science/ art aat.accce/pp11110000000000111100 Issue on Harmonic Analysis and Machine Learning.
Special
Gabor Lugosi and Gergely Neu. Generalization bounds via convex analysis. In Po-Ling Loh and Maxim Raginsky (eds.). Proceedings of Thirty Fifth Conference Learning Theory, volume 178 of Proceedings of Machine Learning Research, pp. 3524-3546. PMLR, 02-05 Jul 2022. URL https: https////poccceengs.... www.mm....ss......mm.ommmmm..eee wtteesss/v/////ue httppree///11///ngg9222...oo
Siyuan Ma, Raef Bassily, and Mikhail Belkin. The power of interpolation: Understanding the effectiveness SGD in modern over wer-parametrized learning. In Jennifer Dy and Andreas Krause Machine Learning, volume 80 of
(eds.), Proceedings the 35th International Conference Proceedings of Machine Learning Research, pp. 3325-3334. PMLR, 10-15 Jul 2018. URL https: http://poceeeiieeeee www.mmlr.peee.. /vcess//800 vv00 mm/0mmalaa a.html.
Liam Madden, Emiliano Dall' Anese, and Stephen Becker. High probability convergence and uniform stability bounds for nonconvex stochastic gradient descent. arXiv e-prints, pp. arXiv-2006, 2020.
URL https::t////. https:///xxxvvvovoeee /tt.://...066660000
Wenlong Mou, Liwei Wang, Xiyu Zhai, and Kai Zheng. Generalization bounds of SGLD for
non-convex learning: Two theoretical viewpoints. Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet (eds.), Proceedings of the 31st Conference On Learning Theory, volume 75 of Proceedings of Machine Learning Research, pp. 605-638. PMLR, 06-09 Jul 2018. URL https: /ttt://proceeee mgs.ml r.press pepoess/vSS. v75 /oui 8a.html.
12

---

Published as a conference paper at ICLR 2023
Jeffrey Negrea, Mahdi Haghifam, Gintare Karolina Dziugaite, Ashish Khisti, and Daniel M. Roy. Information-thewe
generalization bounds for SGLD via data-dependent estimates. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Bue, E. Fox, and R. Gar- nett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Asso- ciates, Inc., 2019. URL https: https::/prrceeed wtt.s/eeurrs.cccppppeeeeeeo ////1//////////ee (1011177222711333711122222222281
Yu Nesterov. Introductory lectures on convex programming, 1998. URL https:
wwwateseerx.is..suueiiii http://dd/wwwwwwwo///ooooooo wttp:///////ooooooao/o1-10000000 wtt.affcooo11111....3355555 replstype-pdf.
Gergely Neu, Gintare Karolina Dziugaite, Mahdi Haghifam, and Daniel M. Roy. Information- theoretic generalization bounds for stochastic gradient descent. In Mikhail Belkin and Samory Kpotufe (eds.). Proceedings of Thirty Fourth Conference on Learning Theory. volume 134 of Proceedings of Machine Learming Research, pp. 3545. PMLR, 15-19 Aug 2021. URL htttps://proceediine wtt.e/eeiiiig......e.s.....e r.press////e........ /t/.//134/4///// neu2 la.html.
Ankit Pensia, Varun Jog, and Po-Ling Loh. Generalization error bounds for noisy, iterative algorithms. In 2018 IEEE International Symposium Information Theory (ISIT), pp. 546-550, 2018. doi: 10. 10.1109//5 2018.847771
Ali Hainezani-Kebbyae Ashish Khisti, and Ben Liang. On the generalization of stochastic gradient descent with momentum, arXiv preprint arXiv:2 13653, 2021. URL url= (https: arxiv.org/ www./a//.... 10//9089994644
Nathan Srebro, Karthik Sridharan, and Ambuj Tewari. Smoothness, low noise and fast rates. In J. Lafferty, C. Williams, J. Shawe-Taylor, R. 7emel, and A. Culotta (eds.), Advances in Neural Information Processing Systems, volume 23. Curran Asso- ciates, Inc., 2010. URL https: / http://rrcceeenns.....e.ee httpccc//papp/210//11... 9
Bohan Wang. Huishuai Zhang, Jieyu Zhang, Qi Meng, Wei Chen, and Tie-Yan Liu. Op- timizing cntommttion-thooretinn generalization bound via anisotropic noise of SGLD. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Ad- vances in Neural Information Processing Systems, volume 34, pp. 26080-26090. Curran As- sociates, Inc., 2021a. URL https:
Hao Wang, Yizhe Huang, Rui Gao, and Flavio Calmon. Analyzing the generaliza- tion capability of SGLD using properties of gaussian channels. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neurul Information Processing Systems, volume 34, pp. 24222-24234. Curran Asso- ciates, Inc., 2021b. URL
Puyu Wang, Liang Wu, and Yunwen Lei. Stability and generalization for randomized coordi- nate descent. arXiv preprint arXiv:2108.074411 2021c URL 2108.07414.
Yue Xing, Qifan Song, and Guang Cheng. On the algorithmic stability of adversarial training. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Ad- vances in Neural Information Processing Systems, volume 34, pp. htt.scc/paaee//221/EE.e. sociates, Inc., 2021. URL https: https//////cccccigg....eeee df1 ff1e1d20ee8 070777745510 712225179541111 77888777777777111678888888 9405a Paperr.dd..
Curran As-
Yikai Zhang, Wenjia Zhang, Sammy Bald, Vamsi Pingali, Chao Chen, and Mayank Goswami. Stability of sgd: Tightness analysis and improved bounds. Uncertainty artificial intelligence. 2021. URL https:/
: / h/ppaarnns par.sss f.gov/bb htv//bibb /biblio//ii/ 0366270.
Pan Zhou, Hanshu Yan, Xiaotong Yuan, Jiashi Feng, and Shuicheng Yan. Towards un- derstanding why lookahead generalizes better than SGD and beyond. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances
13

---

Published as a conference paper at ICLR 2023
in Neural Information Processing Systems, volume 34, pp. http.//pppppe///////eee.. http://aw...aaaa.cooa///////////
Curran Asso-
ciates, Inc., 2021a. URL httpss//pproeeeen....ueeegeeeeee ef5664777687744005555006-6--2200
Yi Zhou, Yingbin Liang, and Huishuai Zhang. Understanding generalization error of SGD noncon- vex optimization. Machine Learning, pp. 1-31, 2021b.
axticle/10.1007//1000 0010:////1119000---00000
Yi Zhou, Yingbin Liang, and Huishuai Zhang. Understanding generalization error of SGD in nonconvex optimization. Machine Learning, 111(():355-77,, 2022. URL https://doi.org 10.1007/s10994-000 02100211-12000 100-066066-
14

---

Published as a conference paper at ICLR 2023
Full-Batch Gradient Descent
Step Size
Generalization Error
Loss
4ev3 Tc / (Copt + ee) +
T 12c²
Te 1 C/
NC
n²
Spath
(ET))
(eT) 20
VC <1
48
B[Rs(Wi))
NC
n1
27 nt
Th 1/28
+
(3 W1 w3ll2 -TE)
C
n
8 8v6 v Ar
4v3 3 + 71
2T
T/2 = 2/
exp
AT
Y-SC
n
Table 3: A list of the generalization error bounds for the full-batch GD. We denote the number of samples by Wi is the initial point of the algorithm, and W is a point in the set of minimizers of the objective. Also, "Cpath" denotes the expected path error (path A Σ [ l²] "Copt" denotes the optimization error Copt - E[Rs(A(S)) Rgg. T is the total number of iterations and define the model capacity (interpolation) error risk 6c (W))(W3)))- Lastly, define the constant M(W)) - max { W [12) ([ss(W5))) and the terms In & (M(WW) min (3/" (8/7 + 1) log /2y, AT & (TT(WW)) min (./7%oo: 2T) /(3 + 7). Lastly, "NC", "C" and "C-SC" correspond to nonconvex, convex and y-strongly convex objective, respectively.
A SUMMARY OF THE RESULTS
Herein, we present summary of the generalization and excess risk bounds. The detailed expressions of the generalization and excess risk bounds appear Table and
B PROOFS
We provide the proofs of the results these sections. We start by proving Theorem and the bounds on the sum-product terms that appear in the stability error bounds, and then we continue with stability and generalization error guarantees, that we prove in parallel. We derive the excess risk bounds by applying the decomposition of the inequality (2).
B. PROOF OF THEOREM 3
is true that for any i.j E [I,...,m
E[f(A(S): 2)] ([((A(S)::)))))))))]]])))))())) 2,)1= 1 B[f(A(S); =x)] E[RssA(S))]
(20)
We show equation 20 through the symmetry the algorithm (at each iteration) and the fact that {= In are identically distributed as follows. The random variables {2]] remain exchangeable."
The 3-smooth property of f(;;z) for all 2 E Z gives
f(A(S()); f(A(S): S (A(S() A(S), vf(A(S): + (|S(S)) A(S) (21)
2
*P(21 C1 C2....; Ci...., Cj... ..... 2m Cn. A(S) w) = Pl11 = 22
, 2j Cj..... 23 C....,, Cn. A(S) w) for any choice of the values C1, .2. Co. and for
any 1, E (1....,m).
15

---

Published as a conference paper at ICLR 2023
Full-Batch Gradient Descent
Step Size
Excess Risk
Loss
Tht S C/BI, AC <1
Vlog(eT)(eT)
E E[Rg( (eT) + Eopt
20
48
NC
n
n²
[8
16T
331 Wi - -wsli
? 1/28
(3 - Walle + Tee) +
n
T
Th 1/23, T VT
+
33
W1
8
C
vn
8v3
y
4v3 AT
-4T%
1/ - 2/(3 +7) +7)
V A
exp
+Aexp
Y-SC
n
+ Y
1377)
2/(3 (1) T (8+7) log 27
8 8v3log
1 + 4v3
VTn +
I'm
+
SCSC
n
Table 4: A list of excess risk bounds for the full-batch GD. We denote the number of samples by n. Wi is the initial point of the algorithm, and W'g point in the of minimizers of the objective. Also, "Cpathi " denotes the expected path error <path & "E=1 ne Ell fWW, 11)] "Copt" denotes the optimization error Copt the model capacity (interpolation) error risk e. A E A - 3E[[|W / M(W)) A max {B (M(W) min {.3/Tie: (8/r + 1) log n) /27, Ar & (TM(WW) min (B/Thoo 2T) /(B ((3++). Lastly, "NC", "C" and "y-SC" correspond nonconvex, convex and y-strongly convex objective, respectively.
(A(S)) Rgl. T' is the total number of iterations and we define
Lastly, define the constants 11)) IE| [E[Rs (W5)) and the terms r, &
The expression Egen [[((((()) 2.) f(A(S); 2]]] and the inequality (21) give
- A -
Egen
E
(A(S()) - A(S), (f(A(S); +
(22)
2
We find an upper bound for the expectation of the inner product of the inequality (22) by applying Mauchy-Schwarde inequality as
- A(S)) -AAAS))
E
SE - ((1)))))-AA))))//V/(((1))))))))
(23)
(aaab(A)) ([I))((())
(24)
here we use the inequalities (a, 6) < ||||||b||| and E < || to derive the bounds in
23 and 24 respectively. By combining the inequalities 22 and 24 find that for any i {l...., n2
it is true that
3
Egen I (II
2 Sstab(A)-
(25)
To find an upper bound for the (egen), we also need an upper bound for negative of égen namely Elf(A(S):z) - )(A(s(())) 24] -Egen- Note that by the same argument
Egen I E [[A(S) A(S | E [IV)(((())))))))))))))))
2 + AI)A A(5
(26)
Then we find upper bound E|[ =)) as follows
E
16

---

Published as a conference paper at ICLR 2023
E )22) =
< 2E [VTS(A(S ); - V
2 2,3%
(27)
The inequality 27 holds because of the B-smoothness of the loss. Additionally,
V /2 [|A(S)- - A(S + 21 1 [[ x)
< 2E [[A(S) A(S [2] BII / 2) 22
+ ((5) A(S
(28)
We combine the inequalities 26, 27 and 28 find
Egen - V 2E [|A(S)) A(S E V(A()( +) |3 A(S
(29)
Finally, through the inequalities 25 and 29 we find
(gen| S V (estab(A)) B[| (AA(S; + 2Btstab(A)
(30)
We use the self- self-bounding property of the non-negative B3-moooh loss function f(; (Srebro et al., 2010, Lemma 3.1), to show
[V[(A(S): + < 4))())));
(31)
The last display, Assumption 1 and equation 20 give
44B]J((ASS) ([))
x)] 43 B[((A(S);
(SSEER((((S))
(32)
4, (E(R)(A(S)) B[Rs(W3)) [[Rs(WW)))
4,3 (Copt - B[Rs(W5)))
(33)
We combine the inequalities 30, 33 and the Definition 1 to find
Iggnn| < 2 2/3 (Copt + te) (stab(A) + 2.eetab(A)-
(34)
The last inequality gives the bound on the generalization error and completes the proof.
B.2 SUM PRODUCT TERMS IN THE STABILITY BOUNDS
Herein we show a lemma for the sum product terms associated with learning rate in Theorem 6 and Theorem 12. Then we will apply that lemma to derive the corresponding stability error bounds.
Lemma 15 The following are true:
If C s 2/ + 7), then
T
T
1- (1 Ot)
Σ
II (1-mm
(35)
?
j=++1
If C/t 2/(8 7), for some C² 2/1 fort 2 1 1 [ and ne 2 ()) for
some C' <2/(7 33 for [&] then
Σ
II
(1
< Colog (e²13/>1).
(36)
2
jmt++
. If E C//t < 2/33, then
208 min { 1
1
Σ nh II (1,B)
2C3 log(eT))
(37)
j=t+1
17

---

Published as a conference paper at ICLR 2023
Proof.
. If = C + 77) then
T
T
T
T
Σ [=1
II (1-18
7--7) c> (1 (1-c))) =c Cy) Σ (1 cイ)
j=t+1
1=1
= =c -0--(1- -y)² 1 1- (-(1-
Cr
7
If m = 2/ for some C 2 2/7 fort t 2 1 + [ and 1/2 = 2/" + for
some C² < 2/(7 + 3) for & - | then
T Σ
(1
73?
7/
2
1=1
j=(+1
1
II
T
(1-
(-Ch)
Ch
Σ
C
II
T
(1-
2j
1=1+1
1=
j=++1
14
[
[r-1
TT-
16
= Σ
T 1I
(1-
Σ
T
C1 -
Σ
C²
+
+
2j
tt
T
==1 5=
[=
==1
1
SC 1 1og(111))
+
1 -
S log (e (31111
I. S C/t < 2/B, then
C Σ t
T
T II
(1+29)
Σ T II (1+
-=(+1
f=++
Σ C
T
II exp
2B )
=1
1=
T C
T
c
Σ
exp
28
Σ
jmt+1
T
C
<
exp
(20B (log(T) + 1 log(t + 1)))
Ce 2081200
1
(1 1)30B
< Ce 208
1
(1 1)203
S Ce 208
(38)
1++2B
T 1+ Σ
= 208200
21-20B
(=2
< 20282000
1+
x1+20p dx
18

---

Published as a conference paper at ICLR 2023
1+ 20B
(1 - T )
2088
20
1+ 2CB
28
S 20208
(39)
2CB
additionally Ei= 1/t S log(eT)) thus the term in the inequality 38 may be upper bounded by Cc2081203 log( eTT) for any T E N, and we conclude that
Σ T II (1,)),)² Ce 200 min { 1 j=t+1
1 2C3 223. log(eT)
(40)
The last inequality completes the proof.
In the next section prove the stability and generalization error bounds for nonconvex losses.
C NONCONVEX Loss: PROOF OF THEOREM & THEOREM 7
Let 21, 22..... 25..... 2n 24 be i.d. random variables, define $ - (21, 22...., 24 ,...,,, and
(()) A (21, 22, 22, 2/ 2n), W1 = W/. The updates for any 2 are
Tht W411 = Wt
vf(We,z))
(41)
n 1=1
O 4+1 = w/(0)
Σ
VS(W
(1) 21) The VV .4)..
(42)
j=Lj
Then for any 1.2 2 1, we derive the stability recursion as
| w(() #11l2
< ||, w((i 1|2
7/
71
j=1.jıi
+ T1 Vf(W,, 2
(/(W( (2)ll)
W w: 1|2 + N
IVf(W, 27) Vf(W .2))ll2
n j=1.j
(IVS(W,, 22) + /| (WW/" .+0)l2)
< ||W 11 + (n - (1)
Bl1W. w/ + 1h (IV 2)11a + (V
(43)
n
WW/-w((11) ||2 1 Bng ||, - w/(0|22 n
Th n (IVS 21 + / .4)1l2).
(44)
inequality 43 comes from the smoothness of the loss. Then by solving the recursion we find
w W
Wr+1
T
(IV (V/ (221l)
II
1+
1
Bmg
n
Ø=++1
n
1 (IV.((...))))) 21)la + + ))ll)
II (1+,3m)) 9mg)
T
n
d=#+
19

---

Published as a conference paper at ICLR 2023
2 T
T
(IVI((,, xi)l + [V/(W .201l2)
Σ
(1 + Bnz)²
1/1
f=1
j=++1
V2
T
T
(IVS =I I .
Σ
II j=
(1+ 1nz))
1/
7h
The last display gives
T
T
T
[[ W f
2 2 t=1
Σ
(IVS(W,,,))
2)12 (V
Σ U/2 1=1
II j=(+1
(1+ + Bn,)²
and by taking the expectation we find
BTI
w
T+1
T II (1 j=t+1
2
Σ
[B[IV 21)EE + B[IVS(WW ,40
Σ T
Bnz)²
?
4e path
II (1 + Bnz)² -=
(45)
n
We evaluate the summation of the products in the inequality 45. Lemma 15 under the choice of decreasing learning rate V)t & C/t & 2/3 shows that
T
T
Bn,)² 2C922 min {1
Σ
The II (1 +=
2C3' log(eT))
(46)
Through the inequalities 45, 46 and Thcorem 3, we derive the bound on the generalization error as
Egen
$ 2/
(cop + (e)Estab(A) + 2BE
T
T II j=(+1
T
T
<
2.(eape tc)
The Σ
(1+ Bnh)² 8,3 Spath n
1/t
II
(1
Bnj)²
7
1=1
j=(+1
4
20B(Eppt + ce) CBTCB min { 1+ 203 log(eT)
<
72
'path 208T228 min { 203
8CB
log(eT))
n²
Under the choice n, I C//t < 1/3 for all t, we choose < 1/3, further we define e é 3C < 1, and C(e, T) min {c + 1/2, log(eT)) to get
4
V (Copt + (eT) + 8 Spath (eT))*((e,)) n²
(ggeal <
4/3
(tapt. + pett + 12 Spath
(eT))
(47)
n
n
The last inequality provide the generalization enror bound and completes the proof.
Next derive upper bounds expected path error Epath and optimization error copts show alternative expression the generalization error inequality 47. We continue by proving the proof of Corollary 8.
20

---

Published as a conference paper at ICLR 2023
C.I PROOF OF COROLLARY 8.
The self-bounding property of the non-negative B-smooth loss function z() (Srebro et al., 2010, Lemma 3.1) gives (V,,,, t, x 4,,, z:). By taking expectation, and through the Assump-
tion I and the equation 20 we find
V f(W, 2)]l 48 = 43E[Rs(W.))) 4
(48)
The definition of Epath (Definition 5), and the decreasing learning rate (n. = C/t < 1/3tt give
Cpath
m BB 24) 5 43
B Rs (W.)
T
1/
(49)
T
4B(Rs(WW)) Σ
<B[Rss(W))log(ee))
(50)
and the inequality 49 holds since the learning rate 1/t < 2/3 guarantees descent at each iteration. Similarly, Copt + E Es The last inequality together with the inequalities 50 and 47 give
Iggeal s
4v3 V(copt (eT) + +2
path n² (cT))
2c
n
8/3 Vlog(eT)(eTT)+ + n log log()
48
(WR)(
n
The last inequality provides the bound of the corollary.
D PL OBJECTIVE
Herein we provide the proofs of the results associated with the PL condition on the objective. We start by proving upper bound on the average output stability. Then by combining Lemma 16 and Theorem 3 we derive generalization error bounds for symmetric algorithms and smooth losses, as well as the generalization eтror bound of the full-batch GD under the PL condition. A similar proof technique of the next lemma also appears in prior work by Lei et al. (Lei & Ying, 2020a, Proof of Lemma B.2).
Lemma 16 Let the loss function [=; )) be non-negative, nonconvex and 3-smooth for all E Z. (w) 1 2 2pl[[s(()) for all Rdd. Thr
Further, let the objective be p-PL, E V (w) any algoritium it is true that
16
85
EIIA(SS0) A(S)
Copt
(E [[[[s(ss)) n2p22
(51)
P
Proof. Define the projection gyy π (A(S())) of the point A(S()) to the set of the minimizers
of Rgm (-), and the similarly the projection Ts +AA(S) of the point A(S) to the set of the minimizers of Rs(-). Then
B|[| ((S A(S)
< 4E (E(()(((() - T + (E([)A(() TH T + [[[[[TTQ] T [121
8 ElR sun (A(5())) Rgo 8 (E(Rs(A(S)) R3] 2T |T sta
(52)
Capt + 2|E[|[ - T
16
4 [E|Rs(TT(()))
Copt
P E(Rs(s))))
(53)
21

---

Published as a conference paper at ICLR 2023
the inequalities 52 and 53 come from the quadratic growth (Karimi al., 2016). Recall that, the PL condition on the objective gives
1 BllVRR((TSO) ([Rs((TSO) - Rs(=s))-
(54)
2μ
We combine the inequalities 53 and 54 find
16
2 R
([IA((S)) - A(S)
<
Eopt +
(55)
1
Also, it is true that
V (gs( )12 = | Rgo (Tg())
Vf(ggii 24)
12
n
2
2
Vf(Tg() 2 +
|
(Tggri)))) x)
(56)
n
n
4/3 (
4, [T n
24)
(57)
n
equation 56 holds because V Rggo g()) 0, the inequality 57 holds for nonnegative losses (Srebro et al., 2010, (Lemma 3.1). Through incquality57 we find,
48 1131
46
E|| VRVV(((TSS
[ (T 2(11 + B 24]
(58)
n²
n²
4
43 + ([[ss
n [[((Ts;
(59)
n²
and the last equality holds because zı, 2 are exchangeable. We combine the inequalities 55 and 59 to find
B[ILA(S() A(S)
v Copt +
83
Σ
E [[s(=s: 2:)1 1 n
Σ
Ef((Tsi))
(60)
72
16
83
opt
+
n2212
(E. [R((TS)) [[((Ts)]).
(61)
Since [[]|A(S()) - A(S) = B[IIA((0)) for any i E [I....,
A(S) for any i, E nI)...,,., we conclude that
16
83
E(IA(S(0)) - A(S) <
Copt
n2p²
(E [s((s) + E([(s)))
(62)
The last inequality provides the bound on the expected stability and completes the proof.
Corollary 17 Let TS (A(S)) be the projection of the point A(S) to the set of the minimizers of Rs(.). Further, define the constant ē ([Rs(Ts) + R(Ts)). For any symmetric algorithm, non-negative 3-smooth loss function f(r all E Z, p-PL objective and E[R;] is true that
8.
16,32
44,3
(ggen I
Copt
n² ē ++
Cape-
(63)
nj
Further, define the constant e & 44 (ax(E + R( alization error of the full-batch GD with slep-size choice the 1/3 and T total number of iterations is bounded as follows
- Rgl]. Then the gener-
c3 (1 11-1
T/2
c22
cB
Iggen| <
+
(64)
n
n2 n2p²
0
22

---

Published as a conference paper at ICLR 2023
Proof. We define the constant ė è ([R)(TT) + R(Ts)] apply Theorem 3 and Lemma 16 to find
Egen
s 2
(opp + +e))stab((1) + C
8
4V23c
323
Eopt + 1632
Copt
2B + tc) +
n² n²2120
n4
/1
2/3tppt
88v2
32,
Copt + 16,32
Copt ce
CCopt +
+
n²pu²
nu
80v2
8v E/2peopee
16,32
448
nu
Copt
+ +
V/
n² n²pr²
2+
Copt.
(65)
The last inequality completes the proof.
E CONVEX LOSS: PROOF OF THEOREM 9 AND THEOREM 10.
We start by proving the non-expansive property of the stability iterates for the case of 3-smooth convex loss. Then we continue with the proof of the stability generalization error.
Lemma 18 Let the gradient of the loss be 3-Lipschitz for all z E Z. If the loss function conver and < 2/B, then for any t < T + 1 the updates W., w! satisfy the next inequality
VV(W)))) (2)) | S IW, w 12.
W. w( (1)
17 Σ
(Vf(We22)) J=1
(66)
Proof. By the definition of B-Lipschitz gradients and triangle inequality, it is true that
[V](We, f(W, d2ll < B|IW, w.(") (1) ll2
(67)
((W,,);
Σ </(W 22)1l S 3| ||W, w 112.
(68)
JEJ
JEJ
Since the function h(W)+ & EEEO Vf(W,,,) is convex and the gradient of h(w) is B)J L-ipschizt follows that (co-coersivity of the gradient)
Σ (W) (V-.:))))VV((((.))..)))))))))))) Vf(W ,2);, W, WW!")
(69)
JEJ
Σ
vf(We&))- - Σ Vf(W(",2))) .2))112
(70)
B
JEJ
JET
Then prove the inequality 66 as follows
- :25) |
We (,(00
T1 n
Σ
j=1.f
- - 11(0013
2 The
Σ (V((W, ( ,5), W. - W((0)
(71)
n
ド=
nr
(VS(W,, 2,) - VS(W ,=))) 12
n2
ド=1,$$1
|W, 1 Th vf(We,zz) Σ ( W. - )
j=1,$$
Σ
Vf(W, 23)
Σ VS(W!"),
j=1μ
j=1.441
23

---

Published as a conference paper at ICLR 2023
[
11:0112
v/(We,
Σ VS(W
3( 1)n
f=1,f
J=1
n Σ
Σ
Vf(We, 27)
vf(W[(),))) 22)1l
(72)
n²
j= 1ij
j jmliiti
W W/
W 112
7tt
1)t
8(n - 1) )
2
Σ j=luøi
- ( ,2))
+
n
IW; 10
(73)
equation 71 holds from the expansion of the squared norm, comes from the inequality 70. The inequality 73 holds under the choice nh < 2/3 and completes the proof.
Lemma 19 (Accumulated Path Error Convex Loss) Let the loss function f 2)) be convex and 3-smooth and nu I 1/23. Then the expected nath-error of the full-batch GD after T iterations is bounded as
T
Epath S 4 W1 - W3lll + R3
mh
(74)
t=1
Proof. The self-bounding property of the non-negative 8-smooth loss function f(:2) (Srebro et al., 2010, Lemma 3.1) gives [[W =) I 48f(W,, 24). By taking expectation, and through the equation 20 we find
fWW, =)] 4WW 2]] 45E))ss(.))-
(75)
Similarly to the approach by Lei & Ying (2020b, Appendix A, Lemma 2), we use the convexity and the assumption 1)t S 1/2, find
[|a+1 W I[W, 7) RRs,W, W
= || W W + [ + 2nc - W,, VRs(W,))
< I[, Will2 + n VRs + 2n (Rs(W3) - Rs(W,))
K || W WEll3 + 25n (W(,) + 2m (Rs(W))) Rs(W)))
< IW: - W + 2 Rs (W3) Rs
The last gives
T
T
T W -
T
Σ n. Rs,,))
Σ
W W3113
+ +2 Σ
RRss(W
t=1
1=1
1=1
T
< W - W313+++ Σ
ne RW3))
(76)
The definition of path (Definition 5), the inequalities 75, 76 and the choice of the learning rate (n S 1/2,3 give
Σ BBlllff(W, 2)11 S 43 Σ 13 (.[RRs(W.))
Epath
< 43 W3lle1 + Σ BB
(77)
The last inequality provides the bound on the épath.
The standard choice 7): S 1/3 gives the next known bound on the optimization error.
Lemma 20 (Optimization Error Convex Loss (Nesterov, 1998)) If f(322) is a convex and B- smooth function and T7 S 1/8, then
E W[[ W
Copt E[Rs(A(S)) Rs(W3)) <
(78)
Σr
24

---

Published as a conference paper at ICLR 2023
E.1 PROOF OF THEOREM 9 AND THEOREM 10
Fm; oy be i.i.d. random variables, define S _ (2,.,2 , 2n) and Let 21, ,2,..., ;,,..,,
Sti) A (Z1, (2,, 22,..., ,..,..,,................... ,,....,,22), 2n), W1 = W1. The updates for any 2 1 are
1/t W+11 We
z))
(79)
n
1 W.()
Σ
Vf(W?
(1) .2)
Th VVW(W .2)
(80)
n
n
Then for any 2 1
W - w Wttll2 12
W w((1) Ue
Σ
n
(VS(W,,))) -V(W,.))VV(((?>)) VS(W/", (2)))22))))) |
n
j= Liti
+ Th V Wf(W,,2) 21) v/WW! ,24
W. w:(0 - Σ
2)) V/WW/ .2,)
j=1
+ Th (IV/(W, ll22 + (VS(W! +V .4)12)
< W. w1 ll2
The
2))la + [V .2))ll)
(81)
n
The inequality 81 comes from Lemma 18. Then by solving the recursion, we find
T "
Wr++ W(( W
ll2 S
(IVJ(W,,)))) 20122 (VS(
n 1=1
thus
T
2
-
1
Σ
+ - (2)]l))
n
1=1
T
<
n
2
110
(IVJ(W,, =)12 + "
(82)
1=1
t=1
Inequality 82 gives that for any i E (1.
T
Wr|1 - W
(1)
<
[ ([([),))))1 + B.lll (O 22)11111
Σ 7
2+1
71
t=1
T Σ
4cpat
E V
n
T7c-
(83)
n
n²
t=1
t=1
A(S(0). Theorem and the inequality 83 give Recall that Wr-1 A(S) and W(
T+1
lggenl /2 (Copt + IB|Rs W ))) (tab(AA) + 2BEstab(A)
22 23 (Cope ())))
4Epath n²
Σ 7e 2,3
46 path
nt
(Copt + R.Rs(W
n
Epath
2,3
Σ
n:
8,3
Spath
n²
nt-
(84)
t=1
25

---

Published as a conference paper at ICLR 2023
Under the choice of constant learning rate 77 1/23, Lemma 19 together with the inequality 83 give 'path S 4 - w
+ 8 (W3)) E Th. and Cupt S 3,33[|]
W Thus
32
B
T
(stab(1) v
Ell W - W3l + BE Rs
5)
Σ
7
n
(85)
n²
2
1=1
32
B
1
T
BillW] - w3ll8 + 2 2
B[ss(W
(86)
n²
2,3
8T
B|I[W] - W3l E 7
(87)
n²
The inequality 84 and Lemma 20 give
I gggn S 22/20 23 (cops (W)))) (saa((A) 2/eesab(A)
8T $ 2/ 23 (Eopt + (W)))
B - EI T
3
8T
ElllW1 W ([R3)) /)
2/
nn
/VT
(Fopt + E[Rs W3))) (B - W3l + (W()))
11
16T
(SEll W11 - W31l8 + +T((Rs(W3)))
n²
8VT
W3ll + (W
(BBl W TE
n
16T
[IIe]) W1 -
n2
(33
W31 + (SB(I W3l + (W
16T
w + RRs(
n
16T
(3 - -3 + 7 +
(BB[II,, W3ll8| + (E(R)((3)))
n²
1
2T (333) Wi
8
W 1 + (W3))
n²
The last inequality completes the proof.
F STRONGLY-CONVEX OBJECTIVE: PROOF OF THEOREM 12 AND THEOREM 13
Similarly to the convex case, first provide the contractive property of the stability recursion in the strongly convex loss case. Then we prove the stability and generalization error bounds.
Lemma 21 Let the objective fanction be 7-strongly convex (7 > 0) and the leave-one-one objective function be "ooo stronnyyy convex for some Nooo 2 0. If the loss function is convex 3-smooth for all 2 E Z and tp < 2/(3 + 7), then any t S T 1 the updates We, w(()) satisfy the inequality
12 1/8
W. w (VRs-: - VRs- (ws)),
< (1 - - I|W W
Proof. The function Rs- (.) is also B-smooth for all E 2 and the strong convexity gives
(V)) V R (w(") (w))), W. W!
26

---

Published as a conference paper at ICLR 2023
B ||, W
1
VRs (W:) VRs -(W:") >|2
(88)
B + The
(3 Yooo 7oo0)
We expand the squared norm as follows
2
Wr w! T/ (VRs-: VRs - (w((
-W 21, (W.s - VRs (W,()), ,,W, W
+ - VRs- )12
I 1|, w mh (
VRg- )12
2nt
8
I|, w!()) 112
1
VRs- - VRs- (R, )1
(89)
3 + 7
(B + Noo)
B-io0
21ft
IW: w 112
B + Nooo
2
[VRg-: <Rs-
+ 1/t
11t 3 + Tioo TTonn
B71oo
21ft
||. - W/( 112-
(90)
B + "loo
We apply the inequality 88 to derive 89. The inequality 90 holds since nhe s 2/(B + 7) and
3 2 "ooo Also
8
2np 3 + Vooo
2Tj. 2,3
T] Yloo-
(91)
Through the inequalities 90 and to derive the bound of the lemma.
Lemma 22 (Accumulated Path Error Strongly Convex Loss) Let the objective function Rgg (-)
be --strongly convex and 8-smooth. Define IT,,T) & (1 exp( -4T% ) (exp(( ( -)).
= 2/(3 + 7), then the expected path-error of the full-batch GD after T iterations are bounded as
482
83T
Epath I
3 7 T)BlIW
- w
B 7 B[Rs(W3)),
(92)
Proof. The self-bounding property of the non-negative 8-smooth loss function f(;2) (Srebro et al., 2010, Lemma 3.1) gives f 2,) [ < 48f(W,, 24). By taking expectation, and through the Assumption and equation 20, we find
VW,,,, 2) < 4 (W,, 2,)1 = 45E Rs (W,) = 4, 4,5 (W,) (s())) + Rs Rs(W)))
(93)
Further, Lemma 23 and the choice of constant learning rate 77 2/(B + 7) give
4t +1
E ElRs - Rss (W3)) < exp
B
E
- W3lll1.
(94)
The definition of ppth (Definition 5), the inequalities 93 and 94 and the constant learning rate (n 2/ x)) give
Epath
(WW, 2)
(95)
-=1
< 48
RBB(RssW
Rs(W3)+ Rs(3))
< 4,3
Σ
T
B
B
exp
-
-41
+1
B[ - w +
B+7
8,3
E [[Rs(W?))
7
27

---

Published as a conference paper at ICLR 2023
43
4t
83T
W -
E
W
Σ exp
+
E
(s)
3+9
P +
B+7
1 - cxp
-47
4
-4
++1
83T
B [[[ W exp
E
(W)))
8+9
B +
3+1 7
exp
Z+1
I(7.2))
462
83T
B+7 T(x T(,, ())[ - -3ll2]++ +
(W))
(96)
B +
The last inequality provides the bound on the Epath. Further, can show that
{
T T) S min
T
(97)
e0+h
simplify the expression in the inequality 96.
Lemma 23 (Nesterov, 1998, Theorem 2.1.14)) (f)(;) is r-stronglyy corvex and B-smooth func- tion and 1) 2/(3 + 7), then
3
4T
Copt
exp
1 +
E| [
12).
(98)
7
Alternativel, if c/t, then
Copt 2
B
2:
E W1 W
(99)
F.1 PROOF OF THEOREM 12 AND THEOREM 13
Let 21, ,2,...,
76, ,....,,,
Fm 2 be i.i.d. random variables, define S A (21, #2,,,,,... ,,, and
((i) A (21, 22,,2,-000 22,.... ........,......... 2...., 2n), W1 = W/. The updates for any 2 1 are
17t W41 Wt
V((W, 2z);
(100)
n 1=1
O 8+1 = w/O' Th
VS(W!) ,2)) Th F 22)).
(101)
n
j=lo
Then similarly to the inequality 81 we get
We+1 41
((20 lla
W, m/(0
17t Σ (V((W,,))) VS(W(),)))
<
+ 11
IVW, V S(W((), ,21112
W. w/(0- me (R.) Rs Rs-:(w("))
+ (IVS(W,, x1]12 + / (WW #1)112)
< (1 N/t Now) } I|, w('0 + th 인
(IVS =) + ( ,1))))))))
(102)
and we apply Lemma 21 to derive the bound in 102. Then by solving the recursion we find
|W++1 (0th--((1,11
28

---

Published as a conference paper at ICLR 2023
7
T
(IVS 2:ll2 + 1V (20l))
II J=
(1 nyob)))
7h
Σ T)t (IVI(W,,::))I) =:)lla + ( 2
T
T
Σ
1/t
(1 - T/ Hoo)
11
j=
5
2
Σ "h (IVJ((,,,))) x) + |V (=)1B)
Σ
1/8
II jmtt1
(1 Th Moo))
1
The last incquality provides the stability bound
|WT+1- - 1
2 " (IVS(W,,,))) 2 + |V
2
Σ
4/ II (1
(103)
j=++1
Inequality 103 gives that for any E n.
B - w 111
2
T/s
[ 2:11 + BIIV ((,
Σ T
II j=1+1
(1 ni No?o
n
t=1
T
T
T
(W,, 2:)
Σ T
II (1 - nyn)
n
t=1
j=t+1
4 4epath
(1 Noo)
(104)
n
j=t+1
Recall that Wr+1 = A(S) and W = A(S()). Due to space limitation, we define )oo)) - ΣL th 15 (1 (1-7) 700 (3) Theorem and the inequality 104 give
Igeaal s 2 23(copt + (W3)) Stab(()) + 2.3aaa)(AA)
(105)
4paac
n NiT, Hooo 2,3 4Epth
< 2 23(Eopt + E(Rs(W33))
UiT, Tooo)
n²
4 (Eapt + E.Rs(W 5)
2280(TT Now + 8,3
Spath
((T Nooo).
n
n²
Under the choice of 11 =C'= B47
3. the inequality 104, Lemmata 15 and 22 and give
T
T
4 path n
B[IIA(S) - A(s()))
<
m/
II
(1
t=l
j=t+1
T
4cpath
1
2 3+y
n²
Nooo
4epath 112
4Epath n2
2T B
<
A(Tioo T)
min
(106)
Nioo
and the last incquality holds since A(Tioo T) < 1/Tooo for any T and the monotonicity of A(Yoo: T)
gives A (Too. 7) < /B for any pair "Noo S 7. Though the inequality 105, we find the generalization error bound
4 /((pt + E.RRs Epptth
Epaah
/2812(m Noo) + 83 Spath (ho)) n²
|Egeul <
7
29

---

Published as a conference paper at ICLR 2023
4 (Eops + ElRs (W5)))
/28A (Nooo T) + 8,3Spai
Al A T)
a
n2
47
2
exp
2 +
B|Il - w3l + [[
E[Rs(WW)))
4,32
8,3
X
[ E W W3l +
E B[Rs(
v /2BA( (Nooo: T)
3 +
B+7
4,9
[(7, T) W2 W
+ 8.9 847
E Rs (
+ 8/3
3+7
A < 7)
n
43
8,3
5 V
[(7,T) T)
+ B
max {B
RR
B +
B+77
4
1T7
48
85T (T;
X 123A( (rito: T) +
n
2
exp
B+7)
B
8+7
B+7
v 2/33( (Tooos T)
49
[(,, T)] +
837
3A (Noo: 7))
+ 8
8+7
8+7
max max ( W1 - W3ll)) Rss
n²
4
45
8.37
7V V
T) +
max {
W3 (W3))}
3 +
B+7)
4 n
4T
43
85T
x 2,3 (THoo; T) +
exp
# 7
+1
B B+
[(7, 7) +
3+7 +
v BA (Tioo T)
48
[7,,
+
88T
+ 8
3+7
B47
BA
Maooooo 2)
max max(3B|IlWW - w3ll2. E(ss
(107)
n
We proceed by applying the upper bounds of [(y, A),o( 7) as appear in the inequalities 97 and 106 respectively and equation 107 gives
|ggenl
4
48 B
8,9T
min
T
+
47
1
B
+
3 Nin
x
max [ W
W3ll3), (W)))) 2 min
2T
4
-2T
43
8,3
3
+
n
exp
B++>
V
B + +
min
8-7
T
+
3 7
2 min
Noh00"
27
48 34y
min
1
T
+
83T D+7
+ 8
13777 -1
45
min
3
27
max
W311),
n12
Noo
4,3T
8.3
B Nioo
+
max {3E W1 - Wglll,, E[Rs))) min
2T
3 +
B 3+7)
4 exp
-2T7
43T
83T
71
3 7
V
+
3 3+y
2 min
"Ho0"
2T
43T
88T
3 2T 22r) })
+ 8
34y
9+7
min
max
3E
-W313) ([
n/2
Boo
30

---

Published as a conference paper at ICLR 2023
8v3
3T
max [3E W1 Wglle. E. ( {
B 2T
V
(1000 Nooo
+
8v3
-27"
ST
3 27 Yioo
+
exp
3 +
V B
+
2 min
27
8T
8 22T) Noo0
+ 96
8+7
min
max
(
W1
(108)
n²
To simplify the last display, we define the terms m(Nov. T) - BT M(W)) a max {BB[IIW, - B[Rss)))
BBT min (3/ 2T) /(B + 7) and
Igeal
8v6
V /m(Moo: (W;)
n
8v6
(22
96
ml Moor 17 M(W))
+
exp
ml /m(Tioo
Noor T") + n²
m
3+71
n
8v6
-2T7
4v3
v /m(nioos 7) M(Wi) ) | vml ( T)
VM(Wi) +
exp
n
B +
n
Choose T log(n)( + 72/2 and define Mm, 108 gives
min
0+7 log n then the inequality B
27
760
Iggeal
8
B
8
max [B W311), min
log m
n
27
Noo
8 n22
3 log n
B 8+7 ?
+
min
log(n)
27
Nooo
48,3 log n
B
+
?
(og(n))
+
min
max (31E]] Wi
7
n2
Ylno
8 logn
4v3
M(W))
Mm. M(W) +
mmm
mm
n
12
n
6 6 logn
VM(W))+ + 4 4 M(Wi)
(109)
n
n
The last inequality completes the proof.
31


Reviews:
[{"review_id": "sHi-XzscxU", "reviewer": "Reviewer_zLoh", "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": "The paper provides sharp generalization bounds for the full-batch Gradient Descent algorithm on smooth losses. It builds upon the stability argument and risk decomposition. It derives a generalization error specifically for nonconvex, convex and strongly convex cases with smoothness assumption. ", "summary_of_the_review": "The paper provides improved generalization analysis for gradient descent for various cases under smoothness assumption. However, the improvement on the number of iterations for GD over SGD is not surprising, which mainly attributes to the less noise in GD and the better convergence rate GD. The paper does not provide insightful implication for practice.", "strength_and_weaknesses": "Strength:\nThe paper provides tighter generalization bounds for Gradient Descent via stability argument, which can serve as basic results for this type of references.\nThe paper is clearly written, and references are covered sufficiently.\n\nWeakness: \nThere are no convincing insights for such bounds. Though the generalization bounds for GD are comparable to that of SGD with much fewer iterations, GD cost much more computation than SGD for each iteration.  Even for the literature where GD achieves the \"same\" excess risk as SGD, GD requires much more pass of data. There is no sufficient motivation to advocate the use of GD over SGD.\n\n\n\nThe expectations in many definitions and theorems all have the same meaning. Please do specify what is expected over.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "NZwqD4A6xc", "reviewer": "Reviewer_Phd7", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This provides us with expected generalization and excess risk guarantees for symmetric, deterministic algorithms on smooth loss functions. These bounds depend on the $\\ell_2$ expected output stability, the expected optimization error, and the model capacity (hence, Theorem 3 and its proof are interesting contributions).\n\nThe bounds are specialized to full-batch gradient descent (GD) in the case of non-convex, convex, and strongly convex functions. Interestingly, the resulting bounds from this paper show that:\n\n* When the loss is convex, GD can reach an expected risk in $\\mathcal{O}(1/\\sqrt{n})$ in $T=\\sqrt{n}$ iterations, as opposed to SGD that requires $T=n$ iterations, albeit with a different choice of the learning rate. \n* When the loss is convex, GD can also reach an expected risk in $\\mathcal{O}(1/n)$ in $T=n$ iterations like SGD with the same learning rate.\n* When the loss is strongly convex, GD can reach a risk of $\\mathcal{O}(\\sqrt{\\log n}/n)$ in only $\\Theta(\\log n)$ iterations, while SGD requires $\\Theta(n)$ iterations to reach a risk in $\\mathcal{O}(1/n)$.\n\nAt the core of the proofs for the bounds on full-batch GD is the path error, which is defined as the cumulative sum of the squared norm of the gradient over iterations, weighted by the learning rate. This is also an important contribution, that is in line with other works from the literature in the idea that the norm of the gradients is one of the keys to understanding the behavior of these algorithms.", "summary_of_the_review": "This paper focuses on bounding the expected generalization and excess risk for symmetric, deterministic algorithms for smooth losses. In particular, it focuses on full-batch gradient descent (GD).\n\nThe paper provides an alternative proof for general algorithms and then generates new proofs for full-batch (GD). These proofs depend on a quantity (path error) that depends on the norm of the loss gradients, which has been shown to be important for this algorithm generalization in the past. The bounds are sharper than previous bounds in the literature and show that GD can obtain better or equal rates than stochastic gradient descent, providing some understanding to recent experimental results.\n\nIn general, I believe the theory is interesting and the results are a valuable asset for the community. Hence, I recommend acceptance. Nonetheless, I would appreciate it if the questions raised in the weaknesses were addressed so that all the theory could be verified and if the following minor comments were taken into account. \n\n**Minor comments and nitpicks that did not impact the score of the review**\n\n* $R_S^\\star$ is never defined, I assume it is $R_S(W_S^\\star)$.\n\n* In Theorem 7, I believe it would be clearer to say that $\\eta_t \\leq C/t$ where $\\beta C \\leq 1$, and then let $\\epsilon \\triangleq \\beta C$.\n* In Theorem 12, you forgot to write that $W_{T+1} \\equiv A(S)$ and $W_{T+1}^{(i)} \\equiv A(S^{(i)})$.\n\n* In the proof of Lemma 15, it seems that in the part where $\\eta_t = C/t \\leq 2 / (\\beta + \\gamma)$, you forgot a jump of line in the inequality in the third line of the array of equations and inequalities.\n\n* Sometimes the notation for the mathematical expressions changes. For instance, you use \"The inequality (8)\" in page 6 and many times in the appendix you don't use the parenthesis. Could you please homogenize the notation in this regard throughout the paper?\n\n* The equation before inequality (37) should be $Ce^{2C\\beta}T^{2C\\beta} \\Big(1 + \\frac{1}{2C\\beta} \\Big) - \\frac{e^{2C\\beta}}{2\\beta}$. \n\n* In Appendix D: in the third line it should be \"generalization error bounds for symmetric and smooth algorithms\".\n\n* In the proof of Lemma 18, it should $\\sum_{j \\in \\mathcal{J}} f(W,z_j)$ that is convex and then the gradient of that, $h(W)$ that is $\\beta |\\mathcal{J}|$-Lipschitz. \n\n* It is not immediately clear that $\\epsilon_{\\textnormal{opt}} \\leq 3 \\geta \\mathbb{E}[\\lVert W_1 - W_S^\\star \\rVert_2^2] / T$. It would be helpful to say that we obtain that from Lemma 20 where we see that $\\epsilon_{\\textnormal{opt}} \\leq 8/3 \\geta \\mathbb{E}[\\lVert W_1 - W_S^\\star \\rVert_2^2] / T$\n\n* In the last array of expressions from appendix E, the second to last expression should be an inequality, not an equality (note that the multiplicative factor of 3 was not present in the first term of the second factor inside the square root).\n\n* In page 29, after (105), I believe you forgot to take into account the factor 2 in that was present in $\\sqrt{2 \\beta \\Lambda(\\gamma_{loo}, T)}$. Then, in all equations following the first $\\min$ is of $\\frac{2\\beta}{\\gamma_{loo}}$ and $2T$. This carries over and I believe the final result should have the multiplicative factor $8 \\sqrt{6}$ instead of $8 \\sqrt{3}$.\n\n* Sometimes the introduced extra notation harms the readability of the text instead of helping it. For instance:\n\n  * $\\Delta_T$ is used in Theorem 14, but never introduced. \n  * The incorporation of $\\textnormal{m}(\\gamma_{loo})$ is used in only one equation to quickly move to $\\textnormal{m}_{n,\\gamma_{loo}}$, practically having no impact in the proof (page 30).\n\n* Some expressions are numbered and some are not. This is okay and standard when the numbered equations are those that are referred to later on. Could you choose either to number all of them or only those that are referred to, please?\n", "strength_and_weaknesses": "**Strengths**\n\n* The paper is generally well written and easy to follow. It feels that this would be true even for people that are only somewhat familiar with these kind of results.\n* The results for full-batch GD in all of the settings are stronger than previously known in the literature. They show that GD can converge faster or equally fast and to better or equal rates than SGD for smooth and both convex and strongly convex losses (which is in line with current experimental results).\n* The appearance of the path error in their proofs and the way it is bounded is interesting and provides insights on what makes full-batch GD perform as it does.\n\n**Weaknesses**\n\n* As mentioned in the text after Theorem 3, (4) is essentially the tightest version of Theorem 2 b) of *[Lei and Ying 2020b]*. However, it would be nice to clarify that this is only up to constants, since the first term in (4) would be divided by 2 and the second by 4 if one were to obtain the variant in that paper.\n* In the remark about the particularization of Theorem 3 under the Polyak-Łojasiewicz (PL) condition, it would be nice to write what PL stands for and to cite the original references from *[Polyak 1963]* and *[Łojasiewicz 1963]* or the paper that coined the term *[Karimi et al. 2016]*. Also, the way the discussion after (5) is written, although correct, is a little confusing. Could you please re-write or explain further the arguments under the interpolation regime and $\\beta \\leq n \\mu / 4$?\n* After Corollary 8 it is said that (9) matches bounds in prior work, including information-theoretic bounds for the SGLD algorithm and it cites *[Wang et al. 2021b]*. I could not see to which bound the text refers after reading the reference, could you point that out and, in case that it needs some further modification, explain that?\n* Throughout the paper it is said that the only assumptions are smoothness (and after convexity and strong convexity) of the loss, and that the algorithm is symmetric and deterministic. Then, apparently dimension-independent complexity of the generalization and the risk are provided. However, the bounds depend on the standard term $\\mathbb{E}[\\lVert W_1 - W_S^\\star \\rVert_2^2]$, which usually depends on the dimension and is only in $\\mathcal{O}(1)$ when the parameter space is bounded by some constant.\\\nAn important element for the bounds of gradient methods under the Lipschitz/smooth assumptions is that they are dimension-independent when the parameter space is bounded. This is also the case here and I believe it should be mentioned clearly before showing the complexity terms that can be derived from these bounds.\n\n* There are some claims that I did not understood. Please, could you explain/justify them to me/in the text a little more?\n\n  * Why does (51) hold? I understand that you use the quadratic growth property in $\\lVert A(S) - \\pi_S \\rVert_2^2$, but I don't see why that would hold for $\\lVert \\pi_{S^{(i)}} - \\pi_S \\rVert_2^2$. Both $\\pi_S$ and $\\pi_{S^{(i)}}$ are projections, of $A(S)$ and $A(S^{(i)})$, but not the projections of each other.\n  * Why does (89) hold?\n  * In (101) you use $1- \\frac{\\eta_j \\gamma}{2}$ and then you replace that in the next array of equations for $(1-\\eta_j \\gamma_{loo})$. Why can you do that?\n  * Why is true that $\\Lambda(\\gamma_{loo}, T) \\leq 2 T / \\beta$?\n  * How do you obtain the third inequality of page 29? I am particularly surprised by the $\\mathbb{E}[R_S(W_S^\\star)]$ before the max inside the squared root. \n\n**References**\n\n*[Polyak 1963] Gradient methods for minimizing functionals (in Russian).* \\\n*[Łojasiewicz 1963] A topological property of real analytic subsets (in French).* \\\n*[Karimi et al. 2016] Linear convergence of gradient and proximal-\ngradient methods under the Polyak- Łojasiewicz condition.* \\\n*[Lei and Ying 2020b] Fine-grained analysis of stability and generalization for stochastic gradient descent.* \\\n*[Wang et al. 2021b] Analyzing the generalization capability of SGLD using properties of gaussian channels.*\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "9SFvBOCEZX", "reviewer": "Reviewer_U9d7", "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:\nThis paper tries to derive generalization bound using stability-based techniques under full-batch gradient descent. The results in this paper do not require any Lipschitz assumption, and the authors consider both convex and non-convex regimes. The techniques used in this paper follows Lei and Ying, where their techniques are mainly used in SGD regimes. This paper generalizes the results into GD regimes. The main difference here is Lemma~18, where the authors show a 1-expansion property for GD. Besides, the authors improve the previous analysis using Thm3. \nOverall, this paper is technically sound and clean, and I would like to see it published in ICLR. \n", "summary_of_the_review": "Overall, this paper is technically sound and clean, and I would like to see it published in ICLR. ", "strength_and_weaknesses": "Strength:\n1. This paper proposes a generalization bound under GD regimes using stability-based techniques. \n2. Although this paper generally follows the ideas of Lei and Ying (this leads to the relaxation of the Lipschitz), this paper makes some improvements.\n3. The authors consider both convex and non-convex regimes in this paper. \n4. The writing is clear and easy to follow. \n\nQuestions:\n1. I find that the results in this paper can be deployed in non-convex cases. Could the authors re-claim the technical aspects and difficulties of this paper in non-convex cases compared to Lei and Ying? \n2. The definition of path error (Def3) is for any i. However, I did not find the dependency of i in the notion $\\epsilon_path$. Do the authors mean the sup over i, or expectation?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "4V1XKwzbXF-", "reviewer": "Reviewer_A39n", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "This paper studies the generalization of full-batch gradient descent for strongly convex, convex, and nonconvex smooth but possibly non-Lipschitz functions. In particular, the authors extend the existing results for SGD to full-batch GD in all cases and compare the excess risk bounds. More importantly, the authors derive these results without the Lipschitz assumption, which is customary in the stability analysis. ", "summary_of_the_review": "Overall, I find this paper interesting as it drops the Lipschitz assumption for the generalization analysis of full-batch GD. However, I have two main questions (mentioned above) regarding the convex case's overall complexity and the nonconvex's convergence rate. I would appreciate it if the authors could clarify these two matters (and I am willing to increase my score given the authors' response). ", "strength_and_weaknesses": "I believe the main interesting result is regarding the strongly convex case where the number of iterations decreases from $n$ to $\\log(n)$. While this is expected (because of the GD convergence rate for the ERM problem), it shows the benefit of full-batch GD in this case.\n\nRegarding the convex case, for the case that the interpolation error is zero, GD and SGD have similar performance, while for the case that the interpolation error is non-zero, full-batch GD leads to $\\sqrt{n}$ improvement. However, one should note that full-batch GD requires $n$ times more gradient computation, and so overall complexity is worse than SGD. I would appreciate the authors' comments on this matter. \n\nRegarding the non-convex case, I am slightly confused by the assumption on learning rate ($\\eta_t \\leq \\Omega(1/t)$). I believe the convergence rate to a stationary point would be very slow in this case. I would appreciate it if the authors comment on the convergence rate under this assumption.  ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster