acceptodds
Under review as a conference paper at ICLR 2027

Stochastic Non-Smooth Convex Optimization with Unbounded Gradients

Abstract

Much of the existing theory on first-order non-smooth optimization is built on a restrictive assumption that the gradients of the objective function are uniformly bounded. We introduce a much more realistic class of generalized Lipschitz functions, where the gradient norms are bounded by an affine function of the optimality gap. We then ask a natural question: what algorithm achieves the best global convergence rates for solving convex stochastic generalized Lipschitz optimization problems? To address this, we develop a new convergence analysis for several existing algorithms and find that AdamW with clipped updates, provably outperforms other popular stochastic optimization methods, such as SGD and AdaGrad. Moreover, our analysis establishes the critical role of AdamW's exponentially weighted gradient accumulation, as opposed to simple averaging. We further show that clipped AdamW is universal and achieves improved rates under the popular generalized smoothness assumption, analyze the convergence of clipped AdamW with diagonal and matrix preconditioners, and extend our results to the quasar-convex setting.

Primary area:
optimization
Keywords:
optimization theory, convex optimization, adaptive optimization, stochastic optimization

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_jAPWOpenReview ↗
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 RG1RG_1 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 RR such that x⋆∈QRx^\star \in Q_R, and several methods use projections onto QRQ_R. The main parameter choices also depend on quantities such as G0G_0, G1G_1, 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
  1. 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.

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

  3. How essential are the assumptions that RR, G0G_0, G1G_1, and the target accuracy are known? Is there a practical way to choose the parameters without this information?

  4. 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?

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

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

Thank you for your time and effort.

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.

Our theoretical results are not tied to Assumption 2: they are also valid under the (L0,L1)(L_0,L_1)-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.

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?

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.

How essential are the assumptions that RR, G0G_0, G1G_1, and the target accuracy are known? Is there a practical way to choose the parameters without this information?

The parameters G0,G1,ϵG_0,G_1,\epsilon are not necessary for implementing Algorithm 2. Algorithm 2 only uses discounting factor α\alpha and effective stepsize η=αR\eta = \alpha 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.

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

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

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 η>0\eta > 0. 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

Reviewer_33NvOpenReview ↗
Rating
4
Confidence
3
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies first-order methods for non-smooth optimization. Compared with the widely studied generalized smoothness setting, the authors introduce a new generalized Lipschitz condition for non-smooth problems. Under this new condition, the paper establishes convergence guarantees for several existing algorithms and further provides improved convergence guarantees for clipped AdamW.

Critical strengths

The theoretical results in this paper are comprehensive and interesting. The proposed generalized Lipschitz condition is reasonable and covers a broad class of functions. Under this new condition, the authors provide detailed convergence analyses for several gradient-based methods. Moreover, while existing works under generalized smoothness do not clearly explain the advantage of AdamW, this paper highlights the important role of AdamW's exponentially weighted gradient accumulation.

The paper is well organized, and the proofs appear to be correct. The assumptions used in the theoretical analysis are also reasonable.

Critical weaknesses

While I understand that this paper mainly focuses on theoretical analysis, including some numerical experiments would further strengthen the paper. For example, previous studies have observed generalized smoothness in practical settings such as LSTM training. It would be helpful to provide concrete examples that satisfy the proposed generalized Lipschitz condition but not the standard Lipschitz condition. In addition, a numerical example demonstrating the advantage of AdamW would help validate the theoretical findings.

The current theoretical analysis mainly focuses on the convex setting. It would also be interesting to investigate whether the proposed framework and convergence results can be extended to general non-convex problems.

Questions for authors

Could the authors briefly discuss the main challenges of extending the current results to general non-convex problems?

1 comment

Thank you for your time and effort.

For example, previous studies have observed generalized smoothness in practical settings such as LSTM training. It would be helpful to provide concrete examples that satisfy the proposed generalized Lipschitz condition but not the standard Lipschitz condition.

There is empirical evidence for the generalized Lipschitz condition in literature, for instance, Figure 1 in [a] shows an approximately affine dependence between gradient norm and training loss. It is also important to highlight that our theoretical findings are not tied to Assumption 2: they are also valid under the generalized smoothness assumption (see lines 460-467).

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

