Thinking Outside the Ball: Optimal Learning with Gradient Descent for Generalized Linear Stochastic Convex Optimization
Authors: Idan Amir
Roi Livni
Nathan Srebro
Venue: NeurIPS 2022 Accept (2022)
Keywords: stochastic
convex
optimization

Abstract: We consider linear prediction with a convex Lipschitz loss, or more generally, stochastic convex optimization problems of generalized linear form, i.e.~where each instantaneous loss is a scalar convex function of a linear function.  We show that in this setting, early stopped Gradient Descent (GD), without any explicit regularization or projection, ensures excess error at most $\varepsilon$ (compared to the best possible with unit Euclidean norm) with an optimal, up to logarithmic factors, sample complexity of $\tilde{O}(1/\varepsilon^2)$ and only $\tilde{O}(1/\varepsilon^2)$ iterations.  This contrasts with general stochastic convex optimization, where $\Omega(1/\varepsilon^4)$ iterations are needed Amir et al. 2021. The lower iteration complexity is ensured by leveraging uniform convergence rather than stability.  But instead of uniform convergence in a norm ball, which we show can guarantee suboptimal learning using $\Theta(1/\varepsilon^4)$ samples, we rely on uniform convergence in a distribution-dependent ball.

Thinking Outside the Ball: Optimal Learning with Gradient Descent for Generalized Linear Stochastic Convex Optimization
Idan Amir Tel Aviv University i idanamir@mail, lau.ac... il
Roi Livni
Tel Aviv University rlivni@tauex tau. ac.il
Nathan Srebro
Toyota Technological Institute Chicago nati@ttic.edu
Abstract
We consider linear prediction with a convex Lipschitz loss, or more generally, stochastic convex optimization problems of generalized linear form, i.e. where each instantaneous loss is scalar convex function of linear function. We show that in this setting, early stopped Gradient Descent (GD), without any explicit regularization or projection, ensures excess error at most E (compared to the best possible with unit Euclidean norm) with an optimal, up to logarithmic factors, sample complexity of Ō(1/=²) and only Ō(1/E²) iterations. This contrasts with general stochastic convex optimization, where Q(1/e") iterations are needed Amir et al. [2]. The lower iteration complexity is ensured by leveraging uniform con- vergence rather than stability. But instead of uniform convergence in a norm ball, which show guarantee suboptimal learning using O ((1/E") samples, rely on uniform convergence in a iestribution-dppedder ball.
1 Introduction
The recent success of learning using deep networks, with many more parameters than training points, and even without any explicit regularization, has brought back interest in how biases and "implicit regularization" due to the optimization method used, can ensure good generalization, even in situations where minimizing the optimization objective itself cannot [28]. Alongside interest in understanding the algorithmic biases of optimization in non-convex, deep models, and how they can yield good generalization [e.g. 6, 8, 13-15, 21, 23-25, 29, 30, 39], there has also been renewed interest in understanding the fundamentals of algorithmic regularization in convex models 21, 9, 10, 31, 33], both as an interesting and important setting its own right, and even more so as basis for understanding the situation in more complex models (how can we hope to understand phenomena deep, non-convex models, we can't even understand them convex models?). In particular, these fundamental questions include the relationship between algorithmic regularization, explicit regularization, uniform convergence and stability; and the importance of stochasticity and early stopping.
In this paper we focus on the algorithmic bias of deterministic (full batch) optimization methods, and in particular of full-batch gradient descent (i.e. gradient descent on the empirical risk, or "training error"). Even when gradient descent (GD) is run to convergence, affords some bias that can ensure generalization. E.g. in linear regression (and even slightly more general settings) where interpolation possible, it can be shown to converge to the minimum norm interpolating solution. This can be
36th Conference on Neural Information Processing Systems (NeurIPS 2022).

---

sufficient for generalizatioon even in underdetermined situations where other interpolators (i.e. other minimizers of the optimization objective) would not generalize well. Indeed, the generalization ability of the minimum norm interpolating solution, and hence of GD, even in noisy situations, is the subject of much study. And in parallel, there has also been work going beyond GD on linear regression, characterizing the limit point of GD, or of other optimization methods such as Mirror Descent, steepest descent w.r.t. a norm, coordinate descent and AdaBoost, for different types of loss functions [12, 17-19, 22, 34, 35, 37,38) 38].
But what about situations where interpolation, or completely minimizing the empirical risk, is not desirable, and generalization requires compromising on the empirical risk? In this cases one can consider early stopping. i.e. running GD only for some specific number of iterations. Indeed, early stopped GD is a common regularization approach in practice, and other learning approaches, most prominently Boosting, can also be viewed as early stopping of an optimization procedure (coordinate descent in the case of Boosting). When and how can such early stopped GD allow for generalization? How does this compare to Stochastic Gradient Descent (SGD), or to using explicit regularization, both in terms of generalization ability, and the number of required optimization iterations? And what tools, such as uniform convergence, distribution-dependee appropriate for studying the generalization ability of GD?
uniform convergence, and stability, are
Our main result We will show that when training a linear predictor with a convex I Lipschitz loss (or more generally, for stochastic convex optimization with a generalized linear instantaneous objective), GD with early stopping can generalize optimally, up to logarithmic factors, with optimal sample complexity O(1/E), and with an optimal number O(1/²)) of iterations (the same as stochastic gradient descent), even without any explicit regularization, and in particular without projections into norm ball-just unconstrained GD on the training error. This contrasts to previous results regarding early stopped GD for arbitrary stochastic convex optimization (not necessarily generalized linear), for which Amir et al. [2] showed ((1/=*) GD iterations are needed (even if projections or explicit regularization is used).
Stability vs Uniform Convergence for SGD and GD The important difference here, and the only property of generalized linear models (GLMs) that we rely on, is that GLMs satisfy uniform convergence Bartlett and Mendelson [4]: empirical losses converge to their expectations uniformly over all predictors in Euclidean balls. This is in contrast to general Stochastic Convex Optimization (SCO), for which no such uniform convergence is possible [33]. Consequently, rather then uniform convergence, the analysis for SCO is based on stability arguments Bassily et al. [5]. For SGD, stability at each step can be used in an online analysis, combined with an online-to-batch conversion, which is sufficient for ensuring optimal generalization with optimal O(1/²²) number of iterations. But for GD, we must consider the stability of the method as a whole, which leads to optimal rates in the case of smooth losses Hardt et al. [16] but otherwise is much worse, necessitating using smaller stepsize, and hence quadratically more iterations [2] showed that this is not just an analysis artifact, but real limitation of GD for general SCO. In this paper, we show that once generalization can be ensured via uniform convergence, e.g. for GLMs, then GD does not have to worry about stability, can take much larger step sizes, and generalize optimally after only Ó(L/²²) iterations.
But we must be careful with how we ensure uniform convergence! To rely on uniform convergence, we need to ensure the output of GD lies in some ball, and the generalization error would then scale with the radius of the ball. A naive approach would be to ensure that output of GD lies in a norm ball around the origin, and rely on uniform convergence in this ball. In Section 4 we show that this approach can ensure generalization, but only with suboptimal sample complexity of is, worse than with the stability-based approach. Instead, we show that, with high probability, the output of GD lies in a small (constant radius) distribution dependent ball, centered not at the origin, but around the (distribution dependent) output of GD on the population objective. Even though this ball is unknown to the algorithm, this is still sufficient for generalization. The situation here is similar to the notion of algorithm dependent uniform convergence introduced by [26], though we should emphasize that here we show that aggortth--depende uniform convergence is sufficient for optimal generalization.
that
Context and Insights Our results complement recent results exposing gaps between generalization using stochastic optimization versus explicit regularization or deterministic optimization in stochastic convex optimization. [31] showed that for a setting that is slightly weaker (where only the population
2

---

loss is convex. but instantaneous losses can be non-convex), there can be large gaps between SGD versus GD or explicit regularization: even though SGD can learn with the optimal sample complexity of O(1/e²), explicit regularization, in the form of regularized empirical risk minimization cannot learn at all, even with arbitrarily many samples, and GD requires at least a suboptimal (11/e2+) number of samples (it is not clear if this sample complexity is sufficient for GD, or even if it can at all ensure learning). This highlights that the generalization ability of SGD cannot be understood in terms of mimicking some regularizer, as well as gaps between stochastic and deterministic optimization.
Returning to the strict SCO setting, where the instantaneous losses are convex, still, uniform con- vergence does not hold, and generalization can only be ensured via algorithmic- dependennt bounds. Nevertheless, optimal generalization can be ensured either thorough explicit regularization, SGD or GD-all three approaches can ensure learning with @(1/=²) samples [5, 27, 33). Even so, differ- ences between deterministic and stochastic methods still exist. [9] shows that in SCO, the output of SGD cannot even be guaranteed to lie in some "small" distribuioor-epeedent set of (approximate) empirical risk minimizers', and so the generalization ability of SGD this settings cannot be at- tributed to any "regularizer" being small. Dauber et al. also shows that GD does not follow some distribution-inue innppiiionn-neeeeeeett regularization path. In contrast, here we show that if we do take the distri- bution into account, then GD is constrained to follow (at least approximately) a predetermined path (i.e. deterministic path, that is independent of the sample, but does depend only on the distribution). Finally, there is also gap between SGD and GD, in this case, in the required number of iterations [2]. Surprisingly. this gap cannot be fixed by adding regularization to the objective [1].
Importantly, for either weak or strict SCO, regularization in the form of constraining the norm of the predictor (i.e. empirical risk minimization inside the hypothesis class we are competing with), not sufficient for learning [10, 33]. The failure of constrained ERM is critical here for the constructions of Amir et al., Dauber et al. and Sekhari et al. establishing the gaps above: since projected gradient descent would quickly converge to the constrained ERM, it would also generalize just as well, and the gaps and constructions are valid also for projected gradient descent.
In this paper we turn to the GLM setting, which is perhaps one of the most well studied frameworks in the learning theory literature, as it captures fundamental problems such as logistic regression, SVM and many more. Uniform convergence for GLMs [4, 20, 32] ensures that constrained ERM learns with optimal sample complexity, and hence so would projected GD with ((1/²²) iterations. Interestingly, GD on the Tikhonov-type regularized objective similarly yields optimal learning with only O iterations [36], indicating the lower bounds of Amir et al. on the iteration complexity do not hold in this setting. But both projected GD and GD the Tikhonov regularized objective are forms of explicit regularization, and so we study unregularized, unprojected, GD. Our results show that (a) when uniform convergence holds, both sample complexity and iteration complexity gaps between stochastic and deterministic optimization disappear (though stochastic optimization of course still much more computationally efficient), and (b) perhaps surprisingly, distribution- dependent uniform convergence is not only able to explain generalization of the output of GD, but it can do better than stability; (c) though it appears to be suboptimal, distribution independent uniform convergence can explain generalization even though the norm could become very large (by making explanations based uniform convergence inside fixed distribution independent class).
2 Problem Setup and Background
We study the problem of stochastic optimization from i.i.d. data samples. For that purpose, we consider the standard setting of stochastic convex optimization. A learning problem consists of family of loss functions/ ʃ W x % - R defined over a fixed domain W S Rd, parameterized by the parameter space X. For each B we denote the domain
B = {w Rd ||w]] s B).
Our underlying assumption is that for each E Z the function f(w; z) is convex and I. 1.-Lipschitz with respect to its first argument w. In this setting, a learner is provided with a sample S = (Z)...., 2n) of i..dd. examples drawn from unknown distribution D. The goal of the learner is to optimize the
'"smallness" here, refers to a size notion that measures how well an empirical risk minimizer over the set generalizes, see [9] for the definition of statistically complex
3

