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

Thanks for your time and efforts spent on reviewing this manuscript. We appreciate the feedback and would like to make some comments on the points you raised in your review.

• [W1]: We agree that this is a drawback and it was explicitly written in the paper. Note, however, that $D$ is indeed the only parameter that the methods need to know. This is the price one pays for getting completely universal methods, automatically adapting to a large variety of other parameters (degree of smoothness $\nu$ and the corresponding smoothness constant $H_{\nu}$, oracle's variance $\sigma$, variance at the minimizer $\sigma_*$, oracle's inexactness $\delta$, etc.), while enjoying the optimal worst-case complexity estimates, typical for non-adaptive methods. We are not aware of any other algorithms with similar properties, especially, working in such a large number of situations and with such a unified treatment as in our work (basic methods and accelerated ones, with variance reduction and without it, etc.).

  While we do agree that it would be very nice to have completely parameter-free algorithms, it seems that this goal may not be achievable for stochastic optimization problems, at least not without additional, somewhat restrictive, assumptions. Please refer to our detailed reply to Reviewer PtE8.

• [W2]: Thank you for the comment. We agree that it would be better to provide more explanations and intuitions. However, we are rather limited by the page limit and therefore must think twice if we want to add anything extra. Could you please clarify where exactly you would like us to elaborate, except better emphasizing the novelty and the challenge?

• [W3]: Note that our paper is mostly theoretical, and we do not attempt to be exhaustive with experiments. But we will take your point into account and add more experiments in the revised version of the paper.

• [W4]: Yes, of course. Our oracle $\hat{g}$ is assumed to be an unbiased estimate of $\bar{g}$, which is itself only an approximation to the true gradient $\nabla f$. Thus, $\hat{g}$ is, in general, a biased estimate of $\nabla f$: $\mathbb{E}\_{\xi}[\hat{g}(x, \xi)] = \bar{g}(x) \neq \nabla f(x)$. Some particular examples where we have biased gradients are mentioned in lines 114-122 and also in lines 186-194. For instance, if we work with finite-sum problems, $f(x) = \frac{1}{n} \sum_{i = 1}^n f_i(x)$, where each function $f_i$ represents another nontrivial optimization problem with a strongly convex objective, $f_i(x) = \max_{u_i} \Psi_i(x, u_i)$, whose solution $\bar{u}\_i(x)$ can be found with accuracy $\delta$, then the natural stochastic gradient $\hat{g}(x, \xi) = \nabla_x \Psi_{\xi}(x, \bar{u}_{\xi}(x))$ (with uniformly chosen index $\xi$) is a biased estimate of $\nabla f(x)$, and $\delta_f = \delta$.

We hope we were able to address all your concerns and kindly ask you to increase your score.

Thanks for the positive evaluation!

Major remarks

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

   Basically, Ass. 6 is satisfied for finite-sum problems with (Hölder) smooth components (see also lines 186-194 in the paper for a more general example).

   The motivation is as follows. Ass. 6 is the generalization of $\mathbb{E}\_{\xi}[\\| g(x, \xi) - g(y, \xi) \\|^2] \leq 2 L \beta(x, y)$, where $\beta(x, y) = f(y) - f(x) - \langle \nabla f(x), y - x \rangle$, for which the main example is the finite-sum objective $f(x) = \frac{1}{n} \sum_{i = 1}^n f_i(x)$ with the usual stochastic oracle $g(x, \xi) = \nabla f_{\xi}(x)$ (for a uniformly chosen index $\xi$) and $L$-smooth components $f_i$. To generalize it to the case when $f_i$ are $(\nu, H)$-Hölder smooth, we need to add $\delta$: $\mathbb{E}\_{\xi}[\\| g(x, \xi) - g(y, \xi) \\|^2] \leq 2 L [\beta(x, y) + \delta]$; then, we can take an arbitrary $\delta > 0$ and let $L = [\frac{1 - \nu}{2 (1 + \nu) \delta}]^{\frac{1 - \nu}{1 + \nu}} H^{\frac{2}{1 + \nu}}$. This is almost our Ass. 6 except that we have the second moment instead of the variance $\mathbb{E}\_{\xi}[\\| [g(x, \xi) - g(y, \xi)] - [\nabla f(x) - \nabla f(y)] \\|^2]$ in the left-hand side (for simplicity, we ignore the possibility of using inexact gradients $\bar{g}$ and function values $\bar{f}$). Using the variance is better because it is always smaller than the second moment and can easily be reduced with mini-batching.

