Universality of AdaGrad Stepsizes for Stochastic Optimization: Inexact Oracle, Acceleration and Variance Reduction

Authors: anton  rodomanov
xiaowen  jiang
sebastian stich cispa
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 20:54:53

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.

Main paper: 
 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 to select stepsizes based on 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 a line search. This is a simple yet powerful mechanism which automatically chooses the best stepsize by checking at each iteration a 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, it is common instead to apply so-called adaptive methods which set up their 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 [32] 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 [34] 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 to know neither the corresponding Lipschitz constants, nor the oracle's variance but enjoying the rates which are characteristic for algorithms 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 [12] . 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 a 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 (4) ).All the previously discussed results were proved only for the classical stochastic optimization setting where the variance of stochastic gradients is 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 variance-reduction. The first such an algorithm was proposed in [16] . The accelerated SVRG method enjoying optimal worst-case oracle complexity for smooth finite-sum optimization problems was later presented in [36] .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.k.a. (δ, L)-smooth) 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 3, with identifying the key property of AdaGrad stepsizes, which allows us to apply these stepsizes, in a unified manner, in a variety of situations we consider later. We present our two mains algorithms, UniSgd and UniFastSgd 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, we 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 Table 1 (in 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 Table 1 : Summary of main results for solving problem (1) with our methods. "Convergence rate" is expressed in terms of the expected function residual at iteration k (or t, depending on the method). "SO complexity" denotes the cumulative stochastic-oracle 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 p g; for SVRG methods, we assume that querying the (inexact) full-gradient oracle s g is n times more expensive than p g, and define the SO complexity as N p g + nNs g , where N p g and Ns g are the number of queries to p g and s g, respectively. The second and third columns should be understood in terms of the BigO-notation which we omit for brevity.Convergence rate SO complexity Assumptions Reference UniSgd (Alg. 1)L f D 2 k + σD √ k + δ f k 1, 2, 3Thm. 4(L f +L p g )D 2 k + σ * D √ k + δ f + δ p g1, 2, 6 Thm. 7UniFastSgd (Alg. 2) of the feasible set; the methods automatically adapt to all other problem-dependent constants. In a number of special cases, our algorithms achieve known state-of-the-art 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.L f D 2 k 2 + σD √ k + kδ f k 1, 2, 3 Thm. 5 L f D 2 k 2 + L p g D 2 k + σ * D √ k + kδ f + δ p g 1, 
preliminaries: 
 Notation. We work in the space R d equipped with the standard inner product ⟨•, •⟩ and a certain Euclidean norm: ∥x∥ := ⟨Bx, x⟩ 1/2 , where B is a fixed positive definite matrix. The dual norm is defined in the standard way: ∥s∥ * := max ∥x∥=1 ⟨s, x⟩ = ⟨s, B -1 s⟩ 1/2 .For a convex function ψ : R d → R ∪ {+∞}, its (effective) domain is the following set: dom ψ := {x ∈ R d : ψ(x) < +∞}. By ∂ψ(x), we denote the subdifferential of ψ at a point x ∈ dom ψ; the specific subgradients are typically denoted by ∇ψ(x).A convex function f : R d → R is called (ν, H)-Hölder smooth for some ν ∈ [0, 1] and H ≥ 0 iff ∥∇f (x) -∇f (y)∥ * ≤ H∥x -y∥ ν for all x, y ∈ R d and all ∇f (x) ∈ ∂f (x), ∇f (y) ∈ ∂f (y).Apart from the special case of ν = 0, such a function f is differentiable at every point, i.e., ∂f (x) is a singleton. A (1, L)-Hölder smooth function is usually called L-smooth.For a convex function ψ : R d → R ∪ {+∞}, point x ∈ R d , vector g ∈ R d , and coefficient M ≥ 0, by Prox ψ (x, g, M ) := argmin y∈dom ψ {⟨g, y⟩ + ψ(y) + M 2 ∥y -x∥ 2 }, we denote the proximal mapping. When M = 0, we allow the solution to be chosen arbitrarily.For a convex function f : R d → R, points x, y ∈ R d and ∇f (x) ∈ ∂f (x), we denote the Bregman distance by β ∇f (x) f (x, y) := f (y) -f (x) -⟨∇f (x), y -x⟩ (≥ 0). When the specific subgradient ∇f (x) is clear from the context, we use the simplified notation β f (x, y).The positive part of t ∈ R is [t] + := max{t, 0}. For τ > 0, we also use log + τ := max{1, log τ }.Problem Formulation. In this paper, we consider the composite optimization problemEQUATIONwhere f : R d → R is a convex function, and ψ : R d → R ∪ {+∞} is a proper closed convex function which is assumed to be sufficiently simple in the sense that the proximal mapping Prox ψ 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, we use the following assumption:Algorithm 1 (s xN , xN , MN ) ∼ = UniSgd p g,ψ (x0, M0, N ; D) Input: Oracle p g, comp. part ψ, point x0 ∈ dom ψ, coefficient M0, iteration limit N , diameter D. 1: g0 ∼ = p g(x0). 2: for k = 0, . . . , N -1 do 3: x k+1 = Prox ψ (x k , g k , M k ), g k+1 ∼ = p g(x k+1 ). 4: M k+1 = M+(M k , D 2 , x k , x k+1 , g k , g k+1 ) ▷ e.g., (3) = M 2 k + 1 D 2 ∥g k+1 -g k ∥ 2 * .5: return (s xN , xN , MN ), where sxN := 1 N N i=1 xi.Assumption 1. The function f in problem (1) is approximately smooth: there exist constants L f , δ f ≥ 0 and s f :R d → R, s g : R d → R d such that, for any x, y ∈ R d , β f, s f ,s g (x, y) := f (y) - s f (x) -⟨s g(x), y -x⟩ satisfies the following inequality: 0 ≤ β f, s f ,s g (x, y) ≤ L f 2 ∥x -y∥ 2 + δ f .Assumption 1 is well-known in the literature under the name (δ, L)-oracle and was originally introduced in [15] . It covers many interesting examples. For instance, ifEQUATION1+ν (see Theorem 13) . If f can be uniformly approximated by an L-smooth function ϕ, i.e., ϕ(x) ≤ f (x) ≤ ϕ(x)+δ, then Assumption 1 is satisfied with s f = ϕ, s g = ∇ϕ and δ f = δ. If f represents another auxiliary optimization problem with a strongly concave objective, e.g., f (x) = max u Ψ(x, u), whose solution s u(x) can only be found with accuracy δ, then f satisfies Assumption 1 with sf (x) = Ψ(x, s u(x)), s g(x) = ∇ u Ψ(x, s u(x)) and δ f = δ. For more details and other interesting examples, we refer the reader to [15] .In what follows, we assume that we have access to an unbiased stochastic oracle p g for s g. Formally, this is a pair p g = (g, ξ) consisting of a random variable ξ and a mapping g : R d × Im ξ → R d (with Im ξ being the image of ξ). When queried at a point x, the oracle automatically generates an independent copy ξ of its randomness and then returns pg x = g(x, ξ) (notation: p g x ∼ = p g(x)). We call g and ξ the function component and the random variable component of p g, respectively. At this point, we only assume that our stochastic oracle p g is un unbiased estimator of s g, and later make various assumptions on its variance.Another important assumption on problem (1) , that we need in our analysis, is the boundedness of the feasible set dom ψ. Assumption 2. There exists D > 0 such that ∥x -y∥ ≤ D for any x, y ∈ dom ψ.Assumption 2 is rather standard in the literature on adaptive methods for stochastic convex optimization (see [16, 18, 30, 34, 36, 49] ) and can always be ensured with D = 2R 0 whenever one has the knowledge of an upper bound R 0 on the distance from the initial point x 0 to the solution x * . To that end, it suffices to rewrite the problem (1) in the following equivalent form:min x∈dom ψ D [f (x) + ψ D (x)], where ψ D is the sum of ψ and the indicator function of the ballB 0 := {x ∈ R d : ∥x -x 0 ∥ ≤ R 0 }.Note that this transformation keeps the function ψ D reasonably simple as its proximal mapping can be computed via that of ψ 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 ψ = 0, the proximal mapping of ψ D is simply the projection on B 0 .Throughout this paper, we 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 in our methods. 
main algorithms and stepsize update rules: 
 We now present our two main algorithms for solving problem (1): UniSgd (Algorithm 1), and its accelerated version, UniFastSgd (Algorithm 2). Except the specific choice of the stepsize coefficients M k , both algorithms are 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 as the Method of Similar Triangles (see, e.g., Section 6.1.3 in [46] ).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), a k+1 = 1 2 (k + 1), A k+1 = A k + a k+1 . 4: y k = A k A k+1 x k + a k+1 A k+1 v k , gy k ∼ = p g(y k ).v k+1 = Prox ψ (v k , gy k , M k a k+1 ). 6: x k+1 = A k A k+1 x k + a k+1 A k+1 v k+1 , gx k+1 ∼ = p g(x k+1).EQUATION= M 2 k + a 2 k+1 D 2 ∥gx k+1 -gy k ∥ 2 * .current point x ∈ dom ψ with the stochastic gradient p g x ∼ = p g(x), next iterate p x + = x + (p g x ) ∈ dom ψ (whichEQUATIONwhere p∆( x M + ) := β f, s f ,s g (x, p x + ) + ⟨s g(x) -p g x , p x + -x⟩ - x M+ 2 ∥p x + -x∥ 2 , c 1 , c 2 , c 3 , c 4 > 0 are some absolute constants, and Var p g (x) := E ξ [∥g(x, ξ) -s g(x)∥ 2 * ]is the variance of p g. The expectations in (2) are taken w.r.t. the randomness (ξ, ξ + ) coming from p g x ≡ g(x, ξ), p g x+ ≡ g(p x + , ξ + ).The main example is the following AdaGrad rule:EQUATIONFor this rule, we have c 1 = 5 2 , c 2 = 4, c 3 = 6, c 4 = 2 (see Lemma 20) . Another interesting example recently suggested in [49] is x M + found from the equationEQUATIONThis equation admits a unique solution which can be easily written down in closed form (see Lemma E.1 in [49] ). For this rule, we havec 1 = 1, c 2 = 2, c 3 = 6, c 4 = 2 (see Lemma 21).Inequality (2) is 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 stepsizesM k ≡ Ď M (in which case M = x 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 inequality but now Ď M is the virtual stepsize existing only in the theoretical analysis. The price for this is the extra error term [min{ x M + , Ď M } -M ] + Ω appearing in the right-hand side of (2). The crucial property of this error term is that it is telescopic, Lemma 18) and therefore its total cumulative impact is always bounded by the controllable constant Ď M Ω. Although a 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, 36] ), 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.k i=0 [min{M i+1 , Ď M } -M i ] + Ω = [min{M k+1 , Ď M } -M 0 ] + Ω (see 
uniformly bounded variance: 
 In this section, we assume that the variance of our stochastic oracle is uniformly bounded. Assumption 3. For the stochastic oracle p g, we have σ 2 := sup x∈dom ψ Var p g (x) < +∞, where Varp g (x) := E ξ [∥g(x, ξ) -s g(x)∥ 2 * ].Under this assumption, we can establish the following efficiency estimates for our UniSgd and UniFastSgd methods (the proofs are deferred to Appendix C). Theorem 4. Let Algorithm 1 with M 0 = 0 be applied to problem (1) under Assumptions 1-3. Then, for the point s x N generated by the algorithm, we haveE[F (s x N )] -F * ≤ c 2 c 4 L f D 2 N + 2σD 2c 1 c 4 N + c 3 δ f .Theorem 5. Let Algorithm 2 be applied to problem (1) under Assumptions 1-3. Then, for any k ≥ 1,E[F (x k )] -F * ≤ 4c 2 c 4 L f D 2 k(k + 1) + 4σD 2c 1 c 4 3k + c 3 3 (k + 2)δ f .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 O(kδ). 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 [15] ).The complexity results from Theorems 4 and 5 are similar to those from [13] . However, it is important that our methods are adaptive and do not require knowing the constants L f and σ.In the specific case when δ f = 0, 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 ∇f (x * ) = 0. 
