Never Go Full Batch (in Stochastic Convex Optimization)
Authors: Idan Amir
Yair Carmon
Tomer Koren
Roi Livni
Venue: NeurIPS 2021 Poster (2021)
Keywords: Stochastic Convex Optimization
First-order Optimization
Gradient Methods
Stochastic Gradient Descent
Generalization

Abstract: We study the generalization performance of $\text{\emph{full-batch}}$ optimization algorithms for stochastic convex optimization: these are first-order methods that only access the exact gradient of the empirical risk (rather than gradients with respect to individual data points), that include a wide range of algorithms such as gradient descent, mirror descent, and their regularized and/or accelerated variants. We provide a new separation result showing that, while algorithms such as stochastic gradient descent can generalize and optimize the population risk to within $\epsilon$ after $O(1/\epsilon^2)$ iterations, full-batch methods either need at least $\Omega(1/\epsilon^4)$ iterations or exhibit a dimension-dependent sample complexity.

Never Go Full Batch (in Stochastic Convex Optimization)
Idan Amir Department of EE Tel Aviv University
Yair Carmon
Blavatnik School of CS Tel Aviv University ycarmon@tauex tau. ac ac.il. il
i idanamir@mail. tau. il
Tomer Koren Blavatnik School of CS, Tel Aviv and Google Research tkoren@tauex. tau. ac.
Roi Livni Department of EE
Tel Aviv University #livni@taued tau, ac
Abstract
We study the generalization performance of full-batch optimization algorithms for stochastic convex optimization: these first-order methods that only access the exact gradient of the empirical risk (rather than gradients with respect to individual data points), that include wide range of algorithms such as gradient descent, mirror descent, and their regularized and/or accelerated variants. We provide new separation result showing that, while algorithms such as stochastic gradient descent can generalize and optimize the population risk to within & after (11E²² iterations, full-batch methods either need at least ((1/E") iterations or exhibit dimension-depeenent sample complexity.
Introduction
Stochastic Convex Optimization (SCO) is a fundamental problem that received considerable attention from the machine learning community in recent years [28, 15, 4, 11, 2]. In this problem, assume a learner that is provided with a finite sample convex functions drawn i.i.d. from an unknown distribution. The learner's goal is minimize the expected function. Owing its simplicity, serves as an almost ideal theoretical model for studying generalization properties of optimization algorithms ubiquitous practice, particularly first-order methods which utilize only first derivatives of the loss rather than higher-order ones.
One prominent approach for ScO-and learning more broadly- is to consider the empirical risk (the average objective over the sample) and apply first-order optimization algorithm to minimize it. The problem of learning is then decoupled into controlling the optimization risk (training error) and bounding the difference between the empirical error and the expected error (generalization error).
over the empirical
convex optimization, the convergence different first-order methods has been researched exten- sively for many years (e.g., [26, 25, 5]), and we currently have very good understanding of this setting in terms of upper as well lower bounds on worst-case complexity. However, in SCO where the generalization error must also be taken into account, understanding is still lacking. In fact, this is one the few thcoretical learning models where the optimization method affects not only the optimization error but also the generalization error (distinctively from models such as PAC learning and generalized linear models). In particular, it has been shown [28, 15] that some minima of the empirical risk may obtain large generalization error, while other minima have vanishingly small
35th Conference on Neural Information Processing Systems (NeurIPS 2021).

---

generalization error. To put differently, learning in SCO is not only a question of minimizing the empirical risk, but also a question of how one minimizes it. However, the results of [28, 15] leave open the question of whether concrete optimization also have different generalization properties.
Towards better understanding, Amir al. [2] recently studied the generalization properties of full- batch gradient descent (GD), where each step is taken with respect to the gradient of the empirical risk. For GD (and a regularized variant thereof), they gave lower bound on the generalization error as a function of iteration number, which is strictly larger than the well-known optimal rate obtained by stochastic gradient descent (SGD), where each step is taken with respect to the gradient at sampled example. Notably, the lower bound of [2] precisely matches the cimeension-indeeeneee stability-basser upper bound recently shown for full-batch GD by Bassily et al. [4]. The separation between full-batch GD and SGD is the first evidence that not only abstract Empirical Risk Minimizers may fail to generalize in SCO, but in fact also basic methods such as GD could be prone to such overfitting, A natural question is, then, whether overfitting is inherent to full-batch algorithms, that minimize the objective only through access to the exact empirical risk, or whether this suboptimality can be remedied by adding regularization, noise, smoothing, or any other mechanism for improving the generalization of GD.
In this work we present and analyze model full-bathhh optimization algorithms for SCO. Namely, we focus on algorithms that access the empirical risk only via a first-order oracle that computes the exact (full-batch) gradient of the empirical loss, rather than directly accessing gradients with respect to individual samples. Our main result provides a negative answer to the question above by significantly generalizing and extending the result of Amir et al. [2]: we show that any optimization method that uses full-batch gradients needs at least ((1/E*) iterations to minimize the expected loss to within e error. This is in contrast with the empirical loss, which can be minimized with only (11e²) steps.
Comparing SGD and GD in terms of the sample size n, we see that SGD converges to an optimal generalization error of 0(1 (n) after O(n) iterations, whereas a full-batch method must perform Q(1²) iterations to achieve the same ((1/v)) test error. We emphasize that we account here for the oracle complexity, which coincides with the iteration complexity in the case of gradient methods. In terms of individual gradients calculations. while SGD uses at most O(n) gradient calculations (one sample per iteration), a full-batch method will perform 2(n²) calculations (n samples per iteration).
The above result is applicable to a wide family of full-batch learning algorithms: regularized GD (with any inteeinndeennnet regularization function), noisy GD, GD with line-search or adaptive step sizes, GD with momentum, proximal methods, coordinate methods, and many more. Taken together with upper bound of Bassily al. [4], we obtain sharp rate of 0(1/E") for the generalization- complexity of full-batch methods. Surprisingly, this rate is achieved by standard GD (with an unusual step-size choice of r = O(E")), and it cannot be improved by adding regularization of any sort, nor by adding noise or any other form of implicit/explict bias.
1.1 Related work
This work extends and generalizes the results of Amir et al. [2] who proved generalization lower bounds for GD (and a specific instance of regularized GD). Our work shows that in fact any full-batch method will suffer from similar lower bounds. Our construction builds upon the one used in [2], which in turn builds upon previous constructions [4, 28). However, our arguments and proofs here more challenging, as we need to reason about general family of algorithms, and not about a specific algorithm whose trajectory can be analyzed directly. Our developments also build on ideas from the literature on oracle complexity lower bounds in optimization [25, 26, 30, 8, 12, 9]. In particular, we first prove our result the simplified setting of algorithms constrained the span of observed gradients [25, 26] and subsequently lift it to general algorithms using random high-dimensional embedding technique proposed by Woodworth and Srebro [30] and later refined in [8, 12]. However, while these works lower bound what we call the empirical risk, we lower bound the generalization error. This requires us to develop somewhat different argument for how the span of the gradients evolve during the optimization: in prior work, the algorithm learns the component of the solution coordinate by coordinate, whereas our work the true (generalizing) solution is present in the observed gradients from the first query, but spurious sampling artifacts drown it out.

---

Empirical studies (outside of the scope of SCO) support the claim that generalization capabilities degrade with the increase of the batch size. Specifically, Zhu et al. [33] indicates that SGD out- performs GD in terms of generalization. The works of Keskar et al. [22] and Hoffer et al. [20] exhibit a similar phenomenon in which small-batch SGD generalizes better than large-batch SGD with the same iteration budget. We provide the first theoretical evidence for this phenomenon for convex losses. Several theoretical studies explore the convergence of stochastic methods that use mini-batches [10, 23, 31]. Note that this setting differs from ours, they assume access to mini- batches sampled without replacement whereas full-batch means we reuse the same (full) batch with each gradient step.
There has also been recent progress in improving the generalization capabilities of GD. Wu et al. [32] interprets mini-batch SGD as a noisy version of GD. They propose a modified algorithm with noise injected to the full-batch gradients. Geiping et al. [16] propose a GD-based training scheme that achieves CIFAR-10 generalization performance comparable to standard SGD training. Interestingly, both proposed algorithms require access to sample-poing and are therefore not "full- batch" by our definition: The scheme [32] requires sample-point data for computing the noise, while statistics to compute a regularization term (as well as batch normalization). Our work shows that (in SCO) this is unavoidable: namely, no data-independent noise or full- batch regularization can be used to improve generalization at a reasonable computational budget.
the GD variant [16] uses
Several other works study the generalization performance of GD [29, 17, 21, 24]. The work of Soudry et al. [29], for example, examines GD on unregularized logistic regression problems. They show that, in the limit, GD converges to a well-generalizing solution by arguing about the bias of the algorithm. Interestingly, both our and their results require slow-training, beyond what is required for empirical error optimization. Another work that highlights the slow convergence of GD is that of Bassily et al. [4]. They were the first to address uniform stability of (non-smooth) GD and SGD, and provided tight bounds. Stability entails generalization, hence our results lead to stability lower bounds for any full-batch method. Consequently, we extend the lower bounds for GD in the work of Bassily et al. [4] to a wider class. It might be thought that the instability argument of Bassily et al. [4] can be used to obtain similar generalization lower hounds-howerdd we note that their techniques also prove instability of SGD (which does generalize). Hence, instability does not immediately imply, in this setting, lack of generalization.
Finally, we note that under smoothness and strong convexity, it is well known that improved rates can be obtained. Specifically, using the stability bound of Bousquet and Elisseeff [6] one can show that we can achieve generalization error of ((1/vn) after (n) iterations if the population risk is (()--strongly convex. The arguments of Hardt et al. [19] imply generalization bound to instances where every sample risk is O(yn) smooth. Our result implies that, even though these special families of functions enjoy appealing learning rates, in general it is impossible to obtain better rates by strong convexxinn or smoothing problem instances via first-order full-batch oracle queries.
2 Problem Setup and Main Results
We study the standard setting of stochastic convex optimization. In this setting, learning problem is specified by a fixed domain W S Re in d-dimensional Euclidean space, and a loss function W x X - R. which is both convex and L-Lipschitz with respect to its first argument (that is, for any z E 2 the function 2(w;2) is L-Lipschitz and convex with respect to w). In particular, throughout the paper, our construction consists of 1-Lipschitz functions and we will focus fixed domain W defined to be the unit Euclidean ball in Rd namely W = (w : ||w|l2 s 1}.
We also assume that there exists an unknown distribution D over parameters z and the goal of the learner is to optimize the true risk (or true loss, or population risk) defined as follows:
F(w) = E こ-D
(1)
We assume that sample S = (zI....,,,,, } is drawn from the distribution D, and the learner has to output ws E W (the exact access the learner has to the sample, and how ws may depend on S is discussed below). We require the solution to be e-optimal in expectation for some parameter e > 0, i...
E [F(ws)] min F(w*) S E. S-DR
W*EW
3

---

As discussed, the standard setting assumees that the learner has direct access to the i.i.d. sample, as well as the gradients of the loss function (i.e., first-order oracle). In this work, though, we focus on specific family full-batch methods. Hence, the optimization process is described as follows: First, an i.i.d. sample (Z1....,22 2n) is drawn from D. Then, the learner is provided with access only to the empirical risk via full-batch first-order oracle which we define next.
Full-batch first-order oracle. Consider a fixed sample (215-..:āá) En) of size n, drawn i...d from D. The empirical risk over the sample S is
L f(w:z) :=1
Fs(w)=
Then, a full-batch first-order oracle is a procedure that, given input w W, outputs
(w) == (VFs(w);Fsl) Fs()))
where (Fs(w) is an empirical risk sub sub-gradient of the form
Fs((w)
vs(wzz)) E=
and each sub-gradient Vf(w, 2;) is computed by the oracle as function of w and ž (that is, independently of 2j for j # i).
We emphasize that the sample fixed throughout the optimization, so that the oracle computes the gradient of the same empirical risk function at every call, hence the name f full-batch. Note that the subgradient with respect to a single data point, i.e., ff(w; 2,), not accessible through this oracle, which only returns the average gradient over the sample S.
Notice that definition above is slightly narrower than general sub-gradient oracle for the empirical risk due to the requirement that the sub-gradients Vf(w, 2,) are chosen independently of Zj for i since we provide here with a lower bound, this restriction strengthens our result. We make this restriction to avoid some degenerate constructions (that in fact can even be used to fail SGD if the gradient at zj may depend on the whole sample), which are of no practical implications.
Full-batch first-order algorithm. A full-butch (first-order) method is naturally defined as any algorithm that has access to the optimization objective-namely the empirical risk Fss Fnsonny via the full-batch first order oracle. In particular, if w, is the r'th query of the algorithm to the full-batch oracle then w,, has to be of the form
w, = (O(o)).... O(,,-)))
where 2: dRy - W is a fixed (possibly randomized) mapping. At the end of the process the algorithm outputs ws. We study the algorithm's is oracle complexity, which is the number of iterations 7 the algorithm performs before halting. Therefore, we assume without loss of generality that ws wy, i.e., the algorithm's output is its 7"th query.
2.1
Main result
In this section establish main result, which provides generalization lower-bound for full-batch first order algorithms. The complete proof is provided in the full version of the paper [1].
Theorem 2.1. Let > O and n,T E N; there exists d poly(2", ,T, 1/E) such that the following holds. For any full-batch first-order algorithm with oracle complexity at most T, there exists I-Lipschitz convex function convexfunction f(w z) in W, the unit-ball in R.d and a distribution D over Z such thut, for some universal constant >
E
[F(ws)) 2 min F(w*) + Q[min (1- c22 cE> VT.
(4)
S-D"
w*eW
An immediate consequence of Theorem 2.1 1 is that in order to obtain less than true risk we need at least 7' = =[(1/=*) iterations.
For simplicity, we state and prove the lower bound in Theorem 2. for the class of first-order full- batch algorithms defined above. However, our constructions readily generalize to local full-batch oracles that provide a complete description of Fs in an arbitrarily small neighborhood of the query point [25, 18]. Such oracles subsume second-order oracles, and consequently our generalization lower bounds hold also for second-orde full-batch algorithms.

---

2.2 Discussion
Theorem 2.1 suggests that full-batch first-order algorithms are inferior to other types of first-order algorithms that operate with access to individual examples, such as SGD. Importantly, this sepa- ration is achieved not in terms of the optimization performance but in terms of the generalization performance. In light of this result, we next discuss and revisit the role of the optimization algorithm in the context of SCO. In particular, we wish to discuss the implications to what are perhaps the two most prominent full-batch optimization methods, GD and regularzied-Gi,, and in turn compare them.
Gradient descent. Perhaps the simplest example of a full-batch method is (projected) GD: GD is an iterative algorithm that at each iteration performs an update step
Wy Hw [w w1
where W is convex set which project the iterated step. The output of GD is normally taken to be wss / Σ w,, (or randomly chosen w,). Notice, that each step requires one call to full batch oracle, and a single projection operation. The convergence analysis of GD to the optimal solution of the empirical risk has been widely studied. Specifically, if is the sample-size, it is known that with 7= (n) and T = On). GD converges to a minimizer of Fs that is 0(1/ (11/V))-su -uu optimal. For the exact variant of GD depicted above, the generalization performance was analyzed in the work of Amir et al. [2] that showed that with T = (n) steps, GD will suffer 2(1/ generalization error. Theorem 2 extends the above result any variant of GD (dynamic learning-rate, noisy GD, normalized GD, etc.).
Regularized gradient descent. We would also like discuss the implication of Theorem 2.1 with respect to regularized variants of GD that operate on the regularized empirical risk
(ww Ar (r())= + (ww)
The main motivation of introducing the regularization term is avoid overfitting, and a popular choice for r is the Euclidean norm r(w) = ||w]]3- This choice leads to the following update rule for GD:
Wi+1 lw - [(1-n:) (2Aw,) n. (.FF),
Again, this update can be implemented using single first-order full- bbtch oracle call that computes the quantity (W,, More generally. for any indeeeindeend,trr, GD on Fis full-batch algorithm When is the Fuclidean norm, the minimizer of f is known to enjoy (with choice À 0(1/ an optimal generalization error of O(1/vn) [6, 28]. This demonstrates the power of regularization and how it can provably induce generalization. Nevertheless, Theorem 2.1 still applies to any optimization method over F. Since optimization f (the regularized empirical risk) to (I//Vn)- precision can be done via a full-batch method, and with less than (n)) calls, observe that there are methods that minimize the regularized-empirice risk but, due to Theorem 2.1 do not reach the optimal generalization error.
The role of regularization. Finally, in light of Theorem 2.1 let us compare the different variants of GD and regularized GD that do generalize well, in order to sharpen of regularization in generalization. The conclusion Theorem 2. 1 that any full-batch method that generalizes well performs at least O(n²) steps. For regularized GD, with &2 regularization, O are indeed sufficient. In particular, with Onn²) iterations we can find a solution that has O(1/n) empirical error. Any such solution would enjoy generalization error of O(1/v)) [28]. For GD, Bassily et al. [4] showed that (nr²) iterations would also suffice to achieve 0(1/vn) error. This is achieved by tuning the learning rate to = (1/ Notice that this improvement does not require any type of added regularization.
understanding of the role
To summarize, both GD and regularized GD with optimal parameters require @(n²) iterations to attain the optimal ( (I/vī)) generalization error. Overall then, explicitly adding regularization is not necessary nor does it improve the convergence rate. One might be tempted to believe that tuning the learning rate in GD induces implicitly some sort of regularization. For example, one might
Note that we are not concerned with the computational cost of computing Vr(w;) since it does not factor into oracle complexity.
5

---

imagine that GD can be biased towards minimal norm solution, which might explain redundaney of regularizing by this norm. However, this turns out also be false: Dauber et al. [11] showed how GD (with any reasonable choice of learning rate) can diverge from the minimal norm solution. In fact, for any regularization term r, one can find examples where GD does not converge to the regularized solution. Thus, even though GD and regularized-Gi) are comparable algorithms in terms of generalization and oracle complexity, they are distinct in terms of the solutions they select.
3 Technical Overview
In this section we give an overview of our construction and approach towards proving Theorem 2. 1. For the sake of exposition, we will describe here slightly simpler construction which proves the main result only for algorithms that remain in the span of the gradients. In more detail, let us examine the family of iterative algorithms of the form
W, VV (VFs(wo), WFs(ww)..... VFs(w:-1)3 n W,
(5)
where W is the unit ball and (w,) full-batch oracle response to query w, as defined in (2) above. Well-studied algorithms such GD and GD with standard l norm regularization fall into this category of algorithms.
To extend the lower bound to algorithms not restricted to the gradient span refine the simpler construction and apply wetl-established techniques of random embedding high-dimensional space. We discuss these modifications briefly in the end of this section and provide the full details in Section and the full version the paper [1].
3.1 A simpler construction
Let us fix n, d 2 and parameters 2 = (a, y) (0, 1)dd x x R2 = 2, such that a E {0, 1)d,
(0,
0 and Y1. Y2 O. Define the hard instance faa Rd+2 x % - R as follows:
foo (a, e, Y)) (w a) + Yi w ew eda2 + r(w).
(6)
where gy. Va and r are
8y(waa) Viieta (w)) with hy(a) 0
a 2 YY2
aa+
a < -Y2.
r(w) m0 max
if (ii) =
2n
va())= = +1
if (a) 1;
if (d 1.
and ed+2 is the (d + 2) 'th standard basis vector. The distribution we will consider is uniform over a. That is, we draw a E (0, 1)d uniformly at random and pick the function for (w; (a, y)). The parameters and y2 of the construction should be thought of as arbitrarily small. In particular, the term Yiva w in Eq. (6) should be thought of negligible, and the first term, gy, roughly
(y(; a) R
c()((mx(-w(().)) 03)
Fed
Another useful property of the construction the population risk F(w) E for (w;; z) is min- imized at w* -ea+2, with expected loss F(w*) -E. However, as we will see, the choice of the perturbation vector Va and the term r(w) hinder the learner from observing this coordinate and; the first ()= queries are constrained to linear subspace where all the points have a high generalization error due to the expectation of the first term gy.
3.2 Analysis
We next state the main lemmas we use, with proofs deferred to the full version of the paper [1]. Given a sample S, let us denote = Lass Va. and
span' (u), ....... = span(u), #2, ... W.

---

Additionally, given fixed sample we write
((S) (i a(i) Va S) U {d +1
for the set coordinates i [d] such that ( = for every a in the sample S, plus the coordinate d + 1.
Lemma 3.1. Let S IT JT. y2= 2n, and suppose that the sample S satisfies (9()) > T. Then there exists a firt--order full-batch oracle such that for any algorithm that adheres
Wi span' (VFs(wo). (Fs(w)).... (Fs(w(-))3
with respect to f(w: (a, e, y)) defined in Eg. (6), we have
Wy span' (S),
Fear2 (ris+ rea+ + ei} for all (T),
where (,) is the the largest coordinates I(S).
We next observe that in any span of the form {yi sed+2 + eiliedy (8) such that [Jy((S) s T, we cannot find solution with better risk than O. On the other hand, note that for w -ed+2, have that
fee (w; (a, E, y)) -E
In other words, our lower bound stems from the following result:
Lemma 3.2. For sufficiently small s 2nEy2, e/V4T, and any vector || s Vd, any output
ws span' {ri + Eea=2++)) ieJr(S)
satisfies
1
Σ (E[d]
he(ws(i)) +ell()))ewww(a)))) 2 2 v7.0 -
2
Lower bound proof sketch for span-restricted algorithms of the form (5). First, observe that the probability of an arbitrary index satisfy a(i) for all E Si (1/2)". Therefore, | the number indexes that hold this from the possible d, distributed as a binomial with d experiments and success probability p 2- Using elementary probability arguments one can show that for sufficiently large d we have [9(5) > T with high probability; see Claim B.2 in the appendix. This implies that the conditions of Lemmas 3.1 and 3.2 hold w.h.p. To conclude, relate the LHS of Eq. (8) to the expected risk
F(w)= a-D
(w: (w: (a, E [w; + E [va] w ed+2 + r(w). a-D
a-D
As (y::; a) is convex w.r.t a (since a(i) = a2))) we can apply Jensen's inequality with Fa-D[a(i) = to obtain:
[gy(ww:))) 2 2 iE[d]
Σ
(2(ww()))
Applying the Cauchy-Schwarze inequality the second term while also using the facts that ||vall s Vd and that ws is in the unit ball, we get:
E [va] - E [llvall - [|w]]] 2 -yi Vd.
For sufficiently small yı this term is negligible, and since r(w) 2 0 we get that the expected risk is approximately the LHS term in Eq. (8). Lastly, recalling that F(-ea+2) = - we get that
F(ws) min F(w) 2 _ +++ min 20 2T2 0) w.h.p. weW
The same lower bound (up to a constant) also holds in expectation by the the law total expectation. Our distribution is supported on 5-Lipschitz convex functions, so that re-parametrizing 1 E as well as for yields the claimed lower bound (4) for the case of span-restricted algorithms.
7

---

3.3 Handling general full-batch algorithms
The above construction establishes an 221/E*) oracle complexity lower bound on any algorithm whose iterates lie in the span of the previous gradients. While this covers a large class of algorithms, techniques like preconditioning [13], coordinate methods [27] and randomized smoothing [14] do not satisfy this assumption. In fact, trivial algorithm that always outputs -ed+2 will solve the hard instance (6) in a single iteration.
To address general algorithms, we employ well-established technique in optimization lower bounds [30, 8, 12] wherein we embed a hard instance f(w; z) for span-constrained algorithms in a ran- dom high-dimensional space. More concretely, we draw random orthogonal matrix U E Rd'xd UU- = (xxa) and consider the d' > d-dimensional instance fo (w::2) = SU' w; along with its corresponding empirical objective Fs.u (w) :/4 Liein Su (w;zz). Roughly speaking, we show that for general algorithm operating with the appropriate subgradient oracle for Fs.u the iterate is approximately in the span of (V/s.u (wo)... .... VFs.u (w,,)) in the sense that the component of w, outside that span is nearly orthogonal to the columns of U. Consequently, the response of the oracle to the query w, at iteration is, with high probability, identical to the information it would return queried with the projection of to the span of the previously observed gradients. This reduces, in a sense, the problem back to the span ppstrrestricted setting described above.
For the embedding technique to work, we must robustify the hard instance construction so that small perturbations around points in the span of previous gradients do not "leak" addi- tional information about the embedding U. To do that we make a fairly standard modifica- tion to the component r(w) in (6) (known as Nemirovski's function [12, 7D). replacing with max (O, maxi (w(i) + +y'), w(d + 1) +Y",, where y'."" are small offset coefficients that go to zero as the embedding dimension d' tends to infinity. We provide the full construction and the proof of Theorem 2.1 in Section 4 and the full version of the paper [1].
4 The Full Construction
As explained above, the key difference between the simplified construction fis and the full construc- tion with which we prove Theorem 2.1 is that modify the Nemirvoski function term r(w) in order to make it robust to queries that are nearly within a certain linear subspace. In particular, we bias the different terms in the maximization defining r r(w) as control the index of the coordinate attaining the maximum. For ease of reference, we now provide a self-contained definition of our full construction with the modified Nemirovski function.
R = Z are such that a E (0. 13d, E and y2. Y3 O. Define the hard instance fun R 4+2 x 2 RR follows:
Fix n, 2 and parameters z = (a, E, y) {0, 1]dd
fwr (a, E)) gy a) Viva w aw ed+2 + r(w),
(9)
where gy, Va and r are
8y a) = Eiclon (w)))(ww(i) with hy(a) =
0
a YY:
a Y/2
a < -
[
Yi
if [d];
r(w)= == max (axxe[aaa)((((00))++-
with o ;
zdn
2
=
if a() = if af) =
2m
* (i) == +1
0
if [d+ 1, 2},
and e; is the i'th standard basis vector in d We consider a distribution D over a that is distributed uniformly over (0, 1)d, that is, we draw E {0. 13dd uniformly random and pick the function for (w; (a, E, y)). The rest of the parameters are set throughout the proof as follows:
EY2 4
6
Y1
Y2
Y3 16
(10)
TVd
8

---

With this choice of distribution D as well our choice of parameters we obtain, since ||v s Vd and by our choice of yı (as well as Jensen's inequality and r(-) 0):
(a, F(w)= E (v. a-D
Σ iE|d]
(2(w(()) +w((d+
(11)
Notice that we also have that for choice w* ddd2, since r(w*) 2y::
7E
F(w*) -
(12)
8
Our development makes frequent use of the following notation from Section 3:
I(S) (i: a(1) = Va e 8) (d 1), J,(S) largest elements in I(S), and Σ Va-
We hegin with the following lemma, which is a robust version of Lemma 3.1 in Section 3. The proof provided in the full version of the paper [1].
Lemma 4.1. Suppose that wo 0. Consider fis (w; (a, E, y)) with parameters as in Eq. (10).
Suppose S is sample such that [I()) > ++ Assume that w is such that
w = W g.
where
E span' (E),(S)
|r ( e eij. and ||9/l min 122 Y1Y3
(13)
3 16dn
Then,
VFs(w) Ee +
for some i E (S), where 9, (S) is the set of the + largest coordinates in I(S).
The following corollary states that the gradient oracle's answers are resilient to small perturbation of the query (as long as they in vicinity of the "right" subspace): the proof is provided in the full version of the paper [1]:
Corollary 4.2. Assume that w is such that
W = W + 9.
where
w, span' (niv+ +e is), sear + eij. and || 5
Y2 Y1y3
min
(14)
4vd
3 16dn
Then,
VFs(w) (F)( Fs(w) (w),
where I1, is a projection onto span; (r +e)
Acknowledgements and Disclosure of Funding
This work has received support from the Israeli Science Foundation (ISF) grant no. 2549/19 and grant no. 2188/20, from the Len Blavatnik and the Blavatnik Family foundation, from the Yandex Initiative in Machine Learning, and from unrestricted gift from Google. Any opinions, findings, and conclusions or recommendations expressed in this work are those of the author(s) and do not necessarily reflect the views of Google.

---

References
[1] I. Amir, Y. Carmon, T. Koren, and R. Livni. Never go full batch (in stochastic convex optimization). CoRR, 0as/2107.004665 2021.
[2] Amir, T. Koren, and R. Livni. SGD generalizes better than GD (and regularization doesn't help). In Conference on Learning Theory, 2021.
[3] K. Ball et al. An elementary introduction modern convex geometry. Flavors of Geomefry, 31:1-58, 1997.
[4] 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.
[5] L. Bottou, F. E. Curtis, and Nocedal. Optimization methods for large-scale machine learning. SIAM Review, 60(2):223- 311, 2018.
[6] O. Bousquet and A. Elisseeff. Stability and generalization. Journal of Machine Learning 2002.
Research,
[7] Bubeck, Jian. Y. Lee, Y. Sidford, et. Complexity highly parallel non-smooth convex optimization. Advances in Neural Information Processing Systems, 2019.
[8] Y. Carmon, J. C. Duchi, O. Hinder, and A. Sidford. Lower bounds for finding stationary points
I. Mathematical Programming, pages 1-50, 2019.
[9] Y. Carmon, A. Jambulapati, Q. Jiang, Y. Jin, Y. T. Lee, A. Sidford, and K. Tian. Acceleration with a ball optimization oracle. In Advances in Neural Information Processing Systems, 2020,
[10] A. Cotter, O. Shamir, N. Srebro, and K. Sridharan. Better mini-batch algorithms via accelerated gradient methods. In Advances Neural Information Processing Systems, 2011.
[11] A. Dauber, M. Feder, T. Koren, and R. Livni. Can implicit bias explain generalization? stochastic convex optimization as case study. In Advances in Neural Information Processing Systems, 2020.
[12] J. Diakonikolas and C. Guzmán. Lower bounds for parallel and handomized optiinzziinniii.. In Conference on Learning Theory, 2019.
[13] J. Duchi, E. Hazan, and Y. Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(7), 2011.
[14] C. Duchi, P. L. Bartlett, and M. J. Wainwright. Randomized smoothing for stochastic optimization. SIAM Journal Optimization, 22(2):674-701, 2012.
[15] V. Feldman. Generalization of ERM in stochastic convex optimization: The dimension strikes back. In Advances in Neural Information Processing Systems, 2016.
[16] J. Geiping, M. Goldblum, P. E. Pope, M. Moeller, and T. Goldstein. Stochastic training is not necessary for generalization. arXiv:2109. 2021.
[17] S. Gunasckar, J. D. Lee, N. Srebro, and D. Soudry. Implicit bias of gradient descent linear convolutional networks. Advances in Neural Information Processing Systems, 2018.
[18] C. Guzmán and A. Nemirovski. On lower complexity bounds for large-scale smooth convex optimization. Journal of Complexity, 31(1):1-14, 2015.
[19] M. Hardt, B. Recht, and Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International Conference Machine Learning, 2016.
[20] E. Hoffer, Hubara, and Soudry. Train longer, generalize better: closing the generalization gap in large batch training of neural networks. In I. Guyon, U. von Luxburg, S. Bengio, H. M. Wallach, R. Fergus, S. N. Vishwanathan, and R. Garnett, editors, Advances Neural Information Processing Systems, 2017.
10

---

[21] Z. Ji and M. Telgarsky. The implicit bias of gradient descent on nonseparable data. data. In Conference on Learning Theory, 2019.
[22] N. S. Keskar, D. Mudigere, J. Nocedal, M. Smelyanskiy, and T. Tang. On large-batch training for deep learning: Generalization gap and sharp minima. In International Conference on Learning Representations, 2017.
[23] M. Li, T. Zhang, Y. Chen, and A. J. Smola. Efficient mini-bateh training for stochastic optimization. In S. A. Macskassy, C. Perlich, J. Leskovec, W. Wang, and R. Ghani, editors, International Conference on Knowledge Discovery and Data Mining, 2014.
[24] Y. Li, E. 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.
[25] A. Nemirovski and D. B. Yudin. Problem complexity and method efficiency optimization. 1983.
[26] Y. Nesterov. Introductory lectures convexxoptimizaaain basic course, volume 87. Springer, 2003.
[27] Y. Nesterov. Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM Journal on Optimization, 22(2):341-362, 2012.
[28] Shalev-Shwartz, O. Shamir, N. Srebro, and K. Sridharan. Stochastic convex optimization. In Conference on Learning Theory, 2009.
[29] 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-255 2018.
[30] B. Woodworth and N. Srebro. Tight complexity bounds for optimizing composite objectives. In Advances in Neural Information Processing Systems, 2016.
[31] B. Woodworth, J. Wang, A. Smith, B. McMahan, and N. Srebro. Graph oracle models, lower bounds, and gaps for parallel stochastic optimization. In Advances in Neural Information Processing Systems, 2018
[32] J. Wu, W. Hu, H. Xiong, J. Huan, V. Braverman, and Z. Zhu. On the noisy gradient descent that generalizes sgd. International Conference on Machine Learning. 2020.
[33] Zhu, J. WU, Yu, Wu, and Ma. The anisotropic noise in stochastic gradient descent: Its behavior of escaping from sharp minima and regularization effects. In K. Chaudhuri and R. Salakhutdinov, editors, International Conference on Machine Learning, 2019.


Reviews:
[{"review_id": "YhHB7KGYoSQ", "reviewer": "Reviewer_XAZp", "summary": "\nThe paper provides a lower bound on the iteration complexity of any full batch algorithm in stochastic convex optimization. In particular, they show that for every T, there exists a function (which depends on T) for which the suboptimality in terms of excess risk for any full batch algorithm run for T steps is lower bounded by 1/T^{1/4}. The proof technique extends upon the lower bound construction of Amir et. al. 2021 [1] for the iteration complexity of GD algorithm, and is based on a span based argument. \n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I support accepting the paper. The main reasons for a low score are: \n\n(1. ) SGD vs ERM: We already know from earlier works that Empirical risk minimizing (ERM) solutions may fail to have low suboptimality at the population level (for eg. in [14], [25]).  Full batch descent algorithms find the ERM solution. I do not see a lot of motivation in proving lower bounds for algorithms which go towards solutions which we know may not generalize. \n\n(2.) Iteration complexity vs work: We know that SGD is statistically optimal for stochastic convex optimization. Furthermore, it is also optimal work wise. It is easy to see that running event 1 iteration of GD is as expensive as running SGD to convergence. Why should we care about lower bounds for full batch algorithms for which we already know that even 1 iteration is worse than the optimal and easy to implement algorithm. \n\n(3.) GD with projection vs without projection: In the paper, the authors run GD with projection and compare the suboptimality of the returned solution with the minimizer in the unit norm ball. In practice, we generally run SGD / GD without projection? Is there any hope to extend the lower bounds for full batch methods run without the projection step. \n\n(4.) Statement of the results: \n\n(a) The authors should add in the main body that the function depends on T (as the parameters and the problem dimension are chosen depending on the value of T).  \n\n(b) I am confused by the way the result is presented in Theorem 3.1. If we look at the proof at the end of page 9, we see that there is an extra \\beta-dependent term multiplying (1/4 - \\eps^2 T) which is data dependent. This term can be arbitrarily small and has been hidden in the proof of Theorem 3.1. One can simply get rid of this term by setting \\eps = 1/T^{1/4} which the authors should do. This would just give a lower bound of 1/T^{1/4} in Theorem 3.1. \n\nThe paper is well written otherwise. It might be useful to explicitly state the upper / lower bounds on \\gamma_1 and \\gamma_2 in various lemmas in the main body.  \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8-10 hours"}, "extra_text": {}}, {"review_id": "YcgHZqlC7-3", "reviewer": "Reviewer_s3Yy", "summary": "This paper considers a problem where one is trying to find an input that minimizes the expected value of a function that one has sample values of. Its goal is to show that algorithms that only have the ability to query the gradient of the average of the samples at specified points may need more queries than a function that can check the gradient on individual samples. In order to do that, the paper finds a class of probability distributions over functions for which any algorithm that gains information on the functions only by querying the gradient of the average of the sampled function needs $\\Omega(1/\\epsilon^4)$ queries to get within $\\epsilon$ of the minimum expected loss.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "As far as I can tell, this never actually proves that one can get a loss within $\\epsilon$ of the optimum in $o(1/\\epsilon^4)$ queries if one is not restricted to working with the averaged gradient, which means it does not actually prove the separation result in the abstract. The lower bound on the number of queries needed to get near the minimum is much less interesting without the contrast than it would be with it.\n\nThis appears to mostly use known techniques to prove the bound. The idea of bounding what one can learn from the gradient reminds me of statistical query bounds, although those would be weaker in that they would use a distorted form of the gradient. The organization is mostly fine, although separating the lemmas in section 4 from their proofs is confusing.\n\n----------------------------------edit--------------------------\n\nThe textbook the authors mention in their rebuttal contains the positive half of the separation. So, I am now recommending that this paper be accepted.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "9"}, "extra_text": {}}, {"review_id": "NBtJS_KnQF1", "reviewer": "Reviewer_ge1M", "summary": "In this paper the authors prove an error lower-bound for full-batch first-order algorithms. This is a generalization of the bound given in Bassily et al. [2]. This new bound of the authors\n- is true for a wider class of functions : GD and SGD, non-smooth and convex \n- implies that to get an $\\epsilon$-risk, full-batch methods require at least $\\Omega (1/\\epsilon^4)$ iterations\nThis shows the advantage of stochastic methods like SGD which only require $\\Omega (1/\\epsilon^2)$ iterations to reach the same risk.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The authors clearly explain the background of Stochastic Convex Optimization (SCO) and present existing results and bounds. The authors also underline the fact that their bound is valid for a large family of algorithms (GD, projected GD, with smooth or non-smooth regularization, etc).\nTo extend their results to general full-batch algorithms, they apply a classical technique described in section 4.3 where they use a random high-dimensional embedding and apply the previous bound on a modified objective.\n\n**Comment after rebuttal**\n\nIn view of the reviews and the discussions, the authors clarified their technical contribution compared to [1] and presented how this generalization could be applied to many 1st order methods including Nesterov's acceleration, CG etc.\n\nThus, I will increase my score to 7. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This paper is theoretical only. No experiments are provided, even to illustrate the different bounds.  \n\nThis paper is a bit out of my standard scientific scope. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "06BO2whB2NN", "reviewer": "Reviewer_aT3D", "summary": "This work studies the generalization performance of algorithms in stochastic convex optimization. Specifically, the authors study the full-batch algorithms where only full gradient and function value information are accessible. By constructing a hard instance of the objective function, the authors show that any full-batch algorithm needs at least $\\Omega(1/\\epsilon^4)$ iterations to obtain an $\\epsilon$-risk function, while stochastic algorithms such as SGD only need $O(1/\\epsilon^2)$. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper shows that there exists a separation between full-batch algorithms and stochastic algorithms in the generalization performance of empirical minimization. Such a separation has been well studied in the pure optimization setting, and this work is the first to study such a problem in the generalization setting. The presentation is clear and easy to understand. The proof is technically sound. Some of my comments are as follows. \n\n- It is a bit hard to tell the significance of the proposed result. On the one hand, the lower bound result reveals that full-batch algorithms will be sample-inefficient compared with SGD, which is not studied in previous works. On the other hand, such a phenomenon is not surprising, since similar separation results have already been studied in previous works studying optimization errors. The tool the authors used is standard (hard instance by  Nemirovski et. al), and it is not clear how the authors contribute given existing works.\n\n- For the use of random rotation matrices, there are some additional works studying optimization lower bounds which also use them. The authors may want to highlight these works in the main text. \n\n[1] Fang, C., Li, C. J., Lin, Z., & Zhang, T. (2018). Spider: Near-optimal non-convex optimization via stochastic path integrated differential estimator. arXiv preprint arXiv:1807.01695.\n\n[2] Zhou, D., & Gu, Q. (2019, May). Lower bounds for smooth nonconvex finite-sum optimization. In International Conference on Machine Learning (pp. 7574-7583). PMLR.\n\n[3] Arjevani, Y., Carmon, Y., Duchi, J. C., Foster, D. J., Srebro, N., & Woodworth, B. (2019). Lower bounds for non-convex stochastic optimization. arXiv preprint arXiv:1912.02365.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors discuss the limitations and there is no negative societal impact about their work. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hrs"}, "extra_text": {}}]

Author rebuttal:

Meta-review: During the discussion phase, all reviewers and the AC found the results are interesting and novel enough for a presentation at NeurIPS. The paper has presented some solid results and bring new insights about negative results of full batch methods.  


Decision: Accept (Poster)