2. There is no problem with $\delta_g$ in Thm. 10. First, let us stress that Thm. 10 covers the standard setting of finite-sum problems with $L$-smooth components. In this case, $L_f = L_g = L$, $\delta_f = \delta_g = 0$, and we recover the classical result from (Allen-Zhu and Yuan, [1]), without any extra assumptions.

   However, it is important that our method is actually more powerful and converges in other regimes as well, e.g., for finite-sum problems with Hölder-smooth components. Indeed, as discussed before, for such problems, $\delta_g$ can be an arbitrary (potentially very small) positive number (and so can be $\delta_f$, see lines 116-117 in the paper). Choosing $\delta_f$ and $\delta_g$ carefully (by optimizing the rate from Thm. 10 while taking into account the fact that $L_f$ and $L_g$ also depend on these constants), we get the following convergence rate: $F_t \lesssim \frac{H D^{1 + \nu}}{(2^t)^{\frac{1 + \nu}{2}}}$ which goes to zero as $t \to \infty$. For more details, see Cor. 41.

3. The previous example shows that $\delta_f$ does not only measure the error between $\bar{g}$ and $\nabla f$ but is also related to the smoothness properties of the objective: even when $\bar{g} = \nabla f$, it is still meaningful to allow for $\delta_f > 0$ (e.g., to handle Hölder-smooth problems).

4. [Ass. 3 vs 6] Indeed, Ass. 6 is weaker than 3 because we can choose any $\delta_g > 0$ and let $L_g \sim \frac{\sigma^2}{\delta_g}$. Then, Thms. 4 and 5 become simple corollaries of Thms. 7 and 8. On the other hand, as already discussed above, Asm. 6 is satisfied for finite-sum problems with smooth components and the standard oracle, while Asm. 3 may be violated for this case (consider the quadratic function on the entire space); even if one defines $\sigma$ in Asm. 3 by looking only at $x$ from the feasible set, $\sigma$ will depend on the diameter of this set and may be potentially very big. We will add the corresponding comments.

5. [Asm. 6 vs 9] When we use exact gradients, $\bar{g} = \nabla f$, both are equivalent; otherwise, one does not seem to imply the other. For some reason, the current proof of Thm. 10 needs Asm. 9 at one place, namely, in lines 693-694, to get the Bregman distance term in Lem. 28, which can then be bounded via the function residual using Lem. 29. To remove Asm. 9, we would need to obtain a counterpart of Lem. 29 in terms of the approximate Bregman distance instead of the exact one, which we do not know how to do at the moment. We will clarify this.

6. [Experiments] We will take your point into account and add more experiments.

   Regarding the mini-batch size, we are not sure if you are correct. Consider, e.g., SGD with mini-batch size $b$ as applied to minimizing an $L$-smooth convex function. To reach accuracy $\epsilon$, it needs $N_b = \frac{L D^2}{\epsilon} + \frac{\sigma^2 D^2}{b \epsilon^2}$ oracle calls, each such a call requires $b$ stochastic gradients. If the computation is sequential, the total SFO complexity is then $b N_b = \frac{b L D^2}{\epsilon} + \frac{\sigma^2 D^2}{\epsilon^2}$, which is minimized for $b = 1$. To our knowledge, mini-batching is provably efficient only when we allow for parallel computations of stochastic gradients; then, the complexity becomes $N_b$ which indeed decreases with $b$ (however, $b$ cannot exceed the limits of our parallelism, e.g., the number of computing nodes). See also Sec. 6 in [54] for a similar point of view.