implicit variance reduction: 
 The assumption of uniformly bounded variance may not hold for some problems, or the corresponding constant σ 2 might be quite large, which is why there has recently been a growing interest in various alternative variance bound assumptions [5, 22, 24, 29, 42, 54, 59] . One interesting option is expressing complexity bounds via the variance at the minimizer, σ 2 * := Var p g (x * ), assuming that the stochastic oracle p g satisfies some extra smoothness conditions. Let us show that, for our Algorithms 1 and 2, we can also establish such bounds, moreover, this can be done without any modifications to the algorithms.In this section, we study problem (1) under Assumptions 1 and 2 and also under the following additional smoothness assumption on the variance: Assumption 6. There exist δ = E ξ [∥[g(x, ξ) -g(y, ξ)] -[s g(x) -s g(y)]∥ 2 * ].Note that Var p g (x, y) is the usual variance of the estimator g(x, ξ) -g(y, ξ) which uses the same randomness ξ for both arguments. Hence, Var p g (x, y) ≤ E[∥g(x, ξ) -g(y, ξ)∥ Lemma 16) . Furthermore, if p g b is the mini-batch version of p g of size b, then p g b satisfies Assumption 6 with the same δEQUATIONδ p g = 1 Lmax E ξ [L ξ δ ξ ] (≤ E ξ [δ ξ ]), L p g = L max , where L max := sup ξ L ξ (seep g b = δ p g but L p g b = 1 b L p g = 1 bL max which can be much smaller than L max when b is large enough.Under the new assumption on the variance, UniSgd enjoys the following convergence rate (see Appendix D.1 for the proof). Theorem 7. Let Algorithm 1 with M 0 = 0 be applied to problem (1) under Assumptions 1, 2 and 6, and let σ 2 * := Var p g (x * ). Then, for the point s x N produced by the method, we haveE[F (s x N )] -F * ≤ c 4 (c 2 L f + 12c 1 L p g )D 2 N + 2σ * D 6c 1 c 4 N + c 3 δ f + 4 3 δ p g .Comparing the above result with Theorem This corresponds to classical results on the usual SGD for which we know all problem dependentconstants. 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 4 and 7.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 (1) under Assumptions 1, 2 and 6, and let σ 2 * := Var p g (x * ). Then, for any k ≥ 1, we haveE[F (x k )] -F * ≤ 4c 2 c 4 L f D 2 k(k + 1) + 24c 1 c 4 L p g D 2 k + 1 + 4σ * D 2c 1 c 4 k + c 3 3 (k + 2)δ f + 4 3 δ p g .Comparing our previous complexity bound for UniFastSgd under the assumption on uniformly bounded variance (Theorem 5) with the bound from Theorem 8, we see that, instead of simply replacing σ with σ * , L f with L f + L p g and δ f with δ f + δ p g , which was the case for the basic method, the situation is now not that simple. Specifically, the L f and L p g terms now converge at different rates: O( 1 k 2 ) and O( 1 k ), respectively. While this may seem strange at first, this behavior is actually unavoidable, at least in the case when δ f = δ p g = 0 (see, e.g., Section E in [59] ). For the case when δ f = δ p g = 0, the complexity result from Theorem 8 is similar to the results for the Accelerated SGD algorithm from [59] . However, the latter paper studies a specific setting where f(x) = E[f ξ (x)],where each component f ξ is L max -smooth and then assumes that f is also L max -smooth, instead of working with the constant L f which can be much smaller than L max . A similar separation of the constants L f and L p g , which we do, was recently considered in [24] , where the authors obtained some similar rates to our Theorem 8. However, it is important that, unlike the algorithms considered in [24, 59] , our UniFastSgd is universal and does not require knowing any problem-dependent constants except D. Furthermore, our results are more general because we allow the oracle to be inexact. 
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 1, 2 and 6. All the proofs are deferred to Appendix E.In addition to the stochastic oracle p g, we now assume that we can also compute the (approximate) full-gradient oracle s g. This allows us to define the following auxiliary SVRG oracle induced by p g with center x ∈ R d (notation p G = SvrgOrac p g,s g (x)) as the oracle with the same random variable component ξ as p g and the function component given by G(x, ξ) = g(x, ξ) -g(x, ξ) + s g(x).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 ∇f (x * ) = 0 (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 p g satisfies Var Assumption 9 is 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 β f, s f ,s g (x, y) involving the approximate function value s f (x) and the approximate gradient s g(x). Nevertheless, both assumptions are actually satisfied for the main examples we discussed after introducing Assumption 6 (see Lemma 16) . A+ = A + a, x0 = A A + x + a A + v0, p G = SvrgOrac p g,s g (x), Gx 0 ∼ = p G(x0). 2: for k = 0, . . . , N -1 do 3: v k+1 = Prox ψ (v k , Gx k , M k a ). 4: x k+1 = A A + x + a A + v k+1 , Gx k+1 ∼ = p G(x k+1 ).5:M k+1 = a 2 A + M+ A + a 2 M k , a 2 A 2 + D 2 , x k , x k+1 , Gx k , Gx k+1 ▷ e.g., (3) = M 2 k + a 2 D 2 ∥Gx k+1 -Gx k ∥ 2 * .6: return (s xN , vN , MN ), wheres xN := 1 N N k=1 x k .Theorem 10. Let UniSvrg (as defined by Algorithm 3) be applied to problem (1) under Assumptions 1, 2, 6 and 9. Then, for any t ≥ 1 and s c 3 := max{c 3 , 1}, we haveE[F (x t )] -F * ≤ [(c 2 c 4 + 1)L f + 48c 1 c 4 L p g ]D 2 2 t + 2s c 3 δ f + 8 3 δ p g .To construct xt , the algorithm needs to make O(2 t ) queries to p g and O(t) queries to s g.We now present an accelerated version of UniSvrg, see Algorithm 4. As UniSvrg, this method is also epoch-based, and its epoch is very similar to UniFastSgd (Algorithm 4) in the sense that it also iterates similar-triangle steps. However, the triangles in UniTriSvrgEpoch are of the form (x, v k , v k+1 ), i.e., they always share the common vertex x, in contrast to the triangles (x k , v k , v k+1 ) in UniFastSgd (in UniTriSvrgEpoch, the role of the average points y k is played by x k ). We note that our UniFastSvrg 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 x0 at Line 1 is rather standard and motivated by the desire to keep the initial function residual appropriately bounded:F (x 0 ) -F * ≤ 1 2 L f D 2 + δ f ;the simplest way to achieve this is to make the full gradient step from any feasible point (see Lemma 34) . Theorem 11. Let UniFastSvrg (Algorithm 4) be applied to problem (1) under Assumptions 1, 2 and 6, and let N ≥ 9. Then, for any t ≥ t 0 := ⌈log 2 log 3 N ⌉ -1 (≥ 0), it holds thatE[F (x t )] -F * ≤ 9[(c 2 c 4 + 1 2 )L f + 6c 1 c 4 L p g ]D 2 N (t -t 0 + 1) 2 + (c 3 t + 1)δ f + 5 3 tδ p g .To construct xt , the algorithm needs to make O(N t) queries to p g and O(t) queries to s g. Assuming that the complexity of querying s g is n times bigger than that of querying p g and choosing N = Θ(n), we get the total stochastic-oracle complexity of O(nt).Note that Theorem 11, 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 10 as well. However, we do not know how to do it, even in the simplest case when δ f = δ p g = 0 and the algorithm has the knowledge of the constants L f and L p g from Assumptions 1 and 6.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, 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 of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
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 ( 1) is the expectation of other functions,f (x) = E ξ [f ξ (x)],where each function f ξ is convex and (ν, H ξ (ν))-Hölder smooth. Consider the g = p g b , s g = ∇f , n = n b .UniSgd (Alg. 1)H f (ν) ϵ 2 1+ν D 2 + 1 b min σ 2 D 2 ϵ 2 , Hmax(ν) ϵ 2 1+ν D 2 + σ 2 * D 2 ϵ 2Cors. 37, 40UniFastSgd (Alg. 2) H f (ν)D 1+ν ϵ 2 1+3ν + 1 b min σ 2 D 2 ϵ 2 , Hmax(ν) ϵ 2 1+ν D 2 + σ 2 * D 2 ϵ 2Cors. 38, 41EQUATIONUniFastSvrg (Alg. 4) [ n ν b H f (ν)D 1+ν ϵ ] 2 1+3ν + [ n ν b Hmax(ν)D 1+ν b (1+ν)/2 ϵ ] 2 1+3ν + n b log log n b Cor. 44 standard mini-batch stochastic gradient oracle p g b of size b, defined by g b (x, ξ [b] ) = 1 b b j=1 ∇f ξj (x), where ξ [b] := (ξ 1 , . . . , ξ b ) with b i.i.d. copies of ξ, and ∇f ξ (x) ∈ ∂f ξ (x)is an arbitrary selection of subgradients for each ξ. We define H f (ν) as the Hölder constant for the function f and H max (ν) := sup ξ H ξ (ν) as the worst among Hölder constants for each f ξ . Note that we always haveH f (ν) ≤ E ξ [H ξ (ν)] but H f (ν) can,in principle, be much smaller than the right-hand side. Also, defineσ 2 := sup x∈dom ψ Var p g1 (x) ≡ sup x∈dom ψ E ξ [∥∇f ξ (x) -∇f (x)∥ 2 * ] and σ 2 * := Var p g1 (x * ) ≡ E ξ [∥∇f ξ (x * ) -∇f (x * )∥ 2 * ].We assume that the computation of p g b can be parallelized and the computation of ∇f is n b times more expensive than that of p g b .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 2 ; the precise statements the corresponding results and their proofs are deferred to Appendix F.Note that our problem is characterized by a large number of parameters, ν, H f (ν), H max (ν), σ, σ * .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 our algorithms are universal: they automatically figure out the best problem class for a specific problem given to them.Question: Does the paper 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 in 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 are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, 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). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments: 
 Let us illustrate the performance of our methods in preliminary numerical experiments2 on solvingEQUATIONwherea i , b i ∈ R d , q ∈ [1, 2] and R > 0.This test problem covers several interesting applications. Indeed, if 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 ∥x∥ ≤ R acts as a regularizer, and problem ( 5) is, in fact, equivalent tomin x∈R d [f (x) + µ 2 ∥x∥ 2 ]for a certain µ ≥ 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 polyhedron feasibility problem: 5) is a problem with Hölder smooth components of degree ν = q -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.find x * ∈ R d , ∥x * ∥ ≤ R, inside the polyhedron P = {x : ⟨a i , x⟩ ≤ b i , i = 1, . . . , n}. Such a point exists iff f * = 0. Note that (The data for our problem is generated randomly. First, we generate x * uniformly from the sphere of radius 0.95R centered at the origin. Then, we generate i.i.d. vectors a i with components uniformly distributed on [-1, 1]. We then make sure that ⟨a n , x * ⟩ < 0 by inverting the sign of a n if necessary. Next, we generate positive reals s i uniformly in [0, -0.1c min ], where c min := min i ⟨a i , x * ⟩ < 0, and set b i = ⟨a i , x * ⟩ + s i . By construction, x * is a solution of our problem with f * = 0, and the origin x 0 = 0 lies outside the polyhedron since there exists j (corresponding to c min ) such that b j = c min + s j ≤ 0.9c min < 0. We compare UniSvrg (Algorithm 3) against AdaSVRG [16] (with parameters K = 3 and η = D = 2R). We next compare UniFastSvrg (Algorithm 4) against AdaVRAE and AdaVRAG [36] . We also compare it 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 j : j = -3, . . . , 4} and choosing the best value in the sense that the algorithm is neither too slow nor has a large error. We report UniSgd (Algorithm 1) and UniFastSgd (Algorithm 2) together with these methods. For UniFastSvrg, contrary to the theoretical recommendation of choosing x0 as the result of the full gradient step, we found it slightly more useful to simply set x0 = x 0 . For all our methods, we use the AdaGrad stepsize (3); the other stepsize (4) works very similarly (see Appendix H.2 for a detailed comparison). For all methods, we use the standard mini-batch stochastic oracle of size b = 256.The results are shown in Fig. 1 , where we fix n = 10 4 , d = 10 3 , R = 10 6 and consider different values of q ∈ {1, 1.3, 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-batch size.We see that, except the AdaSVRG method, all SVRG algorithms typically converge much faster than the usual SGD methods without explicit variance reduction, at least after a few computations of the full gradient. Among the non-accelerated SVRG methods, UniSvrg converges consistently faster than AdaSVRG, 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 as before and fix q = 1.5. As we can see, in the idealized situation, when one can implement the mini-batch oracle computations by perfect parallelism, there is a significant speedup in convergence when increasing the mini-batch size, as predicted by our theory.For additional experiments, including the discussion of implicit variance reduction, see Appendix H.Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments? • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
conclusions: 
 In this paper, we showed that AdaGrad stepsizes can be applied, in a unified manner, in a 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 it 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-free 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 algorithms. Another interesting direction is, of course, nonconvex problems. 
 
 Appendix: A.1 Approximately Smooth Functions Theorem 13 (Lemma 2 in [45] ). Let f : R d → R be a convex (ν, H)-Hölder smooth function for some ν ∈ [0, 1] and H ≥ 0. Then, for any δ > 0, any x, y ∈ R d and any ∇f (x) ∈ ∂f (x), it holds thatβ ∇f (x) f (x, y) ≤ L 2 ∥x -y∥ 2 + δ with L = [ 1-ν 2(1+ν)δ ] 1-ν 1+ν H 2 1+ν(with the convention that 0 0 = 1).Theorem 14. Let f : R d → R be a (δ, L)-approximately smooth convex function with components ( s f , s g), i.e., for any x, y ∈ R d and β f, s f ,s g (x, y) := f (y)s f (x) -⟨s g(x), y -x⟩, we haveEQUATIONThen, for any x, y ∈ R d and any ∇f (x) ∈ ∂f (x), the following inequalities hold:EQUATIONEQUATIONEQUATIONEQUATIONEQUATIONEQUATIONEQUATIONProof. Inequality (7) follows immediately from (6) by substituting y = x.To prove (8), we rewriteβ f, s f ,s g (x, y) + β f, s f ,s g (y, x) = ⟨s g(x) -s g(y), x -y⟩ + [f (x) -s f (x)] + [f (y) -s f (y)],and then apply (7) .Using the first part of ( 8) and applying (6) twice, we obtain (9).To prove (10) and (11) , let us fix some sf 1 (x) ∈ R and s g 1 (x) ∈ R d such that β f, s f1,s g1 (z) := f (z) -s f 1 (x) -⟨s g 1 (x), z -x⟩ ≥ 0 for any z ∈ R d . Note that we can choose either ( s f 1 , s g 1 ) = ( s f , s g) or ( s f 1 , s g 1 ) = (f, ∇f ).In view of ( 6), for any z ∈ R d , we can write the following inequalities:0 ≤ β f, s f1,s g1 (z) ≤ s f (y) -s f 1 (x) -⟨s g 1 (x), y -x⟩ + ⟨s g(y) -s g 1 (x), z -y⟩ + L 2 ∥z -y∥ 2 + δ.Minimizing the right-hand side in z ∈ R d and rearranging, we conclude that1 2L ∥s g(y) -s g 1 (x)∥ 2 * ≤ s f (y) -s f 1 (x) -⟨s g 1 (x), y -x⟩ + δ ≤ β f, s f1,s g1 (x, y) + δ,where the final inequality is due to (7) . Substituting now either ( sf 1 , s g 1 ) = ( s f , s g) or ( s f 1 , s g 1 ) = (f, ∇f ), we obtain either (10) or (11) , respectively. Inequality (12) follows immediately from ( 6) and (10) .Inequality (13) follows from (11) :∥s g(x) -s g(y)∥ 2 * ≤ 2∥∇f (x) -s g(y)∥ 2 * + 2∥s g(x) -∇f (x)∥ 2 * ≤ 4L(β ∇f (x) f (x, y) + δ) + 4Lδ = 4L(β ∇f (x) f (x, y) + 2δ).To prove (14) , we proceed as follows using first (6), then (7) , and then (11) :β ∇f (x) f (x, y) ≡ f (y) -f (x) -⟨∇f (x), y -x⟩ ≤ s f (x) -f (x) + ⟨s g(x) -∇f (x), y -x⟩ + L 2 ∥y -x∥ 2 + δ ≤ ⟨s g(x) -∇f (x), y -x⟩ + L 2 ∥y -x∥ 2 + δ ≤ √ 2Lδ∥y -x∥ + L 2 ∥y -x∥ 2 + δ = L 2 ∥y -x∥ + √ δ 2 ≤ L∥y -x∥ 2 + 2δ,where the final inequality is(a + b) 2 ≤ 2a 2 + 2b 2 , a, b ≥ 0.Remark 15. Some of the inequalities from Theorem 14, namely, ( 7), ( 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 : R d → R be the function f (x) := E ξ [f ξ (x)],where each f ξ : R d → R is convex and (δ ξ , L ξ )-approximately smooth with components ( s f ξ , s g ξ ). Further, let p g be the stochastic oracle defined by g(x, ξ) := s g ξ (x), and let sf (x) := E ξ [ s f ξ (x)], s g(x) := E ξ [s g ξ (x)].Then, p g is an unbiased oracle for s g and, for any x, y ∈ R d , L max := sup ξ L ξ and s δ :EQUATIONFurthermore, for any x, y ∈ R d and any ∇f (x) ∈ ∂f (x), it also holds thatEQUATIONProof. According to our definition of s g, we have E ξ [s g ξ (x)] = s g(x) for any x, so p g is indeed an unbiased oracle for s g. Further, for any x, y ∈ R d , we can estimateVar p g (x, y) ≡ E ξ ∥[s g ξ (x) -s g ξ (y)] -[s g(x) -s g(y)]∥ 2 * ≤ E ξ ∥s g ξ (x) -s g ξ (y)∥ 2 * ≤ E ξ 2L ξ β f ξ , s f ξ ,s g ξ (x, y) + δ ξ ≤ 2L max E ξ [β f ξ , s f ξ ,s g ξ (x, y)] + s δ = 2L max [β f, s f ,s g (x, y) + s δ],where s δ is as defined in the statement; the second inequality follows from Theorem 14 (inequality (10)), and the final identity is due to the linearity of β f, s f ,s g (x, y) in (f, s f , s g) and the fact that, by our definitions,E ξ [f ξ (x)] = f (x), E ξ [ s f ξ (x)] = s f (x), E ξ [s g ξ (x)] = s g(x)for any x. This proves (15) .The proof of ( 16) is similar but now we apply (13) instead of (10):Var p g (x, y) ≤ E ξ ∥s g ξ (x) -s g ξ (y)∥ 2 * ≤ E ξ 4L ξ β ∇f ξ (x) f ξ (x, y) + 2δ ξ ≤ 4L max E ξ [β ∇f ξ (x) f ξ (x, y)] + 2 s δ = 4L max [β ∇f (x) f (x, y) + 2 s δ],where we have used the fact that ∂f(x) = E ξ [∂f ξ (x)] (see Proposition 2.2 in [4]), meaning that, for any ∇f (x) ∈ ∂f (x), we can find a selection of ∇f ξ (x) ∈ ∂f ξ (x) such that ∇f (x) = E ξ [∇f ξ (x)]. A.2 Miscellaneous Lemma 17. Let ψ : R d → R ∪ {+∞} be a proper closed convex function, x ∈ dom ψ, g ∈ R d , M ≥ 0, and let x + := Prox ψ (x, g, M ).Then, for any y ∈ dom ψ, we have⟨g, y -x + ⟩ + ψ(y) + M 2 ∥x -y∥ 2 ≥ ψ(x + ) + M 2 ∥x -x + ∥ 2 + M 2 ∥x + -y∥ 2 .Proof. Indeed, by definition, x + is the minimizer of the function h : R d → R ∪ {+∞} given by h(y) := ⟨g, y⟩ + ψ(y) + M 2 ∥x -y∥ 2 , which is strongly convex with parameter M (or simply convex if M = 0). Hence, for any y ∈ dom ψ (= dom h), we have h(y) ≥ h(x + ) + M 2 ∥y -x + ∥ 2 , which is exactly the claimed inequality.Lemma 18. Let N ≥ 1 be an integer, (M k ) N k=0 be a nondecreasing nonnegative sequence of reals, and let Ď M ≥ 0. Then,N -1 k=0 [min{M k+1 , Ď M } -M k ] + = [min{M N , Ď M } -M 0 ] + .Proof. It suffices to prove the identity only in the special case when N = 2, i.e., to show that γ 0 +γ 1 = Γ, whereγ 0 := [min{M 1 , Ď M } -M 0 ] + , γ 1 := [min{M 2 , Ď M } -M 1 ] + , Γ := [min{M 2 , Ď M } -M 0 ] + .The general case then easily follows by induction.To prove the identity, we use our assumption that M 0 ≤ M 1 ≤ M 2 and consider three possible cases.If M 1 ≥ Ď M , then γ 0 + γ 1 = [ Ď M -M 0 ] + + 0 = [ Ď M -M 0 ] + = Γ. If M 1 < Ď M ≤ M 2 , then γ 0 + γ 1 = (M 1 -M 0 ) + ( Ď M -M 1 ) = Ď M -M 0 = Γ. Finally, if M 2 < Ď M , then γ 0 + γ 1 = (M 1 -M 0 ) + (M 2 -M 1 ) = M 2 -M 0 = Γ.Lemma 19. Let p g be a stochastic oracle in R d . Then, for any x, y, z ∈ R d and any τ > 0, we haveVar p g (x) ≤ (1 + τ ) Var p g (y) + (1 + τ -1 ) Var p g (x, y), Var p g (x, y) ≤ (1 + τ ) Var p g (x, z) + (1 + τ -1 ) Var p g (y, z).Proof. Both inequalities are direct consequences of the standard inequality∥s 1 + s 2 ∥ 2 * ≤ (1 + τ )∥s 1 ∥ 2 * + (1 + τ -1 )∥s 2 ∥ 2* which is valid for any s 1 , s 2 ∈ R d and any τ > 0. Indeed, let g and ξ be, respectively, the function and the random variable components of p g, and let ∆(x, ξ) := g(x, ξ) -E[g(x, ξ)] for any x ∈ R d . Then, for any x, y, z ∈ R d and τ > 0, we can estimateVar p g (x) ≡ E[∥∆(x, ξ)∥ 2 * ] = E[∥∆(y, ξ) + [∆(x, ξ) -∆(y, ξ)]∥ 2 * ] ≤ (1 + τ ) E[∥∆(y, ξ)∥ 2 * ] + (1 + τ -1 ) E[∥∆(x, ξ) -∆(y, ξ)∥ 2 * ] ≡ (1 + τ ) Var p g (y) + (1 + τ -1 ) Var p g (x, y).Similarly,Var p g (x, y) ≡ E ∥∆(x, ξ) -∆(y, ξ)∥ 2 * = E ∥[∆(x, ξ) -∆(z, ξ)] -[∆(y, ξ) -∆(z, ξ)]∥ 2 * ≤ (1 + τ ) E ∥∆(x, ξ) -∆(z, ξ)∥ 2 * + (1 + τ -1 ) E ∥∆(y, ξ) -∆(z, ξ)∥ 2 * ≡ (1 + τ ) Var p g (x, z) + (1 + τ -1 ) Var p g (y, z).Lemma 20 (AdaGrad stepsize). Let function f satisfy Assumption 1. Consider the stepsize update rule xM + = M + (M, Ω, x, p x + , p g x , p g x+ ) defined by x M + := M 2 + 1 Ω ∥p g x+ -p g x ∥ 2 * .Then, this stepsize update rules satisfies (2) withc 1 = 5 2 , c 2 = 4, c 3 = 6, c 4 = 2. Proof. Let p ∆( Ď M ) := β f, s f ,s g (x, p x + ) + ⟨s g(x) -p g x , p x + -x⟩ - Ď M 2 ∥p x + -x∥ 2 .From our Assumption 1 and Theorem 14 (inequality (8)), it follows thatβ f, s f ,s g (x, p x + )+β f, s f ,s g (p x + , x) ≤ ⟨s g(p x + )-s g(x), p x + - x⟩ + 2δ f . Hence, E[ p ∆( x M + )+β f, s f ,s g (p x + , x)] ≤ E ⟨s g(p x + )-p g x , p x + -x⟩- x M + 2 ∥p x + -x∥ 2 +2δ f = E[ p ∆ 1 ( x M + )]+2δ f , where p ∆ 1 ( x M + ) := ⟨p g x+ -p g x , p x + -x⟩ - x M+ 2 ∥p x + -x∥ 2 . Hence, Γ := E[ p ∆( x M + ) + ( x M + -M )Ω + β f, s f ,s g (p x + , x)] ≤ E[ p ∆ 1 ( x M + ) + ( x M + -M )Ω] + 2δ f .From the definition of x M + , it follows that ∥p g x+pg x ∥ 2 * = ( x M 2 + -M 2 )Ω = ( x M + + M )( x M + -M )Ω. Since x M + ≥ M , this means that 1 2 x M + ∥p g x+ -p g x ∥ 2 * ≤ ( x M + -M )Ω ≤ 1 x M + ∥p g x+ -p g x ∥ 2 *Let us now upper bound pΓ := p ∆ 1 ( x M + ) + ( x M + -M )Ω.For this, let us fix an arbitrary constantĎ M ≥ 0 and consider two cases. If x M + ≥ Ď M , we can bound p Γ ≤ p ∆ 1 ( x M + ) + 1 x M + ∥p g x+ -p g x ∥ 2 * ≤ p ∆ 1 ( Ď M ) + 1 Ď M ∥p g x+ -p g x ∥ 2 * =: p Γ( Ď M ). If x M + ≤ Ď M , we can bound p Γ ≤ 1 2 x M + ∥p g x+ -p g x ∥ 2 * + ( x M + -M )Ω ≤ 2( x M + -M )Ω = 2[min{ x M + , Ď M } -M ] + Ω.Combining the two cases, we get pΓ ≤ [ p Γ( Ď M )] + + 2[min{ x M + , Ď M } -M ] + Ω. Thus, Γ ≤ E[ p Γ] + 2δ f ≤ E [ p Γ( Ď M )] + + 2 E [min{ x M + , Ď M } -M ] + Ω + 2δ f .Let us now estimate the first term. Denote p S := p g xs g(x) and pS + := p g x+ -s g(p x + ). Then, p Γ( Ď M ) ≡ ⟨p g x+ -p g x , p x + -x⟩ - Ď M 2 ∥p x + -x∥ 2 + 1 Ď M ∥p g x+ -p g x ∥ 2 * ≤ ⟨s g(p x + ) -s g(x), p x + -x⟩ + 2 Ď M ∥s g(p x + ) -s g(x)∥ 2 * + ⟨ p S + -p S, p x + -x⟩ + 2 Ď M ∥ p S + -p S∥ 2 * - Ď M 2 ∥p x + -x∥ 2Using now our Assumption 1 and Theorem 14 (inequalities ( 9) and ( 12)), we can continue as follows:p Γ( Ď M ) ≤ L f ∥p x + -x∥ 2 + 2δ f + 2 Ď M (L 2 f ∥p x + -x∥ 2 + 4L f δ f ) + ⟨ p S + -p S, p x + -x⟩ + 2 Ď M ∥ p S + -p S∥ 2 * - Ď M 2 ∥p x + -x∥ 2 ≤ ⟨ p S + -p S, p x + -x⟩ + 2 Ď M ∥ p S + -p S∥ 2 * - Ď M -2L f (1 + 2L f Ď M ) 2 ∥p x + -x∥ 2 + 2 1 + 4L f Ď M δ f ≤ 2 Ď M + 1 2[ Ď M -2L f (1 + 2L f Ď M )] ∥ p S + -p S∥ 2 * + 2 1 + 4L f Ď M δ f .Consequently,E [ p Γ( Ď M )] + ≤ 2 Ď M + 1 2[ Ď M -2L f (1 + 2L f Ď M )] E[∥ p S + -p S∥ 2 * ] + 2 1 + 4L f Ď M δ f .In particular, for Ď M > 4L f , we can estimate 2Ď M + 1 2[ Ď M -2L f (1+ 2L f Ď M )] ≤ 2 Ď M + 1 2( Ď M -4L f ) ≤ 5 2( Ď M -4L f ) . Therefore, for any Ď M > 4L f , E [ p Γ( Ď M )] + ≤ 5 2( Ď M -4L f ) E[∥ p S + -p S∥ 2 * ]+4δ f = 5 2( Ď M -4L f ) E[Var p g (p x + )+Var p g (x)]+4δ f ,where the final identity follows from the fact thatE[∥ p S + -p S∥ 2 * ] = E[∥ p S + ∥ 2 * ] + E[∥ p S∥ 2 * ] = E[Var p g (p x + )] + Var p g (x) (because pS + , conditioned on the randomness ξ defining p g x ≡ g(x, ξ), has zero mean).Combining everything together, we getΓ ≤ 5 2( Ď M -4L f ) E[Var p g (p x + ) + Var p g (x)] + 6δ f + 2 E [min{ x M + , Ď M } -M ] + Ω . This is exactly (2) with c 1 = 5 2 , c 2 = 4, c 3 = 6, c 4 = 2.Lemma 21. Let function f satisfy Assumption 1. Consider the stepsize update rule x M + = M + (M, Ω, x, px + , p g x , p g x+ ) defined as the solution of the following equation:( x M + -M )Ω = [ p ∆ 1 ( x M + )] + , p ∆ 1 ( x M + ) := ⟨p g x+ -p g x , p x + -x⟩ - x M + 2 ∥p x + -x∥ 2 .Then, this stepsize update rules satisfies (2)with c 1 = 1, c 2 = 2, c 3 = 6, c 4 = 2.Proof. Let us define p∆( Ď M ) := β f, s f ,s g (x, p x + ) + ⟨s g(x) -p g x , p x + -x⟩ - Ď M 2 ∥p x + -x∥ 2 .Starting as in the proof of Lemma 20, we see thatΓ := E[ p ∆( x M + ) + ( x M + -M )Ω + β f, s f ,s g (p x + , x)] ≤ E[ p ∆ 1 ( x M + ) + ( x M + -M )Ω] + 2δ f ,with the same p ∆ 1 (•) as defined in the statement.Let us now upper bound pΓ := p ∆ 1 ( x M + ) + ( x M + -M )Ω.For this, let us fix an arbitrary constant Ď M ≥ 0 and consider two cases. If x M + ≥ Ď M , we can bound, using the monotonicity of p ∆ 1 (•),p Γ = p ∆ 1 ( x M + ) + [ p ∆ 1 ( x M + )] + ≤ p ∆ 1 ( Ď M ) + [ p ∆ 1 ( Ď M )] + ≤ 2[ p ∆ 1 ( Ď M )] + . If x M + ≤ Ď M , we can bound p Γ ≤ [ p ∆ 1 ( x M + )] + + ( x M + -M )Ω = 2( x M + -M )Ω = 2[min{ x M + , Ď M } -M ] + Ω.Combining the two cases, we get pΓ ≤ 2[ p ∆ 1 ( Ď M )] + + 2[min{ x M + , Ď M } -M ]+ Ω, and henceΓ ≤ E[ p Γ] + 2δ f ≤ 2 E [ p ∆ 1 ( Ď M )] + + 2 E [min{ x M + , Ď M } -M ] + Ω + 2δ f .Let us now estimate the first term. According to our Assumption 1 and Theorem 14 (inequality ( 9)), we have ⟨s g(p x + ) -s g(x), p x + -x⟩ ≤ L f ∥p x + -x∥ 2 + 2δ f .M > 2L f , p ∆ 1 ( Ď M ) = ⟨s g(p x + ) -s g(x), p x + -x⟩ + ⟨ p S + -p S, p x + -x⟩ - Ď M 2 ∥p x + -x∥ 2 ≤ ⟨ p S + -p S, p x + -x⟩ - Ď M -2L f 2 ∥p x + -x∥ 2 + 2δ f ≤ 1 2( Ď M -2L f ) ∥ p S + -p S∥ 2 * + 2δ f .Hence,E [ p ∆ 1 ( Ď M )] + ≤ 1 2( Ď M -2L f ) E[∥ p S + -p S∥ 2 * ]+2δ f = 1 2( Ď M -2L f ) E[Var p g (p x + )+Var p g (x)]+2δ f ,where the final identity follows from the fact thatE[∥ p S + -p S∥ 2 * ] = E[∥ p S + ∥ 2 * ] + E[∥ p S∥ 2 * ] = E[Var p g (p x + )] + Var p g (x) (because pS + , conditioned on the randomness ξ defining p g x ≡ g(x, ξ), has zero mean). Thus,Γ ≤ 1 Ď M -2L f E[Var p g (p x + ) + Var p g (x)] + 6δ f + 2 E [min{ x M + , Ď M } -M ] + Ω , which is exactly (2) with c 1 = 1, c 2 = 2, c 3 = 6, c 4 = 2.C Omitted Proofs for Section 4C.1 Universal SGD Lemma 22 (Stochastic Gradient Step). Consider problem (1) under Assumption 1. Let p g be an unbiased oracle for s g. Let x ∈ dom ψ be a point, M ≥ 0 be a coefficient, p g x ∼ = p g(x), and letp x + = Prox ψ (x, p g x , M ). Denote p ∆(M ) := β f, s f ,s g (x, p x + ) + ⟨s g(x) -p g x , p x + -x⟩ -M 2 ∥p x + -x∥ 2 .Then,E F (p x + ) -F * + M 2 ∥p x + -x * ∥ 2 + β f, s f ,s g (x, x * ) ≤ M 2 ∥x -x * ∥ 2 + E[ p ∆(M )].If further Assumption 2 is satisfied, and x M + ≥ M is a random coefficient (possibly dependent on p g x ), then, we also haveE F (p x + )-F * + x M + 2 ∥p x + -x * ∥ 2 +β f, s f ,s g (x, x * ) ≤ M 2 ∥x-x * ∥ 2 +E p ∆( x M + )+( x M + -M )D 2 .Proof. From Lemma 17, it follows thats f (x) + ⟨p g x , p x + -x⟩ + ψ(p x + ) + M 2 ∥p x + -x * ∥ 2 + M 2 ∥p x + -x∥ 2 ≤ s f (x) + ⟨p g x , x * -x⟩ + ψ(x * ) + M 2 ∥x -x * ∥ 2 .Passing to expectations and rewritingEQUATIONs f (x) + ⟨p g x , p x + -x⟩ + ψ(p x + ) = F (p x + ) -[f (p x + ) -s f (x) -⟨p g x , p x + -x⟩] = F (p x + ) -[β f, s f ,s g (x, p x + ) + ⟨s g(x) -p g x , p x + -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 ofx M + -M 2 ∥p x + -x * ∥ 2 + p ∆(M ) -p ∆( x M + ) = x M + -M 2 ∥p x + -x * ∥ 2 + ∥p x + -x∥ 2and then bound ∥p x + -x * ∥ ≤ D, ∥p x + -x∥ ≤ D using our Assumption 2 and the fact that x, p x + , x * ∈ dom ψ.Lemma 23 (Universal Stochastic Gradient Step). Consider problem (1) under Assumptions 1 and 2. Let p g be an unbiased oracle for s g. Further, let x ∈ dom ψ be a point, M ≥ 0 be a coefficient,p g x ∼ = p g(x), and letp x + = Prox ψ (x, p g x , M ), p g x+ ∼ = p g(p x + ), x M + = M + (M, D 2 , x, p x + , p g x , p g x+ ).Then, for any Ď M > c 2 L f , it holds thatE F (p x + ) -F * + x M + 2 ∥p x + -x * ∥ 2 + β f, s f ,s g (p x + , x) + β f, s f ,s g (x, x * ) ≤ M 2 ∥x-x * ∥ 2 + c 1 Ď M -c 2 L f E[Var p g (p x + )+Var p g (x)]+c 3 δ f +c 4 E [min{ x M + , Ď M }-M ] + D 2 .Proof. According to Lemma 22,E F (p x + )-F * + x M + 2 ∥p x + -x * ∥ 2 +β f, s f ,s g (x, x * ) ≤ M 2 ∥x-x * ∥ 2 +E p ∆( x M + )+( x M + -M )D 2 , where p ∆( x M + ) := β f, s f ,s g (x, p x + )+⟨s g(x)-p g x , p x + -x⟩- x M+ 2 ∥p x + -x∥ 2 .At the same time, according to the main requirement (2) on the stepsize update rule, for anyĎ M > c 2 L f , E p ∆( x M + ) + ( x M + -M )D 2 + β f, s f ,s g (p x + , x) ≤ c 1 Ď M -c 2 L f E[Var p g (p x + ) + Var p g (x)] + c 3 δ f + c 4 E [min{ x M + , Ď M } -M ] + D 2 .Combining the two displays, we get the claim.Lemma 24 (Universal SGD: General Guarantee). Consider problem (1) under Assumptions 1 and 2. Let p g be an unbiased oracle for s g. Further, let x ∈ dom ψ be a point, M ≥ 0 be a coefficient, N ≥ 1 be an integer, and let(s x N , x N , M N ) ∼ = UniSgd p g,ψ (x 0 , M 0 , N ; D), as defined by Algorithm 1, and let x 0 , . . . , x N be the corresponding points generated inside the algorithm. Then, for anyĎ M > c 2 L f , it holds that E N [F (s x N ) -F * ] + M N 2 ∥x N -x * ∥ 2 + N -1 k=0 [β f, s f ,s g (x k+1 , x k ) + β f, s f ,s g (x k , x * )] ≤ M 0 2 ∥x 0 -x * ∥ 2 + c 1 Ď M -c 2 L f N -1 k=0 E[Var p g (x k+1 ) + Var p g (x k )] + c 3 N δ f + c 4 E [min{M N , Ď M } -M 0 ] + D 2 .Proof. Each iteration k of the algorithm, when conditioned on x k , follows the construction from Lemma 23 (withx = x k , p g x = g k , M = M k , p x + = x k+1 , p g x+ = g k+1 , x M + = M k+1). Hence, we can write, after passing to full expectations, that, for each k = 0, . . . , N -1,E F (x k+1 ) -F * + M k+1 2 ∥x k+1 -x * ∥ 2 + β f, s f ,s g (x k+1 , x k ) + β f, s f ,s g (x k , x * ) ≤ E M k 2 ∥x k -x * ∥ 2 + c 1 Ď M -c 2 L f [Var p g (x k+1 )+Var p g (x k )]+c 4 [min{M k+1 , Ď M }-M k ] + D 2 +c 3 δ f ,where Ď M > 2L f is an arbitrary constant. Telescoping the above inequalities (using Lemma 18) and then bounding N [F (s x N ) -F * ] ≤ N k=1 [F (x k ) -F * ] (using the convexity of F and our choice ofs x N = 1 N N k=1x k ), we get the claim. Theorem 4. Let Algorithm 1 with M 0 = 0 be applied to problem (1) under Assumptions 1-3. Then, for the point sx N generated by the algorithm, we haveE[F (s x N )] -F * ≤ c 2 c 4 L f D 2 N + 2σD 2c 1 c 4 N + c 3 δ f .Proof. Applying Lemma 24, substituting our choice of M 0 = 0, estimating Var p g (•) ≤ σ 2 and dropping the nonnegative β f, s f ,s g (•, •) terms, we obtainE[F (s x N )] -F * ≤ 1 N c 4 Ď M D 2 + 2c 1 σ 2 N Ď M -c 2 L f + c 3 N δ f = c 4 Ď M D 2 N + 2c 1 σ 2 Ď M -c 2 L f + c 3 δ f ,where Ď M > 2L f is an arbitrary constant. The optimal Ď M which minimizes the right-hand side isĎ M = c 2 L f + σ D 2c1c4 N . Substituting this choice into the above display, we getE[F (s x N )] -F * ≤ c 4 D 2 N c 2 L f + σ D 2c 1 c 4 N + 2c 1 σ 2 σ D 2c1 c4 N + c 3 δ f = c 2 c 4 L f D 2 N + 2σD 2c 1 c 4 N + c 3 δ f .Lemma 25 (Stochastic Triangle Step). Consider problem (1) under Assumption 1. Let p g be an unbiased oracle for s g, let x, v ∈ dom ψ be points and M, A ≥ 0, a > 0 be coefficients. Further, forA + := A + a, let y = Ax + av A + , p g y ∼ = p g(y), p v + = Prox ψ (v, p g y , M/a), p x + = Ax + ap v + A + .Denote p ∆(M ) := β f, s f ,s g (y, p x + ) + ⟨s g(y)p g y , px + -y⟩ -M A+ 2a 2 ∥p x + -y∥ 2 . Then,E A + [F (p x + ) -F * ] + M 2 ∥p v + -x * ∥ 2 + Aβ f, s f ,s g (y, x) + aβ f, s f ,s g (y, x * ) ≤ A[F (x) -F * ] + M 2 ∥v -x * ∥ 2 + A + E[ p ∆(M )].If further Assumption 2 is satisfied, and x M + ≥ M is a random coefficient (possibly dependent on p g y ), then we also haveE A + [F (p x + ) -F * ] + x M + 2 ∥p v + -x * ∥ 2 + Aβ f, s f ,s g (y, x) + aβ f, s f ,s g (y, x * ) ≤ A[F (x) -F * ] + M 2 ∥v -x * ∥ 2 + E[A + p ∆( x M + ) + ( x M + -M )D 2 ],Proof. Denoting θ := Aβ f, s f ,s g (y, x) + aβ f, s f ,s g (y, x * ) and using the fact that E[p g y ] = s g(y), we can rewriteAF (x) + aF (x * ) + M 2 ∥v -x * ∥ 2 = A[ s f (y) + ⟨s g(y), x -y⟩ + β f, s f ,s g (y, x) + ψ(x)] + a[ s f (y) + ⟨s g(y), x * -y⟩ + β f, s f ,s g (y, x * ) + ψ(x * )] + M 2 ∥v -x * ∥ 2 = A + s f (y) + ⟨s g(y), Ax + ax * -A + y⟩ + Aψ(x) + aψ(x * ) + M 2 ∥v -x * ∥ 2 + θ = E A + s f (y) + ⟨p g y , Ax + ax * -A + y⟩ + Aψ(x) + aψ(x * ) + M 2 ∥v -x * ∥ 2 + θ.Further, by the definition of p v + and Lemma 17,⟨p g y , x * -p v + ⟩ + ψ(x * ) + M 2a ∥v -x * ∥ 2 ≥ ψ(p v + ) + M 2a ∥v -p v + ∥ 2 + M 2a ∥p v + -x * ∥ 2 .This means thatA + s f (y) + ⟨p g y , Ax + ax * -A + y⟩ + Aψ(x) + aψ(x * ) + M 2 ∥v -x * ∥ 2 ≥ A + s f (y) + ⟨p g y , Ax + ap v + -A + y⟩ + Aψ(x) + aψ(p v + ) + M 2 ∥v -p v + ∥ 2 + M 2 ∥p v + -x * ∥ 2 ≥ A + [ s f (y) + ⟨p g y , p x + -y⟩ + ψ(p x + )] + M 2 ∥v -p v + ∥ 2 + M 2 ∥p v + -x * ∥ 2 = A + F (p x + ) + M 2 ∥p v + -x * ∥ 2 -A + p ∆(M ),where the second inequality is due to the definition of p x + and the convexity of ψ, andp ∆(M ) := f (p x + ) -s f (y) -⟨p g y , p x + -y⟩ - M 2A + ∥v -p v + ∥ 2 = β f, s f ,s g (y, p x + ) + ⟨s g(y) -p g y , p x + -y⟩ - M A + 2a 2 ∥p x + -y∥ 2 since p x + -y = a A+ (p v + -v)(by the definitions of y and p x + ). Substituting the above inequality into the first display and rearranging, we get 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 ofx M + -M 2 ∥p v + -x * ∥ 2 + A + [ p ∆(M ) -p ∆( x M + )] = x M + -M 2 ∥p v + -x * ∥ 2 + A 2 +a 2 ∥p x + -y∥ 2 and then bound, using the fact that px + -y = a A+ (p v + -v) together with our Assumption 2,∥p v + -x * ∥ 2 + A 2 + a 2 ∥p x + -y∥ 2 = ∥p v + -x * ∥ 2 + ∥p v + -v∥ 2 ≤ 2D 2 . Lemma 26 (Universal Stochastic Triangle Step). Consider problem (1)under Assumptions 1 and 2, and let p g be an unbiased oracle for s g. Let x, v ∈ dom ψ be points, M, A ≥ 0, a > 0 be coefficients. Further, for A + := A + a, lety = Ax + av A + , p g y ∼ = p g(y), p v + = Prox ψ (v, p g y , M/a), p x + = Ax + ap v + A + , p g x+ ∼ = p g(p x + ), x M + = a 2 A + M + A + a 2 M, a 2 A 2 + D 2 , y, p x + , p g y , p g x+ .Then, for anyĎ M > c 2 L f a 2A+ , it holds thatE A + [F (p x + ) -F * ] + x M + 2 ∥p v + -x * ∥ 2 + A + β f, s f ,s g (p x + , y) + Aβ f, s f ,s g (y, x) + aβ f, s f ,s g (y, x * ) ≤ A[F (x) -F * ] + M 2 ∥v -x * ∥ 2 + c 1 a 2 Ď M -c 2 L f a 2 A+ E[Var p g (p x + ) + Var p g (y)] + c 3 A + δ f + c 4 E [min{ x M + , Ď M } -M ] + D 2 .Proof. According to Lemma 25 (together with the fact that x M + ≥ M which is guaranteed by the requirement on the stepsize update rule), we haveE A + [F (p x + ) -F * ] + x M + 2 ∥p v + -x * ∥ 2 + Aβ f, s f ,s g (y, x) + aβ f, s f ,s g (y, x * ) ≤ A[F (x) -F * ] + M 2 ∥v -x * ∥ 2 + E A + p ∆( x M + ) + ( x M + -M )D 2 ,where p ∆( x M + ) := β f, s f ,s g (y, p x + ) + ⟨s g(y)p g y , px + -y⟩ -x M+A+ 2a 2 ∥p x + -y∥ 2 . Further, according to the main requirement (2) on the stepsize update rule (applied in the variablesM ′ := A+ a 2 M , Ω := a 2 A 2 + D 2 , x M ′ + := A+ a 2 x M + , Ď M ′ := A+ a 2 Ď M for which we have M ′ Ω = M D 2 A+ , x M ′ + Ω = x M + D 2 A+ , Ď M ′ Ω = Ď M D 2 A+ ), it holds that E p ∆( x M + ) + ( x M + -M ) D 2 A + + β f, s f ,s g (p x + , y) ≤ c 1 A+ a 2 Ď M -c 2 L f E[Var p g (p x + ) + Var p g (y)] + c 3 δ f + c 4 E [min{ x M + , Ď M } -M ] + D 2 A + , where Ď M > c 2 L f a 2A+ is an arbitrary constant. Multiplying both sides of the above display by A + 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 (1) under Assumptions 1 and 2. Then, for any k ≥ 1 and any Ď M > c 2 L f , it holds thatE A k [F (x k ) -F * ] + k-1 i=0 [A i+1 β f, s f ,s g (x i+1 , y i ) + a i+1 β f, s f ,s g (y i , x * )] ≤ c 4 Ď M D 2 + c 1 Ď M -c 2 L f k-1 i=0 a 2 i+1 E[Var p g (x i+1 ) + Var p g (y i )] + c 3 δ f k i=1 A i ,wherea k = 1 2 k, A k = 1 4 k(k + 1), k i=1 a 2 i = 1 24 k(k + 1)(2k + 1), k i=1 A i = 1 12 k(k + 1)(k + 2) for each k ≥ 1.Proof. Each iteration k of the algorithm, when conditioned on (x k , v k ), follows the construction from Lemma 26 (withx = x k , v = v k , M = M k , A = A k , a = a k+1 , A + = A k+1 , y = y k , p g y = g y k , p v + = v k+1 , p x + = x k+1 , p g x+ = g x k+1 , x M + = M k+1 ), where A k and a k are the following coefficients:a k = 1 2 k, A k = k i=1 a i = 1 4 k(k + 1). Applying Lemma 26 (dropping the nonnegative β f, s f ,s g (y, x) term) and passing to full expectations, we therefore obtain, for each k ≥ 0,E A k+1 [F (x k+1 ) -F * ] + M k+1 2 ∥v k+1 -x * ∥ 2 + A k+1 β f, s f ,s g (x k+1 , y k ) + a k+1 β f, s f ,s g (y k , x * ) ≤ E A k [F (x k ) -F * ] + M k 2 ∥v k -x * ∥ 2 + c 1 a 2 k+1 Ď M -c 2 L f a 2 k+1 A k+1 [Var p g (x k+1 ) + Var p g (y k )] + c 3 A k+1 δ f + c 4 E [min{M k+1 , Ď M } -M k ] + D 2 ,where Ď M is an arbitrary constant such thatĎ M > c 2 L f a 2 k+1A k+1 . Note however that, for our sequences a k and A k , we havea 2 k A k = 1 4 k 2 1 4 k(k+1) = k k+1 ≤ 1. Therefore, we can replace c1a 2 k+1 Ď M -c2L f a 2 k+1 A k+1in the above display withc1a 2 k+1 Ď M -c2L funder the requirement that Ď M > c 2 L f . Doing this and then telescoping the above inequalities (applying Lemma 18), and using the fact that M 0 = A 0 = 0, we get the claimed inequality.It remains to do some standard computations to see thatk i=1 a 2 i ≡ 1 4 k i=1 i 2 = 1 24 k(k + 1)(2k + 1) and k i=1 A i ≡ 1 4 k i=1 i(i + 1) = 1 4 ( 1 6 k(k + 1)(2k + 1) + 1 2 k(k + 1)) = 1 12 k(k + 1)(k + 2).Theorem 5. Let Algorithm 2 be applied to problem (1) under Assumptions 1-3. Then, for any k ≥ 1,E[F (x k )] -F * ≤ 4c 2 c 4 L f D 2 k(k + 1) + 4σD 2c 1 c 4 3k + c 3 3 (k + 2)δ f .Proof. Let k ≥ 1 be arbitrary and F k := E[F (x k )] -F * .Ď M > c 2 L f , F k ≤ 1 A k c 4 Ď M D 2 + 2c 1 σ 2 Ď M -c 2 L f k i=1 a 2 i + c 3 δ f k i=1 A i = 4 k(k + 1) c 4 Ď M D 2 + c 1 k(k + 1)(2k + 1)σ 2 12( Ď M -c 2 L f ) + c 3 12 k(k + 1)(k + 2)δ f = 4c 4 Ď M D 2 k(k + 1) + c 1 (2k + 1)σ 2 3( Ď M -c 2 L f ) + δ k ,where δ k := c3 3 (k + 2)δ f . We now choose Ď M > c 2 L f which minimizes the right-hand side. This isĎ M = c 2 L f + σ 2D c1 3c4 k(k + 1)(2k + 1), for which we getF k ≤ 4c 4 D 2 k(k + 1) c 2 L f + σ 2D c 1 3c 4 k(k + 1)(2k + 1) + c 1 (2k + 1)σ 2 3 σ 2D c1 3c4 k(k + 1)(2k + 1) + δ k = 4c 2 c 4 L f D 2 k(k + 1) + 4σD c 1 c 4 (2k + 1) 3k(k + 1) + δ k ≤ 4c 2 c 4 L f D 2 k(k + 1) + 4σD 2c 1 c 4 3k + δ k .D Omitted Proofs for Section 5 D.1 Universal SGD Theorem 7. Let Algorithm 1 with M 0 = 0 be applied to problem (1) under Assumptions 1, 2 and 6, and let σ 2 * := Var p g (x * ). Then, for the point s x N produced by the method, we haveE[F (s x N )] -F * ≤ c 4 (c 2 L f + 12c 1 L p g )D 2 N + 2σ * D 6c 1 c 4 N + c 3 δ f + 4 3 δ p g .Proof. Let x 0 , . . . , x N be the points generated inside the method and letF N := E[F (s x N )] -F * .Using Lemma 19 and Assumption 6, we can estimate, for any 0≤ k ≤ N -1, Var p g (x k+1 ) + Var p g (x k ) ≤ 3 Var p g (x k ) + 2 Var p g (x k+1 , x k ) ≤ 6σ 2 * + 6 Var p g (x k , x * ) + 2 Var p g (x k+1 , x k ) ≤ 6σ 2 * + 12L p g [β f, s f ,s g (x k , x * ) + δ p g ] + 4L p g [β f, s f ,s g (x k+1 , x k ) + δ p g ] = 6σ 2 * + 4L p g [3β f, s f ,s g (x k , x * ) + β f, s f ,s g (x k+1 , x k ) + 4δ p g ].Substituting this bound into the general guarantee given by Lemma 24 (and taking into account the fact that M 0 = 0), we obtainN F N + N -1 k=0 E[β f, s f ,s g (x k+1 , x k ) + β f, s f ,s g (x k , x * )] ≤ c 4 Ď M D 2 + 6c 1 σ 2 * N Ď M -c 2 L f + α N -1 k=0 E[β f, s f ,s g (x k+1 , x k ) + 3β f, s f ,s g (x k , x * )] + N (c 3 δ f + 4αδ p g ),where Ď M > c 2 L f is an arbitrary constant and α := 4c1Lp g Ď M -c2L f . Requiring now that 3α ≤ 1 or, equivalently, that Ď M ≥ c 2 L f + 12c 1 L p g =: Ď M min , we can cancel the nonnegative β f, s f ,s g (•,•) terms on both sides and obtain F N ≤ c 4 Ď M D 2 N + 6c 1 σ 2 * Ď M -c 2 L f + δ,F N ≤ c 4 D 2 N c 2 L f + 12c 1 L p g + σ * D 6c 1 N c 4 + 6c 1 σ 2 * σ * D 6c1N c4 + δ = c 4 (c 2 L f + 12c 1 L p g )D 2 N + 2σ * D 6c 1 c 4 N + δ. D.E[F (x k )] -F * ≤ 4c 2 c 4 L f D 2 k(k + 1) + 24c 1 c 4 L p g D 2 k + 1 + 4σ * D 2c 1 c 4 k + c 3 3 (k + 2)δ f + 4 3 δ p g .Proof. Let k ≥ 1 be arbitrary and F k := E[F (x k )] -F * .(x i+1 , y i ) ≤ 6σ 2 * + 12L p g [β f, s f ,s g (y i , x * ) + δ p g ] + 4L p g [β f, s f ,s g (x i+1 , y i ) + δ p g ] = 6σ 2 * + 4L p g [3β f, s f ,s g (y i , x * ) + β f, s f ,s g (x i+1 , y i ) + 4δ p g ].Substituting this bound into the guarantee given by Lemma 27, we obtainA k F k + k-1 i=0 E[A i+1 β f, s f ,s g (x i+1 , y i ) + a i+1 β f, s f ,s g (y i , x * )] ≤ c 4 Ď M D 2 + k-1 i=0 α i+1 E[β f, s f ,s g (x i+1 , y i )+3β f, s f ,s g (y i , x * )+4δ p g ]+ 6c 1 σ 2 * Ď M -c 2 L f k i=1 a 2 i +c 3 δ f k i=1 A i ,whereα i+1 := 4c1L p g a 2 i+1 Ď M -c2L f , a i = 1 2 i, A k = 1 4 k(k + 1), k i=1 a 2 i = 1 24 k(k + 1)(2k + 1), k i=1 A i = 1 12 k(k + 1)(k + 2). Requiring now that 3α i+1 ≤ a i+1 for all i = 0, . . . , k -1 or, equivalently, thatĎ M ≥ c 2 L f + 12c 1 L p g a k ≡ c 2 L f + 6c 1 L p g k, we can cancel the nonnegative β f, s f ,s g (•,•) terms on both sides and obtainF k ≤ 1 A k c 4 Ď M D 2 + 6c 1 σ 2 * Ď M -c 2 L f k i=1 a 2 i + c 3 δ f k i=1 A i + 4 3 A k δ p g = 4 k(k + 1) c 4 Ď M D 2 + c 1 σ 2 * k(k + 1)(2k + 1) 4( Ď M -c 2 L f ) + c 3 12 δ f k(k + 1)(k + 2) + 4 3 δ p g = 4c 4 Ď M D 2 k(k + 1) + c 1 σ 2 * (2k + 1) Ď M -c 2 L f + δ k ,whereδ k := c3 3 (k + 2)δ f + 4 3 δ p g .The minimizer of the right-hand side is ĎM * = c 2 L f + σ * 2D c1 c4 k(k + 1)(2k + 1). However, recall that we also need to satisfy the constraintĎ M ≥ c 2 L f + 6c 1 L p g k. Choosing Ď M = c 2 L f + 6c 1 L p g k + σ * 2D c1 c4 k(k + 1)(2k + 1), we obtainF k ≤ 4c 4 D 2 k(k + 1) c 2 L f + 6c 1 L p g k + σ * 2D c 1 c 4 k(k + 1)(2k + 1) + c 1 σ 2 * (2k + 1) σ * 2D c1 c4 k(k + 1)(2k + 1) + δ k = 4c 2 c 4 L f D 2 k(k + 1) + 24c 1 c 4 L p g D 2 k + 1 + 4σ * D c 1 c 4 (2k + 1) k(k + 1) + δ k ≤ 4c 2 c 4 L f D 2 k(k + 1) + 24c 1 c 4 L p g D 2 k + 1 + 4σ * D 2c 1 c 4 k + δ k .E Omitted Proofs for Section 6Lemma 28 (Basic property of SVRG oracle). Let p g be a stochastic oracle in R d , and let p G = SvrgOrac p g (x) for some x ∈ R d . Then, for any x ∈ R d , the mean value of p G at x is the same as that of p g at x, while Varp G (x) = Var p g (x, x).Proof. Let g and ξ be, respectively, the function and the random variable components of p g, and let g(x):= E ξ [g(x, ξ)], g(x) := E ξ [g(x, ξ)]. Then, by definition, pG is the oracle with the same random variable component ξ and the function component G defined by G(x, ξ) = g(x, ξ) -g(x, ξ) + g(x).Consequently, E ξ [G(x, ξ)] = g(x), and Var p G (x) = E ξ ∥G(x, ξ) -g(x)]∥ 2 * = E ξ ∥[g(x, ξ) -g(x, ξ)] -[g(x) -g(x)]∥ 2 * = VarM ≥ c 2 L f + 12c 1 L p g , α := 4c1L p g Ď M -c2L f, and any ∇f (x * ) ∈ ∂f (x * ), it holds thatE N [F (x + ) -F * ] + M + 2 ∥x + -x * ∥ 2 ≤ 6αN β ∇f (x * ) f (x * , x) + M 2 ∥x -x * ∥ 2 + N (c 3 δ f + 16αδ p g ) + c 4 D 2 E [min{M + , Ď M } -M ] + .Proof. Since p g is an unbiased oracle for s g, so is p G (Lemma 28). Therefore, we can apply Lemma 24 to getE N [F (x + ) -F * ] + M + 2 ∥x + -x * ∥ 2 + N -1 k=0 [β f, s f ,s g (x k+1 , x k ) + β f, s f ,s g (x k , x * )] ≤ M 2 ∥x -x * ∥ 2 + c 1 Ď M -c 2 L f N -1 k=0 E[Var p G (x k+1 ) + Var p G (x k )] + c 3 N δ f + c 4 E [min{M + , Ď M } -M ] + D 2 ,where Ď M > c 2 L f is an arbitrary constant and x k are the points generated inside UniSgd.Applying now Lemmas 19 and 28 and Assumptions 6 and 9, we can estimate, for each k,Var p G (x k+1 ) + Var p G (x k ) = Var p g (x k+1 , x) + Var p g (x k , x) ≤ 2 Var p g (x k+1 , x k ) + 3 Var p g (x k , x) ≤ 2 Var p g (x k+1 , x k ) + 6 Var p g (x k , x * ) + 6 Var p g (x * , x) ≤ 4L p g [β f, s f ,s g (x k+1 , x k ) + δ p g ] + 12L p g [β f, s f ,s g (x k , x * ) + δ p g ] + 24L p g [β ∇f (x * ) f (x * , x) + 2δ p g ] = 4L p g [β f, s f ,s g (x k+1 , x k ) + 3β f, s f ,s g (x k , x * ) + 6β ∇f (x * ) f (x * , x) + 16δ p g ],where ∇f (x * ) ∈ ∂f (x * ) is arbitrary. Denoting α := 4c1Lp g Ď M -c2L f, we thus obtainE N [F (x + ) -F * ] + M + 2 ∥x + -x * ∥ 2 + N -1 k=0 [β f, s f ,s g (x k+1 , x k ) + β f, s f ,s g (x k , x * )] ≤ 6αN β ∇f (x * ) f (x * , x) + M 2 ∥x -x * ∥ 2 + N (c 3 δ f + 16αδ p g ) + c 4 E [min{M + , Ď M } -M ] + D 2 + α N -1 k=0 E[β f, s f ,s g (x k+1 , x k ) + 3β f, s f ,s g (x k , x * )].Requiring now Ď M ≥ c 2 L f + 12c 1 L p g , we get α ≤ 1 3 which allows us to cancel the nonnegative β f, s f ,s g (•, •) terms on both sides. The claim now follows. Theorem 10. Let UniSvrg (as defined by Algorithm 3) be applied to problem (1) under Assumptions 1, 2, 6 and 9. Then, for any t ≥ 1 and s c 3 := max{c 3 , 1}, we haveE[F (x t )] -F * ≤ [(c 2 c 4 + 1)L f + 48c 1 c 4 L p g ]D 2 2 t + 2s c 3 δ f + 8 3 δ p g .To construct xt , the algorithm needs to make O(2 t ) queries to p g and O(t) queries to s g.Proof. The algorithm iterates (x t+1 , x t+1 , M t+1 ) ∼ = UniSgd p Gt,ψ (x t , M t , 2 t+1 ; D) for t ≥ 0, where p G t = SvrgOrac p g (x t ). Applying Lemma 29 with Ď M := c 2 L f + 48c 1 L p g (for which α = 1 12 so that 6α2 t+1 = 2 t ) and passing to full expectations, we obtain, for any t ≥ 0,E 2 t+1 [F (x t+1 ) -F * ] + M t+1 2 ∥x t+1 -x * ∥ 2 ≤ E 2 t β t + M t 2 ∥x t -x * ∥ 2 + c 4 [min{M t+1 , Ď M } -M t ] + D 2 + 2 t+1 c 3 δ f + 4 3 δ p g ,where β t := β ∇f (x * ) f (x * , xt ) and ∇f (x * ) ∈ ∂f (x * ) can be chosen arbitrarily. Rewriting F t+1 := F (x t+1 ) -F * as F t+1 = β t+1 + (F t+1 -β t+1 ) and telescoping the above inequalities (using, Lemma 18), we get, for any t ≥ 1,E 2 t β t + t i=1 2 i (F i -β i ) + M t 2 ∥x t -x * ∥ 2 ≤ β 0 + M 0 2 ∥x 0 -x * ∥ 2 + c 3 δ f + 4 3 δ p g t i=1 2 i + c 4 E [min{M t , Ď M } -M 0 ] + D 2 ≤ β 0 + 2(2 t -1) c 3 δ f + 4 3 δ p g + c 4 Ď M D 2 =: Φ 0 ,where the final inequality is due to the fact that M 0 = 0, while t i=1 2 i = 2(2 t -1). According to Lemma 30, we can choose ∇f (x * ) ∈ ∂f (x * ) such that β i ≤ F (x i ) -F * for all i ≥ 0. Dropping now various nonnegative terms from the left-hand side of the above display, we conclude that2 t E[F t ] ≤ Φ 0 .Let us estimate Φ 0 . Using our Assumptions 1 and 2 and Theorem 14 (inequality ( 14)), we can boundβ 0 ≤ L f ∥x 0 -x * ∥ 2 + 2δ f ≤ L f D 2 + 2δ f . Therefore, Φ 0 ≤ L f D 2 + 2δ f + c 4 Ď M D 2 + 2(2 t -1)(c 3 δ f + 4 3 δ p g ) ≤ LD 2 + 2(s c 3 δ f + 4 3 δ p g ) • 2 t where L := L f + c 4 Ď M ≡ (c 2 c 4 + 1)L f + 48c 1 c 4 L p g and s c 3 := max{c 3 , 1}. Thus, E[F t ] ≤ Φ 0 2 t ≤ LD 2 2 t + 2s c 3 δ f + 8 3 δ p g ,which proves the claimed convergence rate.Let us now estimate the number of oracle queries. At each iteration t, the algorithm first queries s g to construct the SVRG oracle p G t (by precomputing s g(x t )). All other queries are then done only to p G t or, equivalently, to p g inside UniSgd p Gt,ψ which is run for N t+1 = 2 t+1 iterations and thus requiring O(N t+1 ) queries to p g. Summing up, after T iterations, we obtain the total number ofT t=1 O(N t ) = T t=1 O(2 t ) = O(2 T) queries to p g, and T queries to s g.Lemma 30. Let F : R d → R ∪ {+∞} be the function F (x) := f (x) + ψ(x), where f : R d → R is a convex function, and ψ : R d → R ∪ {+∞} is a proper closed convex function. Let x * be a minimizer of F and let F * := F (x * ). Then, there exists ∇f (x * ) ∈ ∂f (x * ) such that, for any x ∈ dom ψ,F (x) -F * ≥ β ∇f (x * ) f (x * , x).Proof. Since x * is a minimizer of F , we have 0 ∈ ∂F (x * ) = ∂f (x * ) + ∂ψ(x * ). In other words, there exists ∇f(x * ) ∈ ∂f (x * ) such that ∇ψ(x * ) := -∇f (x * ) ∈ ∂ψ(x * ). Consequently, for any x ∈ dom ψ, F (x) -F * = f (x) -f (x * ) + [ψ(x) -ψ(x * )] ≥ f (x) -f (x * ) + ⟨∇ψ(x * ), x -x * ⟩ = f (x) -f (x * ) -⟨∇f (x * ), x -x * ⟩ = β ∇f (x * ) f (x * , x).Lemma 31 (Universal Triangle SVRG Step). Consider problem (1) under Assumptions 1, 2 and 6. Let x, v ∈ dom ψ be points, M ≥ 0 and A, a > 0 be coefficients, p G := SvrgOrac p g (x). Further, let, forA + := A + a, x := Ax + av A + , p G x ∼ = p G(x), p v + = Prox ψ (v, p G x , M/a), p x + = Ax + ap v + A + , p G x+ ∼ = p G(p x + ), x M + = a 2 A + M + A + a 2 M, a 2 A 2 + D 2 , x, p x + , p G x , p G x+ . Then, for Ď M := c 2 L f a 2 A+ + 6c 1 L p g a 2A , it holds thatE A + [F (p x + ) -F * ] + x M + 2 ∥p v + -x * ∥ 2 ≤ A[F (x) -F * ] + M 2 ∥v -x * ∥ 2 + c 4 D 2 E [min{ x M + , Ď M } -M ] + + c 3 A + δ f + 5 3 Aδ p g .Proof. Since p g is an unbiased oracle for s g, so is p G (Lemma 28). Therefore, we can apply Lemma 26 to obtainE A + [F (p x + ) -F * ] + x M + 2 ∥p v + -x * ∥ 2 + A + β f, s f ,s g (p x + , x) + Aβ f, s f ,s g (x, x) ≤ A[F (x) -F * ] + M 2 ∥v -x * ∥ 2 + c 1 a 2 Ď M -c 2 L f a 2 A+ E[Var p G (p x + ) + Var p G (x)] + c 3 A + δ f + c 4 E [min{ x M + , Ď M } -M ] + D 2 ,whereĎ M > c 2 L f a 2A+ is an arbitrary coefficient. Using Lemmas 19 and 28 and Assumption 6, we can further boundVar p G (p x + ) + Var p G (x) = Var p g (p x + , x) + Var p g (x, x) ≤ 2 Var p g (p x + , x) + 3 Var p g (x, x) ≤ 2L p g [2β f, s f ,s g (p x + , x) + 3β f, s f ,s g (x, x) + 5δ p g ]. Denoting α := 2c1L p g a 2 Ď M -c2L f a 2 A +, we thus obtainE A + [F (p x + ) -F * ] + x M + 2 v + -x * ∥ 2 + A + β f, s f ,s g (p x + , x) + Aβ f, s f ,s g (x, x) ≤ A[F (x) -F * ] + M 2 ∥v -x * ∥ 2 + c 3 A + δ f + 5αδ p g + c 4 E [min{ x M + , Ď M } -M ] + D 2 + 2α E[β f, s f ,s g (p x + , x)] + 3αβ f, s f ,s g (x, x). Choosing now Ď M = c 2 L f a 2 A+ + 6c 1 L p g a 2A , we get α = 1 3 A (≤ 1 3 A + ), which allows us to drop the nonnegative β f, s f ,s g (•, •) terms from both sides. The claim now follows. Lemma 32 (Universal Triangle SVRG Epoch). Consider problem (1) under Assumptions 1, 2 and 6. Let x, v ∈ dom ψ be points, M ≥ 0 and A, a > 0 be coefficients, N ≥ 1 be an integer, and let(x + , v + , M + ) ∼ = UniTriSvrgEpoch p g,ψ (x, v, M, A, a, N ; D),as defined by Algorithm 5. Then, forA + := A + a and Ď M := c 2 L f a 2 A+ + 6c 1 L p g a 2A , it holds thatE A + N [F (x + ) -F * ] + M + 2 ∥v + -x * ∥ 2 ≤ AN [F (x) -F * ] + M 2 ∥v -x * ∥ 2 + c 4 D 2 E [min{M + , Ď M } -M ] + + N c 3 A + δ f + 5 3 Aδ p g .Proof. Each iteration k of the algorithm, when conditioned on v k , follows the construction from Lemma 31(with v = v k , M = M k , A = A k , a = a k+1 , A + = A k+1 , x = x k , p G x = G x k , p v + = v k+1 , p x + = x k+1 , p G x+ = G x k+1 , x M + = M k+1). Hence, we can write, after passing to full expectations, for each k = 0, . . . , N -1,E A + [F (x k+1 ) -F * ] + M k+1 2 ∥v k+1 -x * ∥ 2 ≤ A[F (x) -F * ] + E M k 2 ∥v k -x * ∥ 2 + c 4 [min{M k+1 , Ď M } -M k ] + D 2 + δ,where δ := c 3 A + δ f + 5 3 Aδ p g . Telescoping the above inequalities (using Lemma 18), we getE A + N k=1 [F (x k ) -F * ] + M N 2 ∥v N -x * ∥ 2 ≤ AN [F (x) -F * ] + M 0 2 ∥v 0 -x * ∥ 2 + c 4 D 2 E [min{M N , Ď M } -M 0 ] + + N δ.The claim now follows from the convexity of F and our definitions x+ = sx N = 1 N N k=1 x k , v + = v N , M + = M N , M 0 = M , v 0 = v.Theorem 11. Let UniFastSvrg (Algorithm 4) be applied to problem (1) under Assumptions 1, 2 and 6, and let N ≥ 9. Then, for any t ≥ t 0 := ⌈log 2 log 3 N ⌉ -1 (≥ 0), it holds thatE[F (x t )] -F * ≤ 9[(c 2 c 4 + 1 2 )L f + 6c 1 c 4 L p g ]D 2 N (t -t 0 + 1) 2 + (c 3 t + 1)δ f + 5 3 tδ p g .To construct xt , the algorithm needs to make O(N t) queries to p g and O(t) queries to s g. Assuming that the complexity of querying s g is n times bigger than that of querying p g and choosing N = Θ(n), we get the total stochastic-oracle complexity of O(nt).Proof. By our definition, the algorithm iterates for t ≥ 0:(x t+1 , v t+1 , M t+1 ) ∼ = UniTriSvrgEpoch p g,s g,ψ (x t , v t , M t , A t , a t+1 , N ; D),where A t and a t+1 are deterministic coefficients satisfying the following equations:EQUATIONIn particular, for any t ≥ 0, we have ĎM ′ t := c 2 L f a 2 t+1 At+1 + 6c 1 L p g a 2 t+1 At ≤ c 2 L f + 6c 1 L p g =: Ď M , and hence [min{M t+1 , Ď M ′ t } -M t ] + ≤ [min{M t+1 , Ď M } -M t ] + (because,for any fixed a and b, the function [min{a, •} -b] + is nondecreasing as the composition of two nondecreasing functions). Applying now Lemma 32 and passing to full expectations, we therefore obtain, for any t ≥ 0,E A t+1 N [F (x t+1 ) -F * ] + M t+1 2 ∥v t+1 -x * ∥ 2 ≤ E A t N [F (x t )-F * ]+ M t 2 ∥v t -x * ∥ 2 +c 4 [min{M t+1 , Ď M }-M t ] + D 2 +N c 3 A t+1 δ f + 5 3 A t δ p g .Telescoping the above inequalities (using, in particular, Lemma 18), we obtain, for any t ≥ 1,A t N E[F (x t ) -F * ] ≤ A 0 N [F (x 0 ) -F * ] + M 0 2 ∥v 0 -x * ∥ 2 + c 4 E [min{M t , Ď M } -M 0 ] + D 2 + N c 3 δ f t i=1 A i + 5 3 δ p g t-1 i=0 A i ≤ A 0 N [F (x 0 ) -F * ] + c 4 Ď M D 2 + N S t (c 3 δ f + 5 3 δ p g ),where, for the last inequality, we have used the fact that M 0 = 0 and denoted S t := t i=1 A i . Thus, for any t ≥ 1,E[F (x t )] -F * ≤ 1 A t A 0 [F (x 0 ) -F * ] + c 4 Ď M D 2 N + S t A t c 3 δ f + 5 3 δ p g .At the same time, according to (17) , A t+1 -A t = √ A t for any t ≥ 0. Hence, by Lemma 33 (and our assumption on A 0 ), we can estimate A t ≥ 1 9 (t -t 0 + 1) 2 for any t ≥ t 0 := ⌈log 2 log 3 1 A0 ⌉ -1 (≥ 0). Further, since the sequence A t is increasing, we can estimate S t ≡ t i=1 A i ≤ tA t , so that St At ≤ t. Substituting these bounds into the above display and using our formula for A 0 , we obtain, for anyt ≥ t 0 , E[F (x t )] -F * ≤ ρ t [F (x 0 ) -F * + c 4 Ď M D 2 ] + t(c 3 δ f + 5 3 δ p g ),Combining the above inequality first with f (x + ) ≤ s f (x) + ⟨s g(x), x + -x⟩ + L f 2 ∥x + -x∥ 2 + δ f and then with s f (x) + ⟨s g(x), x * -x⟩ ≤ f (x * ) (which are both due to our Assumption 1), we obtainF (x + ) = f (x + ) + ψ(x + ) ≤ f (x + ) + ⟨s g(x), x * -x + ⟩ + ψ(x * ) ≤ s f (x) + ⟨s g(x), x * -x⟩ + ψ(x * ) + L f 2 ∥x + -x∥ 2 + δ f ≤ F * + L f 2 ∥x + -x∥ 2 + δ f .It remains to bound ∥x + -x∥ ≤ D.We start with the observation that for our specific example all our main assumptions are satisfied. Remark 35. Under the setting from Example 12, Assumptions 1, 6 and 9 are satisfied with s f = f , Let Algorithm 1 be applied to this problem with the oracle p g = p g b and initial coefficient M 0 = 0. Then, for the point ss g(x) = ∇f (x) := E ξ [∇f ξ (x)], any δ f , δ p g > 0 and L f = 1 -ν 2(1 + ν)δ f 1-ν 1+ν [H f (ν)] 2 1+ν , L p g = 1 b 1 -ν 2(1 + ν)δ p g 1-ν 1+ν [H max (ν)]x N generated by the algorithm, we haveE[F (s x N )] -F * ≤ (2c 2 c 4 ) 1+ν 2 c 1-ν 2 3 1 + ν H f (ν)D 1+ν N 1+ν 2 + 2σD 2c 1 c 4 bN .To reach E[F (s x N )] -F * ≤ ϵ for any ϵ > 0, it suffices to make O [H f (ν) ϵ ] 2 1+ν D 2 + σ 2 D 2 bϵ 2 queries to p g b .Proof. Denote for brevity H f := H f (ν). Taking into account Remark 35 and applying Theorem 4, we get, for any δ f > 0,F N := E[F (s x N )] -F * ≤ c 2 c 4 H 2 1+ν f D 2 N 1 -ν 2(1 + ν)δ f 1-ν 1+ν + c 3 δ f + σ N , where σ N := 2σ b D 2c1c4 N = 2σD 2c1c4bN . Minimizing the right-hand side in δ f (using Lemma 36 with p = 1-ν 1+ν for which p + 1 = 2 1+ν ), we obtainF N ≤ 2 1 + ν c 2 c 4 H 2 1+ν f D 2 N 1 -ν 2(1 + ν) 1-ν 1+ν 1+ν 2 1 + ν 1 -ν c 3 1-ν 2 + σ N = (2c 2 c 4 ) 1+ν 2 c 1-ν 2 3 1 + ν H f D 1+ν N 1+ν 2 + σ N .This proves the claimed convergence rate, and the oracle complexity bound easily follows since each iteration of the algorithm requires only E[F (x k )] -F * ≤ 2 2+ν (c 2 c 4 ) 1+ν 2 ( c3 3 ) 1-ν 2 1 + ν H f (ν)D 1+ν k 1+3ν 2 + 4σD 2c 1 c 4 3bk .To reach E[F (x k )] -F * ≤ ϵ for any ϵ > 0, it suffices to make O [H f (ν)D 1+ν ϵ ] 2 1+3ν + σ 2 D 2 bϵ 2 queries to p g b .Proof. Let k ≥ 1 be arbitrary and denote for brevity H f := H f (ν). Taking into account Remark 35 and applying Theorem 5, we get, for any δ f > 0,F k := E[F (x k )] -F * ≤ 4c 2 c 4 H 2 1+ν f D 2 k(k + 1) 1 -ν 2(1 + ν)δ f 1-ν 1+ν + c 3 3 (k + 2)δ f + σ k ,where σ k := 4σ b D 2c1c4 3k = 4σD 2c1c4 3bk . Minimizing the right-hand side in δ f (using Lemma 36) and estimating k + 2 ≤ 2(k + 1), we obtainEQUATION1-ν 2 + σ k = 2(4c 2 c 4 ) 1+ν 2 ( c3 3 ) 1-ν 2 1 + ν H f D 1+ν k 1+ν 2 (k + 1) ν + σ k .This proves the claimed convergence rate, and the oracle complexity bound easily follows since each iteration of the algorithm requires only O(1) queries to p g b .Remark 39. The efficiency guarantees given by Corollaries 37 and 38 are exactly the same as those from [49] , up to absolute constants. Let Algorithm 1 be applied to this problem with the oracle p g = p g b and initial coefficient M 0 = 0. Then, for the point sx N generated by the algorithm, we haveE[F (s x N )] -F * ≤ c f (ν)H f (ν)D 1+ν N 1+ν 2 + c p g (ν)H max (ν)D 1+ν (bN ) 1+ν 2 + 2σ * D 6c 1 c 4 bN ,where c f (ν) := (2c2c4) H f (ν) ϵ ] 2 1+ν D 2 + 1 b [ H p g (ν) ϵ ] 2 1+ν D 2 + σ 2 * D 2 bϵ 2queries to p g b .Proof. Denote for brevity F N := E[F (s x N )] -F * , H f := H f (ν) and H max := H max (ν). Taking into account Remark 35 and applying Theorem 7, we get, for any δ f , δ p g > 0,F N ≤ c 2 c 4 H 2 1+ν f D 2 N 1 -ν 2(1 + ν)δ f 1-ν 1+ν + 12c 4 H 2 1+ν max D 2 bN 1 -ν 2(1 + ν)δ p g 1-ν 1+ν + c 3 δ f + 4 3 δ p g + σ N ,whereσ N := 2σ * ,b D 6c1c4 N = 2σ * D 6c1c4 bN .Minimizing the right-hand side in δ f and δ p g (using Lemma 36 twice), we getF N ≤ 2 ν c 2 c 4 H 2 1+ν f D 2 N 1 -ν 2(1 + ν) 1-ν 1+ν 1+ν 2 (1 + ν)c 3 1 -ν 1-ν 2 + 2 1 + ν 12c 4 H 2 1+ν max D 2 bN 1 -ν 2(1 + ν) 1-ν 1+ν 1+ν 2 (1 + ν) 4 3 1 -ν 1-ν 2 + σ N = (2c 2 c 4 ) 1+ν 2 c 1-ν 2 3 1 + ν H f D 1+ν N 1+ν 2 + (24c 4 ) 1+ν 2 ( 4 3 ) 1-ν 2 1 + ν H max D 1+ν (bN ) 1+ν 2 + σ N .This proves the claimed convergence rate, and the oracle complexity bound easily follows since each iteration of the algorithm requires only 1 query to p g b .Corollary 41. Consider problem (1) under the setting from Example 12 and also under Assumption 2. Let Algorithm 2 be applied to this problem with the oracle p g = p g b . Then, for any k ≥ 1, we have EQUATION= O(1). To reachE[F (x k )] -F * ≤ ϵ for any ϵ > 0, it suffices to make O [ H f (ν)D 1+ν ϵ ] 2 1+3ν + 1 b [ Hmax(ν) ϵ ] 2 1+ν D 2 + σ 2 * D 2 bϵ 2queries to p g b .Proof. Let k ≥ 1 be arbitrary and denote for brevity F k := E[F (x k )] -F * , H f := H f (ν)F k ≤ 4c 2 c 4 H 2 1+ν f D 2 k(k + 1) 1 -ν 2(1 + ν)δ f 1-ν 1+ν + 24c 1 c 4 H 2 1+ν max D 2 bk 1 -ν 2(1 + ν)δ p g 1-ν 1+ν + c 3 3 (k + 2)δ f + 4 3 δ p g + σ k ,whereσ k := 4σ * ,b D 2c1c4 k = 4σ * D 2c1c4 bk .Minimizing the right-hand side in δ f and δ p g (using Lemma 36 twice) and estimating 1 3 (k + 2) ≤ 2 3 (k + 1), we obtainF k ≤ 2 1 + ν 4c 2 c 4 H 2 1+ν f D 2 k(k + 1) 1 -ν 2(1 + ν) 1-ν 1+ν 1+ν 2 (1 + ν) 2c3 3 (k + 1) 1 -ν 1-ν 2 + 2 1 + ν 24c 1 c 4 H 2 1+ν max D 2 bk 1 -ν 2(1 + ν) 1-ν 1+ν 1+ν 2 (1 + ν) 4 3 1 -ν 1-ν 2 + σ k = (8c 2 c 4 ) 1+ν 2 ( 2 3 c 3 ) 1-ν 2 1 + ν H f D 1+ν k 1+ν 2 (k + 1) ν + (48c 1 c 4 ) 1+ν 2 ( 4 3 ) 1-ν 2 1 + ν H max D 1+ν (bk) 1+ν 2 + σ k .This proves the claimed convergence rate, and the oracle complexity bound easily follows since each iteration of the algorithm requires only O(1) queries to p g b .Remark 42. In the proof of Corollary 41, it was important that δ f and δ p g 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 O( Hmax Let UniSvrg (as defined by Algorithm 3) be applied to this problem with the stochastic oracle p g = p g b and the full-gradient oracle s g = ∇f . Then, for any t ≥ 1,EQUATION, where c f (ν) := [2(c2c4+1)]H f (ν) ϵ ] 2 D 2 + 1 b [ ϵ ] 2 1+ν D 2 .Assuming that the complexity of querying s g b is n b times bigger than that of querying ∇f , we get the total stochastic-oracle complexity of O(N ν (ϵ) + n b log + N ν (ϵ)).Proof. Let t ≥ 1 be arbitrary and denote for brevityF t := E[F (x t )] -F * , H f := H f (ν) and H max := H max (ν).Taking into account Remark 35 and applying Theorem 10, we get, for any δ f , δp g > 0, F t ≤ (c 2 c 4 + 1)H 2 1+ν f D 2 2 t 1 -ν 2(1 + ν)δ f 1-ν 1+ν + 48c 1 c 4 H 2 1+ν max D 2 b2 t 1 -ν 2(1 + ν)δ p g 1-ν 1+ν + 2s c 3 δ f + 8 3 δ p g .Minimizing the right-hand side in δ f , δ p g (using Lemma 36 twice), we obtainEQUATION, . This proves the claimed convergence rate.where c f := [2(c2c4+1)]Let us now estimate the oracle complexity. From the already proved convergence rate bound, we see that F t ≤ ϵ once 2 t ≥ O(1)N (ϵ), where N (ϵ) := [ Let UniFastSvrg (Algorithm 4) be applied to this problem with the stochastic oracle p g = p g b , the full-gradient oracle s g = ∇f , and the epoch length N ≥ 9. Then, for any t ≥ 2t 0 , whereEQUATIONEQUATION, where c f (ν) := [72(c2c4+ 1 2 )]n ν b H f (ν)D 1+ν ϵ ] 2 1+3ν + [ n ν b Hmax(ν)D 1+ν b (1+ν)/2 ϵ ] 2 1+3ν + n b log log n b Proof. Let t ≥ 2t 0 be arbitrary, F t := E[F (x t )] -F * , H f := H f (ν), H max := H max (ν).Taking into account Remark 35 and applying Theorem 11, we get, for any δ f , δ p g > 0,F t ≤ 9(c 2 c 4 + 1 2 )H 2 1+ν f D 2 N (t -t 0 + 1) 2 1 -ν 2(1 + ν)δ f 1-ν 1+ν + 54c 1 c 4 H 2 1+ν max D 2 bN (t -t 0 + 1) 2 1 -ν 2(1 + ν)δ p g 1-ν 1+ν + (c 3 t + 1)δ f + 5 3 tδ p g .Since t ≥ 2t 0 , we can estimate t -t 0 + 1 = 1 2 t + 1 2 t -t 0 + 1 ≥ 1 2 (t + 1), which gives usF t ≤ 36(c 2 c 4 + 1 2 )H 2 1+ν f D 2 N (t + 1) 2 1 -ν 2(1 + ν)δ f 1-ν 1+ν + 216c 1 c 4 H 2 1+ν max D 2 bN (t + 1) 2 1 -ν 2(1 + ν)δ p g 1-ν 1+ν + s c 3 (t + 1)δ f + 5 3 (t + 1)δ p g .Minimizing the right-hand side in δ f , δ p g (using Lemma 36 twice), we obtainEQUATION,where c f := [72(c2c4+ 1 2 )] 1+ν 2 s c 1-ν 2 3 1+ν and c p g := (432c1c4) 1+ν 2 ( 5 3 ) 1-ν 2 1+ν. This proves the claimed convergence rate.Let us now estimate the number of oracle queries. In view of the above convergence rate bound, we haveF t ≤ ϵ once t ≥ T (ϵ) := T 1 (ϵ) + 2t 0 = O T 1 (ϵ) + log log N , where T 1 (ϵ) := [ H f D 1+ν N (1+ν)/2 ϵ ] 2 1+3ν + [ HmaxD 1+ν (bN ) (1+ν)/2 ϵ ] 2 1+3ν = T2(ϵ) N 1+ν 1+3ν, where T 2 (ϵ) := [H f D 1+ν ϵ ] 2 1+3ν + [ HmaxD 1+ν b (1+ν)/2 ϵ ] 2 1+3νdoes not depend on N . Combining this with Theorem 11 saying that, to generate the corresponding xt , the algorithm needs to make O(N t) queries to p N q = N 1-q + n b N q with q := 1+ν 1+3ν ∈ [0, 1], whose minimal value is achieved at N = Θ(n b ). Substituting this value into our complexity bound, we get the stochastic-oracle complexity of O n b (T2(ϵ) n (1+ν)/(1+3ν) b + log log n b ) = O n 2ν 1+3ν b T 2 (ϵ) + n b log log n b .Inexact Oracle and Approximate Smoothness. 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-dependent constants. For more details on the subject, see [14] . Parameter-Free Methods. Parameter-free algorithms originating from the literature on online learning [9, 10, 26, 40, 47, 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, 11, 25, 31, 41] .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 [3] , 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 [21] 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-parameterized regime, or when the stochastic noise is small at the optimal solution [8, 35, 37, 43, 44, 51] . In this work, we call this effect implicit variance reduction. Such a situation is also considered in [19, 54] 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.In this section, we present experiments on the logistic regression problem:f * = min ∥x∥≤R f (x) := 1 n n i=1 log(1 + e -bi⟨ai,x⟩ ) ,where a i ∈ R d and b i ∈ {-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 it satisfies the so-called interpolation condition, meaning that the variance at the optimum is zero. We fix R = 1 and use the mini-batch size of b = 32 for the first two datasets and b = 1 for the last two.Figure 3 shows the results of 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 UniFastSgd converge as fast as the best non-accelerated and accelerated SVRG methods, respectively, which Step size 0 25000 50000 75000 100000125000150000 number of stochastic oracle calls Step size 0 25000 50000 75000 100000125000150000 number of stochastic oracle calls confirms our theory on implicit variance reduction. Otherwise, these two SGD methods are 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.In this section, we compare the AdaGrad stepsize rule (3) with the other rule (4) for UniSgd (Algorithm 1), UniFastSgd (Algorithm 2), UniSvrg (Algorithm 3), and UniFastSvrg (Algorithm 4). We consider the polyhedron feasibility and logistic regression problems under the same setups as in Section 8 and Appendix H.1.The results are shown in Figs. 4 and 5 , 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. Step size UniFastSgd-AdaGrad UniFastSgd-Other UniFastSvrg-AdaGrad UniFastSvrg-Other 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 to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.• The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a 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) is recommended, but including URLs to data and code is permitted.The corresponding source code is available at https://github.com/mlolab/universal-adagrad-experiments. 


Decision: After a length author response period, all reviewers ultimately recommended acceptance of the paper.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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. 

    **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.

    **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.

    **iii.** More importantly, I think different works with AdaGrad-like stepsize are trying to relax it recently as mentioned by the authors.
    
    **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.

2. 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.

3. For some plots, I cannot find the confidence interval. Please add it according to the checklist.
questions: questions: See **Weaknesses**.
limitations: limitations: Not applicable.
paper_summary: paper_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.
strength_weakness: strength_weakness: Rather than pointing out shortcomings, I would like to discuss some issues with the authors.
questions: 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: 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.
paper_summary: paper_summary: This paper proves new convergence rates for stochastic gradient methods with
AdaGrad step-sizes. The authors' build on the fact that AdaGrad step-sizes
adapt to both the smooth and non-smooth settings and extend these results to
show convergence with biased stochastic gradient oracles on functions which are
only approximately smooth. Because Hölder-smooth functions satisfy this class,
this paper shows that AdaGrad step-sizes lead to universal methods which only
require knowledge of the diameter, $D$. As part of their analysis, the authors
also show how to relax the bounded variance assumption and combine AdaGrad
step-sizes with acceleration and variance reduction.
strength_weakness: strength_weakness: - The contributions are fairly niche. Universality of (accelerated) SGD with
    modified AdaGrad step-sizes is known [14], Adagrad is known to converge
    without bounded variance [2], and AdaGrad step-sizes have been used with
    (accelerated) SVRG previously [14, 34]. Thus, this paper fits into a small
    gap by proving universality with a relaxed variance condition and covering
    both acceleration and variance reduction.

- ~The actually degree to which bounded variance is relaxed is not clear since
    the connections between Assumption 3 and Assumption 6 are not developed.~

- ~Variance reduce SGD with AdaGrad step-sizes (UniSvrg) only converges to a 
    neighbourhood of the optimal solution even when using an unbiased stochastic
    gradient oracle.~

- Experiments are only for synthetic problems and do not show the actual relationship
    between oracle calls and optimization error. 

### Detailed Comments

**Note**: The authors have clarified the connection between Assumptions 3 and 6 as well the role of $\delta_g$ in Theorem 10. 

**Assumption 3 vs Assumption 6/9**: 

An important and unaddressed issue is the comparison between between
Assumption 3 and Assumption 6/9. Clearly Assumption 3 implies Assumption 6/9
up to constant factors. But, in what circumstances do Assumptions 6/9 hold
but the variance is not bounded, i.e. Assumption 3 fails? In comparison to this
work, Nguyen et al. [2] give results for (strongly-convex) SGD that depend
only on the stochastic gradient variance at the minimizer and without 
any variance assumption. Indeed, the typical assumption in this setting is only
that $\mathbb{E}[\|g(x^*, \xi)\|_2^2]$ is finite.


**Theorem 10**

I'm somewhat disturbed that SVRG with Adagrad step-sizes doesn't converge
exactly to a minimizer $x^*$ under your assumptions. For example, suppose
$\nabla f$ is $L$-Lipschitz and $\bar g = \nabla f$ so that $\delta_f$ is zero.
In this setting, I expect variance-reduced methods like SVRG to converge
exactly to a minimizer, but Theorem 10 shows UniSVRG converges to a
neighbourhood of size $O(\delta_{\hat g})$. In comparison, standard SVRG, which
does not require any variance bound (Allen-Zhu and Yuan, [1]), converges
exactly. Can you please give sufficient conditions for $\delta_{\hat g}$ to be
zero and explain how they compare to standard SVRG assumptions?

Also, why are both Assumptions 6 and 9 required simultaneously for this
theorem? They provide similar bounds on the variance of the gradient
estimators, so I would have thought that Assumption 9 supplants Assumption 6.

**Experiments**:

I would have liked to see more realistic experiments. I understand that finding
real-world problems for which the diameter $D$ is bounded can be difficult, but
one synthetic regression problem is not sufficient to judge the performance of
the methods analyzed in this paper. In comparison, Dubois-Taine et al. [14]
include a large number of experiments on real-world data.

In addition, I strongly dislike the choice to treat one mini-batch gradient
computation as a single oracle call instead of $b$ calls.  While the choice has
no effects in Figure 1, it is actually quite misleading in Figure 2, where it
makes the total SFO complexity of all the algorithms appear to decrease as
batch-size increases. In reality, the SFO complexity should decrease until a
threshold and then $b$ and then begin to increase again. That is, there is some
optimal batch-size (usually less than $n$) which minimizes total complexity


### Minor Comments

- "Gradient methods are the most popular and efficient optimization algorithms
    for solving machine learning problems." --- They are not the most efficient
    methods depending on the problem class and desired sub-optimality, so I
    wouldn't say this.

- "However, the line-search approach is unsuitable for problems of stochastic
    optimization, where gradients are observed with random noise." --- you may
    want to mention that line-search works with stochastic gradients when
    interpolation is satisfied [1].

- So the difference between the results in Section 4 and [47] is that [47]
    considers a modification of the Adagrad step-size? You might want to 
    state this modification so the difference is clear. 

- Contributions, Bullet 3: I don't like calling this variance reduction. It is
    well-known that SGD with a constant step-size depends only on the variance
    of the stochastic gradients at the minimizer [2], but no one would call SGD
    variance reduced. 

- Table 1: 
    - Can you make the font-size larger? It's a little hard to read this
    table. 
    - If you are reporting Big-O complexities, then can you please put them
        in Big-O notation?
    - You should explain in the caption why UniSgd and UniFastSgd have two 
        convergence rates each (e.g. variance assumptions).

- Line 117: If it's satisfied for any $\delta_f > 0$ then taking limits as
    $\delta_f \rightarrow 0$ would imply that it's also satisfies for 
    $\delta_f = 0$.

- Line 136: I would say the classical method is due to Nesterov [3], while you
    are referring to more recent acceleration methods for composite
    optimization.

- Eq. (4): How you solve this implicit equation, given that $\hat x_+$ depends
    on $\hat M_+$ through the stochastic gradient update?

- Assumption 6: In line 126, you say that the oracle outputs are assumed to be
    independent. However, from the notation in Assumption 6, it seems that
    in this case the oracle is evaluated with the same randomness $\xi$.
    Indeed, this must be the case else Assumption 6 reduces to Assumption 3.
    Maybe you can add a remark clarifying this in the text?

- Theorems 4,7: You should comment somewhere in the text that these rates 
    (according to Algorithm 1) are not anytime, but require knowledge of $N$.

- Line 230: This sentence isn't finished.

- Page 7: The spacing between the algorithm blocks is quite weird. You
    should probably fix this. 

- Theorem 11: I would prefer if you stated this without assuming 
    $N \in \Theta(n)$. 

- Table 2, row 3: I think there's a typographic issue here since you appear to 
    be adding the definition of $N_\nu(\epsilon)$ with the log. 

- Figures 1, 2: 
    - The font sizes are much too small to read. As a rule of thumb,
        the size of text in a figure should be at least as large as the size of
        text in paragraph mode.
    - Figure 1: It would be nice if you reminded the reader that $q$ is the
        power in the test problem in Eq. (5).

- Line 916: You should also reference SDCA [4] and SAG [5], which were very
    early (if not the earliest) variance reduction methods.

### References


[1] Vaswani, Sharan, et al. "Painless stochastic gradient: Interpolation, line-search, and convergence rates." Advances in neural information processing systems 32 (2019).

[2] Nguyen, Lam, et al. "SGD and Hogwild! convergence without the bounded gradients assumption." International Conference on Machine Learning. PMLR, 2018.

[3] Nesterov, Yurii. "A method for solving the convex programming problem with convergence rate O (1/k2)." Dokl akad nauk Sssr. Vol. 269. 1983.

[4] Shalev-Shwartz, Shai, and Tong Zhang. "Stochastic dual coordinate ascent methods for regularized loss minimization." Journal of Machine Learning Research 14.1 (2013).

[5] Schmidt, Mark, Nicolas Le Roux, and Francis Bach. "Minimizing finite sums with the stochastic average gradient." Mathematical Programming 162 (2017): 83-112.
questions: questions: To reiterate, my questions are:

- Why doesn't SVRG with AdaGrad step-sizes converge exactly and under what
    conditions is $\delta_{\hat g} = 0$ satisfied?

- Why are both Assumptions 6 and 9 required to show convergence of UniSVRG? 

- Under what conditions are Assumptions 6/9 weaker than Assumption 3?
limitations: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
2. 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. 
3. More extensive empirical evaluations across a wider range of practical problems on real-world datasets would strengthen the experiments part of this paper.
4. 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?
questions: questions: See the weaknesses part.
limitations: limitations: N/A

Comments: comment: Dear All,

We have noticed that the [RKWAC24] reference in our original reply was missing
a title. The correct reference is the following:

- [RKWAC24] A. Rodomanov, A. Kavis, Y. Wu, K. Antonakopoulos, V. Cevher.
  Universal Gradient Methods for Stochastic Convex Optimization. ICML, 2024.

We would also like to highlight a few other important contributions of our
work, in addition to those mentioned previously.

- We propose a novel version of the adaptive accelerated SVRG method (Algorithm 4).
  This method and its analysis are both much simpler compared to the only other
  existing option which is the AdaVRAE method from [LNEN22], while our
  complexity results are stronger. See our discussion with Reviewers PtE8 and
  soXZ for more details.

- Even in the special case of Hölder-smooth problems with uniformly bounded
  variance, for which the complexity results of our methods coincide with those
  from [RKWAC24], our work still offers some novelty and improvements compared
  to [RKWAC24]. First, our convergence analysis works not only for the modified
  AdaGrad step size from [RKWAC24] but also for the more classical one
  (based on the summation of squared gradient norms, see eq. (3) in our paper).
  Further, our convergence analysis is considerably different and, in fact,
  simpler. In particular, compared to [RKWAC24], we do not need to use several
  rather technical lemmas to handle recurrent sequences involving the
  combination of several terms in different powers depending on $\nu$
  (see Lemmas E.6-E.9 in their paper). Such a simplification is quite
  significant and was the first crucial step allowing us to concisely extend
  the corresponding results to $\sigma_*$-bounds and variance-reduced methods.

- Compared to the variety of other papers, we also allow the stochastic oracle
  to be biased and present concise proofs which cover, in a unified way, many
  different methods (basic and accelerated, with and without variance
  reduction). For example, the whole proof for the accelerated SVRG takes only
  3.5 pages (see Section A.4.2) once we reuse the general result on one step of
  the accelerated SGD (which does not use any variance reduction at all). This
  is also an important aspect of our work which should not be neglected.

We hope the Reviewers and the Area Chair will keep in mind the contributions
mentioned above and in the previous reply during the final evaluation of our
work.
Dear Reviewer aWSb,

Regarding the mini-batch size, we have already explained to you (with two
examples) why the "optimal" mini-batch size you propose will not improve
anything besides maybe (already quite reasonable) absolute constants in the
theoretical worst-case complexity estimates. Such an improvement is rather
insignificant, especially considering the fact that the expression for the
"optimal" mini-batch size involves a number of unknown constants and is
therefore completely impractical; tuning the mini-batch size in the experiments
is possible but will incur an additional overhead defeating the potential
gain in improving the absolute constants.

Note also that Imaizumi [2] does not improve any order of convergence. They
simply say that, for any stepsize $\alpha \leq \frac{1}{L}$, it is possible to
choose a sufficiently large mini-batch size $b \sim \frac{L \alpha \sigma^2}{\epsilon^2}$
such that, after $N \sim \frac{F_0}{\alpha \epsilon^2}$ iterations, the method
will find a point with $\epsilon$-suboptimality in terms of the gradient norm.
However, the total SFO complexity is
$b N \sim \frac{L F_0}{\epsilon^2} + \frac{L F_0 \sigma^2}{\epsilon^4}$,
which is exactly the same result as one gets by using mini-batch size $b = 1$
and choosing the step size
$\alpha \sim \min\\{ \frac{1}{L}, \sqrt{\frac{F_0}{k L \sigma^2}} \\}$
(see Corollary 2.2 in [GL13]).

Therefore, we still disagree with your comment that treating the mini-batch
computation as a single oracle call (assuming the corresponding computation can
be efficiently parallelized) is wrong. In contrast to what you are proposing, in
such a framework, increasing the mini-batch size does provably lead to the
improvement in the total running time, and such an improvement is not just a
(small) absolute constant. Furthermore, the corresponding computational model is
completely realistic (distributed optimization) and does not require tuning the
mini-batch size which is instead simply set to the number of available computing
nodes. Again, see, e.g., [WS21] from our main reply for more details on the
"minibatch parallelization speedup". Note that our viewpoint is still reasonable
even if our methods might not attain the lower complexity bounds from [B2019]
(which are nevertheless for a completely different setting of computing in
parallel full gradients and when the number of such computations is growing
sufficiently fast with the dimension of the space).

**References:**

- [GL13] S. Ghadimi, G. Lan. Stochastic First- and Zeroth-Order Methods for
  Nonconvex Stochastic Programming. SIOPT, 2013.

---

As for the contributions, we kindly disagree that extension to Hölder-smooth
functions is the only main contribution of our work.

As we have already mentioned in our general reply and also during our discussion
with Reviewer PtE8, **another important contribution of our work is establishing
$\sigma_*$-bounds** for SGD methods with AdaGrad step sizes (Theorems 7 and 8),
**including the nontrivial accelerated method**. **These bounds are novel and
have not been proved in any of the previous works.** Neither of the works [AK23]
or (Nguyen et al., [2]) which you mentioned before contains any comparable
results.

**Another significant contribution is a novel version of the adaptive
accelerated SVRG method (Algorithm 4).** This method and its analysis are both
much simpler compared to the only other existing option which is the AdaVRAE
method from [LNEN22], while our complexity results are stronger. See our
discussion with Reviewers PtE8 and soXZ for more details.

Compared to the variety of other papers, we also **allow the stochastic oracle
to be biased** and **present concise proofs which cover, in a unified way, many
different methods (basic and accelerated, with and without variance
reduction)**. For example, the whole proof for the accelerated SVRG takes only
3.5 pages (see Section A.4.2) once we reuse the general result on one step of
the accelerated SGD (which does not use any variance reduction at all). This is
also an important aspect of our work which should not be neglected.
I thank the authors' discussion. I finally decided to maintain my current score after careful consideration.
Dear Reviewer soXZ,

Thanks again for your feedback. Please let us know if you are satisfied with our
reply and if your concerns are now resolved. We would be happy to provide more
explanations if needed.
Thank you. Let us know please if you have any other questions that we can answer
to resolve your remaining concerns.
Dear Reviewer PtE8,

Thanks for the interesting discussion.

**Remark 2:**

As we have indicated in our initial reply, for model selection, one usually
needs to solve $(P_{\lambda})$ not for one specific value of $\lambda$ but for
all of them, and then choose the best one (in terms of accuracy on the
validation set). This is typically done by using grid search over multiple
values of $\lambda$. What we were saying before is that this entire procedure is
equivalent to doing grid search over $D$, solving $(P'_D)$ and choosing the best
solution. Thus, we always know $D$ in the latter procedure.

Regarding strong convexity, it is not entirely true that a strongly convex
problem is always faster to solve than a (non-strongly) convex one. Everything
depends on the specific constants. Indeed, consider the convex problem
$\min_x f(x)$ with $L$-smooth objective and assume that the size of its solution
is $D = \\| x^* \\|$. Solving this problem to $\epsilon$-accuracy by the
Gradient Method (GM) started from the origin takes $O(\frac{L D^2}{\epsilon})$
oracle calls. Now consider the strongly convex $\epsilon$-approximation of the
original objective: $f\_{\lambda}(x) = f(x) + \frac{\lambda}{2} \\| x \\|^2$ for
$\lambda = \frac{\epsilon}{R^2}$. To get an $\epsilon$-solution to the
original problem, we need to minimize the regularized objective up to accuracy
$\frac{\epsilon}{2}$. The function $f_{\lambda}$ is $\lambda$-strongly convex,
so GM needs $\tilde{\Theta}(\frac{L}{\lambda}) = \tilde{\Theta}(\frac{L R^2}{\epsilon})$
oracle calls, which is the same complexity as solving the original (non-strongly)
convex problem. (What we have described here is, in fact, a well-known general
reduction of a convex problem to a strongly convex one, which does not help
to reduce the complexity.) For our example with problems $(P_{\lambda})$ and
$(P'_D)$, we have exactly the same effect: $(P\_{\lambda})$ is easy to solve
only when $\lambda$ is sufficiently large, but then the equivalent problem
$(P'_D)$ has small $D$ and is therefore easy to solve as well. Again, please
see Ch. 5 in [SNW11] (from our initial reply) and p. 125 in particular for an
independent argument why solving $(P'_D)$ instead of $(P\_{\lambda})$ is indeed
a reasonable idea.

**$\sigma_*$-bounds:**

We would also like to repeat our previous comment that establishing complexities
for Hölder-smooth problems is only one of the main contributions of our work.
Another significant one is proving $\sigma_*$-bounds for the basic and
accelerated adaptive methods. To our knowledge, such bounds are novel (even in
the case when $\delta = 0$) and the corresponding proofs are nontrivial
(especially for the accelerated method, see our previous comments on this
matter). Would you perhaps be willing to agree with this and raise your score
further?
> It would therefore be unfair to say that we not "addressing constructive feedback from the reviewers"

I did not say that. To be clear, I think that highly technical arguments are quite difficult to hold over OpenReview, place significant burdens on both reviewers and authors, and are often better replaced by high-level clarifications.

>  We have explained in detail that there is actually nothing wrong with it and our viewpoint corresponds to parallel mini-batch computations.

I still don't agree with this. I think that our discussion so-far has shown that (i) there is an optimal mini-batch size, which in the setting of Gower et al. [1] improves by constants factors and in the setting of Imaizumi [2] improves the convergence order (note this requires a general stochastic setting). These facts are hidden by choice to treat a single mini batch as one oracle call. If you wish to consider highly parallel stochastic oracles which permit multiple, simultaneous oracle calls, then you should state that in the paper. Note that this literature admits different algorithms and different lower-bounds from standard sequential oracles [B2019]. 

> Could you please confirm if you agree with these statements and your concerns are now resolved?

Yes, I agree with these two statements. I will update my review accordingly.

----

Overall, I agree with the remarks by Reviewer PtE8 that the extension to Holder-smooth functions is the main contribution of this paper. As I said in my original review, the contributions of this paper fit into small gap between existing works and, as such, I don't think it will have a large impact on either theory or practice. Since the paper is sound and the contributions are likely interesting to some of the NeurIPS community, I think 6 is an accurate score. 

[B2019] Bubeck, Sébastien, et al. "Complexity of highly parallel non-smooth convex optimization." Advances in neural information processing systems 32 (2019).
Thanks for your rebuttal. It addresses most of my concerns and I am happy to increase my score from 4 to 5.
I thank the author's detailed reply. 

**To Remark 1.** I first apologize for my previous wrong claim of your paper only considering the finite-sum case. However, I should mention that the general lower bound doesn't apply to the finite-sum case as it was proved under the finite variance condition as clearly stated in the previous discussion. $n\to \infty$ is another case that is not included in our previous discussion.

**To Remark 2.** After the clarification, the authors seem to want to say that, instead of solving $P_\lambda$, solving $P'_D$ is acceptable. Again, theoretically speaking, this holds. But no one did this in practice as far as I know. Moreover, what $D$ people should use is still unknown. I remind the author that your setting is a problem with a **known** diameter. Say I want to take $\lambda = 1$ (or $\lambda$ in a set of values), then what $D$ should I use for $P'_D$? More importantly, with $\lambda >0$, $P\_\lambda$ is a strongly convex problem, which can be solved faster than $P'\_D$ if $f$ is not strongly convex, which is the case studied in the paper.

**To Remark 3.** Thanks for the clarification. I understand that the separation between $\delta_f$ and $\delta_g$ is more critical, which I suggest to point out in the paper. Based on this insight, I would like to increase my score to 5.
**Remark 1:**

1. Please note that **our paper does not consider only the finite-sum case**.
   Instead, we consider a general stochastic optimization problem in which the
   objective function can be of any form, as long as we are able to compute its
   stochastic gradients. In particular, it could be the "classical stochastic
   optimization" problem $\min_x \\{ f(x) = \mathbb{E}_{\xi}[F(x, \xi)] \\}$ for
   which the recent lower bounds developed for parameter-free algorithms do
   apply. We mentioned the finite-sum case simply because it is an important
   example (but not the only one).

1. The **lower bounds we were discussing do make sense even for finite-sum problems**
   in the important situation when $n$ is very large ($n \to \infty$). In this
   case, the $O(n + \sqrt{n / \epsilon})$ bound you mentioned is of no use.

**Remark 2:**

We were simply providing an example of an important family of applied problems
which have bounded domain with known diameter. Essentially, the point was that,
instead of the commonly used additive regularization for model selection, one
may use the equivalent "ball regularization".

**Remark 3:**

1. Even when $\delta_f = \delta_g = 0$, some of our results are still new, e.g.,
   Th. 7 and 8. As we indicated in our previous reply, the adaptive
   accelerated SGD method with the $\sigma_*$-bound was considered an open
   question. **If you believe that Th. 8 and its proof containing the
   analysis of Alg. 2 are not new, could you please indicate the
   corresponding works with the same result?**

2. Regarding the addition of $\delta$ in the right-hand side of most
   inequalities, this is largely true. However, **this is not a drawback of our
   approach but instead a confirmation of its elegance**: we offer a
   reasonably simple analysis leading, in particular, to the state-of-the-art
   convergence rates for the Hölder-smooth problems. In contrast, the only other
   existing convergence analysis of AdaGrad methods for Hölder-smooth stochastic
   optimization problems from [RKWAC24] is completely different and more
   complicated: it does not use any $\delta$ and requires several rather
   technical lemmas to handle recurrent sequences involving the combination of
   several terms in different powers depending on $\nu$ (see Lemmas E.6-E.9 in
   their paper).
   
   Nevertheless, some care should be taken with "simply adding $\delta$ everywhere".
   One interesting example is Th. 8 which establishes the convergence rate of
   $O(\frac{L_f D^2}{k^2} + \frac{L_g D^2}{k} + k \delta_f + \delta_g + \frac{\sigma_* D}{\sqrt{k}})$.
   To get, from this result, the correct
   $
     O(\frac{H_f(\nu) D^{1 + \nu}}{k^{\frac{1 + 3 \nu}{2}}} +
     \frac{H_{\max}(\nu) D^{1 + \nu}}{(b k)^{\frac{1 + \nu}{2}}} +
     \frac{\sigma_* D}{\sqrt{k}})
   $
   convergence rate (Cor. 40), it is very important to allow $\delta_f$
   and $\delta_g$ (defined by our Asms. 1 and 6) be different. If we were
   not careful and treated them as the same $\delta$ everywhere, we would end up
   with the slower rate of
   $
     O(\frac{H_f(\nu) D^{1 + \nu}}{k^{\frac{1 + 3 \nu}{2}}} +
     \frac{H_{\max}(\nu) D^{1 + \nu}}{b^{\frac{1 + \nu}{2}} k^{\nu}} +
     \frac{\sigma_* D}{\sqrt{k}})
   $
   (where the second term does not even go to zero when $\nu = 0$).
   **One of the "nontrivial" insights of our work is the realization that such a
   separation is important.**

3. We did not consider AdaVRAG from [LNEN22] because its complexity is worse by
   an extra logarithmic factor.

   As we have already explained in our reply to Reviewer soXZ, **our UniFastSvrg
   algorithm is considerably simpler than AdaVRAE** and is based on the Method
   of Similar Triangles which is well-known in the optimization community.
   Consequently, its convergence analysis is much easier to follow: after
   applying the standard results on one triangle step (which is unrelated to
   SVRG methods at all), it only requires 3.5 pages to finish the proof for the
   accelerated SVRG (see Sec. A.4.2). Of course, we are not speaking here
   about "a general reader who is not familiar with the optimization literature"
   for whom any optimization paper would be very difficult.

   > Acutally, as far as I can see, once one puts $\delta$ in every R.H.S.
   > inequality in the proof of [LNEN22], I cannot see any obvious obstacles to
   > prevent their proof work

   With all due respect, it is impossible to verify such a claim without
   carefully checking every line of their 15+ page long proof.

**Remark [W2]:**

Thanks for the clarification. Note, however, that, for any point $u$, we have
$F(x_k) - F(u) \leq F(x_k) - F^*$. Thus, proving $F(x_k) - F(u) \leq \epsilon$
for any $u$ is exactly the same as proving $F(x_k) - F^* \leq \epsilon$.

**References:**

- [RKWAC24] A. Rodomanov, A. Kavis, Y. Wu, K. Antonakopoulos, V. Cevher.
  Universal Gradient Methods for Stochastic Convex Optimization. ICML, 2024.
Thanks for your reply. My comments are as follows:

**To Major remarks 1.** This response is not convincing.

1. I understand the setting you are considering. But as I stated and commented by the authors, it is undesirable since it may not be practical in many cases.

2.  The description of the lower bound is highly inaccurate. Note the recent lower bounds developed for parameter-free algorithms only apply to classical stochastic optimization. Instead, the current paper considers the finite-sum case. I remark that a key assumption in these lower bounds for general stochastic optimization is the finite variance condition. However, this condition is not usually assumed in the finite-sum case. Hence, the results mentioned by the authors don't make too much sense in the current setting. 

    As a simple example, one cannot apply the famous $O(1/\epsilon^2)$ lower bound in stochastic convex optimization to the finite sum case since the latter admits a well-known faster upper bound $O(n+\sqrt{n/\epsilon})$.


**To Major remarks 2.** Though theoretically speaking, the authors' discussion holds, I am confused about what the authors want to convey. The problem in the paper is to solve $P'_D$ in your notation. However, it seems like the authors want to tell me that grid search on $\lambda$ for $P\_\lambda$ is reasonable, which I think is unrelated to the paper. Could you elaborate more on this point?

**To Major remarks 3.** 

1. As I stated earlier, the telescoping sum appears easily under a bounded domain (see the inequality mentioned in the review) and one only needs to keep every $\delta$ in your notation simply on the R.H.S. of every inequality. If the authors think my statement is not accurate, could you please let me know at which step in the proof requires additional analysis on $\delta$? 

2. Moreover, I would like to clarify that I only said the algorithm and the analysis are not new. I kindly remind the authors that I also pointed out that extending Hölder smooth case is a strength. In other words, the key issue in my opinion is that the analysis doesn't bring any new insights and hence is a trivial combination.

3. The description is also inaccurate for [LNEN22] as it contains two algorithms: AdaVRAE and AdaVRAG. Moreover, whether the proof is difficult to check or not is a subjective view. I think for a general reader who is not familiar with the optimization literature, your paper and [LNEN22] are in the same difficulty when going through the proof. Acutally, as far as I can see, once one puts $\delta$ in every R.H.S. inequality in the proof of [LNEN22], I cannot see any obvious obstacles to prevent their proof work. If the authors think there are some barriers in their proofs, please explicitly write it down.

**To Minor remark [W2].** Note that one reason that people study optimization errors for the finite-sum case is to understand the excess risk of ML algorithms, which can always be decomposed as follows: $\mathbb{E}\_{S,A}[F(x(A))-F(x^*)]=\mathbb{E}\_{S,A}[F(x(A))-F\_S(x(A))]+\mathbb{E}_{S,A}[F\_S(x(A))-F\_S(x^*)]$ where $F(x)=\mathbb{E}\_{z\sim P}[f(x,z)]$, $P$ is an unknown distribution, $x^*\in\mathrm{argmin}F(x)$, $S$ is a set of independent samples of $z$, $F\_S(x)=\frac{1}{\|S\|}\sum\_{z\in S}f(x,z)$, and $x(A)$ is the output by an algorithm $A$. Note that $x^*$ may not be the optimal solution of $F_S(x)$. As such, a bound on the optimization error for any reference point $u$ is more useful than $F_S(x(A))-F\_S^*$ where $F\_S^*=\inf F\_S(x)$.
Dear Reviewer aWSb,

Please kindly note that we have already agreed to clarify several things and add
extra experiments as you suggested. It would therefore be unfair to say that we
are not "addressing constructive feedback from the reviewers".

Our discussion about the mini-batch size was a constructive reply to your
original criticism that our experiments "do not show the actual relationship
between oracle calls and optimization error" and that you "strongly dislike the
choice to treat one mini-batch gradient computation as a single oracle call
instead of $b$ calls". We have explained in detail that there is actually
nothing wrong with it and our viewpoint corresponds to parallel mini-batch
computations. This is a realistic computational model for which the optimal
mini-batch size is the number of available computing nodes.

We would also like to return to the following two major points of criticism from
your original review:

1. "In comparison to this work, Nguyen et al. [2] give results for
   (strongly-convex) SGD that depend only on the stochastic gradient variance at
   the minimizer and without any variance assumption."

2. "I'm somewhat disturbed that SVRG with Adagrad step-sizes doesn't converge
   exactly to a minimizer $x^*$ under your assumptions...  In comparison,
   standard SVRG, which does not require any variance bound
   (Allen-Zhu and Yuan, [1]), converges exactly."

As we have already clarified:

- We do **not** need any extra assumptions compared to (Nguyen et al., [2])
  and (Allen-Zhu and Yuan, [1]). Their smoothness assumption implies our
  Assumptions 1 and 6, and our results are **not** weaker.
- Under the same setting as in (Allen-Zhu and Yuan, [1]), our SVRG method
  **does** converge to a minimizer. There are no problems with $\delta_g$.

Could you please confirm if you agree with these statements and your concerns
are now resolved?
> Please note that we are actually discussing now the general question why $\sigma_*$-bounds are better than the corresponding $\sigma$-bounds for smooth stochastic optimization problems. 

Yes, but that's only because you have changed the direction of this conversation. The paper claims that "the assumption of uniformly bounded variance may not hold for some problems", but we seem to be in agreement that this claim is not really accurate for finite-sum functions under the bounded diameter assumption. 

> Although the resulting solution could potentially improve some absolute constants...

Yes, and the improved constants usually make quite a difference in the experiment results since they are large. 

---

To be frank, I don't appreciate that the authors are changing the goal posts so that valid criticism of their paper appears invalid. Moreover, I don't think that carefully litigating each of my comments/criticisms is a good use for the discussion period. I suggest the authors focus on improving their paper and addressing constructive feedback from the reviewers.
Dear Reviewer aWSb,

Thanks for the discussion.

> adding this type of statement would greatly improve your paper.

We agree and will add it.

> I would like to you provide an example ...

This is exactly the example we mentioned the last time, namely, the quadratic
function with the variance growing with $\\| x \\|$. In this case, $\sigma$
grows with the diameter $D$ and therefore may be arbitrarily large,
in contrast to $\sigma_*$ which may not grow with $D$ at all.

To be more precise, **here is one simple specific example**:
$f(x) = \mathbb{E}\_L[F(x, L)]$, where $L$ is the random variable uniformly
distributed on $[0, L_{\max}]$ and $F(x, L) = \frac{L}{2} \\| x \\|^2$.
We want to minimize this function over the ball of radius $R$ centered at the origin,
and use the standard oracle $g(x, L) = \nabla_x F(x, L) = L x$.
Denoting $\bar{L} = \mathbb{E}[L] = \frac{1}{2} L_{\max}$ and
$L_V^2 = \mathbb{E}[(L - \bar{L})^2] = \frac{1}{12} L_{\max}^2$,
we get $f(x) = \frac{\bar{L}}{2} \\| x \\|^2$, and the variance is
$\sigma^2(x) = \mathbb{E}\_L[\\| g(x, L) - \nabla f(x) \\|^2] = L_V^2 \\| x \\|^2$.
Its maximal value over the feasible set is then
$\sigma = \max \\{ \sigma(x) : \\| x \\| \leq R \\} = L_V R$, while
$\sigma_* = \sigma(x^*) = 0$. For this example, our Asm. 1 is satisfied
with $L_f = \bar{L}$, $\delta_f = 0$, while Asm. 6 is satisfied with
$L_g = L_{\max}$, $\delta_g = 0$. The "classical" convergence rate (Th. 4) is thus
$
  O(\frac{L_f R^2}{k} + \frac{\sigma R}{\sqrt{k}})
  = O(\frac{\bar{L} R^2}{k} + \frac{L_V R^2}{\sqrt{k}})
  = O(\frac{L_{\max} R^2}{\sqrt{k}})
$.
In contrast, the $\sigma_*$-rate (Th. 7) is
$
  O(\frac{(L_f + L_g) R^2}{k} + \frac{\sigma_* R}{\sqrt{k}})
  = O(\frac{L_{\max} R^2}{k})
$,
which is much faster.

Please note that we are actually discussing now the general question why
$\sigma_*$-bounds are better than the corresponding $\sigma$-bounds for
smooth stochastic optimization problems. This question has already been
addressed in many previous works and is not directly related to the specific
adaptive methods we propose. The only important detail is that our "new"
Asm. 6 indeed covers smooth stochastic optimization problems.

> Please see Gower et al. (1) ...

Thanks for the references. We do not mind adding extra experiments with another
way of counting mini-batch computations (as you suggested in the first post) and
will do that in the revised version.

Note, however, that, from the theoretical point of view, the "optimal"
mini-batch size suggested in [Gower et al., 1] does not give any nontrivial
results: it is always comparable to either $b = 1$ or $b = n$. Indeed,
consider, the finite-sum minimization of $f(x) = \frac{1}{n} \sum_{i = 1}^n f_i(x)$
with $L$-smooth components $f_i$ and assume that
$\frac{1}{n} \sum_{i = 1}^n \\| \nabla f_i(x) - \nabla f(x) \\|^2 \leq \sigma^2$
for any $x$. One of the standard examples considered in [Gower et al., 1]
is the so-called $b$-nice sampling meaning that the oracle uses mini-batching
$g_b(x, \xi) = \frac{1}{b} \sum_{j = 1}^b \nabla f_{\xi_j}(x)$ with indices $\xi_j$
chosen uniformly at random from $\\{ 1, \ldots, n \\}$ without replacement.
The variance of such an oracle is $\sigma_b^2 = \frac{n - b}{n - 1} \frac{\sigma^2}{b}$,
so SGD needs
$
  N_b
  = O(\frac{L D^2}{\epsilon} + \frac{\sigma_b^2 D^2}{\epsilon^2})
  = O(\frac{L D^2}{\epsilon} + \frac{n - b}{n} \frac{\sigma^2 D^2}{b \epsilon^2})
$
oracle calls to reach accuracy $\epsilon$. The total SFO complexity is then
$b N_b = O(\frac{b L D^2}{\epsilon} + \frac{n - b}{n} \frac{\sigma^2 D^2}{\epsilon^2})$,
which is exactly the same expression as we wrote in our previous reply, up to
the factor $\frac{n - b}{n}$ which comes because we now use sampling
*without replacement*. As we can see, the resulting expression is a linear
function of $b$, so its minimum value is attained at one of the boundary points:
either $b = 1$ (if $n \geq \frac{\sigma^2}{L \epsilon}$) or $b = n$ (otherwise).
The "optimal" $b$ in [Gower et al., 1] appears to be more complicated simply because
they first rewrite
$b N_b = O(\max\\{\frac{b L D^2}{\epsilon}, \frac{n - b}{n} \frac{\sigma^2 D^2}{\epsilon^2}\\})$
and then minimize the maximum by solving
$\frac{b L D^2}{\epsilon} = \frac{n - b}{n} \frac{\sigma^2 D^2}{\epsilon^2}$.
Although the resulting solution could potentially improve some *absolute* constants,
it will still result in the same SFO complexity of
$O(\min\\{ \frac{L D^2}{\epsilon} + \frac{\sigma^2 D^2}{\epsilon^2}, \frac{n L D^2}{\epsilon} \\})$
as the naive approach selecting either $b = 1$ or $b = n$.

> By [2], I was referring to the work by Nguyen et al. ... Their variance assumption ...

Indeed, they work with the variance at the minimizer. However, our objection
was that there are no other results in the literature showing that AdaGrad does
adapt to the variance at the minimizer for convex finite-sum problems. Note that
the work of Nguyen et al. studies only **non-adaptive** methods.
Thanks for your response.

> 1. It seems there is a certain misunderstanding of Ass. 6, which we hope to clarify.

What misunderstanding? Did I say something in my review which indicated I didn't understand Assumption 6? I just want you to give a concrete example in the paper. 

> 2.  First, let us stress that Thm. 10 covers the standard setting of finite-sum problems with $L$-smooth components.

Does it say this somewhere in the manuscript? I appreciate your general presentation, but it's quite typical to include corollaries showcasing how the theorems behave in simplified settings. I think adding this type of statement would greatly improve your paper. 

> 4. Asm. 3 may be violated for this case (consider the quadratic function on the entire space) 

Don't you assume a finite diameter $D$ in your analysis? In this case, I think finite-sum quadratics should be fine for Assumption 3, right? I would like to you provide an example of a function *in your setting* which satisfies Assumption 6, but doesn't satisfy Assumption 3. Note that I'm not particularly concerned about assuming $D$ is finite (unlike some of the other reviewers), but you shouldn't assume finite $D$ and then make comparisons on the full space. 

Moreover, since you assert $\sigma^2$ may be very big for finite $D$, can you provide a comparison between $\sigma^2$ and $\delta_g, L_g$? 

> 5. [Asm. 6 vs 9] ... which we do not know how to do at the moment

That's unfortunate. I don't have a lot of insight into this problem, but it does seem strange to need both assumptions. 

> 6. [Experiments] Regarding the mini-batch size, we are not sure if you are correct.

There are quite a few papers on this subject which support my comments. Please see Gower et al. (1) and Kento et al. (2). I don't particularly like the second paper, but it get's the point across. 

> 7. Please note that [2] considers another variance assumption...

Sorry, it looks like I missed including the additional references for my review. I've edited the review to add them now. By [2], I was referring to the work by Nguyen et al., which is [2] in my list. Their variance assumption is what I would consider to be "variance at the minimum". Of course you will not agree that your contributions are fairly niche, but that is my opinion. 

[1] Gower, Robert Mansel, et al. "SGD: General analysis and improved rates." International conference on machine learning. PMLR, 2019.

[2] Imaizumi, Kento, and Hideaki Iiduka. "Iteration and stochastic first-order oracle complexities of stochastic gradient descent using constant and decaying learning rates." Optimization (2024): 1-24.