An Even More Optimal Stochastic Optimization Algorithm: Minibatching and Interpolation Learning
Authors: Blake Woodworth
Nathan Srebro
Venue: NeurIPS 2021 Poster (2021)
Keywords: Stochastic
Optimization
Learning
Minibatch
Optimistic
Interpolation

Abstract: We present and analyze an algorithm for optimizing smooth and convex or strongly convex objectives using minibatch stochastic gradient estimates. The algorithm is optimal with respect to its dependence on both the minibatch size and minimum expected loss simultaneously. This improves over the optimal method of Lan, which is insensitive to the minimum expected loss; over the optimistic acceleration of Cotter et al., which has suboptimal dependence on the minibatch size; and over the algorithm of Liu and Belkin, which is limited to least squares problems and is also similarly suboptimal.  Applied to interpolation learning, the improvement over Cotter et al.~and Liu and Belkin translates to a linear, rather than square-root, parallelization speedup.  

An Even More Optimal Stochastic Optimization Algorithm: Minibatching and Interpolation Learning
Blake Woodworth
Nathan Srebro
Toyota Technological Institute at Chicago blake@ttic.
Toyota Technological Institute at Chicago nati@ttic.en
Abstract
We present and analyze an algorithm for optimizing smooth and convex or strongly convex objectives using minibatch stochastic gradient estimates. The algorithm is optimal with respect to its dependence on both the minibatch size and minimum expected loss simultaneously. This improves over the optimal method of Lan [17, which insensitive to the minimum expected loss; over the optimistic acceleration of Cotter et al. [T0]. which has suboptimal dependence on the minibatch size; and over the algorithm of Liu and Belkin [19), which is limited to least squares problems and is also similarly suboptimal with respect to the minibatch size. Applied interpolation learning, the improvement over Cotter et al.] and Liu and Belkin translates to a linear, rather than square-root, parallelization speedup.
Introduction
The massive scale of many modern machine learning models and datasets give rise complex, high- dimensional training objectives that can be very computationally expensive to optimize. To reduce the computational cost, it is therefore important to devise optimization algorithms that can leverage parallelism to reduce the amount of time needed to train. Stochastic first-order methods, which use stochastic estimates of the gradient of the training objective, are by far the most common approach and these methods can be directly improved by using minibatch stochastic gradient estimates, which are easy to parallelize across multiple computing cores or devices. Accordingly, we propose and analyze optimal accelerated minibatch stochastic gradient descent algorithm.
Our analysis exploits that while training machine learning models, is typically possible drive the loss either all the way to zero, or at least very close to zero, and the performance of our algorithm improves as the minimum value of the loss approaches zero. This property has multiple names in different contexts. In learning theory, it is common to show fast rates under the assumption of "realizabilitt"" meeiii
meaning the data can be fit perfectly by the model, i.e. the loss can be driven zero. Even when the problem is not exactly realizable, it is sometimes possible to derive "optimistic rates" that interpolate between fast rates for realizable learning and the slower agnostic rates (K In the context of "interpolation learning." there has recently been great interest in understanding training "overparametrized"
have many more parameters than there are training examples, generally meaning that many settings of the parameters would attain zero training loss both in terms
of optimization 2 9 [5] and generalization 66] 35 38). Finally, in the optimization literature, the minimum value of the objective
there have been efforts to prove optimistic rates depending
or on the variance of the stochastic gradients a the minimizer (TO, 19 23 31]. Regardless of
the name, these ideas are all based on the same fundamental concept of exploiting the fact that the minimum value of the objective is nearly zero
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Our contributions
In Section 3] we present and analyze an accelerated minibatch SGD algorithm for optimizing smooth and convex objectives using minibatch stochastic gradient estimates. Our method closely resembles the methods of Lan [17] and Cotter et al. [I0], but with different stepsizes and momentum parameters, and a tighter analysis. Importantly, our algorithm enjoys a linear speedup in the minibatch size all the way up critical threshold beyond which larger minibatches do not help. In contrast, Lan and Cotter et al.[s bounds have a worse, sublinear speedup and a correspondingly higher critical threshold.
In Section 4 we show that modified version of our algorithm can attain substantially faster convergence when the objective satisfies a certain quadratic growth condition, which is a relaxation of strong convexity. As part of our analysis, we simplify and generalize restarting technique
29 30,, which we show amounts to a reduction from strongly convex optimization to convex optimization. The reduction in the other direction is well-knowd tool in optimization analysis, but our result shows that it goes both ways and may be of more general interest.
1
18
24
26
In Se we prove that our methods are optimal with respect to both the minibatch size and also the minimum value of the loss in the settings we consider. We then explain how our guarantees demonstrate a linear speedup in the minibatch size, which improves over sublinear speedup in previous work
Finally, in Section we extend our results to a related setting where the bound on the minimum value of the loss is replaced by bound the variance of the stochastic gradients at the optimum [as in, e.g. 8 14 21 23 B1]. Under this condition, we establish the optimal error achievable by any learning rule, including non-firstoorder methods, and we show that the optimal convergence rate is nevertheless achieved by SGD-a first-order method without acceleration. Further, we show that the accelerated optimization rate, T-2, is unattainable using minibatches of size 1, but with larger minibatches, our accelerated minibatch SGD method can match the optimal error of SGD using a substantially smaller parallel runtime but the same number of samples.
2 Setting and Background
We consider a generic stochastic optimization problem min
(L(w) = Ez-d(((w;;)]] WERd
This problem captures, for instance, supervised machine learning where : = (x,y) is feature vector and label pair; {(wr (I, y)) is the loss of model parametrized by w that example; and [.ww) is the expected loss. We note that there are two possible interpretations of L depending on what D corresponds to. We can take D to be the uniform distribution over set of training examples, in which case L is the training loss. Alternatively, we can take D to be the population distribution, in which case L is the population risk. An advantage of the latter view is that optimization guarantees directly imply good performance on the population, however, computing an independent, unbiased stochastic gradient estimate requires fresh sample from the distribution, so only "one-pass" methods are possible. Nevertheless, our algorithm and analysis apply equally well in either viewpoint.
We consider optimizing objectives Rdd but we are most interested in dimension-free analysis, i.e. one that does not explicitly depend on the dimension, and our algorithm's 's guarantees hold even in infinite dimension. Indeed, in many applications including machine learning, the dimension can be very large, so an explicit reliance on the dimension would often lead to impractical bounds.
We study the family of optimization algorithms that attempt to minimize using T sequential stochastic gradient estimates with minibatches of size b of the form
((w) Σ Ve(we; for i.i.d. sl,...,, D
(2)
at points wi...., WT of the algorithm's choice. Later, will argue that our proposed method is optimal with respect to all of the algorithms in this family. Because it is easy to parallelize the computation of the b stochastic gradients in the minibatch, T roughly captures the runtime of the algorithm, while n = bT, the total number of samples used, captures its sample complexity.
In our analysis, we will rely on several assumptions about the losses l and the expected loss L.

---

Assumption 1. For almost every ~ D, f(w; 2) is nen-tiia convex, and H H-smooth w.r.t. w, i.e.
H
Vw,u,= ((;;2) + (Vl(u; =), u) s A(w; 2) ((u;)) (Vilu; w u.
2 1|10 ull
This assumption holds, for instance, for training linear models with smooth, convex, and non- negative loss function, as in least squares problems or logistic regression.
Assumption 2. The expected loss L is convex and has minimum value L = miny L(w). which is attained at a point w" with ||=*|| < B.
The minimum value of the loss, L", is the key quantity in our analysis, and we will prove an "optimistic rate" for our algorithm, meaning it performs increasingly well as I,* + 0. The key idea is to use L to bound the variance of the stochastic gradient estimates at the point w". Following prior we observe that under Assumptions [and] we can upper bound (see Lemma 3
work 110 32 33],
2
B| VI VL("") )|" S 2HL
The H- H--iipchhtzness of V allows to upper bound the variance of the stochastic gradients other, non-mininizing points w too. In contrast, a common practice in the optimization literature is to simply assert that the variance of the stochastic gradient estimates is uniformly upper bounded, i.c.
sup E [e(w; 2) V [[w)] < o²
(4)
This bound is very convenient, but it can fail to hold even in very simple cases like least squares regression, where the variance grows with ||]] Therefore, while faster rates may be achieved under the condition 4 this is quite strong and may not correspond well with problems of interest.
For many optimization problems, particularly those arising from training machine learning models, the minimum of the loss, L", can be expected be small. For example, machine learning models are often trained in the interpolation regime 42 6 15 35 388, where the training loss is under- determined, so there are many settings of the parameters which achieve exactly zero training loss. When D is the empirical distribution (see above), the interpolation regime therefore corresponds to L" 0. However, even if D is the population distribution, machine learning problems are often realizable, or nearly realizable, meaning the population risk can also be driven to zero or close to it.
In the optimization literature, it is often possible show enhanced guarantees under the favorable condition of X-strong convexity. However, the assumption of strong convexity is somewhat at odds with our goal of studying the interpolation or pear-interpolation setting. For example, the simplest example of interpolation learning is underdetermined least squares, where the number of observations is less than the dimension; in this case, the empirical covariance is degenerate so the problem is not strongly convex. Furthermore, assuming strong convexity and L Ro O and 8 is non-negative is very strong, and puts very strong constraints on the objective function which may often fail hold.
We consider instead a relaxation of strong convexity, which only requires the objective to grow faster than the squared distance to the set of minimizers, which need not be singleton 77 22 This condition does hold for underdctermined least squares- -with À equal to the smallest non-zero eigenvalue of the covariance- and for many other problems with non-unique minimizers, and it turns out to be sufficient to achieve the faster rates that typically arise from strong convexity.
Assumption 3. The expected loss L is convex; it has minimum value L min L(w); L(0) L A; and L satisfies the following growth condition for all w:
A
L(w) L'
>
min w Earg min L(w) ||w
1²
Related Work
The foundation of much of the work on optimal stochastic optimization algorithms the accelerated
SGD variant, AC-SA, of Lan [17]. This algorithm is analyzed in a different setting, where L is H-smooth, B-bounded, and convex and where the stochastic gradients have uniformly bounded variance 4 and under these conditions, it is optimal, with guarantee
HB²
oB
EL( L c.
+
(5)
T2
VTT
3

---

Algorithm Accelerated Minibatch SGD
wo Wg =
for 1 = 0, 1,l..... T - do
8 = 1 + and it = (tt + 1) for y = min 12H 24H(T+1)* > V
6.2a
HL*T8
# md 3, + (1 3r Du,
#++1 uh Ya9h (1:t where ge (wffd) 1/ Ei= Vilup ; 2/) for i.i. 21, 2,....,24 -p- ~
Wi+1 min L, 1 Wc+1
1++ = 1,,'ua w++1 + (1 Br y
Return: t
In our setting, however, there is no such explicit bound on the gradient variance, and at the same time, Lan's s analysis does not exploit the bound on L* to achieve better rate. Under our Assumptions |
and it is possible to derive a variance upper bound o² 2 B² + 4HL", which yields
HB² T
HB
HB bT
( - L c
VUT +
(6)
The first and third terms of this bound are tight, but we will later show that this guarantee is suboptimal because the denominator of the second term can be improved to bT. When L* Rs H H2 largest possible value of L* under mild condition:] we will later show that this bound is tight, so we can interpret this modification of Lan]s guarantee as being optimal only when L is large.
In other, more directly comparable existing work, Cotter et al. [0] propose and analyze a minibatch SGD algorithm and an accelerated variant similar AC-SA under Assumptions T and 2 Their accelerated method is guaranteed to achieve suboptimality
HB² T
HB²
HB²
MogT 5T
H bT
BL(w) - L'
cc Sc.
+
+
+
VOT
In the special case of b = 1, we will show that this is optimal (up to minor vlog T factor). However, the VbT dependence in the second term can be improved to bT, so Cotter et al. analysis suboptimal when b 1. We also extend our analysis to the Assumptions and
In other related work, Liu and Belkin 19 propose a different minibatch accelerated SGD method. In the special case of least squares objectives where E(w; (ar, y)) ((w, æ) y) that also satisfy Assumptions and with L O, they show that their algorithm attains suboptimality
d H
c'XvbI H
EL(() L' c.
Axp
+ + exp
(8)
As with Cotter et al., we show that the VbT dependence of this guarantee is suboptimal and can be improved to 17. In addition, our analysis goes beyond the special case of least squares with L
In other related work, Bassily al. [5] study non-accelerated algorithms in similar setting. Zhang et al. [40] consider related setting where the losses l are Lipschitz rather than smooth, and where the dimension of the problem is sufficiently small relative to the other problem parameters. Zhang and Zhou (39] study our smooth setting but with an additional restriction that e is Lipschitz and L strongly convex, but show only polynomial convergence versus our linear convergence. Srebro et al. [33] study the performance of the empirical risk minimizer under Assumptions I and as well as stochastic first-order methods with 1; their methods are optimal for b = 1, but they do not analyze the effect of the minibatch size. Vaswani et al. [36] consider different noise assumption, which is similar to requiring I."
TTee minimum 1 - <OHBB²), for example, when flw; is realized within ball of radius O(B).

---

3 A Better Accelerated Minibatch SGD Method
Our Algorithm T is very similar to the AC-SA algorithm of Lan 17 and to the AG algorithm of Cotter et al. [TO]; the difference is that we use different stepsize and momentum parameters and provide a tighter analysis for our setting. Our method provides the following guarantee:
Theorem 1. Let and I. satisfy Assumptions 7 and 2
then Algorithm guarantees for a universal
constant c
H T2
HB²
HB bT
EL(w L' ce
bT
We prove this Appendix A using similar approach as the analysis for AC-SA of Lan [7]. As discussed previously, Lan analysis relies on a uniform upper bound on the stochastic gradient variance on the set {w : |||| I B). While an upper bound can be derived in our setting, it resembles H B² which is too large to achieve good performance. Our analysis, in contrast, exploits the fact that the points wo..... ..... - at which the stochastic gradients are actually computed approach w" as the algorithm proceeds, which implies that the stochastic gradient variance decreases over time. It difficult to identify precisely why our analysis improves in its dependence on the minibatch size, b, compared with Cotter et al.'s bound. However, the primary difference between our analyses is that Cotter et al. use stepsizes " x t" for < 1. while our stepsizes scales linearly with t. Our choice leads to somewhat simpler computations, which may explain our tighter bound.
4 The Reduction and Faster Rates
Our algorithm can also be extended the setting of Assumptions [ndd 3 using restarting argument
The proof is based on simple idea, which we will show amounts to reduction from strongly convex optimization to convex optimization. However, previous applications of restarting schemes tend to involve relatively complex and specialized proofs. Here, we simplify and generalize the approach, and we present it in a way that will hopefully be convenient for future use. We then apply it to provide enhanced guarantee for Algorithm under Assumptions [ariipttioos[nn[]]]]]]
113 18 24
26
29 3Q
Convex optimization algorithms guarantee reducing the value of the objective by an amount that depends on some measure of the distance between the initialization and a minimizer of the objective. The key idea in the analysis that when the objective X-strongly convex, reducing the value of the objective implies reducing the distance to the minimizer:
w0 2(L(w) L*)
|/ fw--w112
X
Therefore, if we apply an algorithm for convex objectives to strongly convex objective several times in succession, each time reducing the suboptimality by a constant factor, then (1) roughly log 1 applications will suffice to reach e-suboptimality and (2) reducing the suboptimality by a constant factor will get no harder with each application since the distance to the optimum is decreasing. Using this idea allows us take algorithm with guarantee for convex objectives and derive an algorithm with a corresponding, better guarantee for strongly convex objectives. We also show that strong convexity can be replaced by weaker condition that generalizes Assumption 3
In order to present the reduction, we first define Definition 1. Given ub I - R4, we say that L satisfies the (A, (,.4)-8m --rowrhhhh condition (hereafter () for all w
L(w) La 2 (x((w)
| ||w w ||3 is equivalent to A-strong convexity, and the condition in Assumption 3 is equivalent to the (A, )CC for (ww) = arg min min, L(w) I|w
For example, the (A, GC for (w))
w 11 The second ingredient of the reduction is the "time" needed by an algorithm to optimize convex or strongly convex objectives:
Definition 2. Let L be any set of convex functions. We define Time(c, B, w. C. A) to be the time needed by the algorithm to find a point with EL(w)) - -L* S e given a point wi with Eap(wa) S B, for any L E L. Similarly, we define Timex (e, A, v. A) to be the time needed by A to find t with B.I(W)) L S given a point we with E. (Wo) I," < A, for any L that also satisfies the (X, GC.
5

---

Algorithm 2 GC2Cvx(A,
Given: Wy s.t. EL wb) - A
for t = 2, , = [logs A do
Set w/ to be the output of A initialized a Wt-1 after 02- ,,,,,, Return WT
We are deliberately vague about the precise meaning of "time" here. Typically, it would correspond to the number of iterations of the algorithm, it could also count the number of times the algorithm accesses a certain oracle, even the wall-clock time of an implementation of the algorithm, but it can correspond to essentially any (subadditive) property the algorithm. With these definitions in hand, we present the reduction, Algorithm which guarantees:
Theorem 2. For any algorithm A and 0 1, GC2Cvx(A, 0) defined in Algorithm guaranttess
[oge A1
Time p-' 01- A A U, (.A.A)
Timex A, C, GC)) <
We prove this very concisely in Appendix B and also discuss several example applications of the Theorem in order to give better sense of how it can be applied. This reduction complements standard tool in the optimization toolbox, which goes in the opposite direction. Specifically, it is very common to take an algorithm for optimizing A-strongly convex objectives and apply convex objectives by optimizing the X-strongly convex surrogate [x(w) L(w) + 3 [| 12. Sometimes, this approach is slightly suboptimal, and the similar, multistep procedure of Allen-Zhu and Hazan [ required, nevertheless, it already known that strongly convex optimization is, for this reason, "casier" than convex optimization. Our result shows that the reverse is also true, so strongly convex and convex optimization are, certain sense, equally hard.
In combination, these two reductions going in each direction appear to be optimal in a certain way. In all of the examples we have tried, composing both reductions converting convex algorithm to a strongly convex one, and then converting that strongly convex algorithm back to convex one- results in only that applying the reduction, Algorithm to an optimal algorithm for convex optimization yields an optimal algorithm for strongly-convex optimization, and conjecture that this holds universally.
monstant-factor degradation in the guarantee. We have also consistently observed
Before moving on, we note that the reduction Algorithm 2 can result in an unusual method. For example, the algorithm GC2Cvx(A Alg e) analyzed below involves repeated invocations of Algorithm 1 resulting in the stepsize and momentum parameters being reset periodically. As whole, resembles Algorithm however it has strange, monoonnt stepsize and momentum schedule. Therefore, while this technique can be useful for deriving new optimization algorithms with better theoretical guarantees, these methods may not always be aethetically pleasing practical, and it may still be useful to study more "natural" methods that can be directly analyzed under the (A, JCG
Finally, we apply Theorem 2 to Algorithm and derive the following stronger guarantee under Assumptions and which we prove Appendix C
Theorem Let and satisfy Assumptions and then the output of GC2Cvx(AIg e) guarantees for universal constants c,
c' d'VXT'
c
HL
BL(w) - La sc. Sc.
A
+ A exp
VH
H
XOT
5 The Optimality of Our Algorithms
Here, we argue that the guarantees in Theorems and 3 are optimal. First, it is well-known that even without any noise, i.c. (ww32) = L(w), any first-order method will have error at least (25
HB²
VXT
L(W) - L* 2 c:
or L(w)- L" c. c. Aexp
-
(10)
T
VH

---

under Assumptions andd2 or Assumptions 1 and 3 respectively (in fact, the latter holds even under the stronger condition of X-strong convexity), Therefore, the first terms our method's guarantees in Theorems] and 3 are tight, and correspond to the rate achieved by accelerated gradient descent [28]
For the remaining second and third terms in each guarantee, we prove lower bound that applies for any learning rule that uses nt i.i.d. samples from the distribution, even non-first-orde methods. This lower bound also applies minibatch first-order algorithms with n 6I' being the total number of stochastic gradient estimates, since each V =) is computed using a single sample.
Theorem 4. For f(w; (x: y)) 2 ((u,, x) - u)² the square loss, for any learning algorithum that takes samples as input, there exists distribution over (x,y) pairs such that & and L satisfy Assumptions for universal constant c, the algorithm's 's output will have error at least
7 andd 2
HB²
HBL
EL ④
L* 2
T2 +1
T
Similarly, there exists a distribution over (z, y) pairs such that and L satisfy Assumptions and (and, in fact, I, is X-strongly convex), and for universal constant c, the algorithm's 's output will have error at least
EL(Ø) - I. c ( 11.1n5g (A...AA.15.
HHL
+ +min
An
We prove this in A using an argument similar to that of Srebro et al. [33] The lower bound for deterministic first-order optimization, (IO), plus the sample complexity lower bound, Theorem together imply a lower bound for the minibatch first-order algorithms that we consider, which matches our guarantees:
Corollary 1. There exists f(w; 2) such that for any algorithm that uses T minibatch stochastic
gradients of size b. there exists distribution over such that & and L satisfy Assumptions Aand and for universal constant c, the algorithm' output will have error at least
HB²
HB²
HB2L"
EL( - -
T
bT
bT
Similarly, there exists E(w; 2) such that for any algorithm that uses minibatch stochastic gradients of size b, there exists a distribution over such that l and L. satisfy Assumptions ① Mand fand, in fact, is X-strongly convex), and for universal constants c, c', the algorithm's output will have error at least
- AASpl
-d.
VXT VH
HL XBT A))
+1. STS + min
It is easy see that this precisely matches our algorithm's guarantee, Theorem I. under Assumptions I and 2 and therefore our algorithm is optimal in that setting. Under Assumptions and this Tower bound and the upper bound, Theorem 3 nearly match, with the only difference being the terms exp( c'-AbT" in the upper bound versus 1 # in the lower bound. However, this gap is
small for bT I 2X exp( e'AATT) ), is at most 1, so the upper bound is within a constant factor of H
the lower bound. For bT 2X. exp( 2'-6T') = is obviously more than constant factor larger than Aurs H = 0, but it is nevertheless exponentially small, so the gap between the upper and lower 2g bound is still nearly negligible.
We note that because Theorem Dapplies any learning rule that uses bT i.i.d. samples, not just first-order methods, if the second and third terms of our algorithms' guarantees are larger than the first terms, then our methods are actually optimal amongst all learning rules. Therefore, for small enough 6, our first-order algorithm is just as good, in the worst case, as any other method including, for example, exact (regularized) empirical risk minimization.
Finally, in the special case that 1, while is true that our minibatch accelerated SGD algorithm is optimal- even amongst all learning rules that use = bT T samples, it is also the case that plain old SGD is also optimal, which guarantees under Assumptions [ndd] [00
HB²
H
EL ④b)
L S c.
+
(11)
T
6T
7

---

matching the lower bound, Theorem with n = bT T. In other words, the novelty and advantage of our method appears primarily through in how leverages minibatches achieve better performance and smaller parallel runtime, as we will now discuss.
6 The Minibatch Parallelization Speedup
Previously, we showed that our algorithms optimal in terms of their upper bounds the error as a function and L" Here, we consider the related question of the algorithm's 's runtime. Since is easy to parallelize the computation of minibatch stochastic gradients of size b, the total runtime of minibatch first-order method scales in direct proportion to T, but may grow much more slowly with aaand it may not grow at all if b parallel computers available. Specifically, if M computing cores or devices are available to parallelize the minibatch computations, then any minibatch first-order algorithm's 's runtime would scale with
Runtime Tx x
Time to compute Vε(u;; 2)
(12)
M
For this reason, it is natural to ask to what extent we can reduce the runtime without hurting performance, i.e. how much we can reduce the number of iterations, T, by increasing the minibatch size, b. To answer this question, it will be convenient to rewrite our guarantees in Theorems T and by
fixing the error, e, and asking how large T must be in order to guarantee error e. Under Assumptions and Assumptions and respectively, this is (ignoring constants)
andd 2
HB²
HB²
HB
T(c)
(13)
E
H
HL*
T())
log
( log
(14)
b
Ac
Written this way, it is easy to see that the number of iterations needed by our algorithm to reach accuracy decreases linearly with the minibatch size b up until the first term becomes larger than the second and third terms. Although it may not be practical to fully parallelize the computation of the minibatches across b workers for large b, this nevertheless represents substantial potential speedup with absolutely no cost to the algorithm's 's theoretical guarantees 100 11, which continues until
HB2
L
H
VHL
b2
33/2 and
b
(15)
cVAlog A
Once b passes these thresholds, no more improvement is possible by increasing the minibatch size, and the iteration complexity is dominated by the first term, which corresponds to the time needed to reach e error using exact accelerated gradient descent (28). In other words, once the minibatch size is this large, the algorithm performs essentially the same if there
no noise in the gradients.
Our algorithms' speedup from minibatching improves significantly over previous results. As men- tioned in the previous section, while SGD can attain the same error as our method using the same total number of samples, n 17, it can only do so with b = 1, and the number of iterations it requires to attain error under Assumptions D and 2 is (ignoring constants) [0
T(c) H
1 L.
(16)
b 2²
Comparing this with our method [3)), we see that SGD always requires at least as many iterations, and quadratically more for large b. In fact, in the case L- = 0. SGD sees speedup at all from
minibatching, whereas our method can be sped up substantially.
Improving over SGD, the minibatch accelerated SGD algorithm of Cotter et al. 10 requires under Assumptions [ and 2 (ignoring constants and log factors)
HB²
1
HB²
1 LB
T(c)
(17)
vb
2
Therefore, their analysis exhibits three regimes rather than our two: first linear 1/b speedup for b < 1 222 then 1/ Vb speedup for
2
HB²
L
<b<
+
(18)
3/2
E
8

---

and finally no speedup for larger b. Therefore, even under the favorable condition that L = 0. Cotter al.j' method has sublinear parallelization speedup from minibatching, and consequently, their method can result in a substantially smaller speedup than ours for any particular minibatch size. The minibatch size they need to reach error in /HB²/c /c iterations optimal number for first-order methods, which corresponds to exact accelerated gradient descent-is the righthand side of (18). which can be larger by a factor of as much as /²ee/e.
and in the special case of least squares problems, the algorithm and analysis of Liu and Belkin 19 exhibits similar sublinear speedup from minibatching:
Similarly. under Assumptions I and 3
V x log vb
H A H log
H
A
IHL
T(c)
(19)
bbb xe
Like with Cotter et al.Js analysis, compared with our method, which enjoys a linear speedup all the way up to the critical minibatch size, we see that Liu and Belkin algorithm has only a 1/v/ speedup in some regimes, it can require much larger minibatches match accelerated gradient descent.
7 Stochastic Optimization with Bounded Variance at the Optimum
So far, we have considered optimizing objectives where the instantaneous losses are non-negative and the value of the minimum of the expected loss is bounded and small, but in other contexts we may want to understand the complexity of optimization in terms of bounds on the variance of the stochastic gradients. In particular,
increasingly common in the optimization literature to assume bound on the variance of the stochastic gradient estimates at the minimizer of the objective, i.e. V[[ =)1 < o².
In Appendix E. we extend our analysis to this setting, with of essentially replacing the quantity 2/H L all of our results far. The main result Theorem 5 in which we prove that in this setting our algorithm guarantees error
HB2 T
HB²
o.B
22 E LL c.
(20)
bT
in the convex setting, and its modification with Algorithm 2 guaarantess error
c'
d'vXT VH
d'AbT')
BL( - I.- c.c A exp
Aexp
A exp
(21)
H
with the relaxed notion of strong convexity from Assumption 3
We also show lower bounds in Corollary 2 confirming that our method is minimax optimal under these conditions.
8 Conclusion
We proposed and analyzed minibatch accelerated SGD algorithm for optimizing objectives whose minimum value is near zero. We show that our method is simultaneously optimal with respect to the minibatch size, b, and the minimum of the loss, L*. which improves over previous results including Cotter et al. [0] and Liu and Belkin [19 which were optimal with respect to L* but not b, and Lan [1 which was optimal with respect
but not Lt* Section (6, we describe how our method's 's improvements over prior work, which takes the form of better dependence on the minibatch size, b, translates into the potential for a substantial reduction in the runtime via parallelizing the computation of the minibatch stochastic gradients. Finally, extend our results to the closely related setting where the L bound is replaced by a bound on the variance of the stochastic gradients at the point w", specifically, and tightly characterize the minimax optimal rates in this setting. Our algorithm and analysis is of particular interest in the context of training machine learning models in the "interpolation//tee r'eaiiiizalll" "awaliizabeee/ooveere /'ovrrparametrized setting, where there exist parameters that exactly or nearly minimize the training and/or population loss, i.e. L and a, are small.
A shortcoming of our method is that its implementation, specifically setting the stepsizes, depends on potentially unknown quantities such as I." and B, and on the time horizon T. The dependence on I' is not particularly serious problem because it is straightforward to convert method to an

---

anytime algorithm using the classic "doubling trick", although this is not very practical and it would be interesting to develop an anytime variant of Algorithm I
On the other hand, the requirement of knowing I. and B to implement the algorithm is a trickier issue. This problem is not unique to our method, and most of the accelerated stochastic first-order methods that we are aware of, including the work of Lan [17] and Cotter et al. [10], use these parameters choose stepsizes and momentum parameters. While these quantities are generally unknown, our algorithm only needs an upper bound on them, so for any known upper bound 7, L" and B > B, our algorithm be implemented using the estimates 1." and B, with corresponding degradation in the guarantee depending on how tight the upper bounds are. Furthermore, when applying stochastic first-order algorithms in practice, one typically sets stepsize parameters via cross- cross-validatie validation rather than according to the theoretical prescriptions, so this may not be a big issue in practice.
Acknowledgments and Disclosure of Funding
We thank Ohad Shamir for several helpful discussions in the process of preparing this article, and also George Lan for a conversation about optimization with bounded σ... BW is supported by a Google Research PhD Fellowship, and this work was also supported by NSF-CCF/BSF award 1718970/0067411 and was done as part of the NSF-Simons Funded Collahoration on the Foundations of Deep Learning thttps://dent //eepf oondatioonns ai//
Additional revenues related to this work: BW consultant at Google on issues related to the project, and was also hosted by Microsoft.
intern at Google Research. NS was a paid
References
[1] Zeyuan Allen-Zhu and Elad Hazan. Optimal black-box reductions between optimization objectives. In D. Lee, M. Sugiyama. Luxburg, I. Guyon, and R. Garnett, editors. Advances in Neural Information Processing Systems, volume 29, Curran Associates. Inc., 2016. URL (htpps: / h/tp://ee/occogooo neurips cc/papper/216/file///eeeee /t0.://0000000000000000077566553
Paper- pdf
[2] Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparameterized neural networks, going beyond two layers. arXiv preprint arXiv: 1.0418,, 2018.
[3] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. convergence theory for deep learning via over- parameterization. In International Conference on Machine Learning, pages 242-252. PMIR, 2019.
[4] Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning, pages 322-332-3333 -32.. PMLR, 2019.
[5] Raef Bassily, Mikhail Belkin, and Siyuan Ma. On exponential convergence of sgd in non-convex over- 2018
parametrized learning. arXiv preprint
[6] Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine-learning practice and the classical bias-variance tradc-off. Proceedings of the National Academy of Sciences, 116 (32):15849-1588) 2019.
[7] Jérôme Bolte, Trong Phong Nguyen, Juan Peypouquet, and Bruce W Suter. From error bounds to the complexity of first-order descent methods for convex functions. Mathematical Programming, 165(2): 471-507. 2017.
[8] Léon Bottou, Frank Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. Siam Review, 60(2):223-111, 2018.
[9] Lénaic Chizat, Edouard Oyallon, and Francis Bach, On lazy training in diffcrentiable programming. Advancex in Neural Information Processing Systems, 32:2937-2947, 2019.
[10] Andrew Cotter, Ohad Shamir, Nati Srebro, and Karthik Sridharan. Better mini-batch algo- rithms via accelerated gradient methods. In Shawe-Taylor, R. S. Zemel, L. Bartlett, F. Pereira, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems Curran Associates, Inc., 2011. URL htttp://pppers... cas.psccc/pppee. 4432- better- mini batch- algori femrithmm-ae via- accelerated- www.ggertdeeetieeeeee pdf
24. pages
10

---

[11] Ofer Dekel, Ran Gilad-Bachrach, Ohad Shamir, and Lin Xiao. Optimal distributed online prediction using mini-batches. Journal Machine Learning Research, 13(Jan):165-200 2012.
[12] Dmitriy Drusvyatskiy and Adrian S Lewis. Error bounds, quadratic growth, and linear convergence of proximal methods. Mathematics of Operations Research, 43(3):119 948, 2018.
[13] Saced Ghadimi and Guanghui Lan. Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization, ii; shrinking procedures and optimal algorithms. SIAM Journal on Optimization, 23(4):2061-200 2013.
[14] Robert Mansel Gower, Nicolas Loizou, Xun Qian, Alibek Sailanbayev, Egor Shulgin, and Peter Richtárik. Sgd: General analysis and improved rates. In International Conference on Machine Learning, pages 2200-5200 PMLR, 2019.
[15] Arthur Jacot, Franck Gabricl, and Clément Hongler. Neural tangent kemnl: convergence and generalization in neural networks. Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 8580-888 1000-8889,77 2018.
[16] Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian Stich, unified theory of decentralized sgd with changing topology and local updates. In International Conference on Machine Learning, pages 5381-5393, PMLR. 2020.
[17] Guanghui Lan. An optimal method for stochastic composite optimization. Mathematical Programming, 133(1-2):366 397, 2012. URL pttps://pods..somattccccttt .ww.o//rrr.rrrroooooooo.oo 1621/
[18] Qihang Lin and Lin Xiao. An adaptive accelcrated proximal gradient method and its homotopy continuation for sparse optimization. International Conference on Machine Learning, pages 73-81. PMLR, 2014.
[19] Chaoyue Liu and Mikhail Belkin. Mass: an accelerated stochastic method for over-parametrized learning. arXiv preprint arXiv: 1810,1399, /3395, 2018.
[20] Siyuan Ma. Raef Bassily, and Mikhail Belkin. The power of interpolation: Understanding the effectiveness of sgd in modern werrpaaameerriee learning. In International Conference on Machine Learning, pages 3325-3334. PMLR, 2018
[21] Eric Moulines and Francis Bach. Non- Non-asymptotic analysis of stochastic approximation algorithms for machine learning. Advances neural information processing systems, 24:451-459, 2011.
[22] Ion Necoara, Yu Nesterov, and Francois Glineur. Linear convergence first order methods for non-strongly convex optimization. Mathematical Programming. 175(1):69-107, 2019.
[23] Deanna Needell, Rachel Ward, and Nati Srebro. Stochastic gradient descent, weighted sampling, and the randomized kaczmarz algorithm. Advances in neural information processing systems, 27:1017-1025. 2014.
[24] Arkaddii S Nemirovskii and Yu E Nesterov. Optimal methods of smooth convex minimization. USSR Computational Mathematics and Mathematical Physics, 25(2):21-30, 1985.
[25] Arkadii Semenovich Nemirovsky and David Borisovich Yudin. Problem complexity and method efficiency in optimization. 1983.
[26] Yu Nesterov. Gradient methods for minimizing composite functions, Mathematical Programming, 140(1): 125-161, 2013.
[27] Yurii Nesterov. Introductory lectures on convex optimization: basic course. 2004.
[28] Yurii E Nesterov. method for solving the convex programming problem with convergence rate o (1/k" 2). In Dokl. akad. nauk Sssr, volume 269, pages 543-547 1983.
[29] James Renegar and Benjamin Grimmer. simple nearly optimal restart scheme for speeding up first-order methods. Foundations of Computational Mathematics, pages 1-46, 2021.
[30] Vincent Roulet and Alexandre d' Aspremont. Sharpness, restart, and acceleration. SIAM Journal on Optimization, (0(1):26--288) 2020.
[31] Mark Schmidt and Nicolas Le Roux. Fast convergence of stochastic gradient descent under strong growth condition. arXiv preprint 1308.1130..3311 2013.

---

[32] Shai Shalev-Shward and Yoram Singer. Online learning: Theory, algorithms, and applications. 2007.
[33] Nathan Stebro, Karthik Sridharan, and Ambuj Tewari. Optimistic rates for learning with a smooth loss. arXiv preprint 1009:3000 2010.
[34] Sebastian Stich. Unified optimal analysis of the (stochastic) gradient method. arXiv preprint 1Xiv:1907.04232,2222 2019.
[35] Alexander Tsigler Peter Bartleu. Benign overfitting ridge regression. arXiv preprint wrXiv:2009.14280 2020.
[36] Sharan Vaswani, Francis Bach, and Mark Schmidt. Fast faster convergence of sgd for over- parameterized models and an accelerated perceptron. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1195-1204. PMI.R, 2019.
[37] Blake Woodworth, Kumar Kshitij Patel, and Nathan Srebro. Minibatch vs local sgd for heterogeneous distributed learning. arXiv preprint wrXiv:2006.047355 2020.
[38] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint 16/iv:6611.03552 2016.
[39] Lijun Zhang and Zhi-Hua Zhou. Stochastic approximation of smooth and strongly convex functions: Beyond the (1/tt) convergence rate. Conference on Learning Theory, pages 3160-3179. PMI.R 2019.
[40] Lijun Zhang, Tianbao Yang, and Rong Jin. Empirical risk minimization for stochastic convex optimization: o(1 /mm)-and o(1/n") )-type of risk bounds. Conference on Learning Theory, pages 1954-1979. PMLR, 2017.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL.? [No]
(d) Did you discuss whether and how consent obtained from people whose data you's 're
using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
12

---

(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "v5R9pRqR1Fr", "reviewer": "Reviewer_GtzK", "summary": "This paper studies an accelerated stochastic gradient method with minibatching for expected risk minimization problems and provides the optimal convergence rate. Remarkable points are that (i) the dependency of the obtained rate on the minibatch size is also optimal, meaning the linear speedup by increase the minibatch size, and (ii) the rate reflects the acceleration due to the interpolation by evaluating the variance at the solution using the optimal value of the objective.", "questions": "", "limitations": "", "rating": 7, "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": "[Contributions]\n\nSince the minibatching technique is frequently adopted in machine learning applications, the research into minibatch efficiency is important. In addition, relaxation of the uniform boundedness assumption on the noise is also an interesting topic. In this context, I think this study makes a good contribution. Concretely, the method achieves the optimality regarding the number of iterations $T$ and the minibatch size $b$ and shows the acceleration due to the interpolation by taking into account the optimal value of the objective.\n\nAccelerated stochastic gradient methods for the expected risk minimization were studied in Lan [14] and Cotter et al. [8]. Compared to these studies, the obtained rate has advantages as follows: \n\n- The rate in Lan [14] is optimal in $T$ but is suboptimal in $b$. Moreover, there is no acceleration due to the interpolation because [14] uses the uniform boundedness on the noise instead of the evaluation of the noise at the optimal solution.\n- The rate in Cotter et al. [8] is optimal in $T$ and accelerated by the interpolation, but is suboptimal in $b$.\n\nHence, I think this submission makes a certain contribution in the context.\n\n[Additional references]\n\nThere are several missing references. \n\nFor finite-sum problems, some methods achieve the accelerated convergence rate and linear speed up by the minibatching simultaneously. For instance, see the following papers:\n\n- Z. Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods, 2017.\n- T. Murata and T. Suzuki. Doubly accelerated stochastic variance reduced dual averaging method for regularized empirical risk minimization, 2017.\n- A. Nitanda, T. Murata, T. Suzuki. Sharp Characterization of Optimal Minibatch Size for Stochastic Finite Sum Convex Optimization, 2019.\n\nThe minimum minibatch size to achieve the optimal iteration complexity was discussed in the last paper. \n\nThe linear speedup by increasing minibatch size up to a certain size was shown for SAGA in the following paper, although they only consider the non-accelerated method.\n\n- N. Gazagnadou, R. M. Gower, and J. Salmon. Optimal Mini-Batch and Step Sizes for SAGA, 2019.\n\nAcceleration due to the interpolation was also considered in the relaxed condition, i.e., PL-condition in the following:\n\n- R. Bassily, M. Belkin, S. Ma. On exponential convergence of SGD in non-convex\nover-parametrized learning, 2018.\n\nThe faster convergence under strong and weak growth conditions was shown in \n\n- S. Vaswani, F. Bach, and M. Schmidt. Fast and Faster Convergence of SGD for Over-Parameterized Models (and an Accelerated Perceptron), 2018.\n\nThese conditions are closely related to the interpolation.\n\nMoreover, an extension of the weak growth condition, which does not require perfect interpolation was also considered in \n\n- R.M. Gower, N. Loizou, X. Qian, A. Sailanbayev, E. Shulgin, and P. Richtarik. SGD: General Analysis and Improved Rates, 2019.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately addressed the limitations and potential negative social impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "UpHzkl3gaSP", "reviewer": "Reviewer_1bhL", "summary": "This paper studies the behavior of accelerated minibatch SGD under smoothness, bounded variance of gradient at optimum and/or quadratic growth assumptions. They also provide a meta algorithm to generate fast methods of solving convex optimization problems satisfying growth conditions from methods of solving convex problems without growth conditions.", "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 is technically sound and clearly written.  \n\nStrengths:\n1. Analysis of minibatch accelerated gradient methods under a slightly different set of assumptions with justification using examples for those assumptions.\n2. A general technique to create algorithms for problems satisfying growth conditions using known algorithms to minimize convex functions.\n3. They also provide lower bounds showing optimality of convergence rates.\n\nWeaknesses: (in decreasing order of importance)\n1. Although the assumption of bounded variance of the gradient only at optimum is weaker than having bounded variance of the gradient at all points, the assumption of having each sample function being smooth is stronger than having only the population function being smooth as is in some of the referred papers. It is unclear to me why one set of assumptions is better than the other. The only example explaining the assumption is that of least squares regression, but having $||w^*|| \\leq B $, we can upper bound the dependence of the gradient on $||w||$ by considering a bounded domain. More examples showing the benefits of this set of assumptions compared to the previous ones would be useful.\n2. It is not very clear to understand what is the one line message of the paper. It seems like having 3 seemingly disjoint contributions, especially section 7, which seems a bit disconnected from the rest of the paper. Some effort can be made to make the paper gel together better.\n3. Interpolation problems are only defined in the special case when $\\mathcal{D}$ is the empirical distribution and not for the general case. Having interpolation problems in the title is slightly misleading because this can confuse the reader regarding whether the results hold only for ERM or for population loss minimization. Either having a general \\textit{definition} of interpolation problems and checking whether the results go through for that or removing the stress on interpolation problems would be useful.\n3. Some of the results are not compared to related work on methods for interpolation problems with growth conditions listed below:\n\n[1] D. Davis and D. Drusvyatskiy. Stochastic model-based minimization of weakly convex\nfunctions. SIAM Journal on Optimization, 29(1):207–239, 2019.\n[2] H. Asi and J. C. Duchi, Stochastic (approximate) proximal point methods: Convergence, optimality, and adaptivity, SIAM Journal on Optimization, 29 (2019), pp. 2257–2290, https://arXiv.org/abs/1810.05633.\n[3] Karan Chadha, Gary Cheng, and John C Duchi. Accelerated, optimal, and parallel: Some results on model- based stochastic optimization. arXiv preprint arXiv:2101.02696, 2021.\n[4] S. Vaswani, F. Bach, M. Schmidt. Fast and Faster Convergence of SGD for Over-Parameterized Models (and an Accelerated Percepton).\n[5] S. Vaswani, A. Mishkin, I. Laradji, M. Schmidt, G. Gidel, S. LaCoste-Julien. Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See main review for weaknesses.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "ShhVbHW2gmF", "reviewer": "Reviewer_re6H", "summary": "This paper presents and analyzes an accelerated algorithm for convex and strongly convex minimization when the objective function is an expectation of a convex function. It claims that the algorithm is optimal w.r.t. Mini-batch size and the convergence rate. The presented algorithm reaches the best-known rate for the accelerated stochastic algorithm and also shows the dependence on the mini-batch size is also optimal.  ", "questions": "", "limitations": "", "rating": 7, "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": "Significance: The paper considers minimizing the population risk in machine learning models, which is one of the major optimization problems in ML. \n\nNovelty: The paper presents a novel algorithm and also discovers a new upper bound for the second moment of the stochastic gradient. Using this upper bound it analyzes the presented algorithm under different assumptions and recovers the optimal upper bounds.   \n\nClearity: it is easy to follow and understand all the technical details and main text of the paper. However, there are some typos here and there that need to be fixed. \n\n\n\n\nMy question\n\n1- The method has a limitation in the sense that it requires knowing L*. Could you replace this with some upper or lower bounds? \n\t\n2- There is no experimental section. It would be helpful to see the performance of the algorithm on the model with real data. \n\n3- Your algorithm is not an anytime algorithm. How can you make it an anytime algorithm? \n\n4-  It is not clear why theorem 2 is not trivial based on the alg 2. \n\n\n", "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": "5"}, "extra_text": {}}, {"review_id": "RgL06URE99z", "reviewer": "Reviewer_vQ2S", "summary": "This paper improves the complexity bound w.r.t. minibatch speedup given by Cotter et al and Liu et al. for minibatch accelerated gradient descent for certain objectives (under sharpness condition). Generally the paper is well-organized with solid theoretical analysis and is easy to follow.\n\n", "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": "The structure of this paper is very clear.  It presents sharper complexities of accelerated sgd than state-of-the-art result by using a refined bound on stochastic noice. The technical analysis is solid, from the theoretical aspect, I think the improvement is quite interesting and the contribution is sufficient. However, it would be much better if the author can empirically verify the algorithm performance.\n\nThe paper tries to design the minibatch algorithm with fixed batch size, can the author also briefly discuss how to use varying batch size, this seems to be a more practical strategy in applications.\n\nI am a little concerned about the parameters in this paper and the assumptions. For example, in assumption 2, it requires some nonstandard parameters such as L^* and B (Assumption 2), which are usually unknown in practice.  In assumption 3, the algorithm also needs the growth condition.\n\nI understand that the paper aims to obtain the sharpest bound possible, but it would also be great if it also discuss what if those parameters are under/overestimated. Would that has a significant impact on the performance? \n\nCan the author also provide some preliminary experiments to to show the superior performance of the proposed approach. \n\n\nOn eq (4), $\\ell(w,z)\\Rightarrow \\nabla\\ell(w,z)$.\n\nEq (59) $\\nabla F(w_t^{md})\\Rightarrow \\nabla L(w_t^{md})$.\n\nLine 300 $E\\|\\nabla \\ell(w^*;z)\\|^2$\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Perhaps the application of this approach does not include regularized problems in which the objective is far bigger than zero. For example, underdertermined linear system is mentioned in the paper. In practice we can add $\\ell_1$ term to enforce sparsity, then we have $L^*>>0$.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers recommend accepting the paper. Please take the time to consider the reviewer's comments and update the paper when preparing the final version. In particular, please discuss the additional related references brought up in the reviews.
Decision: Accept (Poster)