7. [W1] Please note that [2] considers another variance assumption, namely, $\\| g(x, \xi) - \nabla f(x) \\|^2 \leq \sigma_0^2 + \sigma_1^2 \\| \nabla f(x) \\|^2$, which is completely different from ours and is not guaranteed to be satisfied (with good constants) even for finite-sum problems with smooth components. Our assumption is actually much weaker and have never been explored in the literature on AdaGrad. Furthermore, for the accelerated method with AdaGrad step sizes, nothing has been known except for the classical case when the variance is uniformly bounded. We therefore kindly disagree that our contributions are "fairly niche" / straightforward, including also the uniform extension of everything to Hölder-smooth problems.

Minor remarks

Unfortunately, we do not have enough space to answer every remark but we will consider all of them and make the appropriate modifications.

Conclusion

We hope we could answer your questions, and kindly ask you to consider increasing your score to support our work.

Thank you for the positive evaluation of our work. Below you can find the answers to your questions / comments.

The prior knowledge is also not required in UniXGrad[28] and AcceleGrad[32]. What is the difference between them and the proposed algorithm?

From the algorithmic perspective, all the three methods (UniXGrad, AcceleGrad and our UniFastSgd) are different versions of Nesterov's accelerated gradient method. Our UniFastSgd is one of the standard versions known as the Method of Similar Triangles (see Section 6.1.3 in [44] and [31]). The name stems from the fact that the next point $x_{k + 1}$ is defined in such a way that the triangles $(x_k, v_k, v_{k + 1})$ and $(x_k, y_k, x_{k + 1})$ are similar (see the picture on page 1 in the PDF attached to the main rebuttal). In contrast, UniXGrad and AcceleGrad choose $x_{k + 1}$ as the result of the (projected) gradient step from $y_k$, which results in a slightly more complicated iteration with no guarantee of similar triangles.

From the theoretical perspective, the convergence rate guarantees for UniXGrad and AcceleGrad were proved only under the uniformly bounded variance and for functions with either bounded gradients or Lipschitz continuous gradients. In other words, it is not known whether UniXGrad and AcceleGrad can provably adapt to the more general assumptions from our paper (such as Hölder smoothness, variance at the minimizer, etc.). It might be possible to extend our techniques to those methods as well, but we have not investigated this direction as we personally find the Method of Similar Triangles more elegant and simpler to work with.

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.

Thank you for the suggestion. We agree and will elaborate on this in the revised version of the manuscript. Here are some of the reasons why our method is simpler and more elegant than the AdaVRAE algorithm from [34]:

1. Each epoch of our algorithm is essentially the standard Method of Similar Triangles with the only difference that one of the vertices ($\tilde{x}$) is fixed during the epoch (we mention this in lines 240-244; see also the picture on page 2 in the PDF attached to the main rebuttal). As a result, its geometry is much easier to understand than that of AdaVRAE, and we can readily apply the classical results for each Triangle Step (such as Lemma 24) without proving everything "from scratch".
2. Our algorithm uses a simple recurrent formula for the sequence $A_t$, namely, $A_{t + 1} = A_t + \sqrt{A_t}$, which can be easily analyzed using standard techniques (Lemma 32). In contrast, AdaVRAE uses quite complicated ad-hoc formulas which are impossible to even write on a single line.

We hope we could answer your questions, and kindly ask you to consider increasing your score to support our work.

Thanks for your time and efforts spent on reviewing this manuscript. We appreciate the feedback and would like to make some comments on the points you raised in your review.

Major remarks

1. Our assumption on the bounded feasible set is satisfied whenever one knows some upper bound $R$ on the distance $\\| x_0 - x^* \\|$ from the initial point to the solution. In this case, we can easily transform our initial problem into the one with the bounded feasible set of diameter $D = 2 R$ by adding the additional simple ball constraint $\\| x - x_0 \\| \leq R$. This is essentially the setting we consider.

   We agree that it would be highly desirable to develop a completely parameter-free method for stochastic optimization, which would not require the knowledge of any problem-dependent parameters and would automatically and efficiently adapt to all of them. However, according to the several recent works (see [CH24,AK24,KJ24]), this seems too much to ask for. In contrast to the standard deterministic optimization, where one can compute exact function values and use line-search techniques by paying only an additive logarithmic term for not knowing the parameters of the problem, for stochastic optimization, one really needs some nontrivial knowledge of either the distance to the solution $R$, or the smoothness constant / oracle's variance, etc. Without this, the method would not be able to achieve a nearly optimal complexity.

   In other words, without assuming the knowledge of $R$, we would need to impose other restrictive assumptions such as the knowledge of the Lipschitz constant and/or oracle's variance. But then the algorithm will be tailored a particular function class and will not be as universal as our methods (working simultaneously for each Hölder class and different variance assumptions). Therefore, it is quite debatable which assumption is actually better.

