- Rating
- 2
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper considers stochastic nonsmooth convex optimization without assuming uniformly bounded gradients. The authors introduce a generalized Lipschitz condition where the gradient norm may grow with the optimality gap. The main result gives a convergence guarantee for a clipped AdamW-type method with exponential averaging. Unlike the SGD and AdaGrad-Norm variants studied in the paper, its rate avoids an exponential dependence on the gradient-growth parameter. The paper also provides lower bounds for these baselines and extends the analysis to generalized smoothness and quasar-convex problems. The work is entirely theoretical and does not include experiments. I found the theoretical results interesting and technically solid, but the lack of empirical validation makes it difficult to assess whether the proposed assumptions and the suggested explanation for AdamW are relevant to practical ML training.
Critical strengths
-
The paper gives a nontrivial separation under stochastic generalized Lipschitzness. Clipped AdamW removes the exponential dependence on that appears for SGD and AdaGrad-Norm.
-
The analysis of exponential decay is interesting. The argument uses stability of the iterates to obtain the improved convergence bound.
Critical weaknesses
-
The connection to practical deep learning is still limited. Most of the theory is for convex objectives, and the nonconvex extension only covers quasar-convex functions. The paper also has no experiments showing that Assumption 2 is a reasonable model for stochastic gradients in neural network training. Since AdamW is a major motivation of the paper, this makes the practical interpretation less convincing.
-
The algorithms work with a known radius such that , and several methods use projections onto . The main parameter choices also depend on quantities such as , , and the target accuracy. This makes the theoretical guarantees harder to connect to how AdamW is typically used in practice.
-
It is not clear that exponential decay itself is necessary for the improvement. Algorithm 2 gets a much better rate than the simple-averaging variant, but there is no lower bound for Algorithm 1. So the current results do not fully rule out the possibility that the gap comes from the analysis rather than from simple averaging itself.
-
The SGD/AdaGrad comparison is somewhat narrower than the paper’s wording suggests. The lower bounds are proved for specific SGD and AdaGrad-Norm variants. They do not exclude the possibility that other step-size schedules or adaptive variants could avoid the same exponential dependence.
Questions for authors
-
Can the authors give a concrete ML example where Assumption 2 is satisfied, or at least approximately observed in practice? This would help clarify how relevant the proposed setting is to actual AdamW training.
-
Is the gap between Algorithm 1 and Algorithm 2 inherent? In particular, is there any lower bound for the simple-averaging scheme, or could its worse rate be an artifact of the current analysis?
-
How essential are the assumptions that , , , and the target accuracy are known? Is there a practical way to choose the parameters without this information?
-
The nonconvex extension is limited to quasar-convex functions. Do the authors see a path toward a more general nonconvex setting, or is the current analysis fundamentally tied to this structure?
-
The paper does not include experiments. Could the authors provide an evaluation on a standard real-data ML task, comparing the analyzed AdamW-type method with SGD and AdaGrad-Norm? This would help assess whether the theoretical advantage is reflected in a realistic training setting.
-
Could the authors revise the bibliography and update references that currently cite older arXiv versions despite having published conference or journal versions? There also appear to be a few bibliographic inaccuracies, for example in the Nesterov and Polyak entries.
6 comments
The paper does not include experiments. Could the authors provide an evaluation on a standard real-data ML task, comparing the analyzed AdamW-type method with SGD and AdaGrad-Norm? This would help assess whether the theoretical advantage is reflected in a realistic training setting.
We do not plan to include experiments in our paper. Our theoretical separation of Algorithm 2 from Algorithm 1, constant-stepsize SGD and AdaGrad-Norm is a genuine mathematical result, supported by rigorous upper and lower complexity bounds, and does not require any experimental verification.
Besides, once again, we believe that this criticism does not adequately reflect the main contribution of our paper. Our goal is to find an adequate theoretical explanation for existing practical phenomena. The practical phenomena are confirmed by a decade of practice: AdamW with exponential averaging has found a much wider adoption compared to AdaGrad with uniform averaging; SGD with constant stepsizes is often outperformed by SGD with scheduled stepsizes. We do not need to run yet another benchmark to confirm these. Our explanation is adequate, because it is rigorous, mathematically correct, based on adequate and well-established assumptions, and aligns with the practical phenomena.
The request to run experiments specifically with the analyzed method treats the parameter choices in Theorems 6/7 as if they are claimed to give the best performance in real-world ML tasks. We do not consider this an appropriate criterion for evaluating our paper, as we never make such claims. In fact, we have ongoing research results under relaxations of both convexity and generalized Lipschitzness assumptions, suggesting that optimal and practical relations between these parameters may be different. However, the new results explicitly depend on the foundations laid in this paper, and the new results do not invalidate this paper but rather extend and complement it.
Could the authors revise the bibliography and update references that currently cite older arXiv versions despite having published conference or journal versions? There also appear to be a few bibliographic inaccuracies, for example in the Nesterov and Polyak entries.
We cited those paper versions that we personally examined. The published versions may differ from the preprints. We may update these references upon examination. The two typos in (Nesterov, 2018; Polyak, 1990) will be fixed in the revised version of our paper.
The SGD/AdaGrad comparison is somewhat narrower than the paper’s wording suggests. The lower bounds are proved for specific SGD and AdaGrad-Norm variants. They do not exclude the possibility that other step-size schedules or adaptive variants could avoid the same exponential dependence.
Our lower bounds apply to the exact AdaGrad-Norm method from the original paper (Streeter and McMahan, 2010) with an arbitrary choice of the stepsize . We also explicitly state in the paper in several places that we consider constant-stepsize SGD.
Dear Authors,
Thank you for the detailed responses. I appreciate the theoretical clarifications, particularly the proposed lower bound for Algorithm 1, which appears convincing.
However, I am maintaining my score of 2. My main concern remains the gap between the theoretical results and their claimed explanation of AdamW's practical advantages. The cited empirical evidence does not establish Assumption 2, and the guarantees concern a specialized scalar clipped method under restrictive structural assumptions.
Moreover, the paper has not yet been updated to incorporate the promised theoretical results and clarifications, particularly the lower bound for Algorithm 1. Therefore, these contributions cannot yet be fully assessed.
I acknowledge the theoretical value of the work, but the remaining concerns prevent me from raising my score.
Best regards,
Reviewer jAPW
Thank you for your time and effort.
Our theoretical results are not tied to Assumption 2: they are also valid under the (L0,L1)-smoothness assumption (or its stochastic variants), which is well-established in literature (lines 460-467). For Assumptions 1/2, there is also evidence in existing literature that they may be observed in practice. For instance, Figure 1 in [a] shows an approximately affine dependence between gradient norm and training loss.
[a] On the Role of Batch Size in Stochastic Conditional Gradient Methods. Rustem Islamov, Roman Machacek, Aurelien Lucchi, Tony Silveti-Falls, Eduard Gorbunov, Volkan Cevher Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:49997-50023, 2026.
This is not an artifact of the current analysis. The counterexample in Theorem 9, Case II, applies to Algorithm 1 and implies an exponential lower bound for Algorithm 1, just like for AdaGrad-Norm. Thus, the separation between Algorithms 1 and 2 is genuine. More details are in our response to Reviewer uJC5.
The parameters G0,G1,ϵ are not necessary for implementing Algorithm 2. Algorithm 2 only uses discounting factor α and effective stepsize η=αR, which can be determined by hyperparameter tuning, just like with most other existing theoretical analyses in literature. Besides, we do not understand why our paper is treated as if we propose some practical ways to tune parameters of AdamW. The main purpose and contribution of our paper is completely different: we take adequate and well-established assumptions in the literature and develop an analysis that significantly improves our understanding of AdamW and establishes its sharp separation from several other first-order methods. Our contribution is fundamental rather than proposing yet another clone/modification of AdamW.
Analysis in the general non-convex setting without any additional structure would not make any sense for the purposes of this paper: it is provably impossible to obtain any meaningful guarantees about convergence of any first-order algorithm to a global solution. The extension of our results to other non-convex settings with additional structure beyond quasar-convexity is possible: it is part of our ongoing research and will be presented in future work. In addition, there is empirical evidence that (quasar-)convexity itself is an adequate assumption as it can hold on average along optimization trajectories [b,c].
[b] Yi Zhou, Junjie Yang, Huishuai Zhang, Yingbin Liang, Vahid Tarokh. SGD Converges to Global Minimum in Deep Learning via Star-Convex Path. International Conference on Learning Representations (ICLR), 2019.
[c] Tran, Hoang, Qinzi Zhang, and Ashok Cutkosky. "Reevaluating theoretical analysis methods for optimization in deep learning." arXiv preprint arXiv:2407.01825 (2024).