Universality of AdaGrad Stepsizes for Stochastic Optimization: Inexact Oracle, Acceleration and Variance Reduction
Authors: Anton Rodomanov
Xiaowen Jiang
Sebastian U Stich
Venue: NeurIPS 2024 poster (2024)
Keywords: convex optimization
stochastic optimization
adaptive methods
universal algorithms
acceleration
variance reduction
AdaGrad
SVRG
weakly smooth functions
Hölder condition
inexact oracle
complexity estimates
Primary area: optimization

Abstract: We present adaptive gradient methods (both basic and accelerated) for solving
convex composite optimization problems in which the main part is approximately
smooth (a.k.a. $(\delta, L)$-smooth) and can be accessed only via a
(potentially biased) stochastic gradient oracle.
This setting covers many interesting examples including Hölder smooth problems
and various inexact computations of the stochastic gradient.
Our methods use AdaGrad stepsizes and are adaptive in the sense that they do
not require knowing any problem-dependent constants except an estimate of the
diameter of the feasible set but nevertheless achieve the best possible
convergence rates as if they knew the corresponding constants.
We demonstrate that AdaGrad stepsizes work in a variety of situations
by proving, in a unified manner, three types of new results.
First, we establish efficiency guarantees for our methods in the classical
setting where the oracle's variance is uniformly bounded.
We then show that, under more refined assumptions on the variance,
the same methods without any modifications enjoy implicit variance
reduction properties allowing us to express their complexity estimates in
terms of the variance only at the minimizer.
Finally, we show how to incorporate explicit SVRG-type variance reduction into
our methods and obtain even faster algorithms.
In all three cases, we present both basic and accelerated algorithms
achieving state-of-the-art complexity bounds.
As a direct corollary of our results, we obtain universal stochastic gradient
methods for Hölder smooth problems which can be used in all situations.