The current theoretical analysis mainly focuses on the convex setting. It would also be interesting to investigate whether the proposed framework and convergence results can be extended to general non-convex problems.

As a part of our separate ongoing research project, we have extensions of our results to more realistic assumptions beyond quasar-convexity. However, extending our results to the general non-convex setting without any additional structure may not be a reasonable goal: we are concerned with how the algorithm converges to a global solution; however, it is provably impossible to obtain meaningful convergence guarantees beyond weak stationarity guarantees for any first-order method for general non-convex problems without assuming any additional structure.

Reviewer_uJC5OpenReview ↗
Rating
4
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies stochastic convex optimization when gradient magnitudes can grow affinely with the objective gap. Under a structured stochastic oracle assumption, it establishes polynomial complexity for a scalar clipped AdamW variant, whereas constant-step SGD and the specified AdaGrad-Norm method can exhibit exponential dependence on RG1RG_1. The analysis combines online-to-batch conversion with a two-stage averaging schedule and includes extensions to Hölder-type growth conditions and quasar-convexity.

Critical strengths
  • The polynomial versus exponential separation is a substantive result for the algorithms and oracle model considered. The block argument controlling changes in the objective gap is a useful technical contribution and supports the improved dependence on (RG_1).

  • The analysis is coherent, and the main convergence arguments appear sound. The framework also accommodates different regularity levels and a quasar-convex extension, giving the results breadth beyond the main convex setting.

Critical weaknesses
  • The novelty and interpretation need to be sharper. In the convex setting, the gradient-growth condition and exponential growth characterization already appear in Grimmer’s 2017 preprint, and the normalized subgradient rate follows from his general convergence theorem. See Benjamin Grimmer, Convergence Rates for Deterministic and Stochastic Subgradient Methods Without Lipschitz Continuity (2017 preprint; published in SIAM Journal on Optimization, 29(2), 1350–1365, 2019), which is not cited. Also, the better upper bound with exponential averaging does not establish that Algorithm 1 has worse worst-case complexity; its bound could be loose.

  • The scope of the AdamW conclusions could be stated more precisely. The main guarantees concern a scalar, clipped variant, while the diagonal/matrix extensions are only sketched. A precise statement of these extensions, together with examples illustrating the stochastic oracle assumption, would clarify how broadly the conclusions apply.

Questions for authors
  1. Could you clarify the overlap with Definition 4, Theorem 5, and Proposition 14 in Grimmer’s 2017 preprint, acknowledge the earlier results, and distinguish the additional generality and new contributions? Theorem 1.2 of the revised journal version also appears relevant to the normalized subgradient guarantee.

  2. Is there a lower bound establishing worse worst-case complexity for Algorithm 1 than for the exponential-averaging variant? Otherwise, could you clarify that this comparison concerns the proved upper bounds rather than an established worst-case separation?

  3. Could you clarify the role of the almost-sure bound in Assumption 2 and illustrate the decomposition and its constants for a representative stochastic learning model? Is extending the result to an affine root-second-moment bound a plausible direction?

  4. Could you explicitly state the schedule independent of the Hölder exponent? For the diagonal/matrix variants, could you specify the assumptions and resulting convergence rates, or clarify that Appendix D sketches extensions rather than establishing additional convergence theorems?

1 comment

Thank you for your time and effort.

Could you clarify the overlap...

Theorem 5 of Grimmer (2017) can be used to obtain the result of our Theorem 2, Option A, although the explicit iteration complexity is not stated there. Assumption 1/Eq. (1) is indeed a special instance of Definition 4 of Grimmer (2017) and Proposition 14 of Grimmer (2017) is a relevant characterization of this assumption, although both Definition 4 and Proposition 14 are absent from the published version of the paper. Overall, the work of Grimmer (2017) is highly relevant and we will add appropriate citations in our paper. Importantly, the work of Grimmer (2017) further supports our interest in the (M0,M1)(M_0,M_1)-Lipschitzness assumption and its extensions, but does not overlap with the main novelty of our paper: improvement of scalar-stepsize clipped AdamW over other scalar-stepsize methods.

