- Rating
- 3
- Confidence
- 4
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
In this paper, the authors provide a comprehensive analysis of AdaGrad under various settings. More specifically, they first establish negative results for last-iterate convergence (Theorem 3.1, under sub-Gaussian noise), high-probability convergence guarantees (Theorem 3.2), and lower bounds for the averaged iterate under different stochastic settings (Theorems 3.3 and 3.4). In addition, the authors derive upper bounds on the convergence of AdaGrad-Norm/AdaGrad (Theorem 3.5).
Critical strengths
I find the results of this paper extremely valuable, particularly the negative results for AdaGrad. First, some of these results appear to be novel. For instance, I am not aware of any results in the existing literature analogous to Theorem 3.1, which concerns the last-iterate convergence of AdaGrad in the stochastic case. Moreover, the result for sub-Gaussian noise in Theorem 3.4 complements the existing literature (e.g., [1], which establishes high-probability convergence guarantees for the averaged iterate).
Second, I would also like to highlight the proofs themselves, as the techniques developed in this paper may be useful for the future analysis of other adaptive methods, both in the context of high-probability and last-iterate convergence. In particular, I would like to highlight Theorem 3.1: the idea of using rare signals to push the iterate away from the neighborhood of the optimum is especially interesting.
Critical weaknesses
In my view, the only weakness of the paper is Theorem 3.5, which, as the authors themselves emphasize, extends existing results. Interestingly, the authors cannot actually obtain a stronger result than Theorem 3.5: extending the analysis to high-probability guarantees is limited by Theorem 3.2, while attempting to remove the bounded-iterates assumption runs into the lower bound established in Theorem 3.3. Nevertheless, it seems that more informative guarantees would be upper bounds that match at least the lower bounds in Theorems 3.2 and 3.3 (for Theorem 3.4, a corresponding high-probability convergence result already exists in [1]).
References
[1] Liu et al. (2023). High Probability Convergence of Stochastic Gradient Methods
Questions for authors
- Is it possible to establish matching upper bounds for Theorems 3.2 and 3.3?
3 comments
Response to the Authors
Dear Authors,
Thank you for your response and the additional clarifications. Based on your comments and your replies to the other reviewers, I have no further questions and am happy to maintain my positive assessment of the paper.
Best regards,
Reviewer
Thank you for your positive assessment. We sincerely appreciate the time and effort you have devoted to this discussion.
Thank you for your assessment. We agree that matching upper bounds would sharpen the characterization, and have clarified both the role of Theorem 3.5 and the remaining gaps. All newly added or revised text in the manuscript is highlighted in blue.
Theorem 3.5 provides the positive counterpart to the lower bounds: under bounded iterates, classical regret analysis yields explicit noise-adaptive expected average-error guarantees for both normalizations under the conditional ABC model, including O(T−1) when C=0.
Sections 1.2 and 3.5 now identify its contribution as this extension and its explicit constants. The paper’s principal new conclusions are the lower bounds, particularly Theorem 3.1, which excludes every prescribed vanishing expected last-iterate rate under the stated conditional-oracle assumptions. The ABC result explains why these last-iterate and confidence limitations can coexist with favorable expected average-error guarantees.
We have not established matching upper bounds for these two theorems. The revised discussion distinguishes the available guarantee from the unresolved sharp characterization.
For Theorem 3.2, Theorem 3.5 and Markov’s inequality give, under bounded variance and bounded iterates, a bound of orderO(δT1+δTσ)with probability at least 1−δ. Remark 3.5 and Eq. (6) state this guarantee. This bound does not contradict Theorem 3.2, which excludes polynomial decay in T combined with polylogarithmic dependence on 1/δ. Determining the optimal polynomial dependence on 1/δ while retaining the stated rate in T remains an open question.
For Theorem 3.3, the constant lower bound rules out vanishing uniform worst-case expected error. A matching constant upper bound without trajectory control requires further analysis; the lower bound alone does not establish it. Remark 3.12 now states this gap explicitly.
We hope these clarifications address your concerns. We would welcome any further questions or discussion.