The Sample Complexity of Gradient Descent in Stochastic Convex Optimization
Authors: Roi Livni
Venue: NeurIPS 2024 poster (2024)
Keywords: Stochastic Convex Optimization
Learning Theory
Primary area: learning_theory
TL;DR: We analyze the sample complexity of full-batch vanilla gradient descent on a stochastic convex problem

Abstract: We analyze the sample complexity of full-batch Gradient Descent (GD) in the setup of non-smooth Stochastic Convex Optimization. We show that the generalization error of GD, with common choice of hyper-parameters, can be $\tilde \Theta(d/m+1/\sqrt{m})$, where d is the dimension and m is the sample size. This matches the sample complexity of \emph{worst-case} empirical risk minimizers. That means that, in contrast with other algorithms, GD has no advantage over naive ERMs. Our bound follows from a new generalization bound that depends on both the dimension as well as the learning rate and number of iterations. Our bound also shows that, for general hyper-parameters, when the dimension is strictly larger than number of samples, $T=\Omega(1/\epsilon^4)$ iterations are necessary to avoid overfitting. This resolves an open problem by Schlisserman et al.23 and Amir er Al.21, and improves over previous lower bounds that demonstrated that the sample size must be at least square root of the dimension.

The Sample Complexity of Gradient Descent in Stochastic Convex Optimization
Roi Livni
School of Electrical Engineering
Tel Aviv University rli rlivni@tauex. aau.ac... i1l
Abstract
We analyze the sample complexity of full-batch Gradient Descent (GD) in the setup non-smooth Stochastic Convex Optimization. We show that the generalization error of GD, with common choice of where d is the dimension and m is the sample size. This matches the sample complexity of worst-case empirical risk minimizers. That means that, in contrast with other algorithms, GD has no advantage over naive ERMs. Our bound follows from a generalization bound that depends both the dimension well the learning rate and number of iterations. Our bound also shows that, for general hyper-parameete
be é(d/m 1/ Vm),
when the dimension is strictly larger than number of samples, T = Q I/E*) iterations are necessary to avoid overfitting. This resolves an open problem by Amir, Koren, and Livni B, Schliserman, Sherman, and Koren [20], and improves over previous lower bounds that demonstrated that the sample size must be at least square root of the dimension.
Introduction
Stochastic Convex Optimization (SCO) a theoretical model that depicts learner that minimizes a (Lipschitz) convex function, given finite noisy observations of the objective (22). While often considered simplistic, in recent years SCO has become a focus theoretical research, partly, because of its importance to the study of first-order optimization methods. But, also, it has become focus of study because is one of few theoretical settings that exhibit overparameterized learning. In more detail, classical learning theory often focuses on the tension between number of samples, or training data, and the complexity of the model to be learnt. A common wisdom classical theories [17 (24 is that, to avoid overfitting, the complexity of model should be adjusted in proportion to the amount training data. However, recent advances Machine Learning have challenged this viewpoint. Evidently [18 255, state-of-the-art algorithms generalize well but without, explicitly, controlling the capacity of the model to be learnt. In turn, today, it is one of the most emerging challenges, for learning theory, to understand learnability when the number of parameters in learnt model exceeds the number examples, and when, seemingly, nothing withholds the algorithm from overfitting.
Towards this, we look SCO. In SCO, Shalev-Shwartz, Shamir, Srebro, and Sridharan showed how algorithms can overfit with dimension dependent sample size. But, at the same time, it was known 26 that there are algorithms that provably avoid overfitting with fewer examples than dimensions. As such, SCO became a canonical model to study how a well-designed algorithm can avoid overfitting even when the number of examples too small guarantee generalization by an poorithmii-indepeneeee argument (245 II 12 16 22 A step towards understanding what induces generalization is to identify which algorithms generalize. Then, we can ask what yields the separation. Surprisingly, for many well-studied algorithms this question is not always answered.
38th Conference on Neural Information Processing Systems (NeurIPS 2024).

---

Perhaps the simplest algorithm, whose sample complexity is not yet understood, is Gradient Descent (GD). And we turn to the basic question of the sample complexity of gradient descent.
While this question remained open, there have been several advancements and intermediate answers: The first, dimension independent, generalization bound was given by Bassily, Feldman, Guzmán, and Talwar [6] that provided stability bounds [8]. The result of Bassily et al. demonstrated that, sample complexity rate. However,
GD can have flimeniion-independee to use non-standard choice of hyperparameters which affects the efficiency of the algorithm. In particular, the number of rounds becomes quadratic in the size of the sample (as opposed linear, with standard choice). On the other hand, classical covering argument shows that linear dependence in the dimension is the worst possible, for any empirical risk minimizer, irrespective of properties such as stability.
achieve that, one has
In terms of lower bounds, Amir, Koren, and Livni 3 were the first to show that GD may have dimension dependence in the sample complexity. They showed that, with natural hyperparameters, the algorithm must observe number of samples that is at least logarithmic in the dimension. This result was recently improved by Schliserman, Sherman, and Koren (20) that showed that at least square root of the dimension is required. Taken together, so far it was shown that either the algorithm's 's hyperparameters are tuned to achieve stability, at a cost in running time, or the algorithm must suffer some dimension dependence, linear at worst square root at best.
Here, we close the gap and show that linear dependence necessary. Informally, we provide the following generalization error bound, in terms of dimension d, sample size, m, and hyperparameters of the algorithm, and 7' (the learning rate and number of iterations). We show that when 7' is at most cubic in the dimension (see Theorem T for formal statement):
( min 1TvT.1/) m
d
Generalization gap of GD = Q min
The first factor in the RHS describes the linear dependence of the generalization error in the dimension, and corresponds the optimal sample complexity of empirical risk minimizers, as demonstrated by Carmon, Livni, and Ychudayoff [ The second term lower bounds the stability of the algorithm
( and played similar role in previous bounds 3 20 Each factor is optimal at a certain regime,
and cannot be improved. Most importantly, for a standard choice of 1 = O(1/ 1/VT)), the first term is dominant, and the aformentioned lower bound is complemented with the upper bound of Carmon et al. 11. Our result implies, then, a sample complexity of @(d/m m + 1/ vm). When 2 m, the second factor is dominant. When running time is at most quadratic in number of examples, this term also governs the stability of the algorithm, hence the result of Bassily et al. [6] provides a complementary upper bound (see further discussion in Section 3.1).
2 Background
We consider the standard setup of Stochastic Convex Optimization (SCO) in (22]. Set W (w |]w|]| S 1}, and let 2 be an arbitrary, finite domain (our main result is a lower bound, hence finiteness of Z is without loss of generality). We assume that there exists a function f(w 2) that is convex and L-Lipschitz in w E W for every choice of & E 2. Recall that a function f is convex and L-Lipschitz for any w1, W2 E W and 0 s À S 1:
f(Aw1 + (1 A) S Af(w)) + (1 f)2())), and, If(w)) f(w2) Z|[w; wall- (1)
First order optimization Algorithmically we require further assumptions concerning any interaction with the function to be optimized. Recall [9 that, for fixed 2, the sub-gradient set of f(w, z) at point w is the set:
0 0f(w.)) z) = [8: f(w',z) 2 (ww.z) gg T(w'(wwww"- w), Ww. E W].
A first order oracle for f is a mapping (w) such that (w) E (f( 2). Our underlying assumption that a learner has a first order oracle access. In other words, given function f(w, z), we will assume that there is procedure O2 that calculates and returns subgradient at every for every Recall 10 [9] that when |ā fw., 2) = 1, the function differentiable, at w, and in that case, the unique subdifferential is the gradient vf(w,))
2

---

Learning
learning algorithm A, SCO, is any algorithm that receives input a sample (21, (21....5 ................................ , 2 of m examples, and ouiputs parameter ws. An underlying assumption in learning is that there exists a distribution D, unknown to the learner A, and that the sample S is drawn i.i.d from D. The goal of the learner is to minimize the population loss:
F(w) = E (w..z))). z-D
More concretely, We will say that the learner has sample complexity me) if, assuming |S] m(e), then w.p. 1/2 (Again, because we mostly care about lower bounds, fixing the confidence will not affect the generality of our result):
F(ws) min F(w) weW
Empirical Risk Minimization A natural approach to perform learning is by Empirical Risk Minimization (ERM). Given a sample S, the empirical risk defined to be:
Fs(w)
f(w,2).
[S]
An E-ERM is any algorithm that, given sample S, returns solution ws W that minimizes the empirical risk up to additive error & > O. Recently, Carmon et al. showed that any E-ERM algorithm has sample complexity bound of
d 0
m(E) Ō
(3)
E2
The above rate is optimal up to logarithmic factor [2] Namely, there exists construction and
an ERM that will fail, w.p. 1/2, unless m ((d/E) examples are provided"] Importantly, though, there are algorithms that can Iearn with much smaller sample complexity. In particular SGD [26].
stable-GI (6) and regularized ERMs g
Gradient Descent
We next depict Gradient Descent whose sample complexity is the focus of this work. GD depends on hyperparameters 7 E N and 17 2 0 and operates as follows the empirical risk. The algorithm receives as input a sample to the following recursion:
defines Wo = O, and operates for T iterations according
[S] Σ O=(w:)
GD Ws
Wy
W7-1
Wt.
where II is the projection onto the unit ball, and (w,,) subgradient of the loss function f(w, z) at wy. The final output, WGD of the algorithm is the averaged iterate (our result, though, can be
generalized to other possible -uefix-averages such as, say, outputting the last iterate, see Theorem TO). GD constitutes e-ERM. Concretely, it is known 100 17] that GD minimizes the empirical risk and its optimization error given by:
(s(WGD) min (w( min 17 weW
(5)
7/7
The above bound is tight irrespective of the dimensior The population loss have also been studied, and Bassily et al. [6] demonstrated the following learning guarantee:
E F(NgD)- min F(w) o nvT 7p S-D
(6)
11 m
The last two terms in the RHS follow from a stability argument, provided (6, and the first term follows from the optimization еттог of GD as depicted in Eq. (5). Notice that there is always an (nVVT) gap between the generalization error and empirical error of gradient descent.
tte 221/E22 sample complexity bound is more straightforward and follows from standard information-
theoretic arguments
FFrr completeness, demonstrate the lower bound for = Appendix B

---

3 Main Result
Theorem 1. For every d Z 4096, 2 10, 2 and dj > O, there exists a distribution D, and a 4-Lipschitz convex function f(w, 2) in Rd+1, such that for any first order oracle of f(w, 2), with probability 1/2, if we run GD with as a learning rale then:
(D)
min F(w) 2 2. 272 16
min
1032m 1/ min [
WEW
We remark, that the above theorem is for any suffix averaging (e.g. last iterate), and not restricted to the averaged iterate (see Theorem TO). We now specialize our bound for two interesting regimes. First, improve previous dependence the dimension in 20 and obtain generalization error bound for d (2mm+ + +T'13):
Corollary 2. Fix 7,, and suppose S (m + 7).3). There exists distribution D, and 0(1) Lipschitz convex function f(w. in Rd, such that for any first order oracle [(w, z), with probability 1/2, if we run GD for T iterations, then:
F(wSD)
min F(w) 2 Q min nTT wEW
nT 1
The first follows from Theorem [ the second term follows from the optimization error in Eq. (5) Equation 7 does not hold for m, and the linear improvement over 22 20 is tight. This can be seen from Eq. (5) that shows that GD achieves e empirical excess error when 1j ı ((1/VT) and T (1))))) Equation ( becomes vacuous for such choice of parameters, but Carmon et al. showed that the sample complexity of any ERM is bounded by Ó((d+ /m)/m). However, as depicted next, this upper bound becomes tight and GD does not improve over worst-case ERM:
Corollary 3. Suppose T Om, and n @(1/VT). There exists a distribution D, and an O11)-Lipschitz convex function f(w, 2) in IRd", such for any first order oracle of f, with probability 1/2, if we run GD with for T iterations:
F(w GD min F(w) 2 Q weW
1/minn min
d m
vm
Corollary complements Carmon et al. 11 upper bound, and improves over Feldman 12 lower bound that only showed existence of some ERM with the aforementioned sample complexity. To see that Corollary follows from Theorem notice that when d x vm, then d/m < 1/ Vm and the bound dominated by the second term, which is well known-information theoretic lower bound for learning. When d > Vm, and T m m.5 have that T s d², plugging 1) O(1 (1/VT) yields the bound.
3.1 Discussion
Theorem I provides a new generalization error bound for GD. It shows that the worst case sample complexity for ERMs, derived by Feldman [12], is in fact applicable also very natural first order algorithm and not just to abstract ERMs. This Highlights the importance of choosing the right algorithm for learning in SCO. As discussed, the bound tight several regimes, nevertheless still there are unresolved open problems.
Stability in low dimension When GD is treated as a naive empirical risk minimizer, and 0(1/VT), (m), there is no improvement, when using GD, over worst-case ERM. In the other direction, for dimension that is linear in m, one cannot improve over the Q(πVT) term that governs stability. Our bound, though, provide hope that stability low dimension can yield an improved bound. In particular, consider the case where 7 = 1/7 and d < m. This case where we apply stable algorithm in small dimensions. Our bound does not negate the possibility of an improved generalization bound. That would mean that, at least some regime, GD can improve over the worst-case ERM behaviour. We leave open problem for future study

---

Open Question 4. Is there a generalization bound GD such that
dnvT
E
F(ws
(D
min F(w) =0 weW
S-Dm
m
Vm
Alternatively, can we prove an improved generalization error bound such that:
nVV, 1))
E S-Dm
F(wS
min F(w) = = min wEW
Late stopping Another regime where there is gap between known upper bound and lower bound appears when 7 Qmm²). Specifically, the stability upper bound for GD by Bassily et al. [6] gives
min F(w) = o 0001110 weW
+ n7 + n/T
E S-
F(wS
By Corollary 2 for large enough dimension:
E S-Dm
F(w
min F(w) min VT n/T
weW
When 7 = Om²). the two bounds coincide. Indeed, for the n/ /m term to dominate the 17y'T term, must have 7 (2m²)). One has to take at least T O0m²) iterations in order to generalize with GD (in fact, any full batch method [2]). however T = 0(m²) iterations are sufficient. Nevertheless, the above gap does yield the possibility of unstable GD method that does generalize. Particularly, if we just regulate the term nTT, but allow nIT /m 2211, then this may yield a regime where GD is unstable (and ERM bounds do not apply) and yet generalize.
Open Question 5. Are there choices n and (that depend on m) such that nI nT/mm E Q(1), but GD has dimension indpendent sample complexity?
Notice that the rjf'/m / term also governs stability in the smooth convex optimization setup 13 Recall that function f(w,z) 2) is said to be ß-smooth if for all z, f(w, z) is differentiable, and the gradient is an B-Lipschitz mapping [00 15 For smooth optimization, even if VTV = -((1, GD is still stable. Hardt, Recht, and Singer [3 showed that the stability of GD the smooth case is governed by
for 77 1/p. Therefore, the question of generalization when n/T /m 22(1 remains open, even under smoothness assumptions:
qf
Open Question 6. Assume that f(w, z) is @(I)-mmooth, What is the sample complexity of GD, when n and are chosen so that 1) + पा = o(1,, , but yf
2(1).
m
Technical Overview
We next provide a high level overview of our proof technique. For simplicity of exposition we begin with the case T = m We begin by a brief overview of previous construction by Amir al. B that demonstrated Corollary 2 when m 2(log d). The construction in 3 can be decomposed into three terms:
f(w, z) = g(w, Na(w) hww,2) z).
The function g has the property that an ERM may fail learn, unless dimension dependent sample size is considered. Amir et al. 3 incorporated Shaley-Shwarde et al. [22 construction. Later, (20 used Feldman's s function 12 to construct g. The shift from the construction depicted in Shalev-Shwartz et al. [22 to Feldman's ' function is the first step that allows to move from logarithmic to polynomial dependence the dimension. In both constructions an underlying property of g is that there exists a distribution D such that, for small samples, there are overfitting minima. Concretely, there exists ws (0, 1/dd such that
Σ g(ws, (s(ws, = 2(1).
(8)
S
z-D
The challenge is then, to make gradient descent's trajectory move towards the point ws. The idea can be decomposed into two parts:
5

---

Simplifying with an adversarial subgradient:
To simplify the problem, let us first ease the challenge and suppose we can choose our subgradient oracle in a way that depends on the observed sample. Let No be the Nemirovski function [
No(w) = max(--w(),0)
Notice that No is not differentiable and the choice of subgradient at certain points is not apriori determined. For example, notice that every standard basis vector -e, E (N)( More generally, given a sample S, let I = ....., id be exactly the set of indices such that ws, from Eq. (8) (i(() Now assume by induction that w, (i) 0 exactly for i i.....4, then one can show that we can define the subgradient oracle of No:
Oww,) = - E @No)
In that case Wr+1 will satisfy our assumption for ir+1 and we can continue to follow this dynamic for steps.
Notice that, in this case, GD will converge to ws (i 1/ which we assume now for conereteness). One can also show that the output of GD (the averaged iterate) will overfit. The caveat is that our subgradient oracle depends on the sample S. In reality, the sample is drawn independent of the subgradient oracle. and all previous constructions, as well as ours need handle this. This is discussed in the next section. But before that, let us review another challenge which is when 7 # d:
When d < T Another challenge we face with the construction above is that it works when we assume that T = d. That is because, in Nemirovski's 's function, the number of iterates can perform is bounded by the dimension. After iterations T = w(d) then n = vα), and the dynamic will end up with a too small norm vector to induce a sizeable population loss. This strategy will provide, at best, with factor of the form a (n.) Such a factor may be unsatisfactory a very natural setting where, say, T == ((), (m) and d 22( Vm). To obtain the d dependence, we perform the following alternation over the Nemirovski function. Consider the function:
will end up with the vector
Σ nei,
N(w) = max [0, max((w())), max (()))
isjsd
And suppose that at each iteration we return subgradient as follows:
If there is z d, such that w(1) = w(i+ 1) > 7), return subgradient e:+1 -e; e; and w updated by W/+1 = w, 7]0++1 + ne;
If there is no such i, then take the minimal i (if exists) such that (() 0, and return subgradient -e; and update Ws+1 = w, + me;-
When non of the above met, return subgradient
The dynamic of the above scheme is depicted in Fig. | and solves the problem when T d3, One can show that GD will run for at least d' = T iterations, and will increase (d)) coordinates, each, on average, by an order of 0 (nj). This is better than the increase r) each coordinate that we get from Nemirovski's s function. this way we obtain the improved result ryVT, even when d².
When 7 & d, when the number of iterations is smaller than d we face different challenge. The immediate solution is to embed in Rd construction from RT, this will provide us with the ()(vTT) term but, on the other hand, such a construction will not yield Q(d/m (d/m) term. A differentt approach, that exploits the dimension to its fullest, is consider blocks of coordinates and operate on those instead of single coordinates.
The conclusive outcome incorporates both ideas together, and replace the Nemirovski function with version of Eq. (9) that operates on (T33/3 blocks of coordinates. And this concludes our construction. We next move on the challenge of replacing the data dependent oracle with standard first order oracle.

---

Figure 1: Depiction of the dynamics induced by Eq. (16) and our choice sub-differentials
Reduction to sample dependent oracle:
As discussed, the construction above does not yield a lower bound it relies subgradient oracle that is dependent on the whole sample. To avoid such dependence of the oracle on the sample, we observe that if we infer the sample S from the trajectory, i.c. if the state w, "encodes" the sample, then formally the subgradient is allowed to "decipher" the sample from the point w,. In that way achieve this behaviour of sample dependent subgradient oracle. This part becomes challenging and may depend on the way we choose 8, and N. The simplest case, studied by Amir et al. (}] introduced the third function, ht which was small perturbation function that elevates coordinates in and inhibits coordinates not in I. The function h depends on z and not on S, hence it cannot know apriori I. But, important observation is that, in Shalev-Shwartz there exists E S that "certifies" that. In fact, each z can be thought of as a subset of indices, and an index appears z, then it cannot be in So we can build the perturbation in way that every coordinate is elevated, unless certifies E I: In that case we define h(w, z) so that its gradient will radically inhibit
al. [22] construction, if
The last observation is what becomes challenging in our case. As discussed, to achieve improved rate, need use Feldman's 's function. When using Feldman's 's function the coordinates cannot be ruled out, or identified, by single but one has to look at the whole sample to identify /. While Schliserman al. (20) tackle similar problem,
take slightly different approach described next: For each z assign a random, positive, number a(z). We can think of this a as a hash function. Let us add another coordinate to the vector w, ((d + 1). Consider the function
h(w, 2) = ya(z) w(d + 1).
Then dh(w, = ya(z)e Write a(S) 1ST Eges (z)) then in turn:
Σ -1-- ZES
[|
[S]
y, a<2) are chosen correctly, (SS) is one one mapping from samples real numbers, and small ensures that the overall addition of / has negligible affect on the outcome. Then, we may define the subgradient oracle to be dependent on coordinate + which encodes the whole sample. Our final construction will take different ht which adds small strong convexity in this coordinate, for reasons next explained:
Working with any first order oracle Notice that our statement is slightly stronger than what we so far illustrated. Theorem states that, for any subgradient oracle, GD will fail. For that, we need to be little bit more careful, and we want to replace function with function that leads to the

---

same guaranteed trajectory, but at the same time it should be differentiable at visited points. This will ensure a unique derivative, making the construction independent of the choice of (sub)gradient oracle.
Towards this goal, we start with the construction depicted so far and consider the set of all values, gradients, and points (fi- 8j- wj]jes that our algorithm may visit, for any possible time step and any possible sample, with our construction. Notice that, while this set may be big and even exponential, nevertheless finite. What we want is to interpolate a new function through these triplets. In contrast with our original construction, we require a differentiable function at the designated points. Notice, that such an interpolation will have the exact same behaviour when implementing GD on it (with the added feature that the oracle is well defined and unique).
The problem of convex interpolation is well studied, for example Taylor al. 23 shows sufficient and necessary conditions for interpolation of a smooth function. Our case is slightly easier as we do not about the smoothness parameter. On the other hand do require I. Lipschitzness of the interpolation. We therefore provide an elementary. self-contained, proof to the following easy to prove Lemma, (proof is provided in Appendix B)
Lemma 7. Let G = 8). 8,. wyrjes & R x IR x Rd be triplet of values in R,, and gradients and points in Rd, such that ||g s L. Suppose that for every i. E J:
fj + 83 (wi (w)-
(10)
and let
lag = (i: 5 8 (w, w 8i =
Then there exists convex --Lipschitzuuncttii ff such that for all j J: f(wj) = fj. and for all i Lag, f is differentiable at wi and:
f((w)) gt
With Lemma 7 at hand, consider the function
h( 2) ( 1))² a<z)) w(d+1)
The above function encodes in w(d+ 1) the sample and time-step as before. Morcover, because is slightly strongly convex (in coordinate d + 1), wi(d= + 1) # w2(d+ 1) ensures that
A( ((Ww.2) 2) > h(w2,2) + Vh(w2, 2) (wi w2).
Then the term in ff ensures that the triples {ff.gj. w along the trajectory generate gradient vectors that satisfy strict inequality Eq. (10) and in turn, our interpolation from Lemma 7 will be differentiable these points. There's some technical subtlety because the interpolation needs to also take the averaged iterate into account, but this is handled in a similar fashion.
In the next two sections we provide more formal statements of the two main ingredients: First, we define a setup of optimization with a sample-dependen first order Oracle and state lower bound for the generalization error in this setup. The second ingredient is reduction from the standard setup of first order optimization.
4.1 Sample-dependent Oracle
As discussed, the first step in our proof is to consider slightly weaker setup where the first-order oracle may depend on the whole sample. Let formally define what we mean by that. Define
S (S (S)..... S,).Sp U ?"" T),
the set of all subseqences of samples of size at most Given function f(w, z), sample dependent oracle, Og, a finite sequence of first order oracles
Os (0 (S: w. 2w
that each receive as input finite sample S, well w and returns subgradient:
(S.... E (f.
8

---

The sequence of samples can be thought of as the past samples that were observed by the algorithm. In the case of full-hatch GD these will be the whole sample, and for SGD,, each provided to o will be all previously observed samples. Given S E 8n let us also denote
o (S. w)
1
w, W..- E ZES,
Σ
Σ f(w.z) ZES,
(11)
SS
where we let 81.0 0, and Sta-1 = (S,,..., is the concatenated subsample of all previously observed samples the sequence. As discussed, working with a sample-dependent oracle is easier (for lower bounds). And indeed, our first result shows that, if the subgradient can be chosen in way that depends on the sample, we can provide the desired lower bound. For fixed and known 1j > 0, T, sample dependent first order oracle Os, and sequence of samples S S2..... Sy), Wo = and inductively:
define
w² W no (S, ".,. w
and for every suffix < T:
GD w S.s
W1
(12)
S
THs+!
Lemma 8. For every d,T 2 18 and n > 0 there are distribution D, 3-Lipschitz convex function f(w.2) in Rd, as well as a sample dependent first order oracle Og such that: if = (S. S) S for S ~ D Lid, then w.p. 1/2, for every suffix averaging S:
d.1))
GDW - F(0) 2 F(WS5)
min
1032m
min
V2. 272 162
The proof of Lemma 8 is provided in Appendix A.1 of our proof.
We next move to describe the second ingredient
4.2 Reduction to sample-dependent oracles
As discussed, the second ingredient of our proof is a reduction to the sample-dependent setup. Instead of using perturbation function as in 3 we take more black box approach and show that, given sample dependent first order oracle, there exists a function that basically induces the same trajectory. Proof provided in Appendix(A..
Lemma 9. Suppose q R., 119 S 1. And suppose that f(w z) is convex, L-Lipschitz, function over w E RRd let 17 > O, let Og be a sample dependent first order oracle, and for every sequence of sampley S = S2,, ST) define the sequence (WS) as in Eq. 12
Then, for every depends on q, f.T. 7, m, Og, E).
there exists an L ++1 1 Lipschitz convex function o f((w,x), z) over Rd+l (that
such that for any first order oracle for f. define uo = = Rd and x 0 E R2 and:
(u,,x; (11-1,x)-1)
(,((,,,;;))
S S
then if we define:
Σ q()x, and w Σ g()
My q()),,, and,
X4 =
then, we have that Ug w and:
(((()))))),)) f(ws z) s E.
and,
(f((0.0).)) - f(0.2) se.
i.. Rd and R

---

The author would like to thank Tamar Livni for creating Figure 1 Tamar holds all copyrights to the artwork. The author would also like to thank Tomer Koren and Yair Carmon for several discussions. This research was funded in part by ERC grant (FOG, 1011 101116258), as well as an ISF Grant (2188) 20).
Ackgnoveledgments
References
[1] N. Alon, Ben-David, N. Cesa-Bianchi, and D. Haussler. Scale-sensitive dimensions, uniform convergence, and learnability. Journal of the ACM (JACM), 44(4):615-631. 1997.
[2] I. Amir, Y. Carmon, T. Koren, and R. Livii. Never go full batch (in stochastic convex optimization). Advances in Neural Information Processing Systems, 34:25033-25043,, 2021.
[3] L. Amir, T. Koren, and R. Livni. Sgd generalizes better than gd (and regularization doesn't t help). In Conference on Learning Theory, pages 63-92. PMLR, 2021.
[4] I. Amir, R. Livni, and N. Srebro. Thinking outside the ball: Optimal learning with gradient descent for generalized linear stochastic convex optimization. Advances Neural Information Processing Systems, 35:23539-23355 2022.
[5] I. Attias, G. K. Dziugaite, M. Haghifam, R. Livni, and D. M. Roy. Information complexity of stochastic convex optimization: Applications to generalization and memorization. arXiv preprint arXiv:2402.09337, 2024.
[6] R. Bassily, Feldman, C. Guzmán, and K. Talwar. Stability of stochastic gradient descent on nonsmooth convex losses. Advances in Neural Information Processing Systems, 33:4381 14491,, 2020.
[7] A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth. Learnability and the vapnik- chervonenkis dimension. Journal of the ACM (JACM), 36(4):929 965, 1989.
[8] O. Bousquet and A. Elisseeff. Stability and generalization. The Journal of Machine Learning Research, 2:499-526 526,,22662222 2002.
[9] Bubeck, Jiang Y.-T. Lee, Li, and A. Sidford. Complexity of highly parallel non-smooth convex optimization. Advances in neural information processing systems, 32, 2019.
[10] S. Bubeck al. Convex optimization: Algorithms and complexity. Foundations and Trends@ in Machine Learning, 8(3-4)2211-357 2015.
[11] D. Carmon, R. Livni, and A. Yehudayoff. The sample complexity of erms in stochastic convex optimization, arXiv preprint urXiv:2311.05300 2023.
[12] V. Feldman. Generalization of erm in stochastic convex optimization: The dimension strikes back. Advances in Neural Information Processing Systems, 29, 2016.
[13] M. Hardt, B. Recht, and Y. Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International conference machine learning, pages 1225-1234. PMLR, 2016.
[14] D. Haussler and M. Warmuth. The probably approximately correct (pac) and other learning models. The Mathematics of Generalization, pages 17-36, 2018.
[15] E. Hazan et al. Introduction online convex optimization. Foundations and Trends@ in Optimization, 2(3-4):157-322 2016.
[16] R. Livni. Information theoretic lower bounds for information theoretic upper bounds. Advances Neural Information Processing Systems, 36, 2023.
[17] Y. Nesterov. Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media, 2013.
[18] B. Neyshabur, R. Tomioka, and Srebro. In search of the real inductive bias: On the role of implicit regularization in deep learning, arXiv preprint arXiv:1412.66 1412.6614, 2014.
10

---

[19] R. T. Rockafellar. Convex Analysis:(PMS-228) Princeton university press, 2015.
[20] M. Schliserman, U. Sherman, Koren. The dimension strikes back with gradients: General- ization of gradient methods in stochastic convex optimization. arXiv preprint urXiv:2401.12058 2024.
[21] A. Sckhari, K. Sridharan, and S. Kale. Sgd: The role of implicit regularization, batch-size and multiple-epochs. Advances In Neural Information Processing Systems, 34:27422-27433, 2021.
[22] Shalev-Shwartz, O. Shamir, N. Srebro, and Sridharan. Stochastic convex optimization. In COLT, volume 2, page 5, 2009.
[23] A. B. Taylor, M. Hendrickx, and Glineur. Smooth strongly convex interpolation and exact worst-case performance of first-order methods. Mathematical Programming, 161:307-345, 2017.
[24] V. Vapnik and A. Y. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. In Measures of complexity: festschrift for alexey chervonenkis, pages 11-30. Springer, 2015.
[25] C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107-115, 2021.
[26] M. Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th international conference on machine learning (ieml-03), pages 928 928-936, 2003.
A Proof of Theorem I
The proof is an immediate corollary of Lemmas 8 and 9 which we prove in Appendices A.1 and A.2 respectively. To see that Theorem Iindeed follows from these Lemmas, start with 17, d. m, 7 that satisfy the conditions. Let f(w,z) be the function and Og the sample dependent first order oracle, whose existence follows from Lemma with suffix s And let f be the function whose existence follows from Lemma 9 some arbitrarily small Eo. with q()) = for all r. It is easy to see that if we apply GD f and define its output (G (.GD,.GD GD)) then: (D .GGD) (q): and w GDD
Then, we have that w.p. 1/2:
GD (D GD) F((0) F() F(O)
F(w GD) -280 F(0)
1
min
1032m min //mmn((Ld//33)),r) 1 2ED
V2. 272 162
min
1032m min (n/min((4P/136),1]
2 272 162
Where in the last equation, assume Eo be sufficiently small. Finally, note that F(0) win F(w).
Notice, that by the same argument, by taking any sulfix T, and setting q(t) 0 for and q(7) T-s for 2 + 1, we can obtain the following stronger result for any suffix averaging:
Theorem 10. For every d 2 4096, T 2 10, 2 1 and > O and suffix < T. there exists distribution D, and a Lipischi convex function ff fw, 2) in Rd, such that for any first order oracle of (w, Z), with probability 1/2, if we run GD with as learning rate then:
T
F
W
F(0)
1
min
1032m 1
min - (d
2. 272 162
1

---

A.1 Proof of Lemma
For simplicity we will assume that d 2" for some N. the final result will be obtained by embedding construction in subspace of size at least half the original dimension.
We start by recalling Feldman's construction
12
There exists set V S {0, 1) such that:
Vrs V2 12 V1 $ and [|vv|]
5d
7d and (1a) > ed/258).
(13)
16
Indeed, suppose pick randomly w {0, I]d according probability P where each coordinate P(w(f)) = with probability 1/2 (independently). Then, by Hoeffding's inequality for two W1, P independently:
d
P W1 W2
+
S
123
4
16
d
d
d
P W1 W1
$ e
2
16)
Thus, picking V elements i.i.d according to P. randomly, of size [V] 2 d/258 we show by union bound that with positive probability, all [V]2 pairs in will satisfy the requirement. Next, we define distribution D, supported on subsets of V such that for random variable V V each v V w.p. independently. We start by assuming that T z dd (the case T > d is handled at the end), and let k E NN such that:
1/3
d
2d.
17
One can show that without loss of generality we can assume is also a power of (in particular, is divisble by k for large enough 7). We next follow the idea depicted in Section 4 but we want to handle the case & >> 1. For that, we redefine the function in Eq. (9. and take blocks of coordinates. To simplify notations, let us define for two set of indices I,J of elements in [d]: = (i......z ........... ).).
= UJ.....
J if max(i l} < min(j E J}. and we will also write:
Σ ei. and, w(1) w el
Σ w(f)
e1
VIVI ieT
VI
iET
then we define our final function as:
(o. maxx(-x( max (w)))))))---( [M]= k)
N(w) max
(14)
[/|=k
Define a min 1 7V27
1), and let:
f(w, V) = g(w, V) aN(w).
where N is defined in Eq. 14 and g is defined be Feldman's function with suitable choice of threshold:
1 max
45nad
g(w, V)
(15)
Vd
2 1.2
Notice that N is 2-Lipschitz, and is 1-Lipschitz.
To obtain the trajectory, we next define sample dependent oracle. We only define it for samples such that there exists v* & V; for all V; e S (define it arbitrarily to any other type of sample). Let J = (i....,,ar) be set of 7d indices such that r*(i,) # O. Divide the elements of J into d' /k subsets. Namely, let.
To
(ig--) ............ ij j= d'lk.
We start by defining only an oracle the function aN. will later show that the trajectory induced by this oracle stays in the minima of g, and that will show that, for our purposes, can choose the
12

---

same oracle for the whole function f. We denote by Ony the sample dependent oracle for aN, and we first define:
t (0.0) 0,
Next, we define for 1. For any w such that & @N(w), define it arbitrarily. IF aN(w) define it as follows:
If there is multi-index 1 that w(1)) = w([]+1) na: Then:
0 aN ()= = a((,, e1,)-
If there is no such multi-index, and if Ij is the minimal multiindx such that w(1,) 0, set:
o G (S, -a(ee)))
If both conditions cannot be met, then:
6 aN (S)
The trajectory of this dynamic is depicted in Fig. [ for the case k = 1. In the general case, think each coordinate in Fig. as a block size k. Now we assume that [wS) follows the trajectory depicted in Eq. (12) with that choice of Oracle. It can be seen that the update step is such rounds, we will have that for every I;:
that after T' + I d'lk
w (i) = ankd//(1((
(16)
and that for T": w²= w.S.
Moreover, one can show that w, is non zero only in coordinates i J, and that for any subset Ig S such that |/| B:
Σ
(0) max
Σ
w S 1 B
(17)
iein
formal proof provided in Appendix D Notice that:
d'jk
d
+
T.
33
5
Next, for any v*. we have that:
13

---

d'kk
W s
w (t)) =
i=1
(1) E 1,111 5d
s max
Eqs. and
ielB
Ad.
(i)
[=]
(EL,
Vkna((d 1-r)
Eq. 16
1n2
$ Vkna((d' -k)-)) -t)
5d
1
5d 2)
$ Vkna
16k k
2
16k
45d
7d d'
$ Vkna 2(16k)2
16
As such 0 0g(w Vi) for all V,, and define ( so that
od (S, w Vi) o (S, w/))
And we have that, (w 8 is the trajectory obtained from Eq. We also have:
12) with respect to this oracle of also.
w v* Vina Σ
d'jk (d Vina
d'ik
Σ
Vkna d²
k2 2 Vkna
49d
2
2( 2(16k)2
And because T' T,, for every suffix [T]:
16 S
W v* Vkna 46d2 2(16k)2
GD WSs
N
Recall that we assume
136d g T:
466Taand1. 2(16k)2
45vkand155 2(16k)2
(d) 1.5
F(WGD)-Fs(00
2 162 k
an
2
min (nVTT. 1
v2.
272 272
162
(18)
Eq. 18 lower bounds the generalization under the event that there exists E V such that V; d 1T. then for every using the inequality
for every i = 1..... m. Now assume & = min{ 51mm (1 (1-8) 8) e- for 1/2:
P(v P Vi) = =1 - e)" 2 e -2cm 2d/511
and,
P(Ev, TH Vi) 2 1 (1- -2//516 1111111 -d/258 e dnss 1-
1/2.
So far we assume that = 2", notice that if < d we can find a subspace of size d1 > 4 so that T 1. and we obtain our final result by embedding construction in this subspace.
14

---

When 7 17.8
1
Notice that if we take the construction with 7 = L1788') d then:
O (w>)) (w = 0,
hence we can use the above construction for any T' > T, and the subdifferential oracle is defined for every iteration above 7' returning O, and obtain similar analysis the case that T [d"/136], and our bounds yield as in Eq. (18):
F F(w GD S.s
Fs(O) 2
min TV
V2 272 16
A.2 Proof of Lemma
The main ingredient in our proof is the following claim whose proof is provided in Appendix C To state the claim will need few notations. First, for any tuples of sample-sequences in 8 and
s (S, and (S', let us denote (S, = (S',r') i 1' and S1z = ".y. namely the prefixes of
the sample sequences agree up point 1' Second, for mapping : [0. 1], from sample points to real numbers, and a sample S, let us denote
E a(z).
(sS)
SS]
ZES
Claim For every n.Y and a define for every sequence of samples (T), and inductively: xy =0 and
x = (1- rs),
(19)
and define:
S q
Σ (
(20)
Then, for any E > O, there is a choice Y < and a such that:
1. For (S.1) # (S', x x. p
2. For every S. 1, such that I < max q((") # 0} and S:: xx EI q())x
The x represents the different states the trajectory can be in. x represent the output of the trajectory which can be an aggreagated sum. We require that each provide signature for the state, and this will allow us to "code" the state of the trajectory along GD.
We now continue with the proof of Lemma have that:
For every sample dependent first order oracle O(1, we
( (S:
Σ 2ES,
(Si--1ww,))))
(21)
SS,
To simplify notations, let us denote:
(10) (S W$, = Os...z
as S. z completely determine the output. We next define
1 hx(x) r 22(()xx,
where y is arbitrarily small4 and observe that, if x is defined as in Eq. 19
2 = (1 -y)x (S) = =x,-11=
vhz(xS
(22)
SSp
2cS,
'y S E/(T), will suffice
15

---

To simplify notation, let us denote:
and x =xy. w 9'
W 7+1
and assume without loss of generality that (1)( * 7 (Otherwise, look only at the sequence up to point max (ax( # 0)). Consider now the sets triplets:
G( - (v.. (S(W,. h2 (x)) (Os,... VI,( ST 8,1 &
where Os.r+1.2 ((f(w() h2 (x²)) is chosen arbitrarily.
Convexity of f ht ensure that the triplets in G(z) satisfy Eq. 10 for all / S T 1, as in Lemma 7 To apply the Lemma, also want to achieve differentiability at points such that T. Therefore, take any two triplets
ui) (f(W)) 2) h2(x)t) (US..... (haas)a))((()))))))))))))))) (w.. .i 1.2.
where f T and 12 s T and suppose 81 82- To simplify notations, let us write w w, and i xy.
First, by convexity of we have that:
V1 - 1/2 + 82 (u2 u1) =f(w], + f f(w, - (x2)))) - (Os.. Vh2(x2)) ((w1,x)) - ((22x22) =/(w1,z)- - ((w2, 2) 0z (W1 w2) h2(x1) h2(22) (x2(x2) (x) X2))
- - - (x2(x2) (x1 x2)=
Next, because g1 # 82, either (z1(x)) # (12( which implies x # x2, or Os # Os2.t.. which implies (1), (2), which again implies xı x2 by Claim | x1 # x2:
In other words, if g1 # g2 then
hx(x1) - (22(x2) - (/2(x2) (x1 x2)
y (1] 22(z)x1 -23- - -2a(z))2 - (2x: -2a(z)) (x1 x2)
y { + x22 -21 xx2)
y 22)
0
X1 # X2
We showed then, that -2 8 (42 - 41) = 0, implies 82. We obtain, by Lemma 7 that there exists function f((w,x). 2) such that for all and S:
hx
(23)
and for all / $ T.
vf((WS.x)) = (Os.... Vh. (x²)).
(24)
This proves Lemma Indeed. By the Lipschitzness of à the unit ball, we have that |x, s ynT. For sufficiently small y, from Eq. 23 since (( (O), (0, (O)), 0)) e G(z), we obtain that
F0.
nT s
16

---

Further, if we assume by induction that for every 1' 1- My wp. and Xp xy, then from Eq. (24) we have that for any first order oracle:
(u,, (w/-11x1-1)
|
2ES,
+ (w
"
Os.,.z. The (1
(w1-1+
|s,
SES,
(w -
"
(S, w. Vh (1)
|&,
ZEST
(w---1>2/-1) -1 O(S, w 1-1)
Vh
|
- 7S, w.S x),
Σ vhr(a(-1)
= (w),,;),
Eq. 22
which proves, by linearity, that Ug = w.S.
B Proof of Lemma 7
We choose
î(w) = max (fj mmx)=axxp jel
g (w - w
is indeed convex it is the maximum of linear functions. Further, it is known 19 that at each
point wt
af(w) convig, f(w) = f 8 (w-
(25)
It follows that, / is L-Lipschitz. Next, for any wi, notice that assumption implies:
ft 2 + wy} m= f(w)).
jef
On the other hand,
ft = fi+ + [w: wi) s f(wi).
Hence f(w;) = fi. Finally, to see the function is differentiable at designated points, take any i e laiff and consider wy. By Eq. (25). is enough show that if gj f then gi = gj, but this clearly follows from our assumption, and fact that f(w:)) = fi-
C Proof of Claim
We first prove by induction that x 0 and, for / 2 1:
5 = yn [ a(z)
Σ
(1 - (--yn)--
(26)
S
ZEZ
(I'st.zesrl
17

---

Indeed.
x = x Yn px a(S,))
(1 -rn)x;- (nma(S))
(1 (1-mn)=---r
(1 - yn)
Σ
a(z))
Σ m7a(2)
|
|,,
2EZ
(Mst:2E5p))
ZES,
Σ a(z)
Σ
(1- (m-
1 E S,]
ny
yn
|5r1
Ss
ZEZ
[I' (1(C1:ESp))
(1 (1-1n) (1-mn)'-r
(())
S
ZEZ
(
Now, for every S, define a polynomial:
(s....()) 1[ E St-nl
|S
and r be a rational point, sufficinetly small, so that 1- r is not the root of any polynomial of the form Ps...z Ps that is distinet from O. In other words, choose that
-Pssrr))) = (s) (x)
and also require that
I Σ Tm1l
e Σ g(t) (X).
r=1
Notice that there are only finitely many polynomials of the above form, hence we can choose such in any interval (0, E) for any & O. Rewriting Eq. (26 we have:
x YT
Σ a(z) (1 yr)
zeZ
Now, suppose we choose {a(z) be reals, independent over the rationals, and suppose we choose r//
Proof of Item Assume that x S Because a(z) are independent over the rationals, and because P(1 - YT)) are always rationals, we have that Ps.r -r) (1 (1-r) for every But then,
by choice r. But then, 1 r= Indeed, assume by contradiction and w.l.og assume < r': then for any S Ps... is 1' 1-degree polynomial, Vz E Z (X) = (X).
the other hand Ps. is most of degree r < L' - Next, S; # SY. for s f, then we can assume (w.l.o.g) that there is z E S; such that z & S it follows that, by looking at the coefficient of the two polymials of the monomial x we have that:
Ps. (X) # (X).
Overall then, we obtain that if x = then (S,t) (S', r').
Proof of Item 2
The proof of Item 2 is similar to how we proved = r'. Notice that:
Σ 9()xx yn I a(=)
(())ss..:
ZEZ
18

---

Hence x7 =x implies for all z E Z:
( Ps.,,z
For E S we have that E Psr.a a max q(t) # O)-degree polynomial, but on the other hand assume that < max q()) * 0), hence Ps. is lower degree polynomial.
D Proof of Eqs. (16) and (17
D.1 Proof of Eq. (16
To avoid cumbersome notations, we will supress dependence on S and write instead of w..
As first step, observe that at each iteration projection is performed. Indeed, let us show by induction that:
|| ||w, (S, V)Il s 21j (t 1).
The definition of then implies that w, restricted to the unit ball without projections.
To see the above true, let us consider the case where the first type of update is performed:
||w = !|w? no(t)) (S. w. V)11
= I! maer,,) naer,
[d' (w, (1))
+ na))+ (w,(1s+1) na)² +
Σ s=j+2
= _ (w,(1s)) +2na(w;(1)) -w (,(()=1)) 21fFa²
Σ (w,(1,))² + 22n2aa²
w,([++1) = =
$ 21 a² 1+ 122a²
=n a² (1+ 1).
And if the second type of update is performed:
||w 212 = l| no (S, w. V)II
= !lw mae,,
Σ we(ls) + 17²20 3Φ1
w,(1)) =0
$ 2n a² 1 1+122 a²
$ 21j² a² (1+1) 1)
We now move on to prove that Eq. (66) holds by induction.
Specifically, we will show that for Ed k. for any / s do:
do s [d/k that at time Ta, = + I do
d=n
WT,, (4,) = an (do 1-1) s do
(27)
O.W.
Eq. (66) then follows by plugging do = d' /k, and noting that at every step have that if e I, then WT,, (i) = VkwTa, (Iz). Therefore, we are left with proving Eq. (27)
For de 0. To = I and we have, indeed, w1 = O. Next assume we proved the statement for do and we
will prove it for do 1. Here too, will induction, and we prove that, for di do 1, time
Tda.h Tán +
(do + 1-k),
19

---

we have that:
(do 2-1) f) 1 1 di (do + 1 d1 < s da
WTdg (4) an
O.W.
For the case d1=0, Tdo.d; = do, and it follows from our outer-induction step. Assume the statement is true for di and we will prove for di 1, here, yet again, use induction. And will show that for s d2 < do + d1 we have at time
d = -do + Ta, + d2.
we have that:
(do + 1)
15 di
(do -1) 1)
di < do + d2
di (1) an
(do +2
I do d2
(28)
(do + 1))
do + d2 < $ dp
0
o.w.
We start the induction with the case d2 in that case notice that d; Td and by induction hypothesis:
(do + 1- di s da (do - 1)
13 di
WT dp (4)) an
o.W.
In this case, note that there are no two consecutive coordinates that are equal, hence our choice of oracle is defined so that (1))) = Edgss Hence, by our update rule (and the lack of projections which
we proved at the beginning):
(do +2++--0 (do 1-1) do < do 1 == do +
r di
W dT (I:) = an
O.W.
Which satisfies Eq. 28
Now assume that Eq. (28) holds for d2, and take d2 1 < do + di
(otherwise, we are done). Notice that ddo.d dd 1. Observe that Wh,,i.dd: (do + 2 d2) W. (do d2) (notice that do 1 d2 d1), and our update rule is such that
(1)) eldgr2-d2 -lo---dd and obtain then:
(do (2o+2-1)
15
(do 1 -1)
di <I < do (d2 + 1)
WTdg ddg4 dget
WT
nag lage-g am
(do + 2-)
1= do + (d2+1)
(do 1-1)
do +2+2- (d2 + 1) < do
O.W.
The most inner induction step now complete. We now notice that T do do+ = dl which proves the middle-induction step. And notice that Too,do+1 Tdgel, which proves the whole induction argument.
D.2 Proof of Eq.
We only need to show that the following quantity is increasing
x,
Σ iE
wS( 1
20

---

But, as shown in Appendix D the update rule is such that we don't perform projections. It then follows easily from our update step. Indeed if we increase a of coordinates by ar,, then clearly the X, only increases. Also, if we perform update of the form:
w (1)) > (1) + an, (1 (I)+1) an,.
for two consecutive and equal coordinates, then for any 1g: If l includes same number of coordinates from I as j+1 then the magnitude doesn't change. If /B contains more 1 then it increases, and I contains more from ij+1 then consider /B' that swaps coordinates in 1j with j+1 then we clearly have:
Σ LETg'
wT(1
())
iET8'
iE
Dimension independent lower bound for GD
In this section prove that the optimization error of GD in Eq. ( is optimal. The lower bound is an optimization error for first order methods and well established (see [0]. The point here is to show that the bound is valid in any dimension, for GD.
Claim 2. For every choice of T, there exists a convex and Lipschitz,function f(x) R - R such that, if we run GD on f, then
f(woD)-fll f(0) 2 7 2 TnT
Proof. We divide the proof into two cases:
casel: 1) 1/1TT
In this case we choose fxx |x - yl. where y > 0s arbitrarily small (may depend on 17). be seen that for every even iteration, we have that:
vf(x2) =-1,
at every odd iteration
vf(x2++) = =1..
As such, for every even iteration we have that x2, = 0, and at every odd iteration we have that x21+1 We thus have that x GD = and
5( - 0
17 0 2n/
casel: 17 1/rl that GD outputs
this case choose f(x) ax, where a (7=1>) 1. Then, one can show
GD - Σ a (T+ l)n a.
x
and:
(1GDD)f(-D))
(T+ 1)n
a
>
6Tn +
!
2
2(T l)n
3T
2
21

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize to other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should diseuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
22

---

Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of model checkpoint, other means that appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g.. large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
23

---

Answer: [NA]
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cc)
jublic//giides/CodeSuumi wwt.SSuwwisssooooooooooooo ssiomoolcosy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results, See the NeurIPS code and data submission guidelines hhttps://nips.cr http://bllicggiiisseeoeeeeeeeeee
wwwllmmissioooooicy for more details. The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does include experiments.
The authors should answer "Yes" the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer:
[NA]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics httppp////uuutoo..ccc/aaa//ttttt
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No. they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consideration due laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it legitimate to point out that improvement in the quality of generative models could be used to
25

---

generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, thpersswithcoee com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should provided.
this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
26

---

Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details of the dataset/code/model as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
27


Reviews:
[{"review_id": "Mxo1tWd3Qh", "reviewer": "Reviewer_pMTh", "summary": "### Summary:\n \n\nThe authors study the generalization error and sample complexity of GD for GD in stochastic CO. Their results show that one can achieve the generalization error of $\\tilde{\\Theta}(d/m + 1/\\sqrt{m)}$ which is the same as the generalization error of ERM. Indeed, they prove that the linear dependence to dimension $d$ in unavoidable. Moreover, they show that $1/\\epsilon^4$ steps are needed for GD to avoid overfitting where $\\epsilon$ is the optmality gap.", "questions": "### Questions/Comments:\n\n\nThis is an excellent paper, I recomment acceptance as I found the paper well-written and the contributions/motivations are clear. \n\n- Can you explain how this analysis restricts to full-batch GD and what makes it impossible to obtain results for SGD? I recommend adding a bit of discussion to the paper regarding this.", "limitations": "N/A", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "### Pros:\n\n- interesting theoretical problem/results\n- excellent citation to related work\n- extremely well-written", "weaknesses": "### Cons:\n\n- some discussion about SGD is missing", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for taking the time to review the manuscript, and particularly for the positive review.\n\n> - Can you explain how this analysis restricts to full-batch GD and what makes it impossible to obtain results for SGD? I recommend adding a bit of discussion to the paper regarding this.\n\nThank you for the question. First, just to clarify, the results cannot be obtained for SGD as SGD has dimension-independent sample complexity and this is discussed in the paper. But the question remains how SGD circumvent the construction. A discussion about that will be added to the paper as follows:\n\nThe main issue with the proof is that it relies on a reduction to sample dependent oracle (defined in section 4.1). SGD circumvent the reduction (Lemma 9). In more detail, the Lemma assumes the update is given by eq. 12 (the full-batch update rule). Because of this full-batch update rule, we can \"encode\" the whole sample in the trajectory. This allows the reduction, because the oracle that depends on the parameter can \"decipher\" the sample and behave like sample dependent oracle. If the sample points are coming one-by-one, as the case in SGD, then we do not know the sample in the first steps, hence we cannot reduce to a sample-dependent first order oracle.", "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": "", "extra_scores": {}}, {"review_id": "4LaSCbCaHU", "reviewer": "Reviewer_kmCP", "summary": "This paper studies the sample complexity of full-batch gradient descent under stochastic convex optimization problem. The main result of this work provides a lower bound of the generalization gap of GD of order $\\Omega(\\min\\\\{\\frac{d}{m},1\\\\} \\cdot \\min\\\\{\\eta d^{3/2}, \\eta\\sqrt{T},1\\\\})$, where $d$ denotes dimension, $m$ denotes sample size, and $\\eta,T$ denotes learning rate and number of iterations of GD. Notably, this lower bound, together with upper and lower bounds of GD or general ERM established in prior works, implies meaningful results under different regime. In the over-parametrized regime where $d=\\Omega(m+T^{1/3})$, the main result, together with lower bound of empirical risk of GD, yields a lower bound of $\\Omega(\\min\\\\{\\eta\\sqrt{T}+\\frac{1}{\\eta T}, 1\\\\})$. Moreover, when $T=O(m^{3/2})$ and $\\eta=\\Theta(1/\\sqrt{T})$, the main results yields a lower bound of $\\Omega(\\min\\\\{\\frac{d}{m}+\\frac{1}{\\sqrt{m}},1\\\\})$, matching the known upper bound of general ERM algorithms.", "questions": "- From Thm 1 to Cor 3 when $\\eta=\\Theta(1/\\sqrt{T})=\\Omega(m^{-3/4})$ and $d\\le\\sqrt{m}$: I agree that the first term in Thm 1 is lower bounded by $\\min\\\\{\\frac{d}{m},1\\\\} \\ge \\min\\\\{\\frac{1}{\\sqrt{m}},1\\\\}$, but the scond term $\\eta d^{3/2} \\gtrsim d^{3/2}m^{-3/4}$ could potentially be smaller than 1. If so, should the lower bound actually be $\\min\\\\{\\frac{1}{\\sqrt{m}},1\\\\}\\cdot \\min\\\\{\\frac{d^{3/2}}{m^{3/4}}, 1\\\\}$?\n\n- line 219: could the authors elaborate why this new oracle defined in 214-218 only activates $O(d)$ coordinates in $d^3$ iterations? From my intuition, to activate a new coordinate, say $k+1$, the oracle needs to increase all previous coordinates to $k$. Then this would only require $d^2$ iterations to activate $O(d)$ coordinates. I think I miss something here.\n\nMinor comments:\n- It would be clear to clarify early in the paper that $w(i)$ denotes the $i$-th coordinate of a vector $w$.\n- 194: $\\partial N(0)$ => $\\partial N_0(0)$\n- 299: Let => let\n- 300: $\\mathbf{S}\\_{1:0}$ => $S\\_{1:0}$", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper provides an improved lower bound on the sample complexity of full-batch gradient descent for SCO. Under several regimes, the lower bound match existing upper bounds of GD or general ERM and becomes optimal. Moreover, it implies that the worst case sample complexity of GD is the same as that of general ERM. These results contribute to better understanding the sample complexity of the SCO problem.", "weaknesses": "The technical results are solid, but I think the writing could be improved. In particular, the connection between the high-level intuition provided in Sec 4 and the actual constructions in Sec 4.1 is not apparent. For example, it's not clear to me why the oracle $\\mathcal{O}^{(t)}$ defined in Eq. 11 satisfies the zero-chain property depicted in Figure 1.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for the constructive comments and the positive score. Below are answers to concrete questions.\n\n\n- > For example, it's not clear to me why the oracle  𝑂(𝑡) defined in Eq. 11 satisfies the zero-chain property depicted in Figure 1.\n\nNotice that figure 1 refers to eq. 16 and not eq. 11. The figure depicts the specific dynamics of choice and the subdifferentials as appear above eq. 16. The caption of the figure should be rephrased as: “Depiction of the dynamics depicted **above** Eq. (16)”. Or to refer to the main text instead ““Depiction of the dynamics depicted below Eq. (9)”.\n\nFrames 3,6,7 depict the case of item 1 (below eq. 9), and frames 1,2,4,5 the case of item 2 (below eq. 9) and last frame is the last item (partial = 0). Is that more clear?\n\n\n- > should the lower bound actually be $\\min ( \\frac{1}{\\sqrt{m}},1)\\cdot \\min(\\frac{d^{3/2}}{m^{3/4}},1)$ [[as opposed to $1/\\sqrt{m}$]]\n\nNotice that the $\\Omega(1/\\sqrt{m})$ term does not follow from thm 1 but, as stated in the manuscript, “is a well known-information theoretic lower bound for learning”. A citation will be added to the manuscript to clarify. For example, this lower bound can be found in lecture notes: https://optmlclass.github.io/notes/optforml_notes.pdf (theorem 16.7) where it is proven that there are two instances of stochastic convex optimization where every algorithm “fails” on one of them with excess error $1/\\sqrt{T}$ unless more than $T$ examples are observed (in our notation $T=m$)\n\n- > Could the authors elaborate why this new oracle defined in 214-218 only activates  $O(d)$ coordinates in $O(d^3)$\n iterations? \n\nRoughly, to increase coordinate $k$ you need to increase each previous coordinate by $+1$. Increasing coordinate t requires k-t iterations (increasing $k$ and propagating it back). So overall $\\sum_{t=0}^1 k-t= O(k^2)$ iterations in order to increase the $k$’th iteration by 1. So overall $O(1+2^2+3^2….. + d^2)$ to increase all coordinates by one. Which amounts to $O(d^3)$.\n\n\nRegarding minor comments, thanks for the suggestions and for catching typos. We will follow the reviewers' advice and corrections.", "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": "", "extra_scores": {}}, {"review_id": "r85TiMrljQ", "reviewer": "Reviewer_kB6m", "summary": "The paper proved a tight lower bound for the sample complexity of full-batch gradient descent. The authors also presented some open questions in this area.", "questions": "I couldn't understand the paper very well, so I do not have any questions. Please refer to the weaknesses section.", "limitations": "I think the paper is not ready for this conference, and I am not sure how important the result is.", "rating": 3, "confidence": 2, "soundness": 1, "presentation": 1, "contribution": 2, "strengths": "I think the paper is not ready.", "weaknesses": "- The structure of the paper is not standard. There isn't any conclusion, and it seems that the paper is written in a very rushed manner.\n- The notation section is not well-written.\n- It seems that the main contribution of the paper is in Theorem 1, but it is not clear where its proof is located. The proof in the appendix is very short, and it appears that some parts of the proof are in the main body of the paper and some in the appendix. It is not organized very well.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for taking the time to review the manuscript. \n\n- The conclusions are clearly presented in the manuscript, but are also present in the other reviews. If, after reading the other reviews, you still feel that certain contributions are not highlighted enough, please point concretely and we will gladly highlight them.\n- As to notations, please share concrete examples to missing/confusing/non-standard notations. We will gladly fix any such confusion.\n- As to organization, all proofs appear in the appendix. Main theorems and main Lemmas appear in the main text. This is a standard practice.\n\nUnless there are strong reasons for rejection, we ask the reviewer to higher the score so it will not reflect negatively on the paper.", "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": "", "extra_scores": {}}, {"review_id": "eONqhowYf9", "reviewer": "Reviewer_gMtP", "summary": "The paper shows a new lower bound for the generalization error of gradient descent for Lipschitz functions. The bound shows a linear dependency on the dimension that closes the gap between lower and upper bounds in the sample complexity of GD under several regimes. The construction of the function relies on a block version of a variation of Nemirovski function and a reduction from a sample-independent oracle to a sample-dependent oracle. \nThe authors also propose a set of open problems related to the generalization error of GD.", "questions": "- I'm really confused by the fact that all bounds and the proofs use $F(0)$ for the gap. Why is this the case? Why isn't it $\\min_w F(w)$? If the algorithm starts at $w_0=0$, doesn't it mean the function value increases?", "limitations": "Yes", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The paper shows a clever way to make changes and leverage Nemirovski and Feldman's function so as to control the dynamics of the sub-differentials\n- The authors try to give the best intuition for the construction of the function in the presentation of the paper\n- The paper is technically challenging and the proofs have been explained well. I have read some parts of the proofs and didn't see any problem.", "weaknesses": "- I think the main weakness in the paper is the presentation of the results and improvements. I know that these have all been written in the paper, but I found myself lost and rereading many times to see the significance of the results. This could be rewritten in a more concise way with all the improvements under which regimes spelled out explicitly (maybe a table would make sense).\n- There are a few typos: Line 294: sequences. Line 296: receive(s). Line 300: $S_{1:0}$, should S be bolded? Line 320: punctuation and line break.\n- It should be mentioned that Eq 16 will be proven in Appendix D.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for the review and detailed comments.\n\n- > This could be rewritten in a more concise way with all the improvements under which regimes spelled out explicitly (maybe a table would make sense).\n\nA table is an excellent suggestion. We will follow it, thanks!\n\n- > It should be mentioned that Eq 16 will be proven in Appendix D.\n\n\nThanks for catching this. It will be mentioned.\n\nAlso thanks for catching typos!\n\n\n- > I'm really confused by the fact that all bounds and the proofs use 𝐹(0) for the gap. Why is this the case?\n\nThanks for pointing this out. As to the bounds, it will be a good idea to state the results in terms of $\\min_{w\\in W} F(w)$ and not $F(0)$.  (clearly, $F(w)-F(0) \\ge F(w)-min_{w\\in W} F(w)$). \n\nAs for the proofs you are right. We get the excess error w.r.t initialization, which may seem strange. There is no contradiction here, as GD minimizes the empirical loss and the increase is w.r.t population loss. But overall it is strange that you start at an initialization that is better than where you end up with. This also happens, btw, in other similar constructions (see [3])", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper has a clean result on a classical problem and majority of the reviewers seem to share the sentiment. One of the reviewers points out that they found reading the paper hard, perhaps the author can mitigate this issue and strive for better readability. I found the paper to be easy to follow but perhaps this comes from prior area of expertise etc. My main and only if you can call it negative point about the paper is that it focuses on stochastic convex optimization and so while the problem is fundamental it has limited scope in current focus areas in ML and optimization. Overall I recommend the paper for an accept.
Decision: Accept (poster)