Could you clarify the role of the almost-sure bound in Assumption 2...

The decomposition in Assumption 2 is made for purely technical reasons. In fact, as a part of our follow-up work, we have an improved analysis implying that this decomposition is not necessary and can indeed be replaced with a simpler inequality: Eξ∣∇ξf(x)∣2≤G0+G1(f(x)−f∗)\sqrt{\mathbb{E}_\xi \\|\nabla_\xi f(x)\\|^2} \leq G_0 + G_1(f(x) - f^*). This analysis improves the iteration complexity bound of scalar-stepsize clipped AdamW and even makes it near-optimal; however the main theoretical conclusions of our paper about AdamW do not change.

Is there a lower bound establishing worse worst-case complexity for Algorithm 1 than for the exponential-averaging variant? Otherwise, could you clarify that this comparison concerns the proved upper bounds rather than an established worst-case separation?

Such a lower bound exists. We have a counterexample in Theorem 9 for AdaGrad-Norm, which uses uniform averaging similar to Algorithm 1. Exactly the same counterexample from Case II of Theorem 9 can be used to show an exponential lower bound for Algorithm 1. The proof is very similar to the proof in Appendix H.2: the initial gradient is exponentially large and negative, the first step of Algorithm 1 overshoots the minimum in positive direction, $ x_2 = R/2 > x^* $, and after that, for exponentially long time, the momentum remains negative and it holds that $ x_k \geq R/4 > x^* $. Consequently, it takes an exponential number of iterations to reach the precision ϵ\epsilon. In fact, these arguments can be extended to the case where we replace the constant RR on line 6 of Algorithm 1 with an arbitrary parameter η>0\eta > 0 and/or remove clipping. We will add a corresponding theorem and a detailed proof.

Could you explicitly state the schedule independent of the Hölder exponent?

Theorem 10 gives the schedule which is independent of Hölder exponent ν\nu only up to logarithmic factors. However, this schedule can be changed to a completely independent of ν\nu. For sufficiently large universal constants C1,C2>0C_1,C_2 > 0, and for K≥C1(RL1)4K \geq C_1 (RL_1)^4 we can choose αk={1/[C2(RL1)3]k≤⌊K/2⌋8ln⁡(e+K)/Kk>⌊K/2⌋,\alpha_k = \begin{cases}1/[C_2(RL_1)^3] & k\leq \lfloor K/2\rfloor\\\\ 8\ln(e+K)/K & k> \lfloor K/2\rfloor\end{cases}, then we can obtain E[f(xK)−f∗]≤O~(σR/K+R1+νL0/K(1+ν)/2).\mathbb{E}[f(x_K) - f^*]\leq \tilde{O}(\sigma R/\sqrt{K} + R^{1+\nu}L_0/K^{(1+\nu)/2}). The proof is almost identical to that of Theorem 10. We will add appropriate clarifications to Appendix B.

For the diagonal/matrix variants, could you specify the assumptions and resulting convergence rates, or clarify that Appendix D sketches extensions rather than establishing additional convergence theorems?

We will fix the abstract wording about the analysis of the preconditioned methods. However, our wording in the summary of contributions is already appropriate: it does not claim to provide full formal proofs of the preconditioning extensions. The discussion in Appendix D is also appropriate as it gives details and references to derive these extensions: QRQ_R should be defined in terms of an appropriate non-Euclidean norm, and the gradient norm in Assumptions 1-3 should be replaced with an appropriate weighted Euclidean norm. The precise way to choose these norms is described, for instance, by Kovalev (2025, 2026) cited in Appendix D. We may include additional details with precise formulations of the assumptions and theorems. However, the full analysis under these assumptions would almost exactly repeat the analysis in our paper. Including this analysis would significantly increase the size of the appendix and possibly distract readers from the main contributions of our paper. At the same time, we would not like to remove Appendix D completely, because it could create a false impression that our theoretical insights apply only to the scalar-stepsize setting, which is less relevant to practice than the preconditioned setting.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.