Universality of AdaGrad Stepsizes for Stochastic Optimization: Inexact Oracle, Acceleration and Variance Reduction
Anton Rodomanov CISPA
Xiaowen Jiang Saarland University and CISPA* xiaowen. jiangocispa.de
Sebastian Stich CISPA*
anton. anton. r.ton.rodomanovcisspp.co
st stichOcispa.de de
Abstract
We present adaptive gradient methods (both basic and accelerated) for solving convex composite optimization problems in which the main part approximately smooth (a.k.a. (ō, L)-smooth and can be accessed only via a (potentially biased) stochastic gradient oracle. This setting covers many interesting examples including Hölder smooth problems and various inexact computations of the stochastic gradi- ent. Our methods use AdaGrad stepsizes and are adaptive in the sense that they do not require knowing any diameter the feasible set but nevertheless achieve the best possible convergence rates as if they knew the corresponding constants. We demonstrate that AdaGrad stepsizes work in a variety of situations by proving, in unified manner, three types of new results. First, we establish efficiency guarantees for methods in the classical setting where the oracle's ' variance uniformly bounded. We then show that, under more refined assumptions on the variance, the same methods without any modifications enjoy implicit variance reduction properties allowing us express their complexity estimates in terms of the variance only at the minimizer. Finally, we show how to incorporate explicit SVRG-type variance reduction into methods and obtain even faster algorithms. In all three cases, present both basic and accelerated algorithms achieving state-of-the-an the-art complexity bounds. As direct corollary of our results, we obtain universal stochastic gradient methods for Hölder smooth problems which can be used in all situations.
constants except an estimate of the
Introduction
Motivation. Gradient methods are among the most popular and efficient optimization algorithms for solving machine learning problems. To achieve the best convergence speed for these algorithms, their stepsizes needs to be chosen properly. While there exist various theoretical recommendations. dictated by the convergence analysis, on how select stepsizes based various problem-dependent parameters, they are usually impractical because the corresponding constants may be unknown or their worst-case estimates might be too pessimistic. Furthermore, every applied problem usually belongs to multiple problem classes at the same time, and it is not always evident in advance which of them better suits the concrete problem instance one works with. For classical optimization algorithms, this problem is typically resolved by using line search. This is simple yet powerful mechanism which automatically chooses the best stepsize by checking at each iteration certain condition involving the objective value, its gradient, etc.
However, the line-search approach is usually unsuitable for problems of stochastic optimization, where gradients are observed with random noise (unless some extra assumptions are made, see (57). For these problems, common instead apply so-called adaptive methods which up their
CISPA Helmholtz Center for Information Security, Saarbrücken, Germany
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

stepsizes by simply accumulating on-the- fly certain information about observed stochastic gradients.
The first such an algorithm, AdaGrad [17 39), was obtained from theoretical considerations but quickly inspired several other heuristic methods like RMSProp (56) and Adam (2] that are now at the forefront of training machine learning models.
Excellent practical performance of adaptive methods on various applied problems naturally sparked a lot of theoretical interest in these algorithms. An important observation was done by Levy, Yurtsever, and Cevher [4]] who showed that AdaGrad possesses a certain universality property, in the sense that it works for several problem classes simultaneously. Specifically, they showed that AdaGrad converges both for nonsmooth problems with bounded gradient and also for smooth problems with Lipschitz gradient, without needing know neither the corresponding Lipschitz constants, nor the oracle's 's variance but enjoying the rates which are characteristic for algorithums which have the knowledge of these constants. They also presented an accelerated version of AdaGrad with similar properties. An independent version of the accelerated AdaGrad including diagonal scaling was proposed by Deng, Cheng, and Lan [2]. Further improvements and generalization of these ideas were considered in
18
28 30).
Nonsmooth and smooth problems are the extremes of the more general Hölder class of problems. The fact that AdaGrad methods simultaneously work for these two extreme cases does not seem to be a coincidence and suggests that these algorithms should work more generally for any problem with intermediate level of smoothness. Some further confirmations to this were recently provided in [48) although in rather restricted setting of deterministic problems and only for the basic AdaGrad method. The stochastic case and acceleration were constituting an open problem which was recently resolved in 49 for a slightly modified AdaGrad stepsize (see (
All the previously discussed results were proved only for the classical stochastic optimization setting where the variance of stochastic gradients assumed to be uniformly bounded. In a recent work, Attia and Koren (2) showed that the basic AdaGrad method for smooth problems works under the more general assumption when the variance is bounded by a constant plus a multiple of the squared gradient norm. On a related note, it was also shown recently that AdaGrad stepsizes can be used inside gradient methods with SVRG-type aariance-reduction in [16]. The accelerated SVRG method enjoying optimal worst-case oracle complexity for smooth finite-sum optimization problems was later presented in (36].
The first such an algorithm was proposed
Contributions. In this work, we further extend the results mentioned above by demonstrating that AdaGrad stepsizes are even more universal than was shown previously in the literature. Specifically, we consider the composite optimization problem where the main part is approximately smooth (a. (8, L)-smoohh and can be accessed only via a (potentially biased) stochastic gradient oracle. This setting is more general than typically considered in the literature on adaptive methods and covers many interesting examples, including smooth, nonsmooth and, more generally, Hölder smooth problems, problems in which the objective function is given itself as another optimization problem whose solution can be computed only approximately, etc.
Our contributions can be summarized as follows:
1. We start, in Section with identifying the key property of AdaGrad stepsizes, which allows us to apply these stepsizes, in a unified manner, a variety of situations we consider later. We present our two mains algorithms, UniSgd and Uni which are the classical stochastic gradient method (SGD) and its accelerated version, respectively, equipped with AdaGrad stepsizes.
2. We then establish, in Section 4 efficiency guarantees for these methods in the classical setting where the oracle's variance is assumed to be uniformly bounded.
3. In Section 5 we complement these results by showing that, under additional assumptions that the variance is itself approximately smooth w.r.t. the objective function, the same UniSgd and UniFastSgd without any modifications enjoy implicit variance reduction properties allowing us to express their complexity estimates in terms of the variance only at the minimizer.
4. Under the additional assumption that one can periodically compute the full (inexact) gradient of the objective function, show, in Section 6 how to incorporate explicit SVRG-type variance reduction into our methods, obtaining new UniSvrg and UniFastSvrg algorithms which enjoy even faster convergence rates by completely eliminating the variance.
Our results are summarized in T the BigO-notation). In all the situations, we present both basic and accelerated algorithms whose only essential parameter is an estimate D of the diameter
2

---

Table 1: Summary of main results for solving problem (T) with our methods. "Convergence rate" is expressed in terms of the expected function residual at iteration (or I, depending on the method). "SO complexity" denotes the cumulative stochastic-orace complexity of the method since its start and up to iteration k (or t), which is defined as the number of queries to the stochastic oracle ğ: for SVRG methods, we assume that querying the (inexact) aall-gradient oracle g is times more expensive than 9. and define the SO complexity as N3 n.Ng. where Ng and N₂ are the number of queries to 9 and g. respectively. The second and third columns should be understood in terms the BigO-notation which we omit for brevity.
Method
Convergence rale
SO complexity
Assumptiions
Reference
UniSgd (Alg
D
cD VI
+
k
(2 L. j02
8, + 69
Thm.
0²
UniFastSgd (Alg
+
eD
+ kō,
L 0
+ kōj + 68
Thm.
UniSvig (Alg.))
4,6 + 6g
2' log
6
Thm.
UniFastSvrg (Alg.)
HEE log log n13 +(6 + 6g)
Thm
of the feasible set; the methods automatically adapt to all other problem-dependent constants. In a number of special cases, our algorithms achieve known sate--o-theeaas complexity bounds, but not restricted to those special cases. In Section 7 we illustrate the significance of our results by demonstrating that complexities for our methods on stochastic optimization problems with Hölder smooth components can be obtained as simple corollaries from our main results.
Preliminaries
Notation. We work in the space E2 equipped with the standard inner product (---) and a certain Euclidean norm: || = (Bx, æ²) 1/2, where B is a fixed positive definite matrix. The dual norm is defined in the standard way: ||s||+
max max|=|== ()) = (s, B-1s)1/2
For convex function th: Rdd - R U {+ its (effective) domain is the following set: dom de = {r E Rd (xx) +oo}. By (z), we denote the subdifferential of a at a point dom di the specific subgradients are typically denoted by (zb(z).
convex function f: Rd + R is called (v, - smooth for some [0, 1] and H Off [ ff(y) I H| = yll" for all x, y Id and all ff(z) E 0f(x), ff(y) E Of(y). Apart from the special case of // = O. such a function of is differentiable at every point, i.e., 0f(z) is singleton. A (1, -)Hölderrr smooth function is usually called L-smooth.
For a convex function wh: Rd + R [+ point E Rd, vector g E Rd, and coefficient M 2 0, by Prox (z, y, M) = argminy I (g, v) + +z) + fly- - =I|²), we denote the proximal mapping.
When M 0, we allow the solution be chosen arbitrarily.
For convex function f: I + R. points xr y E Rdd and V (xx) E af))),, we denote the Bregman distance by (2,(()))))) w) = f(v - fx) (VS(x), - x) (2 0). When the specific subgradient fxx) is clear from the context, we the simplified notation (r,
The positive part of t R [+] == max 0}. For r > 0, we also use log, T = max(1, (1, log
Problem Formulation. In this paper, we consider the composite optimization problem
[F(x) = (xx + (xx)), F == min
xEdom
where f: IRd + R is convex function, and te Rd - RU is a proper closed convex function which is assumed to be sufficiently simple in the sense that the proximal mapping Proxp can be easily computed. We assume that this problem has a solution which we denote by x".
To quantify the smoothness level of the objective function, use the following assumption:
3

---

Algorithm (NN, Mx) = UniSgd (zu, Mo, N; D)
Input: Oracle G. comp. part v point zo dom yb coefficient Mo, iteration limit N, diameter D.
I: go X ((ro).
2: for ........................
3: 2x+1 = Prux (IK: Sk. MR), 96-1 = ((x++1).
4: Mx+1 = M+ (Mx, D2, 3ks Th+1, 9h. gb+1)
D egg
ME D2 11
axll?
5: return (N,, MN). where EN N Ei=
Assumption 1. The function f in problem ① is approximately smooth: there exist constants o5 2 and f: IR + IR, 9: R + R such that, for any 2, E RR, B3.1.g (2. = f(v)
f(x) - (g(x), y 2) satisfies the following inequality: 0 S f3.1.g (2, < - + +
Assumption well-known in the literature under the name (6, L)-oracle and was originally introduced in 15 It covers many interesting examples. For instance, if f is L-smooth, then Assumption is satisfied with f = f.g = V. 6y = and L = L. More generally, if the function f is (v, Hy)))) Hölder smooth, then Assumption is satisfied with f f.g g = Vf (arbitrary selection and f, 2 1+ [v)] 1o0 (see Theorem 13). If ʃ can be uniformly approximated by an L-smooth function e. i.e., ((x) S f(x) S ((x)+ then Assumption] ] = satisfied with f = o g = Vø and 6 8. If represents another auxiliary optimization problem with strongly concave objective, e.g.. f'x)) max, (ar, u), whose solution ū(a)) can only be found with accuracy 8, then satisfies Assumption [ with f(x) Vxx u(z)), g(x) = V. (xx, u(x)) and 6y 8. For more details and other interesting examples, we refer the reader to [5].
of subgradients), any 8
In what follows, we assume that we have access to an unbiased stochastic oracle for g. Formally, this is a pair 9 (g. E) consisting of random variable and a mapping g: Fd Im R (with Im & being the image of {). When queried at point the oracle automatically generates an independent copy & of its randomness and then returns 9- = g(x, <) (notation: 9N ((x).. We call g and ç the function component and the random variable component of 9. respectively. At this point, we only assume that our stochastic oracle ğ is un unbiased estimator of g. and later make various assumptions its variance.
Another important assumption on problem @.. that we need in our analysis, is the boundedness of the feasible set dom vb
Assumption 2. There exists D such that || yll D for any x, y E dom vb.
Assumption 2 is rather standard in the literature on adaptive methods for stochastic convex op- timization (see [16] 18 30 34 36, 49]) and can always be ensured with D 2Rg whenever one has the knowledge of an upper bound Ro on the distance from the initial point zo to the so- lution x=" To that end, it suffices to rewrite the problem (T) in the following equivalent form: minzedom shs (fx) + (z)] where thD is the sum of & and the indicator function of the ball Bn = E Rd: :1ı zoll I Ro Note that this transformation keeps the function EhD reasonably simple as its proximal mapping can be computed via that of vi by solving a certain one-dimensional nonlinear equation, which can be done very efficiently by Newton's method (at no extra queries to the stochastic oracle); in some special cases, the corresponding nonlinear equation can even be solved analytically, e.g., when ei = 0, the proximal mapping of &DD is simply the projection on By-
Throughout this paper, refer to D from Assumption 2 as the diameter of the feasible set, and assume that its value is known to us. This will be the only essential parameter our methods.
3 Main Algorithms and Stepsize Update Rules
UniSgd (Algorithm D. and its accelerated version, UniFastSgd (Algorithm 2). Except the specific choice of the stepsize coefficients Mg. both algorithms rather standard: the first one is the classical SGD method, and the second one is the classical accelerated gradient method for stochastic optimization [33 also known the Method of Similar Triangles (see, e.g., Section 6.1.3 in (46)).
We now present our two main algorithms for solving problem []:
Both methods are expressed in terms of a certain abstract stepsize update rule M+ defined as follows. Given the current stepsize coefficient M > 0, constant Ω > 0 (the scaled squared diameter),

---

Algorithm 2 J.
Input: Stochastic oracle 0. composite part 1/, point E dom sb, diameter D.
I: Up xo. Mi Ao
for s.....
3: dx+1 = 2 + 1), Ax+1 = Ak ax-1-
4: yt = Azt1
As Ik + n2t1 Uk. 9un = ((v)).
Antt Mr).
5: uk+1 Prox (UX, Ouk
6: 2k+1 Act1
Au TE Acti
gFt1 CEtLUUtI Uhti. 9EL+1 2 0(xa+1).
7: M4+1 Axt1
ti
M Apt1 Ma,
obts D³, yk. 1 gen4s) 1f
Deg. 9
M
"
110
9vu 112
"x11
current point æ E dom & with the stochastic gradient T.. _ [(r), next iterate 2 = x (gx) dom v (which the result of the deterministic function applied to 9r), and the corresponding stochastic gradient g2+ = (({+), the update rule computes M = M (M, S2 x; Z4, Iz. P2,)) (deterministic function of its arguments) such that M+ 2 M and the following inequality holds for any M > c2Lf:
R(((M)) ) + (M+ M) + (++
9 [[Varg( + Varg (x) ] + cad, + ca [minn Mr, M) M]+3},
(2)
S M o2
where ((M+) = By R+ (7(z) Tz, ã. - -))
M | - x112 C1, C2 C3 C4 > are some -
absolute constants, and Varg(1) = Eg 1x1lgg(1:))) (x. g(x))12) is the variance of g. The expectations in (
are taken w.r.t. the randomness (+) coming from 9= g(x, {). Ie+ = g(
The main example is the following AdaGrad rule:
M+ = V M + o 11
Fu l1
For this rule, have a 5. C2 4, C3 = 6, C4 2 (see Lemma 20
Another interesting example
recently suggested in [49] is M found from the equation
M | - Jr x1]
MM M) = (ūn, In, 4+ x)
(4)
This equation admits a unique solution which can be easily written down in closed form (see Lemma E.1 in 449 For this rule, we have c 1, C2 2, cs c4 (see Lemma 27p.
Inequality ( the only property we need from the stepsize update rule to establish all forthcoming results. This inequality is exactly what is typically used inside the convergence proofs for stochastic
gradient methods with predefined stepsizes M& M (in which case M M M). where M depends on problem-dependent constants. The key property of AdaGrad stepsizes (either (3) or (4) is that they ensure the same incquality but now M is the virtual stepsize existing only the theoretical analysis. The price for this is the extra error term [min{ M) MI+ appearing in the right-hand side of ( The crucial property of this error term is that is telescopic, > omin (M M) M. S [min [M++1, .M Mo]+ (see Lemma 18) and therefore its total cumulative impact always bounded by the controllable constant MΩ. Although number of other works on theoretical analysis of AdaGrad methods for smooth optimization use some similar ideas about the virtual stepsize (e.g.. [30 34 (3)). this is the first time one has abstracted away all the technical details and identified the specific inequality (2) responsible for the universality of AdaGrad.
4 Uniformly Bounded Variance
In this section, we assume that the variance of stochastic oracle is uniformly bounded. Assumption 3. For the stochastic oracle g. we have o² = supredom v Varg(z) < +00, where Varg(z) = Eelllg(z, E) 31.
5

---

Under this assumption, we can establish the following efficiency estimates for our UniSgd and Und methods (the proofs are deferred Appendix (C.
Theorem 4. Let Algorithm D Tith Mu 0 be applied to problem under Assumptions Then, for the point nN generated by the algorithm, we have
[[P(TN)] F C2 20Dy
20104
+ czgg.
N
N
Theorem 5. Let Algorithm be applied problem under Assumptions
7
Then, for any k 2 1,
[[F(xx)]- F 4 +I)+1)
20104 C3
Do
(k 2)05.
3k
We see that, in contrast to UniSgd, the accelerated algorithm UniFastSgd is not robust to the oracle's errors: it accumulates them with time at the rate of (kk)). This is not surprising since the same phenomenon also occurs in the classical accelerated gradient method, even when the oracle is deterministic and the algorithm has the knowledge about all constants (see (55).
The complexity results from Theorems and similar to those from 13 However, it is important that our methods are adaptive and do not require knowing the constants L, and
In the specific case when 6y = O, we recover the same convergence rates as in 30 34,, although our methods work for the more general composite optimization problem and, in contrast to (34]. do not require that fz = 0.
5 Implicit Variance Reduction
The assumption of uniformly bounded variance may not hold for some problems, or the corresponding constant o² might be quite large, which is why there has recently been growing interest in various alternative variance bound assumptions (5 22 24 29
42 54 59). One interesting option is expressing Varg (x*).. assuming that the stochastic oracle 9 satisfies some extra smoothness conditions. Let us show that, for our Algorithms | and
complexity bounds via the variance at the minimizer, of
we can also establish such bounds, morcover, this can be done without any modifications to the algorithms.
In this section, we study problem (I) under Assumptions and and also under the following additional smoothness assumption on the variance:
Assumption There exist 8g, Lg 2 0 such that Varg (x, v) s 2Lg 2Lg13 y) + 6g] for any I, Rd, where Varg(z, y) = EE [Il [z <) g(y. E) - [g(x) -b)]]l
Note that Varg y) is the usual variance of the estimator ( glv, {) which uses the same randomness { for both arguments. Hence, Varg (a., y) I [x) glv. []] for any x, y- Furthermore, if 9b is the mini-batch version of 9 of size (i.e., the average of i.i.d. samples of g(x) at any point z), then Varg, (2, y) : Varg(r. y) for any x.y.
For instance, [x) = Eg[Je (x)).. where each function Se is convex and (dg, Lapapooxoxlaately smooth with components (Js, Je), then, the stochastic gradient oracle Ô. defined by g(r, 5) = Fs (a)
satisfies Assumption 6 with f(z) Eg (=)), F(x) Eg (e(Te(x)) and 8g Lmax Eg dg (s
Eg(6g]), Lg = Lmax, where Lmax == sup; Lg (see Lemma I6). Furthermore, if 9o is the batch
version of ğ of size b, then Gr satisfies Assumption with the same dg. = 6g but Lg. Lg L which can be much smaller than Lmax when b is Targe enough.
Under the new assumption on the variance, UniSgd enjoys the following convergence rate (see Appendix D. the proof).
Theorem 7. Let Algoritiun 7 Tith Mo = 0 be applied to problem (1 under Assumptions 7 and 6 and let of == Varg(a*). Then, for the point EN produced by the method, we have
E[F(IN)] F calorL, + 12c, Lz) + 20 20.Di
6oics N
4
+ tc0d
N
Comparing the above result with Theorem we see that we have essentially replaced the uniform bound a with the more refined one σ., at the cost of replacing Ly with Lg + Lg and 8, with dy + 8g-

---

Algorithm 3 UniSvvgg, D)
Input: Oracles G. composite part th, point E dom f) diameter D.
I: uo 20, Md = 0. for 1= 1..... do
3:
(Ze41, 2441, M = UniSgda, (ee, M,, 2 D) with G. SvrgOracg,s (ār).
This corresponds to classical results on the usual SGD for which we know all problem dependent- constants. However, our method is universal and works automatically under both assumptions from the previous section and the current one, and therefore enjoys the best among the rates given by Theorems
For the accelerated algorithm, we have the following result (whose proof is located in Appendix D.2). Theorem 8. Let Algorithm 2 be applied to problem under Assumptions of = Varg(x*). Then, for any k 2 1, we have
and 6 and let
[[[([))] - F" 4c2c, L D2 24cICILLD
20101 40. Do.DV
C3 3
(k: (k
5g.
k(k 1)
k+1
k
Comparing previous complexity bound for UniFastSgd under the assumption uniformly bounded variance (Theorem (5) with the bound from Theorem [ we see that, instead of simply replacing a with d., L5 with L, + Li and of with o, + 8g. which was the case for the basic method, the situation is now not that simple. Specifically, the Ly and Lg terms now converge at different rates: Oz) and O respectively. While this may seem strange at first, this behavior is actually unavoidable, at least in the case when oy = 6g (see, e.g., Section in (59). For the case when oy = 03 = O, the complexity result from Theorem Blis similar to the results for the Accelerated SGD algorithm from 59). However, the latter paper studies specific setting where f(x) E[fe
where each component /e is mSmooth and then assumes that f is also Lmax -Smoth, instead of working with the constant , which can be much smaller than Lmuax- A similar separation of the constants L and Lg. which we do, was recently considered in (24), where the authors obtained some similar rates to our Theorem [8, However, is important that, unlike the algorithms considered in [24] constants
59), our UniFast Sgd is universal and does not require knowing any except D. Furthermore, our results are more general because we allow the oracle to be inexact.
6 Explicit Variance Reduction with SVRG
Let us now show that we can also incorporate explicit SVRG-type variance reduction into our methods. In this section, we consider problem (1) under Assumptions [ and All the proofs are deferred to Appendix B
In addition to the stochastic oracle J. now assume that we also compute the (approximate)
full-gradient oracle g. This allows us to define the following auxiliary SVRG oracle induced by
with center ă E Rd (notation G = SvrgOrac (i)) as the oracle with the same random variable component & as I and the function component given by G(z, f) = g(x, {) g + g(z).
Our UniSvrg method is presented in Algorithm 3 This is the classical epoch- based SVRG algorithm which can be seen as the adaptive version of the SVRG++ method from (1. A similar scheme was suggested in [16], however, instead of accumulating gradient differences as in (3), their method accumulates gradients and therefore does not work without the additional assumption of fx(x=) (which may not hold for constrained optimization).
Let us now present the complexity guarantees. To do so, we first need to introduce, one more assumption we need in our analysis.
Assumption 9. The variance of satisfies Varg (x, v) S 4Tg10 and any V fx) 0f(x).
(x)) (x. v) + 25g) for any x. y Rdd
Assumption 9 very similar to Assumption 6 The only difference between them is that the former contains the standard Bregman distance in the right-hand side, while the latter contains its approximation (),1,((x, y) involving the approximate function value f(x) and the approximate gradient g(r). Nevertheless, both assumptions are actually satisfied for the main examples we discussed after introducing Assumption 6 (see Lemma 16).
7

---

Algorithm 4 Uni
Input: Oracles 9. composite part w. point to E dom v. epoch length N, diameter D.
I: to (To, ((xo)) 0), zo, Mo 0, Ao N-
2: for f 0, 1- do
3: Oc+1 AA, Ac+1 +
+ a++1-
4: (Te41, 01-1; M R Uni'IniSvrrgEooch, a. (ās, vI, Mr, A., N;
Algorithm 5 (z+, U4, M-) = UnilhiSvrgEEpoch,.oo (T, vo, Mo. N)
Input: Oracles 3. comp. part vi, points ž, vo. coefficients Mo. A, a, epoch length N, diameter D. A
I: A+ A+ zu
A_ 3 + A+ vu. G = SvrgOrac (z), Gzo _ G(æo).
2: for h = O,...,N .N- -
do
uk+1 Prox. (Ux, Gax: m²).
Ab I + x uk+l, GrL-1 = ((xx+)). 4: #k+1 = Ai
5: MR+1 = x M+ ( Mx,
a² x.
D2 Ik, TK+1, Gras Gzazt) Deg.
M2 + Tt Gozs1 Go
6: return (æx, UN. Mv), where nN == Φ Σ tk-
Theorem 10. Let UniSvrg (as defined by Algorithm 3) be applied to problem ① under Assumptions aadd Then, for any t 2 1 and T33 == max 1T. we have
2
E(F( - F* (e224 + 1)L, + 48c1 + +Zzzō 3
8
2
To construct Tt, the algorithm needs to make O(2²) queries to 9 and (l) queries to g.
We now present accelerated version of UniSvrg, see Algorithm 4 As UniSvrg, this method is also epoch-based based, and its epoch is very similar to UniFastSgd (A (Algorithm 4 in the sense that it also iterates similar-triangle steps. However, the triangles in UniTriSvvgEEpoch are of the form (7. Uk, 1. i.e., they always share the common vertex म. in contrast to the triangles (æx, Uk. Uk+1) in Unitast (in UniTriSeegEEooch, the role of the average points yı is played by xx)). We note that our UniFastSSig is essentially the primal version of the VRADA method from [53]. but equipped with AdaGrad stepsizes. Alternative accelerated SVRG schemes with AdaGrad stepsizes (3) were recently proposed in 36 however, they seem to be much more complicated.
The special choice of the initial reference point ăy at Line T is rather standard and motivated by the desire to keep the initial function residual appropriately bounded: F(Øo) - F S ,2 + +5; the simplest way to achieve this is to make the full gradient step from any feasible point (see Lemma 34
Theorem 11. Let UniPast (Algorithm + be applied to problem (1) under Assumptions / and and let 2 9. Then, for any 2 40 = [logz logz N - (2 0), il holds that
E [F() - F 91(0201 + L + 601 (eccsLg)D + (cal + 1)8g N(t to 1)2
5
3 -66.
To construct Tt. the algorithm needs to make O(Nt) queries to 9 and O(t) queries to g. Assuming that the complexity of querying g is n times bigger than that of querying 9 and choosing N = ((n), get the total stochastic-oracle complexity of ((n)).
Note that Theorem unlike Theorem 10
does not require the extra Assumption 9 This suggests that Assumption 9 might be somewhat artificial and could potentially be removed from Theorem TO as well. However, we do not know how to do it, even in the simplest case when 8y 5g = and the
algorithm has the knowledge of the constants L, and Lg from Assumptions and
7 Application to Hölder Smooth Problems
To illustrate how powerful our results are, let us quickly consider the specific example of solving the stochastic optimization problem with Hölder smooth components.
Example 12, Suppose that the function f in problem ( is the expectation of other functions,
f(z) = (f))), where each function fe is convex and (v, (x))--Hllde smooth. Consider the
8

---

Table 2: Corollaries of our results for the case when problem ① has Hölder smooth components, defined Example 12 "SO complexity" " is the stochastie-oracle complexity for reaching accuracy e in terms of the
expected function residual, defined as in Table but with 0 = gb. 9 V.. n ni.
Method
SO complexity
Reference
("rle) ifv D² 1 min{ =2g² (#imastt) (e)) 14v D² + =222
UniSgd (Alg.)
Cos.
H Hywwiplty निiT & min { =ap2 (Hmaylle) Tho D2 + =²
UniFastSgd (Alg
Cors 38
[Nu(e] ( (1 1oo D² + t( (mmax(ee) 170 D2] + ne log No(e)
UniSvig (Alg.
Cor
[ "y وبايررر ाx30 1 Hmnelvi 1430 + nn log log
UniPastSvrg (Alg. 4
41140//2.
Cor 44
standard mini-batch stochastic gradient oracle go of size b, defined by (1)) = - = Vee,
where Eig == (fI,...,&E Eb) with i.i.d. copies of &, and fe) E (z) is an arbitrary selection of subgradients for each ç. We define H (v) as the Hölder constant for the function f and H (v) sup, Hg (z))) as the worst among Hölder constants for each fe- Note that we always have (v) - Eg [r]] but Hy(v) can, in principle, be much smaller than the right-hand side. Also, define
(=))l(] and of = Varg, (x*) = (f(x")l1]] We assume that the computation of go can be parallelized and the computation of V is n& times more expensive than that of Do-
o² = suP di Varg, (x) = sup=edom v Ee & V fe (z)
E (x²))
To solve the above problem, we can apply any of the methods we presented before. The resulting oracle complexities (in terms of the BigO-notation) are summarized in Table the precise statements the corresponding results and their proofs are deferred to Appendix F
Note that our problem is characterized by large number of parameters, Hy(D), (v)) O. For each combination of these parameters, we get a certain complexity guarantee for each of our methods, and it is impossible to say in advance which combination results in the smaller complexity bound. However, it is not important for our methods since none of them needs to know any of these constants to ensure the corresponding bound. This means that algorithms are universal: they automatically figure out the best problem class for a specific problem given to them.
8 Experiments
Let us illustrate the performance of our methods in preliminary numerical experiments on solving
f min f(x) = Σ Ka, x) - -b.1 }.
|
where a,,b, by E Rd, 9 E [1,2] and R 0.
This test problem covers several interesting applications. Indeed, q 2, we get the classical Least squares problem. If q 1, this is the well-known Support- Vector Machines (SVM) problem. In both cases, the ball-constraint ||a||| S R acts as a regularizer, and problem (5) is, in fact, equivalent to minzex= [xx + 2 ||~]|²] for a certain f 2 0 (this follows, e.g., from the KKT optimality conditions) such that μ decreases when R increases.
Another interesting application of (5). which we consider in this section, is the felssierro.feasiibillyy problem: find x² E Rd ||=*|| < Rł inside the polyhedron p= (x (a),2)) S bi, 1,.... n. Such a point exists iff f* = O. Note that (5) is a problem with Hölder smooth components of degree = g 1. By varying q in (5). we can therefore check the adaptivity of different methods to the unknown to them Hölder characteristics of the objective function.
The data for our problem is generated randomly. First, we generate x² uniformly from the sphere of radius 0.95 centered at the origin. Then, we generate i.i.d. vectors a; with components uniformly distributed on 1]. We then make sure that (a,, x²) < by inverting the sign of a, if necessary. Next, we generate positive reals s; uniformly in [0, 00.1mmin), where Cmin == mii;
(a,, min,(a,, < O. and set by (a;, x²) + 8t. By construction, x² is a solution of our problem with f O, and the origin xig = 0 lies outside the polyhedron since there exists j (corresponding to Cmin) such that
by Gmin + 8j S 0.9Gmin <0 O.
"The corresponding source code is available at attp:///shh..coommmmbaaiiiiiilad

---

Figure 1: Comparison of different methods on the polyhedron feasibility problem
Figure 2: Impact of mini- size on performance our methods.
We compare UniSvrg (Algorithm 3 against AdaSVRG (16) (with parameters K 3 and 1)= D 2R). We next compare UniFastSvrg (Algorithm 4 against AdaVRAE and AdaVRAG [36]. We also compare with the FastSvrg method with constant stepsize, which is the primal version of the VRADA method from (53]: the stepsize is selected by doing a grid search over {10' : -3...., 4} and choosing the best value the sense that the algorithm neither too slow nor has a large error. We report UniSgd (Algorithm M and UniFastSgd (Algorithm 2 together with these methods. For UniFastSvrg, contrary to the theoretical recommendation of choosing žp as the result of the full gradient step, we found it slightly more useful to simply set 20 = .n. For all our methods, we use the AdaGrad stepsize (3); the other stepsize (4) works very similarly (see Appendix H..2 for detailed comparison). For all methods, we use the standard mini-batch stochastic oracle of size h = 256.
The results are shown in Fig. where we fix n 10 d 10 R 10th and consider different values of E [1, 1.6,2) We plot the total number of stochastic oracle calls against the function residual. We treat one mini-batch oracle computation as one stochastic oracle call. If we compute the full gradient, we count this as n/b stochastic oracle calls where n is the total number of samples and b denotes the mini- size.
We see that, except the AdaSVRG method, all SVRG algorithms typically converge much faster than the usual SGD methods without explicit variance reduction, least after few computations of the full gradient. Among the non-accelerated SVRG methods, UniSvrg converges consistently faster than AdaS while UniFastSvrg performs the best across the accelerated ones. Note that FastSvrg with constant stepsize is not converging when the problem is not Lipschitz smooth (q < 2), in contrast to our universal methods.
In Fig. 2 we also illustrate the impact of the mini-batch size b on the convergence of our methods.
We consider the same values of n, d, R before and fix 1.5. As situation, when one can implement the mini- batc- oracle computations by perfect parallelism, there is significant speedup in convergence when increasing the mini-bater size, predicted by theory.
see, in the idealized
For additional experiments, including the discussion of implicit variance reduction, see Appendix
Conclusions
In this paper, we showed that AdaGrad stepsizes can be applied, in unified manner, in large variety of situations, leading to universal methods suitable for multiple problem classes at the same time. Note that this does not come for free. We still need to know one parameter, the diameter D of the feasible set. While is not necessary to know this parameter precisely, the cost of underestimating or overestimating it, can be high (all complexity bounds would be multiplied by the ratio between our guess and the true D). At the same time, there already exist some parameter-fre methods which are based on AdaGrad and aim to solve precisely this problem 6
11
25
31 41). It is
therefore interesting to consider extensions of our results to these more advanced a algorithms. Another interesting direction is, of course, nonconvex problems.
10

---

Acknowledgements
The authors are thankful the anonymous reviewers for their comments and suggestions. Sebastian Stich acknowledges funding support from the Meta Research Award and the Google Research Award.
References
[1] Z. Allen-Zhu and Y. Yuan. Improved SVRG for Non-Strongly-Conner or Sum-of-Non-Conves Objectives. International Conference on Machine Learning, pages 1080-1089, 2016.
[2] A. Attia and Koren. SGD with AdaGrad Stepsizes: Full Adaptivity with High Probability to Unknown Parameters, Unbounded Gradients and Affine Variance. In International Conference on Machine Learning. pages 147-1177, 2023.
[3] R. Babanezhad Harikandeh, M. O. Ahmed, A. Virani, M. Schmidt, J. Konečný, and S. Sallinen. StopWasting My Gradients: Practical SVRG. Advances in Neural Information Processing Systems, 28, 2015.
[4] D. P. Bertsekas. Stochastic optimization problems with nondifferentiable cost functionals. Journal of Optimization Theory and Applications, 12(2):218-231 1973.
[5] L. Bottou. F. E. Curtis, and Nocedal. Optimization Methods for Large-Scale Machine Learning. SIAM Review, 60(2):223 2018.
[6] Y. Carmon and O. Hinder. Making SGD Parameter-Free. In Conference on Learning Theory, pages 2360-2389, 2022.
[7] C.-C. Chang and C.-J. Lin. LIBSVM: library for support vector machines. ACM Transactions on Intelligent Systems and Technology, 2:27:1-27:27, 3, 2011.
[8] A. Cotter, O. Shamir, N. Srebro, and K. Sridharan. Better mini batch algorithms via accelerated
gradient methods. Advances in Neural Information Processing Systems, 24, 2011.
[9] A. Cutkosky and K. Boahen. Online Learning Without Prior Information. In Conference on Learning Theory, pages 643-677, 2017.
[10] A. Cutkosky and F. Orabona. Black-Box Reductions for Parameter-free Online Learning in Banach Spaces. In Conference On Learning Theory. pages 1493-1529, 2018.
[11] A. Defazio and K. Mishchenko. Learning-Rate-Fiee Learning by D-Adaptation. In Interna- tional Conference on Machine Learning, pages 7449-7479, 2023.
[12] Q. Deng, Y. Cheng, and G. Lan. Optimal Adaptive and Accelerated Stochastic Gradient Descent. arXiv preprint arXiv: 111.00053,, 2018.
[13] O. Devolder. Stochastic first order methods in smooth convex optimization. CORE Discussion Papers, 2011/70, 2011.
[14] O. Devolder. Exactness, Inexactness and Stochasticity in First-Order Methods for Large-Scale Convex Optimization. PhD thesis, Université catholique de Louvain (UCL), 2013.
[15] Devolder, Glineur, and Nesterov. First-order methods of smooth convex optimization with inexact oracle. Mathematical Programming, 146:37-75, 2013. DOT: 10. 1007/
013-0677-5
[16] B. Dubois-Taine, S. Vaswani, R. Babanezhad, M. Schmidt, and S. Lacoste-Julien. SVRG meets AdaGrad: painless variance reduction. Machine Learning, 111(12)4439-4444 2022.
[17] J. Duchi, E. Hazan, and Singer. Adaptive Subgradient Methods for Online Learning and Stochastic Optimization. Journal of Machine Learning Research, 12(7), 2011.
[18] A. Ene. H. L. Nguyen, and A. Vladu. Adaptive Gradient Methods for Constrained Convex Optimization and Variational Enequalities. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35 of number 8, pages 7314-7321, 2021.
[19] E. Gorbunov, F. Hanzely, and P. Richtárik. A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent. In International Conference on Artificial Intelligence and Staristics, pages 680-690, 2020.
[20] R. M. Gower, P. Richtárik, and F. Bach. Stochastic quasi-gradien methods: variance reduction
via Jacobian sketching. Mathematical Programming, 188(I):135-19) 2021.
[21] R. M. Gower, M. Schmidt, F. Bach, and P. Richtárík.
Methods for Machine
Leamnngg Proceedings of the IEFE, 108(1 ():1)) 1968-199,,, 2020.

---

[22] R. M. Gower, N. Loizou, X. Qian, A. Sailanbayev, E. Shulgin, and P. Richtárik. SGD: General Analysis and Improved Rates. In International Conference on Machine Learning, pages 5200- 5209, 2019.
[23] G. N. Grapiglia and Y. Nesterov. Regularized Newton Methods for Minimizing Functions with Hölder Continuous Hessians. SIAM Journal on Optimization, 27(1) DO1: 10. 1137/
16M1087801
[24] S. Iladarideva,, A. Juditsky, G. Lan, and T. Li. Accelerated stochastic approximation with state-dependent noise. arXiv preprint arXiv:2307.0143 2023,
[25] M. Ivgi. O. Hinder, and Y. Carmon. DoG is SGD's Best Friend: A Parameter-Free Dynamic Step Size Schedule. In International Conference on Machine Learning, pages 14465-14499, 2023.
[26] A. Jacobsen and A. Cutkosky. Unconstrained Online Learning with Unbounded Losses. In International Conference on Machine Learning, pages 14590-14630, 2023.
[27] R. Johnson and T. Zhang. Accelerating Stochastic Gradient Descent using Predictive Variance Reduction, Advances in Neural Information Processing Systems, 26, 2013.
[28] P. Joulani, A. Raj. A. Gyorgy, and C. Szepesvári. A Simpler Approach to Accelerated Op- timization: Iterative Averaging Meets Optimism. In International Conference Machine Learning, pages 4984-4993, 2020.
[29] A. Juditsky, A. Kulunchakov, and H. Tsyntseus. Sparse recovery by reduced variance stochastic approximation. Information and Inference: A Journal of the IMA, 12(2):851-88) -916, 2023. [30] A. Kavis, K. Y. Levy, F. Bach, and V. Cevher. UniXGrad: A Universal, Adaptive Algorithm with Optimal Guarantees for Constrained Optimization. Advances in Neural Information Processing Systems, 32, 2019.
[31] A. Khaled, K. Mishchenko, and C. Jin. DoWG Unleashed: An Efficient Universal Parameter- Free Gradient Descent Method. Advances Neural Information Processing Systems, 36:6748-
6769. 2023.
[32] D. P. Kingma and J. Ba. Adam: A Method for Stochastic Optimization. International Confer-
ence on Learning Representations (ICLR), 2015.
[33] G. Lan. An optimal method for stochastic composite optimization. Mathematical Programming, 133(1):3653397) 2012.
[34] K. Y. Levy, A. Yurtsever, and V. Cevher. Online Adaptive Methods, Universality and Accelera- tion. Advances in Neural Information Processing Systems, 31, 2018.
[35] C. Liu and M. Belkin. Accelerating SGD with momentum for over-parameterized learning. arXiv preprint arXiv:1810. 13395, 2018
[36] Z. Liu, T. D. Nguyen, A. Ene, and H. Nguyen. Adaptive Accelerated (Extra-)Gradient Methods with Variance Reduction. In International Conference on Machine Learning, pages 13947-
13994, 2022.
[37] S. MaM. R. Bassily, and M. Belkin. The Power of Interpolation: Understanding the Effectiveness of SGD Modern Over-parametrized Learning. In International Conference on Machine Learning, pages 3325-3334, 2018.
[38] M. Mahdavi, L. Zhang, and R. Jin. Mixed Optimization for Smooth Functions. Advances in Neural Information Processing Systems, 26, 2013.
[39] H. B. McMahan and M. Streeter. Adaptive Bound Optimization for Online Convex Optimiza- tion. arXiv preprint arXiv:
2010.
[40] Z. Mhammedi and W. M. Koolen. Lipschitz and Nomparator-Norm Adaptivity in Online Learning. In Conference on Learning Theory, pages 2858-2887, 2020.
[41] K. Mishchenko and A. Defazio. Prodigy: An Expeditiously Adaptive Parameter-Free Learner.
arXiv preprint 2rX.v:2306..611
2023.
[42] E. Moulines and F. Bach. Non-Asympiotic Analysis of Stochastic Approximation Algorithms
for Machine Learning. Advances in Neural Information Processing Systems, 24, 201
[43] I. Necoara, Y. Nesterov, and F. Glineur. Linear convergence of first order methods for non- strongly convex optimization. Mathematical Programming, 175:69- 107-699-77-000 2019.
[44] D. Needell, R. Ward, and N. Srebro. Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz Algorithm. Advances in Neural Information Processing Systems, 27, 2014.
12

---

[45] Y. Nesterov. Universal gradient methods for convex optimization problems. Mathematical
Programming. 152:381-404, 2015. DO1: 10.
[46] Y. Lectures on Convex Optimization, volume 137. Springer, 2nd edition, 2018.
[47] F. Orabona. Simultaneous Model Selection and Optimization through Parameter-free Stochastic
Learning. Advances in Neural Information Processing Systems, 27, 2014.
[48] F. Orabona. Normalized Gradients for All. arXiv preprint arXiv:2308. 008800561,,1 2023.
[49] A. Rodomanov, A. Kavis, Y. Wu, K. Antonakopoulos, and V. Cevher. Universal Gradient Methods for Stochastic Convex Optimization. arXiv preprint arXiv:2402.03210 2024.
[50] M. Schmidt, N. Le Roux, and Bach. Minimizing finite sums with the stochastic average
gradient. Mathematical Programmingg 162:83-112, 2017.
[51] M. Schmidt and N. I.. Roux. Fast Convergence of Stochastic Gradient Descent under Strong Growth Condition. arXiv preprint arXiv: 637,6370, 2013.
[52] S. Shalev-Shwartz and TT. Zhang. Stochastic Dual Coordinate Ascent Methods for Regularized Loss Minimization. Journal of Machine Learning Research, 14(1), 2013.
[53] Song, Y. Jiang, and Y. Ma. Variance Reduction via Accelerated Dual Averaging for Finite-Sum Optimization. In Advances in Neural Information Processing Systems, volume 33, pages 833-844, 2020.
[54] S. U. Stich. Unified Optimal Analysis of the (Stochastic) Gradient Method. arXiv preprint arXiv:1907 190..0422, 2019.
[55] M. Streeter and H. B. McMahan. No-Regret Algorithms for Unconstrained Online Convex Optimization. In Proceedings of the 25th International Conference on Neural Information Processing Systems, volume 2, pages 2402-2410, 2012.
[56] T. Tieleman. Lecture 6.5-rmsprop: Divide the gradient by a running average of its recent magnitude. Coursera: Neural Networks for Machine Learning, 4(2):26, 2012.
[57] S. Vaswani, A. Mishkin, Laradji, M. Schmidt, G. Gidel, and S. Lacoste-Julien. Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates. Advances Neural Information Processing Systems, 32, 2019.
[58] C. Wang, X. Chen, A. Smola, and E. Xing. Variance Reduction for Stochastic Gradient Optimization. Advances in Neural Information Processing Systems, 26, 2013.
[59] B. E. Woodworth and N. Srebro. An Even More Optimal Stochastic Optimization Algorithm: Minibatching and Interpolation Learning. Advances in Neural Information Processing Systems, 34:7333-7344 2021.
[60] L. Zhang, M. Mahdavi, and R. Jin, Linear Convergence with Condition Number Independent Access of Full Gradients. Advances in Neural Information Processing Systems, 26, 2013.
13

---

A General Auxiliary Results
A.1 Approximately Smooth Functions
Theorem 13 (Lemmaa 2 in [45)). Let f: R&d - R be a convex (v, -)-öllder smooth function for
some v E [0, 1] and H 2 0. Then, for any 6 > 0, any v. E Rd and any Vf(x) E (z)), , it holds
that Bj () (a, v) S || ull + ā with L (يل i=v H (with the convention that 0 1).
Theorem 14. Let f: R + IR be a (6, L) apprrxximmttl smooth convex function with components (f.g), Le., for any 2, y E Id and (z. y) = f(y) - f(x) (g(z), y 2), we have
I.
0 Σ 3 (z, y) -
|| - y/1² +
(6)
2
Then, for any x. E E and any vf(x)) E 0f(z). the following inequalities hold:
(g(x) - g(v), x - v) S f(x) S f(x) < f(x)
(7)
- (g(x) - g(y), x - 8) + 26,
(8)
(0(x) -
(9)
[[((x) g(v)ll 2111
(10)
[ a(v)ll 2 (z,9)
(11)
lTī()) - 7(1) - 1/ v/ 4L5,
(12)
(Ø(xx) - (())1 - 4L(0)/100( (z. + 26),
(13)
10 (x. v) - L||= v/ + 25.
(14)
Proof. Inequality follows immediately from 6 by substituting y =
To prove we rewrite
(F. + (v.x) = (g(x) - (()))) x v) (ffxz) - - f(=))+ (f(y) - f(y)).
and then apply
Using the first part of (8 and applying (6) twice, we obtain
To prove (10) and
let us fix some f1(x) E R and (x) E R such that 3y. .. (z) =
f(=) - [(( (g) (x), = - s) 2 0 for any z E Rd, Note that we can choose either (Ji, 71 = (ʃ g)
or (f = (f.V In view of (6). for any E Rd. we can write the following inequalities:
0 < F..... (x) s f(v) - f1x) (z)())) x) + (Tv) - (z), v) + 2 || y11² + 8.
Minimizing the right-hand side in IRd and rearranging, we conclude that
1 27 (b D. (1) < f(y) - (x) (7. (z). - x) + + Fr (I. v) + 5,
where the final inequality is due to 7 Substituting now either (fi,T) (F.z) (F.0)) (f, ff), we obtain either 10 or 11 respectively.
Inequality
(2)
follows immediately from 6 and (10
Inequality
13 follows from
[Ø(x)) - g(v) < -00) -Vf(z)1
S <4L18
+6 4L8 =4L(0) (x) v) + 26).
14

---

To prove
[4p. we proceed as follows using first 6 then 7.. and then 1I
fix) (x. v) = ((v) [(x) - (VI()), - x)
S f(()) - f(x) - (g(x) - vf(z), - x) 2 1ly - x x2² +
s (G(x)) V y x) + L // lly - - +
S V2Lølyy 2|| + / |ly =I1? +6
(V I1y x11 + vo) L x: 1/1 + +20
where the final inequality is (a + b)2² - 2a² + 20 a, 2 0.
Remark 15. Some of the inequalities from Theorem 14 namely, 10 and (12 were established
already in [15). We nevertheless prefer to present the corresponding proofs since they are rather simple, and we use the associated ideas for proving the other new inequalities.
Lemma 16. Let f: IRd + be the function (ax) == [g([e(())) where each Sc: TR: - IR is convex and (ōg, Lg) -xparoppoximttely smooth with components (fe. Te)- Further, let 9 be the stochastic oracle defined by g(x, E) == De (z), and let f(x) = IE Iee [x))], F(x) == Eg (x])e(=)) Then, I is an unbiased oracle for g and, for any x. y E ERR., Timax == supe L and 8 = Timax BT( it holds that
Varg(z. v) S 2T (3, f1 (1. v) +
(15)
Furthermore, for any x, y Rd and any ff(x)= E 0f(x). it also holds that |3/
Varg(æ, 8) S 4Lmax (m)) (3/1000) xz, y) 28).
(16)
Proof. According to our definition of 9, we have Eglge(z)) (=)] g(x) for any x, so is indeed an estimate
unbiased oracle for g. Further, for any x. y E Rd,
Varg (2. v) E&g [Il le (ar) Fe (v) (x(x) [())]11]]
< Es [llge( (x) g8 [1) < Ee [2L (3 fe. me (z. v) 6c)
S 2 2ma (Eg f fe (x. v)1 + 8) = m |3 f. f. (r. y) + 8).
where 8 is as defined in the statement; the second inequality follows from Theorem 14 (inequal-
ity (10), and the final identity is due to the linearity of By.T.g (2, v) in (f, f.g) and the fact that, by our definitions, [g(fe(=)) f(x), Ee (x)] f(x). 13g 19c (x)] = g(z) for any x. This proves [5
The proof of 16 is similar but now we apply instead (TOp:
Varg (2x, v) < Egg [Igge(()) (1)) - E5g [Lg (B)
V le (w) (x, v) 28g)] fc
< 4Tmax [8 (x))
(x. v)] + 25) = 4 4 (3] (3) (()) (xr, v) + 28),
where we have used the fact that 0f(x) = Ee fe(()) (see Proposition 2.2 in (4), meaning that, for any fx(x) E (x), we can find a selection of fz()) E (ff(z) such that Vf(z) = F fe (z)).
A.2 Miscellaneous
Lemma 17. Let wh Rd + I U (+00} be a proper closed convex function. I E dom 1 g E R4. M > 0, and let
x4 Prox (x. g. M).
Then, for any y E dom vi we have
M x yl 2 (x+ )+
M
M
(9. v - x4) + (vv)
+
x
1
|
2
15

---

Proof. Indeed, by definition, 2+ is the minimizer of the function h: R - R U {+o)} given by h(y)) = (g. v) (b) - M || yll?. which is strongly convex with parameter M (or simply convex if M = 0). Hence, for any dom a/r (= dom It), we have h(y) 2 h(x+) + / lly x+1. which is exactly the claimed inequality.
Lemma 18. Let N 2 be an integer, (M&) be a nondecreasing nonnegative sequence of reals, and let M 2 0. Then,
N-1 min [ M - M+]++ = [min (MN M - Mo]+.
R=0
Proof. suffices to prove the identity only in the special case when N = 2, i.e., to show that "o + I. where "Yo = 1,, M Mol+. Vi = [min M2, M) M1]+. == [min (2,, M) - Mol++
The general case then easily follows by induction.
To prove the identity, we use our assumption that M, S M2 I M2 and consider three possible
[M Mol+ +0 [M Mol+ r. If M1 < M S M2. then Yu + 71 (M1 Ma) + (M M₁ = M Mo r. Finally, if M2 < M, then yo + m
cases. If M1 2 M. then "o + 21
(M, - Mo) + (M₂ Mi) M2
Mo = r.
Mo
Lemma 19. Let 9 be stochastic oracle in IR4, Then, for any x. yr 2 E Rd and any T > we have
Varg(=) S (1 + 7) Varg(y) + (1 + r Varg(r, Varg(z, S (1 + T) Varg (z, 2) + (1++ Varg z).
Proof. Both incqualities are direct consequences of the standard inequality ||s + s2ll < (1 s)]s I1. + (1 - - l| which is valid for any $1,82 Id and any т > 0. Indeed, let and & be, respectively. the function and the random variable components of g. and let A(x, {) g(x,{) E[g(x, {)] for any z e Rd. Then, for any 2, y, 2 Rd and O, we can estimate
Varg(x) = A x 1) = (1 <) + [A (x, E) - (3r.
< (1 + - |I|| A (y, 1) (1 + [B[| (1x, <) - ()33 = (1+ Varg (v) + (1 (1+ Varg (z, v).
Similarly,
(ar v) = TE {x) [) = B[I[A (2. 5) - A(2,0) - (1) A(2,))1
< (1 + T) E - [(, + (1 (1+r~))[[A((+)) [x2
(1 + T) Varg +) Varg (v,
B Omitted Proofs for Section 3
Lemma 20 (AdaGrra stepsize). Let function of satisfy Assumption 7 Consider the stepsize update rule M4 (M,M, F., Dn Dz defined by
M.
M
100, 12.
Then, this stepsize update rules satisfies
2 with ci
5. 02 c3 C4 2.
Proof. Let ((M) = Byfj., ( (g(x) gr, 24 - x) - 11 1 From our Assumption
and Theorem 14 (inequality (8)) it follows that (1, x)) 25.. Hence,
(2 S -
M
E (MM (2,. x)] = E (g(24) In. 24-24
a - x 1
+25 EI (M4
2
16

---

where ( = (gx+ - -2. - x) - -----1 + - x112. Hence.
M
T= =[M() + (M+ MIΩ + By.. ( x+) < R A (M+) + (M_ -M]] + +26
From the definition of M4, follows that 1|ā,, - 02 = (M M220 = (M+ + MM - M)S.
Since M+ 2 M, this means that
1 M-
10=, 3xll? S (M+ M)Ω S
10 02
2M+ +
Let us now upper bound f == (M,) + (M+ M)Ω. For this, let fix an arbitrary constant
M 2 0 and consider two cases. If M+ 2 M, we can bound
î (M,
10=+ - 32 < (M) + M
10 3211==f(11
M+
If M- < M, we can bound
10=,
Gell2 + (M+ M)Ω s 2(M4 M) = 2[min| ( M) - M2+
2M
Combining the two cases, we get i < [MMM + 2mmi M4, M) - 52. Thus,
r - 20, S ([( + 2 1 min [ M) -2 + 28
Let us now estimate the first term. Denote $ = 02 g(x) and S .e. - -((+)) Then,
M
1
f(M) (02+ 2+ =x) ب x1|² +
M 10 - 02
< (7(6)) - g(x), ,+ x) ( =1)
M
M
+ ( - 3. - x) + M S - S|1
2 |6+ - xx
Using now our Assumption and Theorem
(inequalities and
12) ). we can continue as follows:
f(M) & | - x1|2+ + +28 +
M [1 - xx12 + (L,
+ -1,--5,55 x) ||
2
- -11
.M
|5+ 1/
M
2
M- 2T, + 2L,
$ (8, - S, 2+ x) + M
13, $1
1G4- + +2(1+
||5
4L
)o, M
2
2 (
(2 +
1
|1+ - 31 + 22 22
4L
)o.
M
2 21 + )
M
Consequently,
B[((())+++ <
2
1
E11 - + +2 +2 4Lg AL1)
M )0
M
2[M 21
22, y M
In particular, for M > 4Lf, we can estimate
S
2 M
+ 2000 S 2(M
M
2(M 12-22,,11 (1+ -
Therefore, for any M > 4Ly,
([((MM))+ 2(M AL,) E[|[ - +112++45 = 2(M 4L,)
E(Varg Varg +
where the final identity follows from the fact that E S112] 11 [2] + |[||113]
E B[[arg(G++) + Varg(x) (because S4, conditioned on the randomness ş defining 9- = g(x, E) has zero mcan).
17

---

Combining everything together, we get
PS 2(M AL2)
E B[Varg( + [arg(x)]
68, + 2 2 [min M) - M]+2}.
This is exactly ( with 6₁ =
5 2 02
= 4, c3 = 6, c4 =
Lemma 21. Let function f satisfy Assumption
Consider the stepsize update rule M+ M4 SMM.2a R4, In_) defined as the solution of the following equation:
1
M
- (M+ = (0x, Dz. 24 - -x)
1 xx?
2
Then, this stepsize update rules satisfies
with 02 = cg
6, c4
Proof. Let us define (MM) == 3. }4) + (g(x)) - 92. 2 z)
M
2 1| - Starting as in
the proof of Lemma 20
that
:= (M)( + (M+ M)Ω BIs. (2t. < E A M+ + (M- M)R 26
with the same (-)-) as defined in the statement.
Let us now upper bound f = (M+) + (M+ M)2. For this, us an arbitrary constant M 2 0 and consider two cases. If M+ 2 M, we can bound, using the monotonicity of (.(-),
î = A (M,) - A (M, ( - (1)))
If M_ < M, we can bound
f Â )]+ + (M+ - = - M)Ω 2[min M,, M) - M2+ + 2[min| (M+, M) - M2 and hence
Combining the two cases, we get i <
r E + 25 I (E(( + 2 [min (M,, M) - M]+ + 25
Let us now estimate the first term. According to our Assumption and Theorem 14 (inequality P)) we have (g(++) g(x), 2_ - x) I L z=|² + 20,, Hence, denoting S = IN g(x) and S+ = Dz+ g(+++) we can estimate, for any M 2T.g.
M
(M) = (g( g(x). - x) + $$_ - + x)
2 1 z/|2
$ 184-5,55 3, x)
M M-2Lj
21j
| - x1|² + 28, 2
113 118+- -3112 1112-112 28y.
2(M 2L,)
Hence,
(((+) S 2(M 2L - -$13)+25-- 2(M -24,)
E. V. Varg
where the final identity follows from the fact that E||| - S11:1 E| + B1|| || B[Varg Varg(x) (because S4, conditioned on the randomness defining gr = glz, E) has zero mean).
Thus,
T M 2L,
E Va ( + Varg 68, + 2 ( M} - M]-2).
which is exactly
2 with c₁ C2 2, c3 6, = 2.
18

---

Omitted Proofs for Section 4
C.1
Universal SGD
Lemma 22 (Stochastic Gradient Step). Consider problem ① under Assumption 1 Let 9 be an unbiased oracle for g. Let dom v be a point, M 2 be coefficient, In _ g(r), and let
2 Prox (I, M)).
Denote ((M) (1, (g(x))
Tu. -+ -x)
1 x Then,
M s x² [|p] $1.5a((0, x²)
M 1 x= 1 E|
E F(++) F"
If further Assumption 2 is satisfied, and M+ 2 M is random coefficient (possibly dependent g.x ). then, we also have
E F(2+)
F
M 2
( x²) -
14+ x" x013]
M
(M4
Proof. From Lemma 17 it follows that
M
1, - x²1 1 M 1 - ze12
f(x) + (Tn, 34 2) + x+++) +
2
M
s f(x) + (Or, - x) + +(xx)))
+
| - x x²11?
2
Passing to expectations and rewriting
Bxf(x) (0,, x² x)) v/xx'())) = f(x) (0(x)) - x) 1b(x*)) F(x*) -B (x,
=
and
+ ((. -2) ((++) -
(g., +4 -x)] = F((+) - ( (2, - (g(z)) - Du, St x)}
we obtain the first of the claimed inequalities.
To prove the second one, we simply add to both sides of the already proved first inequality the expected value of
M+ M
=11 + A(M) - A(M+) = M4 M (11 - x²11 + 1| sel(²)
14+
2
2
and then bound ||+. - x11 & D, | æl < D using our Assumption 2 and the fact that Jr, $4,," xx dom
Lemma 23 (Universal Stochastic Gradient Step). Consider problem ① under Assumptions 7 Mand 2
Let 9 be an unbiased oracle for g. Further, let x E dom up a point, M 0 a coefficient, In 2 }(r), and let
24
Prox, (I, 9z. M), DN- g(24), M4 MM, D2 x. a... In-).
Then, for any M > cgL.s, it holds that
M
E F( F²
1 1²1 112 +
x)] +,,
M
11 1
E Ha
2
c2L,
Proof. According to Lemma 22
F(2,) F* M
( x*) < M
f x0
x 10 ( -MD%)
19

---

where (M+)) = 8/,f,(2, to the main requirement (2) on the stepsize update rule, for any M > c2l.g.
2--) -r 1| - At the same time, according
E ( + (M+ M)D² f1F [++
C1
g (++) + Varg(=)] + cgdy + c1 B [min M+, M+ M2]
M c2L,
Combining the two displays, we get the claim.
Lemma 24 (Universal SGD: General Guarantee). Consider problem ① under Assumptions and
Let g be an unbiased oracle for g. Further, let x E dom vb be point, M 2 0 be coefficient, N 2 be an integer, and let
(TN, EN, MN) = Un Mo. N; D),
as defined by Algorithm 7 and let To.-... IN be the corresponding points generated inside the algorithm. Then, for any M o2L., it holds that
MN
E N[F(TN) - F+]+
IN - x
x²11²
Σ
13 (1141, Tx.) + (.. x*)]
2
k=0
Mo
100
x²12+ +
C1
N
B B| ( + (xx)( + cgNoo
2
M
c2Ls
k=0
+ E [min M) D2}.
Proof. Each iteration the algorithm, when conditioned on Ik, follows the construction from Lemma 23 (with x 2k. Dr- 9b. M = M2, 2+ I++1, Pr_.. = Ik+1, M4 Mc+1). Hence, we can write, after passing to full expectations, that, for each k O.....N.
E (((++1) - F
Mc+1
|
x11 By. (2 mx) J. x*)
2
<
E
Me 2
I xx 11+
(arrg (M++1 M Mx]+ D2 +ezdg,
M
LLLs
where M 2Ly is arbitrary constant. Telescoping the above inequalities (using Lemma 18 and (F(*x)
then bounding (TF( F*) s 1 F*] (using the convexity of and our choice of EN 3 Em 2R). get the claim.
Theorem 4. Let Algorithm with Mo = 0 be applied to problem for the point N generated by the algorithm, we have
under Assumptions Then,
D2 + 2
2010s N
E [[(x) F <
+ czdj.
N
Proof. Applying Lemma 24 substituting our choice of Mo estimating Varg()) S o² and dropping the nonnegative 3I (:.)) terms, we obtain
20102N
C4 MD2 D
2010²
[[ F*
(MMD2 + M M + +cNN8))
+ czdg,
N
M Lc
where M > 2L, is arbitrary constant. The optimal M which minimizes the right-hand side is 2e1 c4
M -22, + by
N. Substituting this choice into the above display, we get
DA (22L. + DV Ca
2c1 N)
20 o
E [( F* &
+ CzŌ5
N
N
D
CoCaL,,D3 D)2
20164
+
22oD V
czdy.
N
N
20

---

C.2 Universal Fast SGD
Lemma 25 (Stochastic Triangle Step). Consider problem ①I under Assumption [ Let 9 be an unbiased oracle for let z, dom i be points and M, A 0, a > O be coefficients. Further, for A+ A a, let
Ax + aU
Ax + a0+
y =
Oy = ((y),
i = Proxs By. M M/a,,
A+
A+
Denote ((M f1.F.n (v. x+) (gly)
Fy. ++ v)
MA+ 2n
|
u11 Then,
E A+ - F*] +
M
10 x² x²1]²]
+ ( (v. + f.f. (v,
2
M
- S -
ブ 1 x01' 112 + (AA,E(
If further Assumption then we also have
is satisfied, and M4 2 M is a rundom coefficient (possibly dependent on Iy).
M+
A+ (F(24) - F +
10+ x² x²] + +BB + +3..FF.(V."")
2
M || xt (EIAA((M + (M, M)D"),
s A(F(x) F*)+ +
Proof.
Denoting 0 == A3 1 a (.3.5.6(1.2") and using the fact that [[ g(v). we can
rewrite
M
AF(x) + affx"") + 2 ||0 1²12
2
= Al((v) + (T(y), x - y) + 3 31.. (1, + (xx)
M
+ +als(y) + (5(v), x' v) + B (y. x² + ++((0))
+ || - xx x²11
2
M
= At) + (gly), Au ax A+y) + Avb(x) + axb(x*)
+ || xx" 112 0
2
M
E f+) Gy: Ar ax -A4) + (br)) + av(x*))
|||
x² 113
+ 0.
Further, by the definition of 04 and Lemmal 17
M
M.
M
Gy. xx - -4+ + (x0((x))))))
||I x= 112 2 (00+) +
|| 64
1|2
+
10+ - x 112
2a
2a
2a.
This means that
M
A+ A+ + (Gy, Ax + +xx - A4y) + Aw(x)) + axb(x") (x+))x)))+) + ||v - x²113
2
M
M
2 A4y(y) + (0,, Ax + aa0 - -A4y) + Ad(x)) + av((1))
+
||U
0+
112
+
10- x x11
2
2
2 A4 + 34 -) + +++)) + M
M
||0 1-1
14
112
2
2
A4F(2)) + M
10+ - (
2
where the second inequality is due to the definition of 2 and the convexity of th. and
M
A(M) = f(++) fly) (gys 2+ y)
||0
6+11
2A
MA
3 f,11 (v, x+) + (g()) By. ã. 2)
||
2a²
4 x, (0+ v) (by the definitions of y and R4). Substituting the above inequality into the first display and rearranging, we get the first of the claimed inequalities.
since - -
21

---

To prove the second one, we simply add to both sides of the already proved first inequality the expected value of
M+ M 100 ( M- M (10+ (101-
A
1
m/1
a²
and then bound, using the fact that 3+ y = a, (0+ - together with our Assumption 2
11+ x
3 y11² = 1,+ x011 11++ =112 s 2D
Lemma 26 (Universal Stochastic Triangle Step). Consider problem ① under Assumptions Hand and let 9 be an unbiased oracle for Let x, v E dom v be points, M, A 2 0, > 0 be coefficients. Further, for A+ == A + a, let
Ar +
Ax + ad.
y
Iy g(y), 0
M/a);
84
A+
A+
a²
A+
a²
g2+- g(ā+), M+
M+
M, D2 y, 2.,y2.41 14. 9v.
A+
a²
A+
Then, for any M > C2L. A.
a²
it holds that
M+
A+ (F F*] +
04 x x²11²+ (...((((+.))) - =A8 + aB5,s((xxx))
2
aaa²
S AlF(x) - FT]
+
|| - x²12² +
M 02L, a² E[Varg (++ Varg(v)]
2
+ o + ct E [min M,, M} - D2}.
Proof. According to Lemma 25 (together with the fact that M4 M which is guaranteed by the requirement on the stepsize update rule), we have
M
A+ - F*] +
10+
x x11]?] + AB x) + a3 +33.111(,1x')
2
M
s (FF -F*1+ +
|/0 xx x=112 +E[A,, (M+) + (M+ AM4-MM ()) 1
where ((M+) = (y k4) + (ā(y) Jy, y) 1 y|12. Further, according the a² D3. A:
main requirement 2 the stepsize update rule (applied in the variables M' = A M, Ω
M4 == A Mr M' = A+ M for which we have M'Ω = M Da A, Min Mr D² A, M'Ω = M D2 it holds that
A )
a²
D2
(M,+ + (M+ -M)
M)
A+ + (85fo((+.1))
CI ([ + Varg(v)) + czdy + ca (minn M)
MM,,
D2 M]+
M o2L.
A
where o2Ls A. an arbitrary constant. Multiplying both sides of the above display by A4 and adding the result to the first display, we obtain the claim.
Lemma 27 (Universal Fast SGD: General Guarantee). Consider Algorithm 2 applied to problem under Assumptions 1 andd 2
Then, for any l 2 1 and any M c2Ly, it holds that
k-1 (x(F(z)) - F*]+ DIA 1.FF1/FFFFg (2.11, + a4+1 1441381...0011....0
k-1
S <cMD² + M To k=0
Σ
o (ar3(13))1)) + Varg(ui) + esd, Σ A,
22

---

where = =, A₁ = }k(k+ 1), Ex= a3 = (k + Σx= A + for each k: 2 1.
Proof. Each iteration of the algorithm, when conditioned on (Igg, ux), follows the construction from Lemma 26 (with x 3k, Uk. M Mg, A Ak, dg+1, A+ Ak+1, y/ yk-
Gy - 9m 0+ Uk+1, 34 Tk Dz+ 4 1 M+ Mx+1). where A₁ and ag. are the following coefficients: ag = j1,, As = Σi= = kk(k + 1). Applying Lemma 26 (dropping the nonnegative
F.J.a x) term) and passing to full expectations, we therefore obtain, for each k 2
M++1
E
AR+1 M [F(++1) F=]
11=+1-1=11 + A (t..a///././........ + + 1 (2k, x")
2
- -F Mk
c1
s E (n(F(xx)-
l1e - =I"1++
(Varg(<++1) + Varg (Va+
o241
M o2h, Apt1
+ cz oj + ca [[lmmin M} Mx]+ D2}.
where M is an arbitrary constant such that M > 02 of
Note however that, for our sequences Ok
Au+1
of $42
c197+1 in the above
and Ag, we have
I+1 S 1. Therefore, we can replace
A
+
M M Ag+1
2 display with M under the requirement that M > c2Ly. Doing this and then telescoping the above inequalities (applying Lemma 18), and using the fact that My = AA = O, we get the claimed inequality.
It remains to do some standard computations that Σi= at Ex 1 2 1)(k
and Σx= A 1 i(i +1 [( 1) + 1) + ki + 1)) 1 + () + 2). O
Theorem 5. Let Algorithm be applied problem ① under Assumptions 73 Then, for any k 2 1,
E[F(xx)] - 1' s 402CaL,1D2
20144
Do 3k
(k 2)0
k(k +1
Proof. Let 2 be arbitrary and F. = E[F(2x)) F*. Applying Lemma 27 dropping the
nonnegative (1.ra(()')) terms and bounding Varg() 0²,
obtain, for arbitrary constant
M > c2L1s
1 F& S Ak
C4 MD2 +
20
Σ
a + 0zd, Σ A1)
M - -c2L1 1=1
i=1
4
(cMD22 + cjk(k + 1)kk + 1)o²
C3
k(k + 1)(k+ + +2)5,)
kikk + 1)
12(M c24,))
12
MD2
ci c1k2k + +10²
1:kk 1)
3(M 1.6--21. c221,)
where 6R = 5 (k: + 2)0y.
We now choose M 02hy which minimizes the right-hand side, This
M = c2L, + 20
a
k(k 12k + 1), for which we get
V
3e4
4²
σ
Ci k(k 1)(2k + 1)) +)(kk+1)
e1 (2k + 1)0²
F5 S k(k + 1)
C2Tis +
+ 8z
2D V
3ca
3 V
K 1)(2k + +1)
3cd
(2c4 +1)
4c D2
20,04
+ 40D
+ 8z S
+ 40
V
+ 8x.
kik 11
3k(k + 11)
k(k +
3k
23

---

D Omitted Proofs for Section 5
D.1 Universal SGD
Theorem Let Algorithm with Mo = be applied to problem ① under Assumptions and let o² = Varg(x*). Then, for the point N produced by the method, have
and
B[ F F' cale2Tag 12c, (g) + +20.D1
601
4
+ tcs5
3
N
N
Proof. Let zo. .0.............................. EN the points generated inside the method and let PN = [[[[(TN) F". Using Lemma and Assumption 6 estimate, for any 0
1
Varg(#*+1) Varz(#)) I 3 Varg(1x) + (arg(en+11,
s 6o Varg 2 2k)
s G + 12 (T
4Lg ( (1 + +
6 + 4Lg 3,3 f. (7,, x + ( + 45g).
(
Substituting this bound into the general guarantee given by Lemma 24 (and taking into account the fact that Mo = 0), we obtain
NFN +
( mx) + PI.F (xk,,=))
k=
60, 2
N-1 +
S MD2
Σ k=
3 (1,, + N(c385 + 400g), F (T
M - oا
where M e2L, is an arbitrary constant and a = M- Requiring now that 3a S or,
4erLa
equivalently, that M 2 02 + 12 Muinn we can cancel the nonnegative (t.Fag(t))) terms on both sides and obtain
MD
6010²
FN
M M +
N
where c3dg 5z.
The optimal coefficient M, minimizing the right-hand side M, However, we still need to respect the constraint M 2 Mmin- Choosing M
(2L, + D
N
02 + 12c, Lg + D
B we conclude that
c1
DD2 (o2L, 12 + G. BOIN
6c
FN s
DV a1
+ 8
N
D
ca(e2L, + 12c 12 D2
60gcs
+ +20.D1
+ 5.
D.2 Universal Fast SGD
Theorem 8. Let Algorithm 2 be applied to problem 1 under Assumptions 7 and 6 and let o? Varg(#"). Then, for any k > 1, we have
[[F(xx)] - F* 4020a D2 D2
24cicLLDD2
2014s
4o. 4o.DV
(k +
2)
+
k+1
k
Proof. Let k > 1 be arbitrary and F5 == E[F(xx)] F*. Using Lemma can estimate, for each i, Varg(1 Varg(u)) Varg(y:) Varg (#1+1,
19 and Assumption 6
60? + Varg ( + 2 Varg (x141, v.)
6aa? + 12 3 f U1 x²) + 5g] + 41g 19 (x 8g)
60? + 133 f. (1i, x²) + By. (1141.3)) 46g]-
24

---

Substituting this bound into the guarantee given by Lemma 27
we obtain
A&
B
f (v.
R-1
6010,
S 0q M2
(T:41, (1 (1:1) (1/,, 446g+
M c2L Σ a 4G555 Σ A/s
04+1 1=0
where 0i+1
4e, Lggi+
M M-ozhy 04 1/2, As 11a(k: 1), Ei at 3 k(k 1) + 1), E. A
or, equivalently, that M M ,zL, + 12c, Lga = caL, + 60g Ligh, we can cancel the nonnegative / $3.F.0 (.,)) terms on both
k 1)(k: + 2). Requiring now that 305+1 di+1 for all i ...... ; k
sides and obtain
6c10?
k
Fk - A GMMD2 + M - M i=1
Σ
a + 0309 Σ
As +
Ano5)
3
E=1
(GIMD22 + c0,k(K + (2k + 1)
C3 8yk(k + 1)(k + +2) + +50
+
k(k 1)
4(M c2Lr)
12
4²
c102(2k 1)
7:I 11
M
-c2bs
where 6g ş (A: + 2)05 + 5
The minimizer of the right-hand side is M. c2b, + d
2D k + 1)(2k + 1). However, recall
that we also need to satisfy the constraint M 2 ozL, , 6c₁ Lgk. Choosing M o2 + 6cs Lgk
k(k + 1)(2k + 1), we obtain
2D
Fk S k(k 1)
D2
(c2L) 601 Lok + +
O.
c1 k(k + 1)(2k 1)(2++1)) 1)) +
0 + 1)
+ 8
2D VDV ca
k(k + 1) +
V ca
402c,L, hikk 1)
24 + 40.0D
92c + 1)
+ 8n
k+1
k(k + 1)
AC
24g + 4oxD
20101 + Sk.
k(k 1)
k+1
k
E Omitted Proofs for Section
Lemma 28 (Basic property of SVRG oracle). Let 9 be stochastic oracle in Id,, and let G SvrgOracy (z) for some ă E Rd. Then, for any E R&, the mean value of G at is the same that of while Varz(x) Varg ())
Proof. Let g and & be, respectively, the function and the random variable components of g. and let g(z) = Eglo Eglg(1.85 {) ((i) == E& [g E)] Then, by definition, & is the oracle with the same random variable component & and the function component G defined by G(r,)) gxx, E) ( E) + g()).
Consequently, Eg [G(,, {)] g(x), and
Var (x) E& [I]G(z, {) -=(x)]11]
Eg [1]1((1))) - g((, [9(x) ( Varg ().
E.1
Universal SVRG
Lemma 29 (Universal SVRG Epoch). Consider problem I under Assumptions 7 and Let I, E dom v be points, M 2 0 be a coefficient, N 2 1 be an integer, G = SvrgOrac, (z) and let (5+, x4, M+) = UniSgd (z, M, N;
25

---

as defined by Algorithm f ff(x), it holds that
Then, for any M 2 ozL, + 12 a= 4orla
and any Vf(x²)
M-
N(F(E+)) - - M+ 10 - x² x²113]
M
x 6aN (x", (1",
|| - x²112
+ +c B [mmin[ M} M]-}.
2
Proof. Since I an unbiased oracle for g. so is & (Lemma 28). to get
Therefore, we can apply Lemma 24
N-1
M+
E ((F((+)-
-
20 - x² x²112 1
+
( + +, x"]]]
2
k=0
M
| 1=112
C1
(( Var cg
2
M
c2
k=0
ca [[[[minnMM M) M]+ D²},
where M o is an arbitrary constant and zy are the points generated inside UniSgd.
Applying now Lemmas 19 and 28 and Assumptions 6 and we can estimate, for each k
(#k+)) Var (xh) Varg(#*+1, Varg(1x: .) Varg (1 3 (arg(okk
S 2 Varg 2x) + (arg + 6 Varg (x .))
S 44gg33. f.f.g (Ix+1, + 0g1 + 12L 1/ f. (I x" ") + dg1 + 24L Ff((") (x", 26g]
= =4[gl3 f.f.8 (3++1, + 33, f. (Tkk x*) + 63, f(a" (x ;)) 16dg]
where Vf(z*) E 0f(x² ) is arbitrary. Denoting a = M M-c2L,
L0,2 we thus obtain
E N[F(++) - F*1 + M
1z+ - x²11² +
N-1
Σ k=0
18 s. f (1)+1. + BI.F (xx. x"]] ]]]
I <6aN3 (x" (x*, +
| - x² x²11 + Ncco - 16adg) ) + c4 [min M+, M} - MD D2}
2
+ Σ (( (
Requiring now M 2 cabs 12c, we get a 1 which allows us to cancel the nonnegative (. terms on both sides. The claim now follows.
Theorem 10. Let UniSvrg (as defined by Algorithm 3 be applied to problem [ under Assumptions
2 6 and Then, for any 2 and C3 == maxfca, 1}. we have
E[F(2.)) - F [(e2cs + 1)L, + 48c1c4 + 2rz0 -g-
8
2
To construct 3t, the algorithm needs to make O(2") queries to I and O(t) queries to g.
Proof. The algorithm iterates (ā++1, Fe+ M++1) i) z UniSgd (It, Mr, 2':1 D) for 2 0, where
G. SSrrgOrac (ā+). Applying Lemma 29 with M = Ls + 48c, L3 (for which a 1z so that 6a2 = 2 and passing to full expectations, we obtain, for any 1 2 0.
1
B 12 (T++1) - F* + Mi-1
| - x²1]]]
2
Me
|| x11 +c (min M411.110 M3 M.]+ + +2 (csō) + 4 ;,0)
< E
2' 3r +
2
26

---

where Bt == 5. ((((") (x+ ,ā)) and Vf(x=) E (x*) can be chosen arbitrarily. Rewriting Fi+1
F( ) F* Fi+1 = Bet1 + (Fi-1 Bet1) and telescoping the above inequalities (using,
Lemma 18 we get, for any t 2 I,
Mr a| x x²112]
E
2 B +
-8)) + 21 3,)
2
==1
Mo
|100 - x0112 + (cnds + 4 2
S 80
+
Σ
2 ca [min M} Mo]+ D2}
i=1
4 S. +2 - 1) (c05, +
3 0g) + cq MD² = Do.
where the final inequality is due to the fact that Mo = O, while Σ 2' 1). According to Lemma 30 we can choose /x(²)) E 0f(x*) such that 8 - F( - FM for all > 0. Dropping
now various nonnegative terms from the left-hand side of the above display, we conclude that
2 [ Po.
Let us estimate to. Using our Assumptions and 2 and Theorem 14 (inequality
(4 we can bound
3o & م - x²" + 26, & D2 + 26y. Therefore.
Φ - D2 + 2 + MD² + +2(22 (c + 3%) s LD2 + 2(Tzdy + (5g) 2
where L Ly + c (0204 + 1 + 48 and ō2 == maxfcs, 1). Thus,
P
LD2
8
B(F]] <
3 3
2
2
which proves the claimed convergence rate.
Let us now estimate the number of oracle queries. At each iteration f, the algorithm first queries g to construct the SVRG oracle G, (by precomputing g(āz)). All other queries are then done only to G, or, equivalently, to δ inside UniSgda,. which is run for No+1 = 2 iterations and thus requiring ((N++1) queries to g. Summing up, after T' iterations, we obtain the total number of E O(N)) Et= ((2²) O(2 queries to g. and T queries g.
Helper Lemmas
Lemma 30. Let F: Rd + { be the function F(x) = fx))+(+()) where f: IR + Ris convex function, and uh: R - R { is a proper closed convex function. Let x² be a minimizer of F and let F* == =F(("). Then, there exists fz(x) E Of(x") such that, for any x E dom v,
F(x) - F 2 3
f(x') (x",
Proof. Since x" is minimizer of F, we have 0 E 0F()*) ( 0f(z²)) + Orb(="). In other words, there exists fz(=*) E 0f(x*) such that Ve((**) - fz("²) dx(z*). Consequently, for any E dom v.
F(x) - F" = f(x) - f(x)) + (xxx - v(x'){ 2 [(x) - -s(x)) + (Vib(="), -xx) = f(x) - f(x)((()))))))))))) (Vf(z x x²) 8/ (71(0)) (a" xx).
x²)
E.2 Universal Fast SVRG
Lemma 31 (Universal Triangle SVRG Step). Consider problem under Assumptions 7 and Let ā, E dom & be points, M 2 0 and A, a be coefficients, G := SvrgOrac, (ō). Further, let,
for A4 := A + a,
+== A% + av
At + ad
G2 G(x),
04 = Proxo (v, Gr. M/a),
G4 =
A+
A+
G~
G(T+);
M =
a²
M
A+ M,
a²
D2 x
-., G G.t)
A+
a
A
27

---

Then, for M = 02l.g o²
661 Lg d²
it holds that
x.
A+[1F(++) - F*] + M+ 11 x²²
2
$ A(F(E)) - F*] + M
|/2 x²1 =12 2 + c2 E [min| (M+, M) - M]+} + c3A4d, + =
2
Proof. Since 9 is an unbiased oracle for 9. so is G (Lemma 28) Therefore, we can apply Lemma 26 to obtain
M+
E A+1 F*]
10+
112 x=
A+ 3 f (x: m) + A3,
2
M
qia²
$ AlF(5) - F=]
|/ x²11
B[Varg - Varg(x)]
2
M c2L
cc cs [ M+, MJ MJ+
where M
c2Ls a² A+ an arbitrary coefficient. Using Lemmas
and 28 and Assumption 6 we can
further bound
Varg(5+) + (x) Varg(f+, (a, 8) S 2 Varg 3 (arg( 2L.g f. () 33, (,, ()) +5g)
Denoting a = 2c1 Lza M M
we thus obtain
a2
A4
M+
E A+1F((+) F*]
10+ x²11 A+ A. 2t] + A3
2
M
$ A(F(E) - F*1
|/U 2²112 c3A 8, + 5adg ca Bf[min M M) M D
2
+ 2a E[3 f. (2.. + 3a.3,.f.. (2, Z).
Choosing now M c2Ls o² 60g T we get a A (S A44) which allows us drop the nonnegative 3 (..fg((:)) terms from both sides. The claim now follows.
Lemma 32 (Universal Triangle SVRG Epoch). Consider problem (I) under Assumptions 7 and Let ē, E dom & be points. M 2 and A, be coefficients, N 1 be an integer, and let
(ã+, U4, M+) = UnitriSserllipcch (ū, v, M, A, a, N;
as defined by Algorithm
Then, for A4 == A + a and M = c2b, _ + 6c Lg x holds that
M_
E [(A,N(F(E4)
F*1 +
2 1|0 x=11"
M
5 a1 1 x0 112 D22 [1mmin(M,,,MM M) MM +N M]+]+ MN())N((AA,0))))
< AN([F(G) - F
2
Proof. Each iteration k of the algorithm, when conditioned 2k, follows the construction from Lemma 31 (with Uk. M Mr. A Ap. a ak+1, A_ As+1. I Ik. G. Ga.-
0. Uh+1. &4 = FA++1 Go G 11 M4 = 12+1). Hence, we can write, after passing to full expectations, for each l: O,..., N 1,
Mk+1
B [+ - F*] +
||++1
x= 12
2
Mr ||
< A(F(()
F*
+ E
- x 2 + ca (min M) - M+]+D² +
2
28

---

where 8 = 03A46y + 5 3 Aòg. Telescoping the above inequalities (using Lemma 18 we get
MN
E A+
F((x) - +
lle x x=1
2
k=1
Mu 1|v0 x=11 1112 + D2 [M M) Mo]+ } + No.
S AN - F=] +
The claim now follows from the convexity of F and our definitions __ EN = N km Tk-
Σx
04 UN, M+ MN. Mo M, V.
Theorem 11. Let UniPast (Algorithm + be applied to problem ① under Assumptions 7 and 6 and let 2 9. Then, for any 2 40 flog2 logs N1 - (2 0), il holds that
[[F( - F 91 L 66g + (egt + 1)6g + 3 10g.
5
N(t - +
To construct it, the algorithm needs to make O(Nt) queries to 9 and O(t) queries to g. Assuming that the complexity of querying 9 is times bigger thun that of querying and choosing N = (()).
we gel the total stochastic-oracle complexity of ((n)).
Proof. By our definition, the algorithm iterates for t 0:
(Tz41s Ve+1, 1)+1) = UniTriSvrgEpoch, g. (Te, vt. Mr, AG, N;:1,;;))
where A, and 06+1 are deterministic coefficients satisfying the following equations:
A++1 A + as+l
a++1 = -V.
(17)
tug Ti + 60g A1 + 6cg M, and In particular, for any t 2 0, we have Mf == cgLs A++1
hence [mingMM+1,, M,) Mc]++ < [min(Me+1:: M) M.J+ (because, for any fixed a and b, the function (mi } b]+ is nondecreasing as the composition two nondecreasing functions).
Applying now Lemma 32 and passing to full expectations, we therefore obtain, for any 2 0.
- FF) Me+1
E A N(F(t+1)
|1e+1 x²|]3]
M I|ve-x x +ealmmin (M++1, M) M.J- +N (caArr+188+ Ardg) 2
E ANN[T(
Telescoping the above inequalities (using, in particular, Lemma 18). we obtain, for any 2 1,
ANE))(() F+1 < AoN(F((Bu) F*1 + Mu
2 1lu0
xx
c4 [ffminn Mc M) Mol+ D2} + N (C30) Σ A
5 63 Σ A.
$ AnN(F(2o) - -
MD2 + NS, S. + (6))
where, for the last inequality, we have used the fact that Mo = 0 and denoted S, = Ei=1 A,. Thus, for any t 2 1.
1 (Ao(F(5o) - F+++ c. MD² Ag
S. (3dd + 5 _,4))
B[F(G))] F" S
+
A,
3
At the same time, according to 17) A,+1 - --= VA, for any t 2 0. Hence, by Lemma 33 (and our
assumption on Ag), we can estimate A, 2 (1- +1) for any 2 lo := [log, logs Ao
(2 0).
Further, since the sequence A, increasing, we can estimate S, Dt A, S t.A, so that
Substituting these bounds into the above display and using our formula for Ao. we obtain, for any t 2 lo
[[F(2,) - F 2 p:(F(eo)) F McMD + t(c3d 5dg)
29

---

where N()-to+1)² 1 1. By our choice of žo. it holds that F( F 2 + 8y (see
Lemma 34 Denoting L = L + c (02c4 + 2 + 6eicsLg. we get
E[F( F po(DD + +5) + t(e36) + 3 (6) S P.LD (est + 1)68 + ftōg.
which is exactly the claimed convergence rate bound.
Let us now estimate the number of oracle queries. At the beginning, the algorithm makes query compute vn- All other queries to the oracles then done, each iteration only inside the call to Uni Vrirriss (Algorithm 5). Each such a call needs only one query to y to construct the SVRG oracle & (by precomputing (()), and ((N) queries I (which implements each query G). Summing up, we get, after iterations, the total number of O(NI) queries to I and (() queries to g.
Helper Lemmas
Lemma 33 (c.f. Lemma 1.1
23
Let At be a positive sequence such that
A4+1 A 2 7A,
for all t 2 O, where y > O, and let Ao S 3% Then, for any t 2 0. we have
7( (2)1/22
ift < to
A 2
[ tu +)3,
ift 2 to.
where to = [log logs
21 Ao
(2 0).
Proof. By replacing A, with A; = Ar/r,, we can assume w.l.o.g. that y 1.
For any 2 O, we have A4+1 2 VA,, and hence
A 2 A! 1/22
In particular, for to (as defined in the statement), get to 2 logg logs Ao - 1, so 2'0 2 logs Ao and hence
A 2 A log, (1/Aa) =(3 -3-1loss (1/Ao)) 1ogg(1/Aa) 2/00g(1///)) = 1
(recall that Ao S 3 < 1).
On the other hand, for any to. we have
VA + A + 1
A /A 2
/ VA.-
VA,
A
1
VI+3+1
3'
VAg
where we have used the fact that A, 2 Av 2 since A, is monotonically increasing. Telescoping these inequalities and rearranging, we get, for any 1. 2 lo-
1 1)²² = (1-ta to + 1)2. +
A 2 (1(1- (1-- to) + A
(t (t- to)
2
3
Lemma 34. Consider problem
under Assumptions 7 and 2 Let x dom th and let x.
(2 (())) 0). Then, F(x+)=
F* < L + 55.
Proof. From the first-order optimality condition for the point x4 (see Lemma 17 it follows that
(z)z,, x- 24) + +x=²) 2 vxx+).
30

---

Combining the above inequality first with f(x+) S f(z) + (g()), x) + L x+ x|12 + 61
and then with f(z) + (g(x), x² x) - f(²*) (which are both due to Assumption obtain
F(z+) f + +(x+) - f (x+) + (g))), x= - z+) + x0x2))
- f(z) + (g(x), x² - z) + xx(*) + L 1| - =x11² 6,
2
- F / 12+ x1| 89.
remains to bound || - Ø S D.
Omitted Proofs for Section 7
We start with the observation that for our specific example all main assumptions satisfied. and are satisfied with f = f.
Remark 35. Under the setting from Example 12 Assumptions
g(z) fz()) = V fe (x)) any òz, 03 0 and
tTē [H (mm) (
1- 1 2(1 + v)
1
[H)
Lg
2( + v)6g
Further, the oracle D.. satisfies Assumption with of = sllP=doom Vargo (x) f and o..b = Varg, (x*) ! o
Proof. For b this follows from Theorem and Lemma and and our definitions of o² and o.. The general case b 2 1 follows from the fact that the standard mini- batchbn of size reduces each of
variances Varg, (-) and Varg, (:.)) in times.
The following auxiliary result will be useful throughout this section:
Lemma 36. Let b. > 0 be real. Then,
mine a 120 to + bt (p =pp+1)e 1)
(")
Proof. The expression inside the min is convex function in f. O. Differentiating and setting its derivative to zero, we see that the minimum attained at t, = (%) p+r Hence,
PFI
b
PFI
min bt
(p + 1)a P+T
ap
F.1 Uniformly Bounded Variance
Corollary 37. Consider problem ① under the setting from Example 12 and also under Assumption Let Algorithm [ be applied to this problem with the oracle ğ Go and initial coefficient Mo 0. Then, for the point EN generated by the algorithm, we have
(20204)
C
Hh H2(D)Ditv N
2210s bN
[[F((N)] F <
+ 20 DV
1+v
To reach [F]([N)]] F* S efor any e > 0, it suffices to make O (y( D Ot-
o²D² bea
queries
Proof. Denote for brevity Hy == (v),). Taking into account Remark 35 we get, for any 8y 0,
and applying Theorem
C2c4H 14 D
1-
1-v
142
Fy E F(((N))] F+
+ czd; + ON.
2(1 + v)
31

---

where ON = 20 2cses = 20
20.es Minimizing the right-hand side in ōy (using Lemma 36 BN
N
1-2 for which p + = (4x) with = 14v
we obtain
2
C204H D
1
1+
2
FN S
+ +aN
1+
N
2(1 +
1 V
1-u
(20201)
C3
HyD
NN.
1+
N 1
This proves the claimed convergence rate, and the oracle complexity bound easily follows since each iteration of the algorithm requires only 1 query to go-
Corollary 38. Consider problem ① under the setting from Example 72 and also under Assumption Let Algorithm 2 be applied to this problem with the oracle 9 = Tt. Then, for any l 2 1, we have
2 (02c1) 2 (
H H
20101
[[F(xx)] F
1o
1+V
k
3bk
To reach [[x)) F* I for any e 0, it suffices to make O to 9b-
+
D²D²
queries
be
Proof. Let k 2 1 be arbitrary and denote for brevity H1 Hy(v). Taking into account Remark 35 and applying Theorem 5 we get, for any oy > O,
F=== B[F(x]] F s kik + 1)
4e2c, 14 D=
1-
ITr
C3 ( + o
2(1 + v)5g
where oR = 1o,D
20.4 = 1o
2014, 30k
Minimizing the right-haun hand side in dy (using Lemma 36 obtain
3h
and estimating :: + 2(k: 1),
2
4C2c4 D
v
ITc
1
1 1 20g (k: + (k)
4
F& - 1+V
+ ok
kik + +1
2(1 +
1
2(402c4)
4
(1)) +
D1
+ok.
1+V
h (k 1)2
This proves the claimed convergence rate, and the oracle complexity bound easily follows since each iteration of the algorithm requires only ((1) queries to 9b.
Remark 39. The efficiency guarantees given by Corollaries 37 and 38 are exactly the same as those from 49 up to absolute constants.
F.2 Implicit Variance Reduction
Corollary 40. Consider problem ①1 under the setting from Example 12 and also under Assumption 2
Let Algorithm|| The applied to this problem with the oracle δ = Gb and initial coefficient Mo Then, for the point EN generated by the algorithm, have
(V)
(((v)llmxx (V)D++
be1cs bN
B[F(TN)] F <
+ +20.Di
N 4
(6N) 142
1au 1 T
1 (g) 12
where cy(v)
(2eacs)
O(1) and cg(v) (24cr)
O(1). To reach
1+v
[[F(TN)] F* for any e > 0, it suffices to make 0(1 Hy(() queries to go.
-
D + Halv)
+ D) +
D²
be
32

---

Proof. Denote for brevity EN = E(F(EN)] into account Remark 35 and applying Theorem
- Hy Hy == (v( and Hmax = (v). (v). Taking
7
we get. for any oz. 6g > 0,
f 1ir
D
-
12c max D2 1
t+2 + cz0₁ + 53 + ON,
4
FN S
N
2(1 v18y
bN
221+
3
where NN == 20,,, D. DV
6c151 VV.
ceres bN
Minimizing the right-hand side in o3 and og (using
N
Lemma 36 (wice), we get
2
C2C4 H
DD2
1 - V
(1 +1+ 13
FN -
+ 1
N
[2(1 + +v)
1 1/
Hia D2
1-
L I
4
(1 1
+ +NN
1+ v
bN
2(11 + v)
v
(202(4)
1he 2
C3
H2 DD+
(24c1)
140
(4)
1-v
Hmaxx D1+v
+
toN-
1+ V/
N
1+
(bN) '2"
This proves the claimed convergence rate, and the oracle complexity bound easily follows since each iteration of the algorithm requires only 1 query to go.
Corollary 41. Consider problem ① under the setting from Example and also under Assumption 2 Let Algorithm be applied to this problem with the oracle 9 Gb. Then, for any k 1, we have
[[F()x)] - F* v Cj (
(v)DI+H cg(v)Hmax: (m)x(v) ++ + +40.D
201cs
k -
3m
(bk)) 1
bk
where ey = (80204) 2 (3oa) 2
(() and cg(v)
= (4801e8)
2
($) 1-v
0(). To reach
1tv
1+v
[[F(x))] - Ft S for any 6 > 0, it suffices to make O (1 ([H)(W))
to
1450 + Mmax(u) पि. D32
D bea
queries 9o-
Proof. Let k 2 1 be arbitrary and denote for brevity F2 = Hmax- = Hm) Taking into account Remark 35 and applying Theorem g
Hy and we get, for any
0g > 0,
2 FB < AC2CH -o D2
1- v
1-2 ITc
24c C4 max bk
H Fee D2
1- v
1-v ITv
k(k
2(1 v)o,_
2(1 + vVōg_
+
Ca (k + 2)
2 + 63 + oke
4
3
20,4s 2014 40.D where 0k = 4o, D
Minimizing the right-hand side in By and 69 (using
#
bk
Lemma 36 twice) and estimating 1/4 (A: + +)
< [1 + 1), we obtain
FB <
2
402c,H,
5 TFo D
1-
175
14
+
20x v)
3
(k 11)
1 1+
k(k +111 1)
2(1 + v)
1-
(1+D) 2) 1ov
2
max D
1-
T#c
0k
1+
bk:
2(1 + Fv)
1 --v V
(802c4) 1
(2))
H2
(48c)ca) C4)
(1)
-
H Huax D4+v
+ OR-
1+
k (k+
1 v
(bk) -
This proves the claimed convergence rate, and the oracle complexity bound easily follows since each iteration of the algorithm requires only ((1) queries to Gr.
Remark 42. In the proof of Corollary 41 it was important that 8y and 5g were allowed to be two separate constants. If we were not paying attention to such a separation and simply used the same
everywhere, we would end up with the much weaker rate of 0 (max(y) for the second term.
k2
33

---

F33 Explicit Variance Reduction with SVRG
Corollary 43. Consider problem I under the setting from Example 12 and also under Assumption Let UniSvrg (as defined by Algorithm 3 be applied to this problem with the stochastic oracle و 9b and the full- gradient oracle g f.. Then, for any t 2 1,
Cg H max (mm) [()( - F S ((v
(2t) 12
(62*)
1+
where cf(v) = [(oxe++1)] - (28x) = 0(1), cg(v)= = (96c1ca)
-
0(1), 23 ==
14
1+V
max (ca, 13. To get (F S e, it suffices to make (e), queries to Tb and (1og+ Ne(e))
queries V f, where No(e)= 1 गे. D² + t1 (mmae j D2, Assuming that the complexity of querying Go is no, times bigger than that querying V., we get the total stochastic-orack complexity ON ny log, (e)).
e
Proof. Let t 2 1 be arbitrary and denote for brevity F, ==
11 = Hy(v) and and applying Theorem I0
H Huax= == (v). Taking into account Remark 35
we get, for any
5, 0g > 0,
(0204 + 1)H; D2 1- v
48c C4
H Ion D2
1 1- v
+ 25zdd + 8 0/
Fe S
max
2
2(1 + v/66
b2c
2(1 + v0)0
Minimizing the right-hand side in 8,, 5g (using Lemma 36
twice), we obtain
2 Ft
(c204 + 1)H3 D2
1-
1
(1 11+
4
1+v
2
2(1 + v)
1-v
4
+
2
48c; C4 Hinse D2
1 - v
(1+ (1+
+
1
62
2(1 + v)
1-
Cj H HH D1+
og Hmax D1+t (b2c) 2
(2t)
where cy gence rate.
[202204 + 13]
1 (2ng)
140 1-v and cg (96c1c4) 2 ($)
This proves the claimed conver-
142
142
Let us now estimate the oracle complexity. From the already proved convergence rate bound, we
see that F, < once 2 > O(1) where N(e) = = D2 - D2, At the same time, according to Theorem 10 generate the corresponding ãt, the algorithm needs to make O(2*) queries to Zo and (tt) queries to V.. Combining these two facts together, we get the claimed (e)) queries to Go and (log, ((e) = Olog,, (e)) queries to Vf.
Corollary 44. Consider problem ①[ under the setting from Example 7aaumple[2ande 72 also under Assumption 2 Let UniFastSvrg (Algorithm 4 be applied to this problem with the stochastic oracle 9 9b.
the full- gradient oracle ff. and the epoch length N 2 9. Then, for any t 2t.. where
to = [log, log, N1 - 1 (2 0). it holds that
cg(v) Hmax (m))) (V)))((
E [[F( - F <
N N
11+ 18
(bN) + (t + 1)
18
O(1), C3 = max 1). To get E[F( F* Sc, it suffices to make ((NT(()) queries to Go and (()
queries f. where TE) = Di 0(1). cg(v) (4320144) 1 (7) I-v
where cy(v) [220224 b1
2 30
1=2
1tv
H Mmos (2)
14 + +log loga N. Assuming that
N 2
(oN)
the complexity of querying Jo is nu times bigger than that of querying V and choosing N- = ((s)). m H Dt) 2
we get the total stochastic-oracle complexity of O (
61401/2
ms log log no)
34

---

Proof. Let t 2 2gg be arbitrary, F; = E(a(
F", H H == Hmax(v) (v). Taking
into account Remark 35 and applying Theorem
II]
we get, for any og. 53 0.
FiS 9c244 + H 1 DD2 1- V
14.
54c c4 muux D2
1 V
N(t to + 1)2
2( + v10g
2(1 + v/j0g. bN to + 1)²
5
+ (cst + 1)6, + tóg.
3
Since & 2 2tu, we can estimate --to to + 1- 2 2 to + [ + 1), which gives us
36(0201 + H
T4 D²
1-V 2(1 + v)6g
1-v
21601 H max D²
1
5 N(I+ 1)3
bN(1 + 1)2
2(1 + v)
5 (1+ 1)0g-
+ C1(l + 1)65 +
3
Minimizing the right-hand side in öy, 8g (using Lemma 36 twice), we obtain
2
36(e2c4 + 1) D²
v
It
1/20
(1 + D)S 1
1/2
Fe 5 1
N(I + 1)2
2(1 + v)
1-V
2
216ci C4 Hmax D2
1 -
1t
1+2
(1 (1+))((++1))
+ 1+v
bN + 1)²
2(1 + v)
1 1-v
Ci H mmxx D1t2
N (1+1)
(bN) (1 1)
[72(22c++
+]1 " E and cg (13201c4)
($)
where C gence rate.
This proves the claimed conver-
1+2
1+2
Let us now estimate the number of oracle queries. In view of the above convergence rate bound,
we have F; S e once t 2 T(c) = Ti (c) + 2t = (T) + log log N). where T, (c) =
Trw + Hunn Dite T
Tgíe) where T2(c) = " | 1
+ Hmax Dite 1730 B0
(bN))1+0072
1 N
does not depend on N. Combining this with Theorem 11 saying that, to generate the correspond-
ing 3t, the algorithm needs to make ((Ni) queries Go and (l) queries V,, we get the claimed
O(N((c)) queries to Jo and ((T(c)) queries to f.
Assuming now that the complexity of querying Vf is ns times bigger than that of querying go. we get the total stochastic-orace complexity of O(N + (e)) O(N + nx) N0-=)/0
Tafe)
log log N]). Ignoring the houbly-logarithmi term, we get the expression of the form (N + n2) No =
N + ny.
Ny with ==
1+v E [0, 1], whose minimal value is achieved at N = O(n)). Substituting
1+3v
this value into our complexity bound, we get the stochastic-oracle complexity of Omrs( (117//13
(e(c)
2u
log m)) = (n,
T2(e) + na log log nt))
G Additional Discussion of Related Work
Devolder, Glineur, and Nesterov [15] introduced the notion of the inexact first-order oracle and analyzed the behaviour of several first-order methods for smooth convex optimization using such an oracle. Although their work was motivated by the desire to present the general definition of an inexact oracle covering many different applications. it was also observed that this oracle model is suitable for studying weakly smooth problems. This insight was later used in (45) to develop universal gradient methods for Hölder smooth problems. First stochastic gradient methods for approximately smooth functions with inexact oracle were proposed in [13]. These algorithms however are not adaptive and require the knowledge of problem-dependdr constants. For more details on the subject, see [4]
Inexact Oracle and Approximate Smoothness.
35

---

20-1
10"1
1.5
10-h
20-4
10-
10"1
1014-
20a1
10
20-0
10
20-4
20
10"0
numberol
of cnrie
122
10-1
20-3
10"1
10-1
10-7
30-1
20-
10"1
20
10
10"
10-1
20000) 212003
Figure 3: Comparison of various methods on the logistic regression problem with real-world data.
Parameter-Free Methods. Parameter- algorithms originating from the literature online learning (9 [0 40 (7 [55] is another popular type of adaptive methods. They are usually endowed with mechanisms helping achieving efficiency bounds that are almost insensitive (typically, with logarithmic dependency) to the error of estimating certain problem parameters, such as the diameter of the feasible set 6
Variance Reduction. Variance reduction techniques encompass a set of strategies that enhance the convergence speed of SGD when multiple passes are possible over the training dataset. Various researchers simultaneously introduced methods to reduce variance around the same period [27] 38
50
52 58 60). The consideration of mini-batching in the context of these methods is documented in 33, while, in (20), it is shown that the convergence rate is influenced by both the average and the maximum smoothness of individual components. For further details, see (2T) and the references therein.
Sometimes, it is even not necessary to use an explicit variance reduction mechanism. SGD may converge fast in the so-called over over-parameterizee regime, or when the stochastic noise is small the optimal solution [8] 35 37 43 [T]. In this work, we call this effect implicit variance reduction.
Such a situation is also considered in [19 [4] and, more recently, Woodworth and Srebro (59) proposed an accelerated SGD algorithm for this setting, under the assumption that the smoothness and noise constants are known.
H Additional Experiments
H.1 Logistic Regression with Real-World Data
In this section, we present experiments on the logistic regression problem:
min f(x) = 1 |
log(1 + b)(a)))))
1=1
where a, Rd and b, E (-1, 1} are features and labels taken from diverse real-world datasets from LIBSVM [7]: mushrooms (d < n)), w8a (d < n), leu (d >> n) and colon-cancer (d >>>>> n). The dataset leu is quite special because satisfies the so-called interpolation condition, meaning that the variance at the optimum is zero. We fix = and use the mini-batch size of b = 32 for the first two for the last two.
datasets and
Figure shows the results our experiments. The solid lines and the shaded area for each method represent, respectively, the mean and the region between the minimum and the maximum values after three independent runs of the algorithm. We see that, on the leu dataset, UniSgd and UniFast converge fast as the best non-accelerated and accelerated SVRG methods, respectively, which
36

---

8-333
1+144
1-2
1.7
120
120
1845
DROEE 530000 230000 JOMB0 250089
20089 5203 NOERR LOOCCELOOSSSOE
2833
17
100
.03C 13000 23A00 JOM80
5200 LOOKKLS
3803
4ICE
6-11
1-11
337
6-12
1.5
105
10
10
150
107
14*
18
407
25:000
2558 1128 75000 200001000010000
+000
$2000
ofaccharic
15
72
0.0
55
10P
1373 P70chan 0800
Figure 4: Comparison of our methods for different stepsize update rules on the polyhedron feasibility problem.
confirms theory on implicit variance reduction. Otherwise, these two SGD methods typically much slower than the SVRG algorithms. Our UniSvrg method performs consistently better than AdaSVRG across all the datasets. Overall, all adaptive accelerated SVRG methods demonstrate comparable performance for solving these smooth problems.
H.2 Comparison between Stepsize Update Rules
In this section, we compare the AdaGrad stepsize rule 3 with the other rule for UniSgd (Algorithm Tp. UniFastSgd (Algorithm{2) UniSvrg (Algorithm B) and UniFastSvrg (Algorithm 4 We consider the polyhedron feasibility and logistic regression problems under the same setups in Section and Appendix H.I
The results are shown in Figs. anddn where we plot the function residual and the stepsize (inverse of M) against stochastic oracle calls. We see that the two stepsize rules work very similarly across all test cases, which was not evident from the theory alone.
37

---

6-11
6914
37
10
1E-3
10-4
30.11
10"0
20-1
30:10
16
20-14
of
of cifo
of
11.
12
2200 234
1008 2050K 30.00
20L33
4624
620
J0CC
2XX
J00C 4200
6-11
e-114
4-1
12"
12'5
33-
30
21x4
11.4
oawter vecterns mede cals
1 wwwteet warerrhh
number Mecwit CNICE-ats
13"1
12
13-
Figure 5: Comparison of our methods for different stepsize update rules on the logistic regression problem with real-world data.
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Each claim is justified by theorem.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long clear that these goals not attained by the paper.
38

---

2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Each theorem is followed by discussion. For the numerical experiments in Section / we carefully discuss the performance of the method. Additional experiments are presented in Appendix H
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, c.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Answer:
[Yes]
Justification: Yes. This a theory paper. All proofs are provided the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
39

---

Answer: [Yes]
Justification:
We provide the pseudocode and the hyperparameter settings for all algorithms.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g.. to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
We provide the GitHuu link to our code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.c ec/
boblic/guiddss/ http:///guuido///oeuuuiiiisssss
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https /niiss cc/
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
40

---

The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Everything is carefully described in Section 8 and Appendix H
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: Different runs of the same algorithm for the same hyperparameter settings result almost the same performance in our experiments. Therefore, we plot only one curve for each method, focusing more on highlighting the (more significant) differences between various methods.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
41

---

Answer: [No]
Justification: This is not important for the results we present since the algorithms are compared in terms of oracle calls and not the actual time of execution. All experiments run on a standard MacBook Pro laptop and do not require a lot of computational power.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: This is theory paper.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g.. there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: This is theory paper. We do not expect immediate societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (c.g., disinformation. generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out, For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
42

---

11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Does not apply.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We cite the LIBSVM dataset.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. cww datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-pa re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do not release any new assets in this paper.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/modell as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
43

---

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


Reviews:
[{"review_id": "d6CPpudyjr", "reviewer": "Reviewer_PtE8", "summary": "This paper studied how to apply AdaGrad type stepsize for stochastic convex optimization in a unified way. It proposed different algorithms and a general rule for the stepsize. Later, the authors presented different convergence rates under different settings, all of which match the existing best results. Finally, numerical experiments are given to show the better performance of these new algorithms.", "questions": "See **Weaknesses**.", "limitations": "Not applicable.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The paper also extends the result to the Hölder smooth case.", "weaknesses": "1. The major weakness is still Assumption 2. Though I understand this condition is widely used in the prior works with AdaGrad stepsize, this doesn't mean we should always accept it. \n\n    **i.** From the practical perspective, a bounded domain means one either has some prior information on the solution or puts some artificial constraints on the problem. However, both of them may not be realistic. A simple example is logistic regression with separable data (but this is unknown in advance). Then clearly, putting a bounded domain can guarantee the existence of $x^*$. However, one can notice that a better solution always exists but not in the domain.\n\n    **ii.** From the analysis perspective, with a bounded domain, one can immediately bound $\\frac{M_k\\\\|x_k-x^*\\\\|^2-M_k\\\\|x_{k+1}-x^\\*\\\\|^2}{2}\\leq\\frac{M_k\\\\|x_k-x^*\\\\|^2-M_{k+1}\\\\|x_{k+1}-x^\\*\\\\|^2}{2}+O((M_{k+1}-M_{k})D^2)$ to get a telescoping sum, which significantly simplify the analysis. In my experience, this is the major hardness. Without a bounded domain, one has to pay more effort to control this term or may meet other difficulties if one chooses to divide $M_k$ in the analysis.\n\n    **iii.** More importantly, I think different works with AdaGrad-like stepsize are trying to relax it recently as mentioned by the authors.\n    \n    **iv**. To summarize, under Assumption 2, the paper is more like a combination of different existing results. Nothing particularly new I can find in both algorithms and proofs. Even under Assumption 1 (or any inexact oracle), the proofs still follow the classical steps and one only needs to put $\\delta$ in the R.H.S. of every inequality.\n\n2. If I am not wrong, all results (except Theorems 7 and 8) in the paper hold for any $F(u)$ but not only $F^*$. If so, the authors can add a remark to state it to improve the paper. But feel free to correct me if I missed something.\n\n3. For some plots, I cannot find the confidence interval. Please add it according to the checklist.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your time and efforts spent on reviewing this manuscript. We\nappreciate the feedback and would like to make some comments on the points you\nraised in your review.\n\n## Major remarks\n\n1. Our assumption on the bounded feasible set is satisfied whenever one knows\n   some upper bound $R$ on the distance $\\\\| x_0 - x^* \\\\|$ from the initial point\n   to the solution. In this case, we can easily transform our initial problem\n   into the one with the bounded feasible set of diameter $D = 2 R$ by adding\n   the additional simple ball constraint $\\\\| x - x_0 \\\\| \\leq R$. This is\n   essentially the setting we consider.\n\n   We agree that it would be highly desirable to develop a completely\n   parameter-free method for stochastic optimization, which would not require\n   the knowledge of any problem-dependent parameters and would automatically and\n   efficiently adapt to all of them. However, according to the several recent\n   works (see [CH24,AK24,KJ24]), this seems too much to ask for. In\n   contrast to the standard deterministic optimization, where one can compute\n   exact function values and use line-search techniques by paying only an\n   additive logarithmic term for not knowing the parameters of the problem, for\n   stochastic optimization, one really needs some nontrivial knowledge of either\n   the distance to the solution $R$, or the smoothness constant / oracle's\n   variance, etc. Without this, the method would not be able to achieve a nearly\n   optimal complexity.\n   \n   In other words, without assuming the knowledge of $R$, we would need to\n   impose other restrictive assumptions such as the knowledge of the Lipschitz\n   constant and/or oracle's variance. But then the algorithm will be tailored a\n   particular function class and will not be as universal as our methods\n   (working **simultaneously** for each Hölder class and different variance\n   assumptions). Therefore, it is quite debatable which assumption is actually\n   better.\n\n2. Note that problems with bounded domains arise quite commonly in machine\n   learning problems. In fact, any $\\ell_2$-regularized convex problem $\\min_x\n   [f(x) + \\frac{\\lambda}{2} \\\\| x \\\\|^2]$ ($P_{\\lambda}$) (e.g., logistic\n   regression) is equivalent to $\\min_x \\\\{ f(x) : \\\\| x \\\\| \\leq D \\\\}$ ($P'\\_D$)\n   for a certain $D$, so that there is a one-to-one correspondence between them.\n   In practice, one usually selects the right regularization coefficient\n   $\\lambda$ by using the grid search, i.e., solving $(P\\_{\\lambda})$ for\n   multiple values of $\\lambda$ and checking the quality of the resulting\n   solution $x_{\\lambda}$. But this is exactly the same as doing the grid search\n   over $D$, solving $(P'\\_D)$ and checking the quality of the corresponding\n   solution $x'\\_D$. For an additional discussion of bounded domains, see also\n   Ch. 5 in [SNW11] and p. 125 in particular.\n\n3. We kindly disagree with your assessment that, under Assumption 2, our paper\n   is just a trivial combination of different existing results. Consider, for\n   example, the following two particular cases of (only a part of) our results:\n   - Adaptive accelerated SGD for smooth problems with the bound via $\\sigma_*$\n     (Theorem 8 for $\\delta_f = \\delta_{\\hat{g}} = 0$).\n   - Adaptive accelerated SVRG method for functions with Hölder-smooth\n     components (last row in Table 2 or Corollary 42).\n\n   In our opinion, both results are quite nontrivial:\n   \n   1) The first (nonadaptive)\n   accelerated method with the bound via $\\sigma_*$ was suggested only recently,\n   in [WS21]; the adaptive method was mentioned there as an open question. The\n   algorithm was later revisited and improved in [IJLL23] (by properly\n   separating the smoothness constants), however, the method was still\n   non-adaptive.\n   \n   2) We are aware of only one adaptive accelerated SVRG method, namely, AdaVRAE\n   from [LNEN22], which was proven to work only for functions with Lipschitz\n   gradient. However, as we explained in our reply to Reviewer soXZ, that\n   algorithm and the corresponding proofs are rather complicated and it is\n   extremely difficult to check if the method provably works for the more\n   general class of Hölder-smooth problems.\n\n   Could you please be more specific and explain in detail why you believe that\n   the above two results are not particularly new and easily follow from the\n   existing results in the literature (assuming our Assumption 2 holds)?\n   Please provide some references.\n\nReferences:\n- [CH24] Y. Carmon, O. Hinder. The Price of Adaptivity in Stochastic Convex\n  Optimization. arXiv:2402.10898, 2024.\n- [AK24] A. Attia, T. Koren. How Free is Parameter-Free Stochastic Optimization?\n  ICML, 2024.\n- [KJ24] A. Khaled, C. Jin. Tuning-Free Stochastic Optimization. ICML, 2024.\n- [WS21] B. Woodworth, N. Srebro. An Even More Optimal Stochastic Optimization\n  Algorithm: Minibatching and Interpolation Learning. NeurIPS, 2021.\n- [LNEN22] Z. Liu, T. Nguyen, A. Ene, H. Nguyen. Adaptive Accelerated\n  (Extra-)Gradient Methods with Variance Reduction. ICML, 2022.\n- [IJLL23] S. Ilandarideva, A. Juditsky, G. Lan, T. Li. Accelerated stochastic\n  approximation with state-dependent noise. arXiv:2307.01497, 2023.\n- [SNW11] S. Sra, S. Nowozin, S. Wright. Optimization for Machine Learning. MIT\n  Press, 2011.\n\n## Minor remarks\n\n- [W2] ($F(u)$ instead of $F^*$): Yes, this is indeed true, but we do not see\n  how this could be useful for improving our results. We would appreciate it if\n  you could elaborate.\n- [W3] (confidence interval): Thank you, we will add it.\n\n## Conclusion\n\nWe hope we were able to address your concerns and kindly ask you to reconsider\nyour score.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1ppdmuFTA7", "reviewer": "Reviewer_soXZ", "summary": "This paper demonstrates the universality of AdaGrad in stochastic optimization, presenting adaptive algorithms that converge efficiently without prior knowledge of problem-specific constants.  The research contributes novel variance reduction techniques, theoretical proofs, and empirical evidence, showcasing robust performance across optimization scenarios.  It advances the field by offering a versatile approach to stochastic optimization, hinting at potential extensions to more complex problem sets.", "questions": "The prior knowledge is also not required in UniXGrad[28] and AcceleGrad[32]. What is the difference between them and the proposed algorithm?", "limitations": "It is mentioned on line 246 of page 7 that \"Alternative accelerated SVRG schemes with AdaGrad stepsizes (3) were recently proposed in [34]; however, they seem to be much more complicated. \" I think it would be beneficial if the author discussed the algorithm in [34] in detail to help readers understand the advantages of the algorithm in this paper more clearly.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper's strength lies in its theoretical depth, the algorithms are designed to be universally applicable to a wide range of optimization problems, including those with Hölder smooth components, showcasing a high level of adaptability. They also illustrate the impact of the mini-batch size on the convergence of proposed methods, which further helps to verify the theorem.", "weaknesses": "Rather than pointing out shortcomings, I would like to discuss some issues with the authors.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the positive evaluation of our work. Below you can find the\nanswers to your questions / comments.\n\n> The prior knowledge is also not required in UniXGrad[28] and AcceleGrad[32].\n> What is the difference between them and the proposed algorithm?\n\nFrom the algorithmic perspective, all the three methods (UniXGrad, AcceleGrad\nand our UniFastSgd) are different versions of Nesterov's accelerated gradient\nmethod. Our UniFastSgd is one of the standard versions known as the\nMethod of Similar Triangles (see Section 6.1.3 in [44] and [31]). The name stems\nfrom the fact that the next point $x_{k + 1}$ is defined in such a way that the\ntriangles $(x_k, v_k, v_{k + 1})$ and $(x_k, y_k, x_{k + 1})$ are similar (see\nthe picture on page 1 in the PDF attached to the main rebuttal). In contrast,\nUniXGrad and AcceleGrad choose $x_{k + 1}$ as the result of the (projected)\ngradient step from $y_k$, which results in a slightly more complicated iteration\nwith no guarantee of similar triangles.\n\nFrom the theoretical perspective, the convergence rate guarantees for\nUniXGrad and AcceleGrad were proved only under the uniformly bounded variance\nand for functions with either bounded gradients or Lipschitz continuous\ngradients. In other words, it is not known whether UniXGrad and AcceleGrad can\nprovably adapt to the more general assumptions from our paper (such as Hölder\nsmoothness, variance at the minimizer, etc.). It might be possible to extend our\ntechniques to those methods as well, but we have not investigated this direction\nas we personally find the Method of Similar Triangles more elegant and simpler\nto work with.\n\n> It is mentioned on line 246 of page 7 that \"Alternative accelerated SVRG\n> schemes with AdaGrad stepsizes (3) were recently proposed in [34]; however,\n> they seem to be much more complicated. \" I think it would be beneficial if the\n> author discussed the algorithm in [34] in detail to help readers understand\n> the advantages of the algorithm in this paper more clearly.\n\nThank you for the suggestion. We agree and will elaborate on this in the revised\nversion of the manuscript. Here are some of the reasons why our method is\nsimpler and more elegant than the AdaVRAE algorithm from [34]:\n\n1. Each epoch of our algorithm is essentially the standard Method of Similar\n   Triangles with the only difference that one of the vertices ($\\tilde{x}$)\n   is fixed during the epoch (we mention this in lines 240-244; see also the\n   picture on page 2 in the PDF attached to the main rebuttal). As a result, its\n   geometry is much easier to understand than that of AdaVRAE, and we can\n   readily apply the classical results for each Triangle Step (such as Lemma 24)\n   without proving everything \"from scratch\".\n2. Our algorithm uses a simple recurrent formula for the sequence $A_t$,\n   namely, $A_{t + 1} = A_t + \\sqrt{A_t}$, which can be easily analyzed using\n   standard techniques (Lemma 32). In contrast, AdaVRAE uses quite complicated\n   ad-hoc formulas which are impossible to even write on a single line.\n\nWe hope we could answer your questions, and kindly ask you to consider\nincreasing your score to support our work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fDLi5ekonZ", "reviewer": "Reviewer_aWSb", "summary": "This paper proves new convergence rates for stochastic gradient methods with\nAdaGrad step-sizes. The authors' build on the fact that AdaGrad step-sizes\nadapt to both the smooth and non-smooth settings and extend these results to\nshow convergence with biased stochastic gradient oracles on functions which are\nonly approximately smooth. Because Hölder-smooth functions satisfy this class,\nthis paper shows that AdaGrad step-sizes lead to universal methods which only\nrequire knowledge of the diameter, $D$. As part of their analysis, the authors\nalso show how to relax the bounded variance assumption and combine AdaGrad\nstep-sizes with acceleration and variance reduction.", "questions": "To reiterate, my questions are:\n\n- Why doesn't SVRG with AdaGrad step-sizes converge exactly and under what\n    conditions is $\\delta_{\\hat g} = 0$ satisfied?\n\n- Why are both Assumptions 6 and 9 required to show convergence of UniSVRG? \n\n- Under what conditions are Assumptions 6/9 weaker than Assumption 3?", "limitations": "The contributions fit into a fairly small gap given previous work and experiments are not actually sufficient to justify the methods. See main review for details.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The theoretical setting is extremely general, covering composite optimization\n    with Hölder smooth functions with biased stochastic gradient oracles\n    satisfying a relaxed variance bound.\n\n- The analysis covers SGD as well as accelerated SGD and (accelerated) SGD \n    with variance reduction.\n\n- The synthetic experiments show that the proposed methods are faster than\n    existing methods and adapt to different degrees of smoothness in the\n    objective function.", "weaknesses": "- The contributions are fairly niche. Universality of (accelerated) SGD with\n    modified AdaGrad step-sizes is known [14], Adagrad is known to converge\n    without bounded variance [2], and AdaGrad step-sizes have been used with\n    (accelerated) SVRG previously [14, 34]. Thus, this paper fits into a small\n    gap by proving universality with a relaxed variance condition and covering\n    both acceleration and variance reduction.\n\n- ~The actually degree to which bounded variance is relaxed is not clear since\n    the connections between Assumption 3 and Assumption 6 are not developed.~\n\n- ~Variance reduce SGD with AdaGrad step-sizes (UniSvrg) only converges to a \n    neighbourhood of the optimal solution even when using an unbiased stochastic\n    gradient oracle.~\n\n- Experiments are only for synthetic problems and do not show the actual relationship\n    between oracle calls and optimization error. \n\n### Detailed Comments\n\n**Note**: The authors have clarified the connection between Assumptions 3 and 6 as well the role of $\\delta_g$ in Theorem 10. \n\n**Assumption 3 vs Assumption 6/9**: \n\nAn important and unaddressed issue is the comparison between between\nAssumption 3 and Assumption 6/9. Clearly Assumption 3 implies Assumption 6/9\nup to constant factors. But, in what circumstances do Assumptions 6/9 hold\nbut the variance is not bounded, i.e. Assumption 3 fails? In comparison to this\nwork, Nguyen et al. [2] give results for (strongly-convex) SGD that depend\nonly on the stochastic gradient variance at the minimizer and without \nany variance assumption. Indeed, the typical assumption in this setting is only\nthat $\\mathbb{E}[\\|g(x^*, \\xi)\\|_2^2]$ is finite.\n\n\n**Theorem 10**\n\nI'm somewhat disturbed that SVRG with Adagrad step-sizes doesn't converge\nexactly to a minimizer $x^*$ under your assumptions. For example, suppose\n$\\nabla f$ is $L$-Lipschitz and $\\bar g = \\nabla f$ so that $\\delta_f$ is zero.\nIn this setting, I expect variance-reduced methods like SVRG to converge\nexactly to a minimizer, but Theorem 10 shows UniSVRG converges to a\nneighbourhood of size $O(\\delta_{\\hat g})$. In comparison, standard SVRG, which\ndoes not require any variance bound (Allen-Zhu and Yuan, [1]), converges\nexactly. Can you please give sufficient conditions for $\\delta_{\\hat g}$ to be\nzero and explain how they compare to standard SVRG assumptions?\n\nAlso, why are both Assumptions 6 and 9 required simultaneously for this\ntheorem? They provide similar bounds on the variance of the gradient\nestimators, so I would have thought that Assumption 9 supplants Assumption 6.\n\n**Experiments**:\n\nI would have liked to see more realistic experiments. I understand that finding\nreal-world problems for which the diameter $D$ is bounded can be difficult, but\none synthetic regression problem is not sufficient to judge the performance of\nthe methods analyzed in this paper. In comparison, Dubois-Taine et al. [14]\ninclude a large number of experiments on real-world data.\n\nIn addition, I strongly dislike the choice to treat one mini-batch gradient\ncomputation as a single oracle call instead of $b$ calls.  While the choice has\nno effects in Figure 1, it is actually quite misleading in Figure 2, where it\nmakes the total SFO complexity of all the algorithms appear to decrease as\nbatch-size increases. In reality, the SFO complexity should decrease until a\nthreshold and then $b$ and then begin to increase again. That is, there is some\noptimal batch-size (usually less than $n$) which minimizes total complexity\n\n\n### Minor Comments\n\n- \"Gradient methods are the most popular and efficient optimization algorithms\n    for solving machine learning problems.\" --- They are not the most efficient\n    methods depending on the problem class and desired sub-optimality, so I\n    wouldn't say this.\n\n- \"However, the line-search approach is unsuitable for problems of stochastic\n    optimization, where gradients are observed with random noise.\" --- you may\n    want to mention that line-search works with stochastic gradients when\n    interpolation is satisfied [1].\n\n- So the difference between the results in Section 4 and [47] is that [47]\n    considers a modification of the Adagrad step-size? You might want to \n    state this modification so the difference is clear. \n\n- Contributions, Bullet 3: I don't like calling this variance reduction. It is\n    well-known that SGD with a constant step-size depends only on the variance\n    of the stochastic gradients at the minimizer [2], but no one would call SGD\n    variance reduced. \n\n- Table 1: \n    - Can you make the font-size larger? It's a little hard to read this\n    table. \n    - If you are reporting Big-O complexities, then can you please put them\n        in Big-O notation?\n    - You should explain in the caption why UniSgd and UniFastSgd have two \n        convergence rates each (e.g. variance assumptions).\n\n- Line 117: If it's satisfied for any $\\delta_f > 0$ then taking limits as\n    $\\delta_f \\rightarrow 0$ would imply that it's also satisfies for \n    $\\delta_f = 0$.\n\n- Line 136: I would say the classical method is due to Nesterov [3], while you\n    are referring to more recent acceleration methods for composite\n    optimization.\n\n- Eq. (4): How you solve this implicit equation, given that $\\hat x_+$ depends\n    on $\\hat M_+$ through the stochastic gradient update?\n\n- Assumption 6: In line 126, you say that the oracle outputs are assumed to be\n    independent. However, from the notation in Assumption 6, it seems that\n    in this case the oracle is evaluated with the same randomness $\\xi$.\n    Indeed, this must be the case else Assumption 6 reduces to Assumption 3.\n    Maybe you can add a remark clarifying this in the text?\n\n- Theorems 4,7: You should comment somewhere in the text that these rates \n    (according to Algorithm 1) are not anytime, but require knowledge of $N$.\n\n- Line 230: This sentence isn't finished.\n\n- Page 7: The spacing between the algorithm blocks is quite weird. You\n    should probably fix this. \n\n- Theorem 11: I would prefer if you stated this without assuming \n    $N \\in \\Theta(n)$. \n\n- Table 2, row 3: I think there's a typographic issue here since you appear to \n    be adding the definition of $N_\\nu(\\epsilon)$ with the log. \n\n- Figures 1, 2: \n    - The font sizes are much too small to read. As a rule of thumb,\n        the size of text in a figure should be at least as large as the size of\n        text in paragraph mode.\n    - Figure 1: It would be nice if you reminded the reader that $q$ is the\n        power in the test problem in Eq. (5).\n\n- Line 916: You should also reference SDCA [4] and SAG [5], which were very\n    early (if not the earliest) variance reduction methods.\n\n### References\n\n\n[1] Vaswani, Sharan, et al. \"Painless stochastic gradient: Interpolation, line-search, and convergence rates.\" Advances in neural information processing systems 32 (2019).\n\n[2] Nguyen, Lam, et al. \"SGD and Hogwild! convergence without the bounded gradients assumption.\" International Conference on Machine Learning. PMLR, 2018.\n\n[3] Nesterov, Yurii. \"A method for solving the convex programming problem with convergence rate O (1/k2).\" Dokl akad nauk Sssr. Vol. 269. 1983.\n\n[4] Shalev-Shwartz, Shai, and Tong Zhang. \"Stochastic dual coordinate ascent methods for regularized loss minimization.\" Journal of Machine Learning Research 14.1 (2013).\n\n[5] Schmidt, Mark, Nicolas Le Roux, and Francis Bach. \"Minimizing finite sums with the stochastic average gradient.\" Mathematical Programming 162 (2017): 83-112.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the positive evaluation!\n\n## Major remarks\n\n1. It seems there is a certain misunderstanding of Ass. 6, which we hope to clarify.\n   \n   Basically, Ass. 6 is satisfied for finite-sum problems with (Hölder) smooth components (see also lines 186-194 in the paper for a more general example).\n\n    The motivation is as follows. Ass. 6 is the generalization of $\\mathbb{E}\\_{\\xi}[\\\\| g(x, \\xi) - g(y, \\xi) \\\\|^2] \\leq 2 L \\beta(x, y)$, where $\\beta(x, y) = f(y) - f(x) - \\langle \\nabla f(x), y - x \\rangle$, for which the main example is the finite-sum objective $f(x) = \\frac{1}{n} \\sum_{i = 1}^n f_i(x)$ with the usual stochastic oracle $g(x, \\xi) = \\nabla f_{\\xi}(x)$ (for a uniformly chosen index $\\xi$) and $L$-smooth components $f_i$. To generalize it to the case when $f_i$ are $(\\nu, H)$-Hölder smooth, we need to add $\\delta$: $\\mathbb{E}\\_{\\xi}[\\\\| g(x, \\xi) - g(y, \\xi) \\\\|^2] \\leq 2 L [\\beta(x, y) + \\delta]$; then, we can take an arbitrary $\\delta > 0$ and let $L = [\\frac{1 - \\nu}{2 (1 + \\nu) \\delta}]^{\\frac{1 - \\nu}{1 + \\nu}} H^{\\frac{2}{1 + \\nu}}$. This is almost our Ass. 6 except that we have the second moment instead of the variance $\\mathbb{E}\\_{\\xi}[\\\\| [g(x, \\xi) - g(y, \\xi)] - [\\nabla f(x) - \\nabla f(y)] \\\\|^2]$ in the left-hand side (for simplicity, we ignore the possibility of using inexact gradients $\\bar{g}$ and function values $\\bar{f}$). Using the variance is better because it is always smaller than the second moment and can easily be reduced with mini-batching.\n\n1. There is no problem with $\\delta_g$ in Thm. 10. First, let us stress that Thm. 10 covers the standard setting of finite-sum problems with $L$-smooth components. In this case, $L_f = L_g = L$, $\\delta_f = \\delta_g = 0$, and we recover the classical result from (Allen-Zhu and Yuan, [1]), without any extra assumptions.\n\n    However, it is important that our method is actually more powerful and converges in other regimes as well, e.g., for finite-sum problems with Hölder-smooth components. Indeed, as discussed before, for such problems, **$\\delta_g$ can be an arbitrary (potentially very small) positive number** (and so can be $\\delta_f$, see lines 116-117 in the paper). Choosing $\\delta_f$ and $\\delta_g$ carefully (by optimizing the rate from Thm. 10 while taking into account the fact that $L_f$ and $L_g$ also depend on these constants), we get the following convergence rate: $F_t \\lesssim \\frac{H D^{1 + \\nu}}{(2^t)^{\\frac{1 + \\nu}{2}}}$ which goes to zero as $t \\to \\infty$. For more details, see Cor. 41.\n\n1. The previous example shows that $\\delta_f$ does not only measure the error\nbetween $\\bar{g}$ and $\\nabla f$ but is also related to the smoothness\nproperties of the objective: even when $\\bar{g} = \\nabla f$, it is still\nmeaningful to allow for $\\delta_f > 0$ (e.g., to handle Hölder-smooth problems).\n\n1. [Ass. 3 vs 6] Indeed, Ass. 6 is weaker than 3 because we can choose any\n$\\delta_g > 0$ and let $L_g \\sim \\frac{\\sigma^2}{\\delta_g}$. Then, Thms. 4 and 5\nbecome simple corollaries of Thms. 7 and 8. On the other hand, as already\ndiscussed above, Asm. 6 is satisfied for finite-sum problems with smooth\ncomponents and the standard oracle, while Asm. 3 may be violated for this case\n(consider the quadratic function on the entire space); even if one defines\n$\\sigma$ in Asm. 3 by looking only at $x$ from the feasible set, $\\sigma$\nwill depend on the diameter of this set and may be potentially very big.\nWe will add the corresponding comments.\n\n1. [Asm. 6 vs 9] When we use exact gradients, $\\bar{g} = \\nabla f$, both are\nequivalent; otherwise, one does not seem to imply the other. For some reason,\nthe current proof of Thm. 10 needs Asm. 9 at one place, namely, in lines\n693-694, to get the Bregman distance term in Lem. 28, which can then be bounded\nvia the function residual using Lem. 29. To remove Asm. 9, we would need to\nobtain a counterpart of Lem. 29 in terms of the approximate Bregman distance\ninstead of the exact one, which we do not know how to do at the moment.\nWe will clarify this.\n\n1. [Experiments] We will take your point into account and add more experiments.\n\n   Regarding the mini-batch size, we are not sure if you are correct. Consider, e.g., SGD with mini-batch size $b$ as applied to minimizing an $L$-smooth convex function. To reach accuracy $\\epsilon$, it needs $N_b = \\frac{L D^2}{\\epsilon} + \\frac{\\sigma^2 D^2}{b \\epsilon^2}$ oracle calls, each such a call requires $b$ stochastic gradients. If the computation is sequential, the total SFO complexity is then $b N_b = \\frac{b L D^2}{\\epsilon} + \\frac{\\sigma^2 D^2}{\\epsilon^2}$, which is minimized for $b = 1$. To our knowledge, mini-batching is provably efficient only when we allow for parallel computations of stochastic gradients; then, the complexity becomes $N_b$ which indeed decreases with $b$ (however, $b$ cannot exceed the limits of our parallelism, e.g., the number of computing nodes). See also Sec. 6 in [54] for a similar point of view.\n\n1. [W1] Please note that [2] considers another variance assumption, namely,\n$\\\\| g(x, \\xi) - \\nabla f(x) \\\\|^2 \\leq \\sigma_0^2 + \\sigma_1^2 \\\\| \\nabla f(x) \\\\|^2$,\nwhich is completely different from ours and is not guaranteed to be satisfied\n(with good constants) even for finite-sum problems with smooth components.\nOur assumption is actually much weaker and have never been explored in the\nliterature on AdaGrad. Furthermore, for the accelerated method with AdaGrad\nstep sizes, nothing has been known except for the classical case when the\nvariance is uniformly bounded. We therefore kindly disagree that our\ncontributions are \"fairly niche\" / straightforward, including also the uniform\nextension of everything to Hölder-smooth problems.\n\n## Minor remarks\n\nUnfortunately, we do not have enough space to answer every remark but we will\nconsider all of them and make the appropriate modifications.\n\n## Conclusion\n\nWe hope we could answer your questions, and kindly ask you to consider\nincreasing your score to support our work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "TdTeeIGyDa", "reviewer": "Reviewer_AhYx", "summary": "The paper explores the adaptive gradient methods for solving convex composite optimization problems. The authors propose two main algorithms, UniSgd and UniFastSgd, equipped with AdaGrad stepsizes. They establish efficiency guarantees under various conditions, demonstrating implicit and explicit variance reduction properties. The results are also extended to incorporate SVRG-type variance reduction, leading to faster convergence rates.", "questions": "See the weaknesses part.", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. This paper extends existing results by showing the universality of AdaGrad stepsizes in a more general setting, providing efficiency guarantees and state-of-the-art complexity bounds.\n2. The proposed methods are adaptive, not requiring problem-specific constants, making them practical for real-world applications.\n3. Numerical experiments validate the theoretical findings, showing the practical effectiveness of the proposed methods.", "weaknesses": "1. Although the authors call their algorithm adaptive methods, the proposed algorithm still requires knowing the domain diameter, which is an obvious drawback. Also, the reliance on the boundedness of the domain might also limit the application of the methods in more general or practical scenarios.\n2. The main body of this paper is difficult to understand. It seems that the algorithms are all rather complicated and the authors do not explain the methods clearly. Also, I think the authors should further emphasize the novelty and the challenge of this paper. \n3. More extensive empirical evaluations across a wider range of practical problems on real-world datasets would strengthen the experiments part of this paper.\n4. The authors claim in the abstract that “the main part can be accessed only via a (potentially **biased**) stochastic gradient oracle”, but it seems that the paper assumes an unbiased stochastic oracle. Maybe I missed something, but I do not find where we use the biased oracle. Can you explain this more clearly?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your time and efforts spent on reviewing this manuscript. We\nappreciate the feedback and would like to make some comments on the points you\nraised in your review.\n\n- [W1]:\n  We agree that this is a drawback and it was explicitly written in the paper.\n  Note, however, that $D$ is indeed the **only** parameter that the methods need\n  to know. This is the price one pays for getting completely universal methods,\n  automatically adapting to a large variety of other parameters (degree of\n  smoothness $\\nu$ and the corresponding smoothness constant $H_{\\nu}$, oracle's\n  variance $\\sigma$, variance at the minimizer $\\sigma_*$, oracle's inexactness\n  $\\delta$, etc.), while enjoying the optimal worst-case complexity estimates,\n  typical for non-adaptive methods. We are not aware of any other algorithms\n  with similar properties, especially, working in such a large number of\n  situations and with such a unified treatment as in our work (basic methods and\n  accelerated ones, with variance reduction and without it, etc.).\n\n  While we do agree that it would be very nice to have completely parameter-free\n  algorithms, it seems that this goal may not be achievable for stochastic\n  optimization problems, at least not without additional, somewhat restrictive,\n  assumptions. Please refer to our detailed reply to Reviewer PtE8.\n\n- [W2]:\n  Thank you for the comment. We agree that it would be better to provide more\n  explanations and intuitions. However, we are rather limited by the page limit\n  and therefore must think twice if we want to add anything extra. Could you\n  please clarify where exactly you would like us to elaborate, except better\n  emphasizing the novelty and the challenge?\n\n- [W3]:\n  Note that our paper is mostly theoretical, and we do not attempt to be\n  exhaustive with experiments. But we will take your point into account and add\n  more experiments in the revised version of the paper.\n\n- [W4]:\n  Yes, of course. Our oracle $\\hat{g}$ is assumed to be an unbiased estimate of\n  $\\bar{g}$, which is itself only an **approximation** to the true gradient\n  $\\nabla f$. Thus, $\\hat{g}$ is, in general, a biased estimate of $\\nabla f$:\n  $\\mathbb{E}\\_{\\xi}[\\hat{g}(x, \\xi)] = \\bar{g}(x) \\neq \\nabla f(x)$. Some\n  particular examples where we have biased gradients are mentioned in lines\n  114-122 and also in lines 186-194. For instance, if we work with finite-sum\n  problems, $f(x) = \\frac{1}{n} \\sum_{i = 1}^n f_i(x)$, where each function\n  $f_i$ represents another nontrivial optimization problem with a strongly\n  convex objective, $f_i(x) = \\max_{u_i} \\Psi_i(x, u_i)$, whose solution\n  $\\bar{u}\\_i(x)$ can be found with accuracy $\\delta$, then the natural\n  stochastic gradient $\\hat{g}(x, \\xi) = \\nabla_x \\Psi_{\\xi}(x,  \\bar{u}_{\\xi}(x))$\n  (with uniformly chosen index $\\xi$) is a biased estimate of\n  $\\nabla f(x)$, and $\\delta_f = \\delta$.\n\nWe hope we were able to address all your concerns and kindly ask you to increase\nyour score.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all the reviewers for their valuable comments. We did our best to
answer all the questions and will be happy to continue the discussion if
needed.

After reading the reviews, we had the impression that several aspects of our
work were probably unnoticed or underappreciated (perhaps, due to the high level
of generality of our presentation). Therefore, we would like to draw the
reviewers' attention to the following few of our contributions which are
particular cases of our general results but are nonetheless quite important in
themselves:

1. Adaptive methods for minimizing finite-sum objectives
$f(x) = \frac{1}{n} \sum_{i = 1}^n f_i(x)$ with $L$-smooth components $f_i$,
whose convergence rate is expressed in terms of the variance $\sigma_*$ at the
minimizer (Theorems 7 and 8 for $\delta_f = \delta_g = 0$).

1. Extensions of these algorithms to Hölder-smooth problems (first two rows in
Table 2 or Corollaries 39 and 40).

1. Variance reduction methods for finite-sum problems with Hölder-smooth
components.

We are not aware of any other works that provably solve any of the
aforementioned problems, even under the assumption that the distance to the
solution is known, or the feasible set is bounded.

Regrading the first contribution or, more generally, relaxing the assumption of
uniformly bounded variance, we know only the works [FTCMSW22,AK23]. However,
they use a different variance assumption, which is weaker than ours and is not
guaranteed to hold for finite-sum problems with smooth components. Furthermore,
the corresponding methods are not accelerated. The first non-adaptive
accelerated method capable of solving finite-sum problems while enjoying the
variance bound only at the minimizer was developed only recently in [WS21];
making this method adaptive was left as an open question.

As for the Hölder smoothness, it is important to mention that the very fact that
stochastic AdaGrad methods, including the accelerated algorithm, provably work
for the entire Hölder class (and not just for its extreme subclasses&mdash;those
with bounded or Lipschitz continuous gradients&mdash;which was known before from
[LYC18,KLBC19]) is very recent and was proved only in [RKWAC24]. The extension
of the corresponding results to $\sigma_*$-bounds and explicit variance
reduction are both highly nontrivial tasks.

We would also like to point out that, for each of the above three contributions,
we do not only present the basic methods but also the accelerated ones, which is
always rather challenging.

With that being said, we hope the reviewers could take another look at our work
and increase their scores.

Finally, we attach the PDF containing the two pictures clarifying the geometry
of our accelerated methods, as discussed with Reviewer soXZ.

References:
- [RKWAC24] A. Rodomanov, A. Kavis, Y. Wu, K. Antonakopoulos, V. Cevher. ICML, 2024.
- [AK23] A. Attia and T. Koren. SGD with AdaGrad Stepsizes: Full Adaptivity with
  High Probability to Unknown Parameters, Unbounded Gradients and Affine
  Variance. ICML, 2023.
- [FTCMSW22] M. Faw, I. Tziotis, C. Caramanis, A. Mokhtari, S. Shakkottai, R.
  Ward. The Power of Adaptivity in SGD: Self-Tuning Step Sizes with Unbounded
  Gradients and Affine Variance, COLT, 2022.
- [WS21] B. Woodworth, N. Srebro. An Even More Optimal Stochastic Optimization
  Algorithm: Minibatching and Interpolation Learning. NeurIPS, 2021.
- [KLBC19] A. Kavis, K. Levy, F. Bach, V. Cevher. UniXGrad: A Universal,
  Adaptive Algorithm with Optimal Guarantees for Constrained Optimization.
  NeurIPS, 2019.
- [LYC18] K. Y. Levy, A. Yurtsever, V. Cevher. Online Adaptive Methods,
  Universality and Acceleration. NeurIPS, 2018.

Meta-review: After a length author response period, all reviewers ultimately recommended acceptance of the paper.
Decision: Accept (poster)