2. Note that problems with bounded domains arise quite commonly in machine learning problems. In fact, any $\ell_2$-regularized convex problem $\min_x [f(x) + \frac{\lambda}{2} \\| x \\|^2]$ ($P_{\lambda}$) (e.g., logistic regression) is equivalent to $\min_x \\{ f(x) : \\| x \\| \leq D \\}$ ($P'\_D$) for a certain $D$, so that there is a one-to-one correspondence between them. In practice, one usually selects the right regularization coefficient $\lambda$ by using the grid search, i.e., solving $(P\_{\lambda})$ for multiple values of $\lambda$ and checking the quality of the resulting solution $x_{\lambda}$. But this is exactly the same as doing the grid search over $D$, solving $(P'\_D)$ and checking the quality of the corresponding solution $x'\_D$. For an additional discussion of bounded domains, see also Ch. 5 in [SNW11] and p. 125 in particular.

3. We kindly disagree with your assessment that, under Assumption 2, our paper is just a trivial combination of different existing results. Consider, for example, the following two particular cases of (only a part of) our results:

   • Adaptive accelerated SGD for smooth problems with the bound via $\sigma_*$ (Theorem 8 for $\delta_f = \delta_{\hat{g}} = 0$).
   • Adaptive accelerated SVRG method for functions with Hölder-smooth components (last row in Table 2 or Corollary 42).

   In our opinion, both results are quite nontrivial:

   1. The first (nonadaptive) accelerated method with the bound via $\sigma_*$ was suggested only recently, in [WS21]; the adaptive method was mentioned there as an open question. The algorithm was later revisited and improved in [IJLL23] (by properly separating the smoothness constants), however, the method was still non-adaptive.

   2. We are aware of only one adaptive accelerated SVRG method, namely, AdaVRAE from [LNEN22], which was proven to work only for functions with Lipschitz gradient. However, as we explained in our reply to Reviewer soXZ, that algorithm and the corresponding proofs are rather complicated and it is extremely difficult to check if the method provably works for the more general class of Hölder-smooth problems.

   Could you please be more specific and explain in detail why you believe that the above two results are not particularly new and easily follow from the existing results in the literature (assuming our Assumption 2 holds)? Please provide some references.

References:

• [CH24] Y. Carmon, O. Hinder. The Price of Adaptivity in Stochastic Convex Optimization. arXiv:2402.10898, 2024.
• [AK24] A. Attia, T. Koren. How Free is Parameter-Free Stochastic Optimization? ICML, 2024.
• [KJ24] A. Khaled, C. Jin. Tuning-Free Stochastic Optimization. ICML, 2024.
• [WS21] B. Woodworth, N. Srebro. An Even More Optimal Stochastic Optimization Algorithm: Minibatching and Interpolation Learning. NeurIPS, 2021.
• [LNEN22] Z. Liu, T. Nguyen, A. Ene, H. Nguyen. Adaptive Accelerated (Extra-)Gradient Methods with Variance Reduction. ICML, 2022.
• [IJLL23] S. Ilandarideva, A. Juditsky, G. Lan, T. Li. Accelerated stochastic approximation with state-dependent noise. arXiv:2307.01497, 2023.
• [SNW11] S. Sra, S. Nowozin, S. Wright. Optimization for Machine Learning. MIT Press, 2011.

Minor remarks

• [W2] ($F(u)$ instead of $F^*$): Yes, this is indeed true, but we do not see how this could be useful for improving our results. We would appreciate it if you could elaborate.
• [W3] (confidence interval): Thank you, we will add it.

Conclusion

We hope we were able to address your concerns and kindly ask you to reconsider your score.

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.