---

population risk defined as follows:
FD(W) E (f(:))) z-D
More formally, an algorithm A is said to learn the class W (in expectation), with sample complexity m(E) if given i..d. sample S (21....-Zz) such that 2 m(E), the learner returns solution A(S) that holds
E [FD(A(S)) min (D(w)++ +
weW A prevalent approach in stochastic optimization, is to consider, and optimize, the empirical risk over a sample S:
S-2"
Fs(w) 1 Σ f(w:z)) zi).
(1)
2.1 Gradient Descent (without projections).
concrete and prominent way in minimizing the empirical risk in Eq. (1) is with Gradient Descent (GD). GD an iterative algorithm that runs for T iterations, and has the following update rule that depends on learning-rate ry:
w n ()FFs((?))
where w O, and (W5 is the (sub)gradient of Fs at point w.y. The output of GD is normally taken to be the average iterate,
T
(3)
1=1
Throughout the paper we consider the aforementioned output in Eq. (3), though we remark that our results also extend to any reasonable averaging scheme (including prevalent schemes such as tail-averaging or random choice of w,).
It is well known (e.g. [32]) that the output of GD with standard initialization at the origin, enjoys the following guarantee the empirical risk, for every B:
B²
is (w min Fw(w) nl.2 wewe
(4)
1/
In contrast, as far as the population risk, it was recently shown in [2] that, for sufficiently large d, GD suffers from the following sub optimal rate?
E [FD
min (D( 22 miininnnV wEW
177 13)
1
(5)
S-D"
In particular, setting for concreteness B 1. a choice of 1 1/VT and T = 0(1/E²) may lead to g-error over the empirical risk, but susceptible overlitting. In fact, turns out that 7 O(1/et) iterations are necessary and sufficient [5] for GD (with or without projections) to obtain O(e) population error.
2.2 Generalized Linear Models.
One, important, class of convex learning problems the class of generalized linear models (GLMs). In GLM problem, f(w;2) takes the following generalized linear form:
f(w; z) = f(w (xx).))
(6)
where % = X x y. ((a.)) is convex and L-Liischitz w.r.t. and, Φb X - H is an embedding of the domain X into some norm bounded set linear space (potentially infinite).
As we mostly care about norm bounded solutions, we will assume for concretness that [|((x)| s 1. We also treat the value of the function zero constant, namely (e( z 0(1). In turn, the function f is L- L-Lipschitz as well, and we obtain by Lipschitness that:
[f(w, [[(w (fx), y) O[]w][L).
7the result in [2] is formulated for projected-GDD however the authors note the proof holds verbatim to the unprojected version.

---

Uniform Convergence of GLMs. One desirable property of GLMs is that, in contrast with general convex functions, they enjoy dimension-indee innppeedddnndeeeee uniform convergence bounds. This, potentially, allow us to circumvent the bound in Eq. (5). In more detail, seminal result due to Bartlett and Mendelson [4] shows that, under our restrictions on and Φ. the empirical risk Fs(w) converges uniformly to the population loss (w) as follows for any B:
E sup {FD(w)- Fs(W))] 2LB S-D"
Vn
weW
By a similar reasoning, one can show a stronger property for GLMs, which we will need: uniform convergence any ball, not necessarily centered around zero. More formally, for every and K let us notate
w == (w: ||w uIl s K}.
We can then bound the expected generalization error of W as follows:
Lemma 2.1. Suppose E(a,)) y) L-Lipschitz w.r.t. a and Φ : - H is an embedding in a linear
space H such that [[<p(x)]| s 1. Then, for f as in Eq. (6). We have for any a and K
2LK
E
sup
sup {Fn(w) - -Fs(w)] wEWK
S-D"
Vn
The proof is essentially the same the proof of Eq. (8), and exploit the Rademacher complexity of the class. For the sake of completeness we repeat in the supplementary material.
Eq. (8), and more generally Lemma 2.1, imply that any algorithm, A whose range is restricted to B-bounded ball, that has an optimization guarantee of,
(s() - min Fs(w) = 0 LB wEWs
Vn
will also obtain O(LB/ Vn) convergence rate of the excess population risk. For eorexample, projected- GD is an algorithm that enjoys the aforementioned generalization bound.
3 Main Results
Theorem 3.1. Suppose D is distribution over Z = X V. Let f: Rd x - R be loss function of the form given in Eq. (6) such that for all y E y. e(, y) is convex and L-Lipschitz with respect to its first argument and such that for all x E X [1)((x)] 1. Then, for the gradient descent solution
in Eq. (3) and for any B E & we have:
E [F](W)]] min (n s ō nL'T vL
B² n/I
+ tn
S-D"
WEWB
Vn
In particular, setting ==00(((LTT) and T we get,
E [W s inf (w) + + L([ 2 S-Im
woRd
Vni
Thus, Theorem 3.1 shows that using GD, in the case of GLMs, we can learn the class W with sample complexity m(e) = Ó(1/²²) and number of iterations T = Ō(1/e²).
Note that, an improved rate of [[]]] /ll//n) can be obtained, if we choose n = ([Iw]I/(LV))) but this requires prior knowledge of the bounded domain radius. The bound we formulate above is for learning rate that is oblivious to the norm of the optimal choice w.
The key technical tool in proving Theorem 3. is the following structural result that characterizes the output of GD over the empirical risk, and may be of independent interest:
Theorem 3.2. Let S = (2i..... Zn3 be an ii.d sequence drawn from some unknown distribution D. Assume that f Rd x Z - R is convex and L-Lipschitz.funcie first argument. Then, given the distribution D there exists a sequence u1.....ur ur that depends on D (but independent of the sample S), such that, for any ö E (0, 1) with probability of at least 1 ö over S. the iterates of gradient descent, as depicted in Eq. (2), satisfy:
for all z Z, with respect to its
nLi Vn
VI E [7]
| u
vlog(T/6)+ + n/..vi
5

---

For example, we can set 17 (L/VVT and 7 = (n), then with probability O(1/n):
| u,Il O())
As such, for the natural choice learning rate and iteration complexity, we obtain that the iterates of GD remain at the vicinity of deterministic trajectory, predetermined by the distribution to be learned. Our following result shows that this bound is tight up to some logarithmic factor. We refer the reader the supplementary material for the full proof.
Theorem 3.3. Fix I.TT and n. For any sequence uI..... UT, independent of the sample S, there exists a convex and 1.-Lipschitz function f W Z - R and a distribution D over Yo, such that, with probability at least 1/20 over S, the iterates of gradient descent, as depicted in Eq. (2), satisfy:
Vr E [T]
I! u,ll 2 Ω
nLI VT
+ +nLVi
3.1 High Probability Rates
We next move discuss results for learnability with high probability. We first remark that using Markov's 's inequality and, standard techniques to boost the confidence, One can achieve high proability rates a logarithmic computational and sample cost in the confidence.
we want, though, to achieve high probability rates for the algorithm without alterations, the standard approach requires concentration bounds which normally rely on boundness of the predictor. This, unfortunately is not true when we run GD without projection, as the prediction can be potentially unbounded.
However, under natural structural assumptions that are often met for the types of losses we are usually interested in, achieve such boundness by clipping procedure which next describe.
For this section we consider a loss function (a, y). such that y [-b, b] and, we assume that:
((0yl.y) a a lyl. ((a.)) y) Z ((-bylyy) a -lyl.
and Va b-b (e(a. c.
(9)
Note that this is a very natural assumption to have in the case of convex surrogates for prediction tasks. For example, this holds for the widely used hinge loss E(a.y) max (0, 1- ya) in binary classification. Observe that under this assumption, we consider w - ((x) as a predictor of y, the learner has no incentive to return prediction that is outside of the interval [-b, b).
Thus, we define the following mapping g(a)
2 b, g(a) = a [-b,b], a -b.
(10)
and consider the clipped solution g(wS.. (xx)) where w the original output of GD defined in Eq. (3). We can now present our high probability result.
Theorem 3.4. Suppose D is distribution over % = x y and let WB = {w Rd -[wlll s B). Let ((a,y) v) be a generalized linear loss function of the form given in Eqs. (6) and (9) such that for all E Y, {(:,)) is convex and L-Lipschitz with respect to its first argument. Then, for the gradient descent solution in Eq. (3) and the function gaa) in Eq. (10) we have with probability at least 1 6
[w]l 7pT
1og(2/8)
E (x,y)-D G (b()))))))) s inf E [e(w- (p(x))()))))))))))))))))))))))))
+
weRd
(1.y)-D
0 L Vlog 4T/8)+
nL2VT
log(8/0)
+ nL2 + +
n
Vn
In particular, setting 7 = 1/(LVT) and T n we obtain that with probability 1- 8::
E (x.))- | ((((()))((x))))))) inf weWi
((x)))D [(w ((.),))
+
[+ log (/6)
vn

---

Comparison with ron-dissribution-depeeeee uniform convergence
In this section, contrast approach with what might be possible with non-distibutioo-ddeendenn uniform convergence. In particular, we consider an argument based on ensuring that the output of GD, with some stepsize 7j and number of iterations T, always (or with high probability) in a ball of radius B1n, 7) around the origin, namely, || s B(n. T). Hence, using Rademacher complexity bounds for GLMs, we can say that its population risk is within O VT) of its empirical risk. By selecting and T to be very small, one can always ensure that the output of GD is small ball, but we also need to balance that with the empirical suboptimality of the output. That is, traditional bounds require us to find and T that balance between the guarantee on the empirical suboptimality and the guarantee on the norm of the output. Such an approach would then result in population suboptimality that is governed by these two terms:
traditional,
I Vn
(n) inf sup max n. D.f
E SS-D"
[Fs(()))
min Fs(w)J, E
(11)
weW!
S-D"
where D and are taken over all valid distributions such that f convex and Lipschitz. In particular, we would get,
E S-Da
[FD("))
s min FD(w) O(G(n))
weW!
Claim 4.1. For GLMs it holds that G(n)= = O(L/n)
Proof. The upper bound follows by taking 1/(VV)) and 7' = vn, bounding the first term using the standard GD guarantee in Eq. (4), and the second term by noting that each step increases the gradient by at most nL. Therefore, || s nLT and we obtain,
Gnn) n nT
Vn
11/44
For the lower bound we consider two deterministic functions in one dimension. When nf nn/4/1 we consider the deterministic objective f(w;;z) :) L.w. Clearly, the norm of the solution || Σ nLr 2 nL/22, thus:
| L
L
11/4
When nT n//4//L we consider the objective f(w: /4 -nI(T 1)/((n Thus, the empirical risk is:
Similarly, we have that w
(T 1)
L
L
L 2Tn
L 11/
Fs(wS) min Fs(w) WEW!
2
Ω
2n
1/4
2n
The claim shows that uniform convergence fixed ball around the origin ensure learning, but with a suboptimal sample complexity of (1) To obtain better bounds using this approach, additional structural assumption the loss the distribution required. For example, the work of [34] assumes max-margin and smoothness(specificaal the logistic loss) to obtain bounds on the norm of the solution, while result applies to general Lipschitz GLMs without any distribution assumptions. It is insightful to directly contrast Eq. (11) to the approach of Section 3, which essentially entails looking at:
|| L
(n) = inf sup max n. D.
[T min Fs(w)]. E (S-D"
E
weW!
S-D"
Vn
for some deterministic u. We can then apply uniform concentration guarantee for ball around it, and so G is also sufficient to ensure:
E
[FD[S)]] s min Fn(w) +(G())
S-D"
wEW!
In Section we show that (() ((L/Vm), improving on G(n) and yielding optimal learning, up to logarithmic factors.
7

---

Technical Overview
Our main result, Theorem 3.1, establishes generalization bound for GD without projection, and it builds upon structural result presented in Theorem 3.2. We next, then, outline the derivation of both these results. Because the most interesting implication of our results are derived when we choose 7 = ((/VT) and O(z), we will focus here the exposition on this regime. This mainly to avoid clutter notation. Hence, unless stated otherwise we assume that 7' and are fixed appropriately.
Our proof of Theorem 3.1 relies on two steps, First, through Theorem 3.2 we argue that that output of GD will be (w.h.p) in a fixed ball that depends solely the distribution (but not on the sample). Then, as a second step, we can apply standard uniform convergence for bounded-norm balls (see Lemma 2.1) to reason about generalization.
The second step, builds on standard generalization bound that is derived through Rademacher com- plexity. Also notice, that the first step follows immediately from Theorem 3.2. Indeed, Theorem 3.2 argues that there exist a sequence uI,..., My such that w is the trajectory of GD over the empirical risk, we will have (w.h.p):
......,,y
|| urll 0(1).
The output GD is the averaged iterate, hence we obtain that indeed S restricted to ball around u = 7 Σ/= 44, as required. Therefore, we are left with proving our main structural result: That the iterates of GD are in proximity of a trajectory UI....,.T that depends solely on the distribution (i.e. Theorem 3.2).
For the end of proving Theorem 3.2, we introduce the following GD trajectory:
Gradient Descent on the population loss. We consider an alternative sequence of gradient descent that operates on the population loss FD (w) rather than the empirical risk Fs(w). The update rule is then.
wh = - -1)FFD(W?)
(12)
The sequence w....... wp will serve as the sequence (I.................... UT.
In the proof of Theorem 3.2 we require high probability rates. However, for the simplicity of the exposition, we will prove here slightly weaker, expectation, result: (the proof defered the supplementary material).
Lemma 5.1. Let S = (ZI...., In} be an i..dd sequence drawn from some unknown distribution D. Assume that f Rd % - R is convex and L-Lipschitz function, for all Z, with respect its first argument. Then, the iterates of gradient descent, as depicted in Eqs. (2) and (12), satisfy:
VI [T]
E [INg (w/]-wP1]] O S-D"
ntI
+ nLVI
This lemma bounds the distance, expectation, between the GD trajectory over the empirical risk and the GD trajectory over the population risk. Again, we remark that obtain the final result in Theorem 3.2, a stronger high probability version Lemma 5.1 is required. The proof of Theorem 3.2 follows similar lines that of Lemma 5.1 with modifications concerning specific concentration inequalities.
One crucial challenge in proving Lemma 5,1 stems from the adaptivity of the gradient sequence. In particular, notice that the sequences w². w. are governed, respectively, by the dynamics
w w -WFs( w/ = = nVFFDw?)).
At first glance, since (w) is an estimate of VFD(w), might seem that the result can be obtained by standard concentration bounds and application of a union bound along the trajectory. Unfortunately, such a naive argument cannot work. Indeed, since Wt. for 2 2, depends on sequence S, (W,(w,) is not necessarily unbiased estimate of (FD(w,) This is not just seemingly, and a construction [2] demonstrates how, even after only two iterates the gradient (Fs(w,) can diverge, significantly, from VFD (w,). While these constructions are outside of the scope of GLMs,

---

we remark that Theorem 3.2 holds for any convex and Lipschitz function. Also, it was in fact shown uniform
that even for GLMs [11]. the estimate of the gradients don't have any iimension-indepentee convergence bound, making it challenge pursue such proof direction. To summarize, we need to prove that the two sequences remain in the vicinity, even though, apriori, the update steps of the two functions may be different at each iteration.
Towards this goal, we follow an analysis, reminiscent of the uniform argument stability analysis of [5] for non-smooth convex losses. In a nutshell, both arguments compare the trajectory to reference trajectory, and bound the incremental difference between the two trajectories while exploiting monotonicity of the convex function. In the case of stability, the reference trajectory is the trajectory w induced by a sample 5' = 24.............................. Zn) that differ on a single example from the sample S (ZI, Ri..... Zn)
Bassily et al. showed that if and S' are two sequences that differ on a single example, then:
nT + nVT
|| w 0
In comparison, show:
n Vn + n
[llw w/l1]
S-D"
We note, that both results are optimal. Namely, the stability bound of [5] is the optimal stability rate, and the proximity bound provide is the best possible bound against fixed point, independent of the sample.
Note that both bounds yield 0(1) difference for the natural choice of and T. However, 0(1)- stability guarantees are vacuous in the sense that they not provide any interesting implication over the generalization of the algorithm. Whereas, we provide point, completely independent of the sample S. This does imply generalization in our setup.
guarantee to some fixed
One might also suggest that our result of ((1)-proximity can be derived from O()-staaility. How- ever, it turns this is not the case. For the same instance we use to lower bound the proximity by D(TT//m) in Theorem 3.3, it can be easily shown that GD will be O(nT -ttblle. Setting 1) = (1)) and T (n) will then imply 0(1) sttastibylyyyy but with Q(vn) (iyyn)pppxiiity This asserts that our result is not a direct consequence of standard stability arguments.
Acknowledgements RL received support from the Israeli Science Foundation (ISF) (grant no 2188/20) and from Google research scholar award. The work was funded in part by the Israel Council for Higher Education Data-Science Centers.
References
[1] Amir, Y. Carmon, T. Koren, and R. Livni. Never go full batch (in stochastic convex optimization). In Advances in Neural Information Processing Systems, 2021.
[2] I. Amir, T. Koren, and R. Livii. SGD generalizes better than GD (and regularization doesn't t help). In Conference Learning Theory, 2021.
[3] S. Arora, N. Cohen, W. Hu, and Y. Luo. Implicit regularization in deep matrix factorization. Advances in Neural Information Processing Systems, 32, 2019.
[4] L. Bartlett and Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. J. Mach. Learn. Res., 3:463 482, 2002.
[5] R. Bassily, V. Feldman, C. Guzmán, and K. Talwar. Stability of stochastic gradient descent on nonsmooth convex losses. In Advances in Neural Information Processing Systems, 2020.
[6] G. Blanc, N. Gupta, G. Valiant, and P. Valiant. Implicit regularization for deep neural networks driven by an ornstein-uhlenbeck like process. Conference on learning theory, pages 483-513. PMLR, 2020.

---

[7] S. Boucheron, G. Lugosi, and P. Massart. Concentration Inequalities A Nonasymptotic Theory of Independence. Oxford University Press, 2013. ISBN 978-0-19-953525-5. doi: 10. 11.003//hhmmtt1m0098819933333333 050/9780199535255. 001.
org/ 1093/
[8] L. Chizat and Bach. Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. In Conference Learning Theory, pages 1305-1338. PMLR, 2020.
[9] A. Dauber, M. Feder, T. Koren, and R. Livni. Can implicit bias explain generalization? stochastic convex optimization as a case study. In Advances in Neural Information Processing Systems, 2020.
[10] V. Feldman. Generalization of ERM in stochastic convex optimization: The dimension strikes back. In Advances in Neural Information Processing Systems, 2016.
[11] D. J. Foster, A. Sekhari, and K. Sridharan. Uniform convergence of gradients for non-convex learning and optimization. Advances in Neural Information Processing Systems, 31, 2018.
[12] Gunasekar, D. Lee, D. Soudry, and N. Srebro. Characterizing implicit bias in terms of optimization geometry. In G. Dy and A. Krause, editors, Proceedings of 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pages 1827-1836. PMLR, 2018. URL pprttee//proeeediggss waaiinngsmmm..... watissmmr..ppp. halr.prees//880
gunasekar18a http:///s.......ae///oooo/a/aaaa html.
[13] S. Gunasekar, J. D. Lee, N. Srebro, and D. Soudry. Implicit bias of gradient descent on linear convolutional networks. Advances in Neural Information Processing Systems, 2018.
[14] S. Gunasekar, B. Woodworth, S. Bhojanapalli, B. Neyshabur, and N. Srebro. Implicit regu- larization in matrix factorization. 2018 Information Theory and Applications Workshop, 2018.
[15] J. Z. HaoChen, C. Wei, J. Lee, and T. Ma. Shape matters: Understanding the implicit bias of the noise covariance. In Conference on Learning Theory, pages 2315-2357. PMLR, 2021.
[16] M. Hardt, B. Recht, and Y. Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International Conference Machine Learning, 2016.
[17] Zi and M. Telgarsky. The implicit bias of gradient descent on nonseparable data. In Conference on Learning Theory, 2019.
[18] Z. Ji, M. Dudík, R. H. Schapire, and M. Telgarsky. Gradient descent follows the regularization path for general losses. In Conference on Learning Theory, 2020.
[19] Z. Ji, M. Dudík, R. H. Schapire, and M. Telgarsky. Gradient descent follows the regularization path for general losses. In J. D. Abernethy and S. Agarwal, editors, Conference on Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event [Graz, Austria]. volume 125 Proceedings Machine Learning Research, pages 2109-2136. PMLR, 2020. Sechttp:/prroceedinng mlr. A....prees/v125 /t//jjj2000 jim0a.html.
[20] S. M. Kakade, K. Sridharan, and A. Tewari. On the complexity of linear prediction: Risk bounds, margin bounds, and regularization. In D. Koller, D. Schuurmans, Y. Ben- gio, and L. Bottou, editors, Advances in Neural Information Processing Systems 21, Pro- ceedings of the Twenty-Second Annual Conference on Neural Information Processing Sys- tems, Vancouver, British Columbia, Canada, December 8-11, 2008 pages 793-800, Cur- ran Associates, Inc., 2008. URL https: /ttp///eeocecc..////e///// www.sps.eeriicccooee cctppp//////0/////////// $b9999cc88055444433333rr
bentraatthtmll
[21] Y. Li, T. Ma, and H. Zhang. Algorithmic regularization in parrmmarameterize matrix sensing and neural networks with quadratic activations. In Conference On Learning Theory, pages 2-47. PMLR, 2018
[22] Y. Li, X. Fang, H. Xu, and T. Zhao. Implicit bias of gradient descent based adversarial training on separable data. In International Conference on Learning Representations, 2019.
10

---

[23] K. Lyu and J. Li. Gradient descent maximizes the margin of homogeneous neural networks. In International Conference on Learning Representations, 2019.
[24] E. Moroshko, B. E. Woodworth, S. Gunasekar, J. D. Lee, N. Srebro, and D. Soudry. Implicit bias in deep linear classification: Initialization scale vs training accuracy. Advances in neural information processing systems, 33:22182-22193, 2020.
[25] M. S. Nacson, S. Gunasekar, J. Lee, N. Srebro, and D. Soudry. Lexicographic and depth- sensitive margins in homogeneous and non-homogeneous deep models. In International Con- ference on Machine Learning, pages 4683 4692.. PMLR, 2019.
[26] V. Nagarajan and J. Z. Kolter. Uniform convergence may be unable to explain generalization in deep learning. Advances in Neural Information Processing Systems, 32, 2019.
[27] A. S. Nemirovski and D. B. Yudin. Problem complexity and method efficiency in optimization. 1983.
[28] B. Neyshabur, R. Tomioka, and N. Srebro. search of the real inductive bias: On the role of implicit regularization in deep learning. In International Conference Learning Representations (workshop track), 2015.
[29] S. Pesme, L. Pillaud-Vivien, and N. Flammarion. Implicit bias sgd for diagonal linear networks: provable benefit of stochasticity. Advances in Neural Information Processing Systems, 34, 2021.
[30] N. Razin, A. Maman, and Cohen. Implicit regularization in tensor factorization. In Interna- tional Conference on Machine Learning, pages
PMLR, 2021.
[31] A. Sekhari, K. Sridharan, and S. Kale, Sgd: The role of implicit regularization, batch-size and multiple-epochs. Advances in Neural Information Processing Systems, 34, 2021.
[32] S. Shalev-Shwartz and S. Ben- Understanding machine learning: From theory to algorithmss Cambridge University Press, 2014.
[33] Shalev-Shwartz, Shamir, Srebro, and K. Sridharan. Stochastic convex optimization. In Conference on Learning Theory, 2009.
[34] O. Shamir. Gradient methods never overfit on separable data. CoRR, abs/2007.0000 2020. URL htttp::/aaxxv..or/aab/////// 00028..
[35] D. Soudry, E. Hoffer, M. S. Nacson, S. Gunasekar, and N. Srebro. The implicit bias of gradient descent on separable data. The Journal of Machine Learning Research, 19(1):2822-288 2878, 2018.
[36] K. Sridharan, S. Shalev-Shwartz, and N. Srebro. Fast rates for regularized objectives. Advances Neural Information Processing Systems, 2008
[37] M. Telgarsky. Margins, shrinkage, and boosting. In International Conference on Machine Learning, pages 307-315, PMLR, 2013.
[38] T. Vaskevicius, V. Kanade, and P. Rebeschini. The statistical complexity of early- stopped mirror descent. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems 33: Annual Con- ference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6- 12, 2020, virtual, 2020. URL https: httt::://prrceedingss www.neeu.ucc.c.o ceepppps.cc/paper/22000 224d266996c11882cchh6666666666 -wter4-bbsttttttte
[39] B. Woodworth, S. Gunasekar. J. D. Lee, E. Moroshko, P. Savarese, I. Golan, D. Soudry, and N. Srebro. Kernel and rich regimes in overparametrized models. Conference on Learning Theory, pages 3635-3673. PMLR, 2020.

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'l rou're using/curating? [N/A]
(e) Did you discuss whether the data are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
12


Reviews:
[{"review_id": "fEuJ9onKR1I", "reviewer": "Reviewer_VfrU", "summary": "The paper studies the gradient descent for a stochastic convex optimization problem for a generalized linear model. With excess error at most $\\epsilon$, sample complexity and number of iterations of $\\tilde{O}(1/\\epsilon^{2})$ is needed in contrast to the general stochastic convex optimization, where $\\Omega(1/\\epsilon^{4})$ is needed.  ", "questions": "(1) In the abstract, and introduction, you mentioned ''early stopped'' gradient descent, but when you introduce your gradient descent algorithm in (2) and afterwards, it seems to me (I hope I didn't miss anything) that you never talk about ''early stopped'' again. Where did you use ''early stopped'' in your analysis?\n\n(2) In equation (3), should it be from $t=1$ to $T$?\n\n(3) In equation (11), what is the space you are taking supremum over for $D$ and $f$?\n\n(4) In line 478 in the supplementary material, it is better to use '','' instead of ''.'' to end the last equation and write ''where'' instead of ''Where'' here. Same can be said about line 495.\n\n(5) Cauchy-Schwartz should be Cauchy-Schwarz.\n\n(6) In the proof of Theorem 3.1, for the equation between line 494 and line 495, what do you mean by $P(w\\notin\\mathcal{W}_{u}^{K})$? The previous term involves taking sup over $w$, but here, it is for some arbitrary $w$? Also in the same line, what do you mean by $\\sup_{S}$? What is the space of the supremum taken over? Can you explain in more detail how do you get the next inequality?\n\n(7) Line 509. In the statement of Theorem, instead of ''Boucheron, Lugosi and Massart 7'' write ''Boucheron, Lugosi and Massart [7]''.\n\n(8) In line 522, I am confused with the notation $u=\\frac{1}{T}\\sum_{t=1}^{T}u_{t}$. In the equation between line 262 and 263, you had $\\bar{u}$. So both $u$ and $\\bar{u}$ denote average?\n\n(9) In line 528, can you provide a reference to McDiarmid or perhaps even state what it is?\n\n(10) In line 531, line 538, what is ''union bound''? \n\n(11) In line 533, ''set $w^{\\ast}$'', do you mean ''set $w^{\\star}$''? \n\n(12) In line 545, maybe you can define Rademacher random variables for the convenience of the readers.\n\n(13) In line 578, ''with the same probability'', I just want to know whether this is indeed with the same probability, or with at least the same probability?\n\n(14) In line 600, what is ''reverse triangle inequality''? I know what triangle inequality is, but I am not familiar with reverse triangle inequality. Plus in the second line below, you wrote (triangle inequality) instead of (reverse triangle inequality).", "limitations": "It seems the author(s) did not include a discussions on the limitations and potential negative societal impact of their work.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The logic and contributions of the paper are clear. To the best of my knowledge, the results are novel. \n\nIn terms of weakness, I think although the results are new, they are not that surprising because one knows that there is dimension-independent uniform convergence bounds for generalized linear models and it is reasonable to expect that sample complexity and number of iterations for a stochastic convex optimization problem for a generalized linear model will be better than the general stochastic convex optimization. In addition, I think the presentations can be improved here and there, and some points can be made more clear which I will detail in the questions below.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "OjJuowjO_1X", "reviewer": "Reviewer_JR1r", "summary": "This paper shows that gradient descent with early stopping in the context of Generalized Linear models has an optimal sample and iteration complexity.", "questions": "1. Some emphasis is put on the fact that this work is dealing with Gradient descent without projection, but the generalization guarantees are obtained with respect to the best classifier in a constrained ball $\\mathcal{W}^B$. (see, for instance, Theorem 3.1). (in comparison, [2] uses projections).\n\n2. In the same vein, I am a bit confused with some statements that compare the output of GD (unconstrained) and the solution of the constrained problem. For instance in (4) if we assume that the optimum is at $w=0$ and we take $B=\\eta \\approx 0$, we get that $F_S(\\bar w^S) \\leq \\min_w F_S(w)$ which is not possible if we initialize at $w_0 \\neq 0$ because we would have $\\bar w^S \\approx w_0$ and thus  $F_S(\\bar w^S) \\gg \\min_w F_S(w)$. Can you comment on that and/or provide a precise citation/proof for equation (4)? I read [17] and the closest statement to (4) in [17] is Theorem 3.1 about online gradient descent where there is a projection step for the iterates. If we considered GD with projection, it would not be a problem since one projection step would bring us to the optimum. It seems to me that usually, in the proof of (4) the quantity $\\|x^* - x^t\\|$ appears and is upper bounded by $2B$ because $x^*$ and $x^t$ **belong to the constraint set.** \n3. By reading the statement of Theorem 3.1, I was not 100% sure how you would go from the constrained to the penalized formulation. I got it by reading the proof of Thm 3.4. You use the fact that the constrained statement is valid for any $B$. Thus it is critical to make sure that (4) is valid and precise that the first statement of Theorem 3.1 is valid for any $B$.\n\n4. In any case,  you could also assume that the optimum is achieved and use the fact that $$F_S(\\bar w^S) \\leq \\min_{w \\in \\mathbf{R}^d} F_s(w) + \\eta L^2 + \\frac{\\|w^*-w_0\\|^2}{\\eta T}$$ \n ? Another alternative for (4) to be true would be to use $\\mathcal{W}^B$ with $B$, and $u$ picked such that we know that $\\bar w^S$ belongs to $\\mathcal{W}^B$, but you would not get the penalized version of the result. \n\n\nOverall, I may change my grade depending on the answers to these questions. (mainly question 2.) Precisely, I am currently leaving them the benefit of the doubt, but if the statement in Eq.4 is not clarified, I may decrease my score to 4. On the other hand, if all my questions are correctly addressed, I may increase my score to 7.\n", "limitations": "The iteration complexity is maybe optimal, but the oracle complexity is n * iteration complexity which is $ O(1/\\epsilon^4)$. So still worse than SGD. It is briefly addressed by the authors.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I am not an expert in the specific field of this paper, so it is hard for me to assess if this paper is not missing some important related work. However, to the extent of my knowledge, it seems that this paper is not missing any critical related work. \n\n1. (Pro and con) On the one hand, the result seems new and interesting as it contrasts previous results on generalization of GD and SGD with early stopping. On the other hand, it seems that SGD is superior to GD even in that setting (since an iteration is significantly cheaper for SGD.) Thus we may consider that this result is not groundbreaking.  However, I still think this paper is in the interest of the community (assuming that its results are correct)\n\n2. (Pro) The core of the technical contribution (Thm 3.1) is very well explained. \n\n3. (Con) I found the exposition of some of the results not 100% clear. I have some serious doubts about some results mentioned in this paper (mainly equation (4) and its consequences). I am hopeful that the authors can clarify this during the rebuttal. (see my questions) \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "9OAIZwV5wOF", "reviewer": "Reviewer_csuM", "summary": "The authors study the problem of excess risk minimization of convex Lipschitz Generalized Linear Models (GLMs) over euclidean norm balls.\n\nThey consider the classical setting of minimization of the empirical risk as a surrogate for the excess risk.\nThey consider the Gradient Descent (GD) algorithm to optimize the empirical risk, except they _do not_ rely on projections and simply run plain GD.\n\nUsing the uniform convergence of GLMs, the authors show that plain GD with early stopping outputs an $\\epsilon$-accurate solution (compared to the best solution contained in a euclidean norm ball) in $O(1/\\epsilon^2)$ iterations with $O(1/\\epsilon^2)$ samples.\n\nThis contrasts with the performance of GD under the more general setting (i.e. non-GLM) where the complexity is $O(1/\\epsilon^4)$.\n\nFinally, the authors show through a lower bound and matching upper bound a non-distribution-dependent convergence is possible for GD without projections, but the resulting is then $O(1/\\epsilon^4)$.\n\n ", "questions": "Apart from the above questions, here are some more minor remarks:\n\n* I did not fully understand the last part of the sentence line 126.\n* In the second equation of Theorem 3.1, I believe $\\norm{w}^2$ should be $B^2$\n* Supplemental material, equation after line 503: the $c>0$ is refered to as $t$ and then $c$.\n* Supplemental material, to apply Theorem line 509 to the current problem, I believe $c_i= 4L$, while the authors use $c_i = L$. This has no major impacts, but it changes the constants in the rest of the proof and in the theorem statement.\n* Equation 10: $g(a) = ...$\n* line 284: \"the\" -> \"that\"\n", "limitations": "NA", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strength\n\nThe paper is well-written and easy to follow. \nThe problem at hand is well described, and even though I am not an expert in the field, the related work section seems complete.\nThe proofs are kept simple and arguments follow each other nicely.\n\nI particularly appreciate part 5 which gives an overview of the main arguments of the proofs, and make diving in the proofs easier.\n\n# Weaknesses\nI am wondering about the relevance of the result. \nNamely, as the authors mention, rates of $O(1/\\epsilon^2)$ are already known for SGD, and SGD is the go-to method in practice as iterations are much cheaper than GD.\nSo is the main contribution that GD reaches that rate without projections ? or is it the distribution dependent uniform convergence argument ? or a mix of both ? I know the authors discuss this at the end of the introduction, but it would be great if they could clarify.\n\nAlso, the authors often refer to the notion of stability, especially at the end of section 5, but I believe that they never actually define it. Could the authors clarify this ?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept