acceptodds
Under review as a conference paper at ICLR 2027

Momentum Makes (Adaptive) Subgradient Methods Optimal for Stochastic Nonsmooth Nonconvex Optimization

Abstract

SGDM (stochastic gradient descent with momentum) consistently outperforms vanilla SGD across a wide spectrum of modern deep learning tasks, including the training of residual networks and Transformer-based large-scale models. Yet, theoretical understanding of this performance advantage remains incomplete, especially for the nonsmooth and nonconvex settings that dominate real-world deep learning applications. From an online learning perspective, a line of recent studies cutkosky2023optimal,ji2026derandomized,zhang2024random has established that carefully modified SGDM variants attain optimal convergence rates for locating Goldstein-style stationary points, thereby providing theoretical support for the empirical benefits of momentum acceleration. Despite these fruitful advances, existing studies heavily depend on additional algorithmic modifications such as model randomization or momentum clipping that deviate notably from practical SGDM implementations. In this paper, we pursue an alternative approach to directly analyze the convergence of standard SGDM over a broad family of weakly convex optimization problems. Equipped with squared-geometric-CDF randomized output, we prove that SGDM achieves optimal convergence rates under a mildly relaxed notion of Goldstein stationarity. Our results are valid for constant, decaying, and adaptive learning rate schedules alike. Furthermore, as a secondary contribution, our analysis extends to a slightly modified SGDM with one-time momentum reset, yielding novel theoretical insights into its recently observed empirical performance in training large language models and deep reinforcement learning.

Primary area:
optimization
Keywords:
Stochastic gradient descent with momentum, nonsmooth nonconvex optimization, weakly convex optimization, Adaptive methods

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_Rz8rOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies stochastic gradient (subgradient) methods with momentum when individual function are Lipschitz and the full objective is weakly convex. It introduces an L2L_2-moment relaxation of Goldstein stationarity that allows subgradients evaluated at the averaged points drawn from a distribution with bounded expected squared distance from the output. The main analysis keeps the standard SGDM updates but selects the output iterate using a squared-geometric-CDF distribution. For constant step sizes, it obtains the complexity of O(μ1/2ϵ−4+ρ2μ−1/2)O(\mu^{1/2}\epsilon^{-4}+\rho^2\mu^{-1/2}), or O(δ−1ϵ−3+ρ2δϵ−1)O(\delta^{-1}\epsilon^{-3}+\rho^2\delta\epsilon^{-1}) under the corresponding relaxed (δ,ϵ)(\delta,\epsilon)-Goldstein criterion. It also derives bounds for decaying step sizes and AMSGrad-type adaptive steps under an additional bounded-loss assumption, and presents a lower bound for the proposed stationarity criterion. Besides, the appendix analyzes a one-time momentum reset and reports CIFAR-10 experiments for the reset variants.

Overall, the analysis is interesting, but the scope of the optimality claim and its connection to the motivating applications require stronger support.

Critical strengths

The direct treatment of SGDM is the strongest part of the paper. The authors leave the momentum update unchanged and place the additional randomization in the choice of the output iterate. This gives the result a closer connection to ordinary SGDM than analyses that require clipping or repeatedly resetting momentum.

I also appreciate that the argument is developed for more than one learning-rate schedule. The authors define their relaxed stationarity criterion carefully, explain how it relates to more familiar notions, and provide a lower-bound argument to put the rate in context. Together, these make the contribution more substantial than a convergence bound for one particular schedule.

Critical weaknesses

My main reservation is about how the optimality result is framed. The proposed L2L_2 stationarity notion allows subgradients to come from outside the fixed neighborhood used in ordinary Goldstein stationarity, as long as their squared distance is controlled on average. This may be a useful target, but the comparison with prior Goldstein results should make the change in target more explicit.

I am also unsure whether the lower bound matches the assumptions of the upper bounds. Theorem 4 uses a Lipschitz objective and a stochastic estimator with bounded variance, whereas the convergence results assume that every sample loss is GG-Lipschitz. If the hard instance satisfies this stronger condition, the paper should say so; otherwise, the optimality claim needs to be qualified.

The experiments leave the main algorithmic idea largely untested. They focus on the secondary momentum-reset variant, whose curves are nearly indistinguishable from the baselines, rather than examining what the randomized output rule contributes. I would also be more careful with the deep-learning motivation: global Lipschitzness and weak convexity are not automatic for unrestricted networks, and the decaying and adaptive results additionally require bounded losses.

Questions for authors
  1. Does the lower-bound construction satisfy the per-sample Lipschitz assumption used in the upper bounds? If not, what is the precise setting in which the rate is claimed to be optimal?
  2. On a weakly convex problem satisfying the assumptions, how does the proposed output rule compare with selecting the last or a uniformly sampled iterate, measured using the paper's stationarity criterion?
  3. Can the authors give a representative learning objective that satisfies the stated global assumptions, or narrow the discussion of applications accordingly?
3 comments
AuthorsOpenReview ↗

Response to Reviewer Rz8r (Part I)

Thank you for your insightful review. We hope the following responses adequately address the raised concerns and questions, and we are ready to clarify any further points.

Your comment: This may be a useful target, but the comparison with prior Goldstein results should make the change in target more explicit.

Our response: Thank you for your appreciation of our proposed (μ,ϵ)(\mu,\epsilon)-L2L_2-regularized stationarity criterion. With this new target, we can directly analyze the convergence of vanilla SGDM for nonsmooth nonconvex optimization — a goal that could not be achieved using the standard Goldstein stationarity without additional algorithmic modifications. As suggested, we have clarified this contrast and explicitly highlighted the shift in stationarity target in Section 3.6, within the paragraph on convergence criteria and iteration complexity.

Your comment: If the hard instance satisfies this stronger condition, the paper should say so; otherwise, the optimality claim needs to be qualified.

Our response: Thanks for this valuable comment.

  • For Theorem 1 with constant learning rates, the original sample-wise GG-Lipschitz loss condition in Assumtion 1 can be relaxed to a second-moment bounded oracle condition E[∣g^(w;Z)∣2∣w]≤G2\mathbb{E}[\\|\hat g(w;Z)\\|^2\mid w]\le G^2, under which our upper bound still holds. The hard instance ff in Theorem 4 is GG-Lipschitz and satisfies E[∣∇f(w)−g^(w;Z)∣2∣w]≤G2\mathbb{E}[\\|\nabla f(w) - \hat g(w;Z)\\|^2\mid w]\le G^2. This yields E[∣g^(w;Z)∣2∣w]≤E[∣∇f(w)−g^(w;Z)∣2∣w]+∣∇f(w)∣2≤2G2\mathbb{E}[\\|\hat g(w;Z)\\|^2\mid w]\le \mathbb{E}[\\|\nabla f(w) - \hat g(w;Z)\\|^2\mid w] + \\|\nabla f(w) \\|^2\le 2G^2, so the hard instance satisfies this relaxed requirement and falls within the function class for Theorem 1. Accordingly, the leading rate O(μ1/2ϵ−4)\mathcal{O}(\mu^{1/2}\epsilon^{-4}) established in Corollary 1 is order-optimal, certified by the lower bound from Theorem 4.

  • For Theorems 2 and 3 with decaying and adaptive learning rates, the additional bounded-loss condition remains necessary. We have therefore withdrawn our earlier optimality claims for Corollaries 2 and 3 that relied on Theorem 4. Even so, these best-known upper bounds remain meaningful benchmarks, as prior guarantees for SGDM under decaying or adaptive learning‑rate schedules are scarce.

Following your suggestion, we have updated the assumptions in Section 2.3 and their citations across the theorems to incorporate this refinement. Optimality is now claimed only for Corollary 1.

Your comment: The experiments leave the main algorithmic idea largely untested.

Our response: Per your suggestion, we have added new experiments on CIFAR‑10 using ResNet‑101 and ViT to validate our proposed squared‑geometric‑CDF randomized output rule. Our main finding is that this rule reliably selects high‑quality stationary iterates and avoids the heavy tail of low‑quality draws that plagues uniform sampling. Complete experimental details are available in the newly added Section 4 of the revised manuscript.

Your comment: I would also be more careful with the deep-learning motivation.

Our response: We fully agree that global Lipschitzness and weak convexity do not hold out of the box for unconstrained deep networks such as standard CNNs or Transformers, though weak convexity may be attained with carefully chosen activations (e.g., GELU) and final predictors (e.g., cross‑entropy). Our motivation is twofold: first, many regularized or spectrally constrained network variants satisfy these conditions over bounded domains; second, our theory establishes best-known convergence guarantees for SGDM under these standard mathematical assumptions widely adopted in stochastic optimization.

AuthorsOpenReview ↗

Response to Reviewer Rz8r (Part II)

Your question: Does the lower-bound construction satisfy the per-sample Lipschitz assumption used in the upper bounds? If not, what is the precise setting in which the rate is claimed to be optimal?

Our response: No, the hard instance ff in Theorem 4 does not satisfy the sample‑wise Lipschitz loss condition originally imposed in Theorem 1. As noted earlier, however, this requirement can be relaxed to a second‑moment bounded oracle condition under which the same upper bound continues to hold. Under this weaker assumption, the hard instance falls within the admissible function class for Theorem 1, so the leading rate of Corollary 1 is order‑optimal, certified by the lower bound from Theorem 4.

We have retracted our prior optimality claims for Corollaries 2 and 3, since those rely on the bounded‑loss condition that our hard instance violates. The remaining upper bounds still constitute meaningful benchmarks, given the scarcity of existing convergence guarantees for SGDM under decaying and adaptive learning‑rate schedules for nonsmooth nonconvex optimization.

Your question: On a weakly convex problem ..., how does the proposed output rule compare with selecting the last or a uniformly sampled iterate, measured using the paper's stationarity criterion?

Our response: In terms of gradient norm, our proposed output rules Option I and Option II are comparable to uniform sampling, and all three outperform the last iterate. For prediction accuracy, our randomized output rules yield consistently tighter and more favorable distributions than uniform sampling on both ResNet‑101 and ViT; Option II attains a median performance competitive with the last‑iterate benchmark. Full results and discussions can be found in Section 4 of the revised manuscript.

Your question: Can the authors give a representative learning objective that satisfies the stated global assumptions, or narrow the discussion of applications accordingly?

Our response: As stated in the opening paragraph of our introduction, a canonical family of weakly convex functions takes the composite form f(x)=h(c(x))f(x)=h(c(x)) where hh is convex and LL-Lipschitz continuous, and cc is β\beta-smooth. Such compositions are generally neither convex nor smooth, yet they are LβL\beta-weakly convex. As a concrete example aligned with our experiments, neural networks with smooth activations such as softplus and GELU fall into this class: the loss can be written as f=h∘cf=h\circ c, with hh a convex prediction head such as cross‑entropy and cc a smooth hierarchical feature map. GELU also attains competitive or superior performance relative to the nonsmooth ReLU (Hendrycks & Gimpel, 2016).

We remark at the end of Section 2.3 that the bounded-loss assumption can be practically enforced using capped losses widely adopted in LLM training, as studied by Rivière et al. (2024). Relaxing this global boundedness condition remains an important direction for future work.

References

Dan Hendrycks, Kevin Gimpel. (2016). Gaussian Error Linear Units (GELUs). arXiv:1606.08415.

Morgane Riviere, Shreya Pathak, Pier Giuseppe Sessa, et al. (2024). Gemma 2: Improving open language models at a practical size. arXiv:2408.00118.

Dear Reviewer Rz8r,

We sincerely appreciate your careful evaluation of our work. We have addressed all your concerns and revised the manuscript accordingly. Please feel free to reach out if you have any remaining questions; we are happy to provide further clarifications.

Best regards,

The Authors

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

The paper analyzes stochastic subgradient descent with momentum for weakly convex objectives. It introduces an L2 relaxation of Goldstein stationarity and a regularized formulation that can be certified using geometrically weighted past subgradients and iterate distances. With specialized randomized output rules, it derives convergence bounds for constant, decaying and scalar norm-based AMSGrad learning rates; the latter two settings additionally assume bounded losses. It also presents a lower-bound reduction, a one-time momentum-reset extension, and preliminary CIFAR-10/ResNet-101 comparisons of reset and baseline optimizers.

Critical strengths

CS1. Lemma 1 and Theorem 1 connect momentum energy to a finite geometric witness for relaxed stationarity while preserving the standard SGDM update. The deterministic lower-bound treatment of learning rates also provides a useful framework for the decaying and adaptive cases.

Critical weaknesses
  • Matching optimality under the stated assumptions is not established. Assumption 1 gives an almost-sure bound on stochastic subgradients through sample-wise Lipschitz losses, and the decaying/adaptive results also require bounded losses; Theorem 4 and Lemma 12 specify only a Lipschitz objective and a bounded-variance oracle. The hard instance therefore needs to be placed in the same class. The advertised joint rate also suppresses the term 75G22ε2μ\frac{75G^2}{2\varepsilon^2\sqrt{\mu}} in Corollary 2, which can dominate when μ=o(ε2)\mu=o(\varepsilon^2), while Corollary 3's leading coefficient depends on (v^0+s2)−2(\hat{v}_0+s^2)^{-2} (ss denotes the safeguard).

  • The explicit convergence guarantees need some corrections. Corollary 1's step choice requires T≥4ρ2/μT\ge 4\rho^2/\sqrt{\mu}, which its displayed budget need not imply. In Corollary 2, with G=M=ρ=1G=M=\rho=1, μ=10−8\mu=10^{-8}, ε=0.01\varepsilon=0.01, the permitted T=6777140661T=6777140661 makes the proof's final bound bigger than the target 10−410^{-4}; thus the asserted budget implication is invalid. B.5 also substitutes random ητ2\eta_\tau^2 where Lemma 1 requires deterministic aτ2a_\tau^2. These appear repairable without changing the intended exponents.

Questions for authors

See Weaknesses. In particular:

  • Can the lower-bound oracle be realized by sample losses satisfying the upper bounds' Lipschitz and bounded-loss assumptions, with precise minimax quantifiers and a nontrivial accuracy regime? What restrictions on (μ,ε,s,v^0)(\mu,\varepsilon,s,\hat{v}_0) justify the headline rate?
  • Can you provide corrected sufficient budgets and the deterministic-coefficient version of B.5?
2 comments
AuthorsOpenReview ↗

Response to Reviewer XURG

Thank you for your insightful review. We hope the following responses adequately address the raised concerns and questions, and we are ready to clarify any further points.

Your comment:  Matching optimality under the stated assumptions is not established. ...The hard instance therefore needs to be placed in the same class.

Our response: Thanks for this valuable comment.

  • For Theorem 1 with constant learning rates, the original sample-wise GG-Lipschitz loss condition in Assumtion 1 can be relaxed to a second-moment bounded oracle condition E[∣g^(w;Z)∣2∣w]≤G2\mathbb{E}[\\|\hat g(w;Z)\\|^2\mid w]\le G^2, under which our upper bound still holds. The hard instance ff in Theorem 4 is GG-Lipschitz and satisfies E[∣∇f(w)−g^(w;Z)∣2∣w]≤G2\mathbb{E}[\\|\nabla f(w) - \hat g(w;Z)\\|^2\mid w]\le G^2. This yields E[∣g^(w;Z)∣2∣w]≤E[∣∇f(w)−g^(w;Z)∣2∣w]+∣∇f(w)∣2≤2G2\mathbb{E}[\\|\hat g(w;Z)\\|^2\mid w]\le \mathbb{E}[\\|\nabla f(w) - \hat g(w;Z)\\|^2\mid w] + \\|\nabla f(w) \\|^2\le 2G^2, so the hard instance satisfies this relaxed requirement and falls within the function class for Theorem 1. Accordingly, the leading rate O(μ1/2ϵ−4)\mathcal{O}(\mu^{1/2}\epsilon^{-4}) established in Corollary 1 is order-optimal, certified by the lower bound from Theorem 4.

  • For Theorems 2 and 3 with decaying and adaptive learning rates, the additional bounded-loss condition remains necessary. We have therefore withdrawn our earlier optimality claims for Corollaries 2 and 3 that relied on Theorem 4. Even so, these best-known upper bounds remain meaningful benchmarks, as prior guarantees for SGDM under decaying or adaptive learning‑rate schedules are scarce.

Following your suggestion, we have updated the assumptions in Section 2.3 and their citations across the theorems to incorporate this refinement. Optimality is now claimed only for Corollary 1.

Your comment:  The advertised joint rate also suppresses the term 75G22ϵ2μ\frac{75G^2}{2\epsilon^2\sqrt{\mu}} in Corollary 2, ...while Corollary 3's leading coefficient depends on (v^0+ε2)−2(\hat v_0+\varepsilon^2)^{-2}.

Our response: Following your comment, we have further emphasized in Remark 7 that the sample-complexity bound in Corollary 2 yields the leading rate O(μ1/2ϵ−4)\mathcal{O}(\mu^{1/2}\epsilon^{-4}) within the regime μ=Ω(ϵ2)\mu =\Omega(\epsilon^2). This regime holds upon choosing μ=O(δ−2ϵ2)\mu=\mathcal{O}(\delta^{-2}\epsilon^2) to attain the target (δ,ϵ)(\delta,\epsilon)-L2L_2-Goldstein stationarity, as discussed in Remark 4. Regarding the factor (v^0+ε2)−2(\hat v_0+\varepsilon^2)^{-2} in Corollary 3, we note in Remark 8 that its scale can be readily controlled by taking v^0=O(1)\hat v_0=\mathcal{O}(1), e.g., v^0=∥g(0)∥\hat v_0=\|g(0)\|.

Your comment: The explicit convergence guarantees need some corrections. 

Our response: Thank you for identifying these bugs. Fortunately, they can be easily fixed by correcting the constants in Corollaries 1 and 2 and replacing ητ2\eta^2_\tau with aτ2a^2_\tau in Appendix B.5. All these revisions have been highlighted in the updated manuscript.

Your question: Can the lower-bound oracle be realized by sample losses satisfying the upper bounds' Lipschitz and bounded-loss assumptions, with precise minimax quantifiers and a nontrivial accuracy regime?

Our response: Constructing lower-bound oracles that satisfy the sample-wise Lipschitz and bounded-loss conditions is a thrilling open problem, which we are actively investigating. Accordingly, we now only assert order optimality for the bound in Corollary 1.

Your question: What restrictions on (μ,ϵ,ε,v^0)(\mu,\epsilon,\varepsilon,\hat v_0) justify the headline rate?

Our response: The leading rate O(μ1/2ϵ−4)\mathcal{O}(\mu^{1/2}\epsilon^{-4}) in Corollary 2 holds for μ=Ω(ϵ2)\mu =\Omega(\epsilon^2), which can be realized by setting μ=O(δ−2ϵ2)\mu=\mathcal{O}(\delta^{-2}\epsilon^2) to achieve the target (δ,ϵ)(\delta,\epsilon)-L2L_2-Goldstein stationarity. For the term (v^0+ε2)−2(\hat v_0+\varepsilon^2)^{-2} in Corollary 3, we control its scale by taking v^0=O(1)\hat v_0=\mathcal{O}(1), e.g., v^0=∥g(0)∥\hat v_0=\|g(0)\|.

Your question: Can you provide corrected sufficient budgets and the deterministic-coefficient version of B.5?

Our response: Yes, we have corrected these minor issues in the revised manuscript.

Dear Reviewer XURG

We sincerely appreciate your careful evaluation of our work. We have addressed all your concerns and revised the manuscript accordingly. Please feel free to reach out if you have any remaining questions; we are happy to provide further clarifications.

Best regards,

The Authors

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

This paper studies sgd with momentum applied to Lipschitz loss. Existing analysis show that using momentum allows to achieve optimal bounds, but the related algorithms are complemented with additional mechanisms (because of the use of online to nonconvex conversion (O2NC) framework). This paper relaxes the notion of Goldstein stationarity to a L2\mathbb{L}^2 version, and show that for this notion vanilla sgd with momentum (with careful random choice of output) achieves similar complexity than the existing one using O2NC, although the latter hold for the classical Goldstein stationarity.

Critical strengths
  • I believe the conceptual question of achieving the best existing results with algorithms that more closely match the one used in practice is relevant. To me, this work addressed this question (in the setting it considers) in a way that is both convincing and rather original.
  • The paper is clear and well written, the various remarks provide clear insights on the results. As far as I can tell, the work is overall pretty solid, with some interesting complementary aspects are discussed in the appendix (reduction of their criterion in the smooth setting in appendix A, or incorporating momentum reset (or restart) in appendices E-F). I should point out that I am not very familiar with the literature on this subject, so I am not in a position to determine whether it addresses the issue adequately.
Critical weaknesses
  • The obvious limit is that as the newly introduced stationary notion is weaker, this induces that in some sense the results are weaker compared with previous works. In particular, it is not entirely clear what conclusions can be drawn from comparisons such as the one presented in Table 1 (yet the authors are rather clear about this limit, which is a good point). Also, I think this new L2\mathbb{L}^2-Goldstein stationary concept deserved a little more study. For instance, cannot we build examples of specific function and distribution for which a point is a (δ,0)(\delta,0)-L2\mathbb{L}^2-Goldstein stationary point, while not being a (δ,c)(\delta,c)-Goldstein stationary point for some c=O(1)c=O(1) ? As arbitrary distributions are allowed, it seems quite likely to me.

  • The motivation of this work is to more closely match practical implementations of sgd with momentum. To my knowledge, in practice we generically consider the last iterates, while the work consider a non-standard randomized way to chose the output. To my understanding the analysis is tightly linked to this choice of randomized output, such that it is not clear whether it can be relaxed. This create a mismatch between real implementations and the analysis of the paper. It is not really a critical weakness, but I think it deserves to be discussed, at least briefly in the conclusion.

Questions for authors

There is an important point I would like to clarify. To my knowledge, one quantity that is not too hard to bound when studying these kind of algorithms is some averaging or sum of (sub)gradients. Yet it does not provide one single point that approximates well a critical point. For smooth optimization, an easy way is to consider the min of the gradient norm over the trajectory. Of course in this nonsmooth case it is not that trivial to exhibit a good point.

If I understand well, another way to present your contribution is that you provide a randomized rule to output a point of the algorithm that is likely not too far from the iterates that serve to build the average of subgradients (in a weighted mean-square sense). This can indeed be formulated through the probabilistic language that is used in Definitions 1 and 2. Yet, from an optimization point of view, the former interpretation seems way more natural and intuitive, to me at least. However, it is somewhat hidden inside the analysis.

If I misunderstood, may you clarify to me please?

If I indeed understood well, could you explain why you chosed to introduce the idea through this L2\mathbb{L}^2 point of view which involves possibly arbitrary distributions P ? In particular, it seems to me that arbitrary choices of distributions may allow to consider potentially pathological examples.

4 comments
AuthorsOpenReview ↗

Response to Reviewer 5MGn

Thank you for your insightful review and positive evaluation of our work.

Your comment: The obvious limit is that as the newly introduced stationary notion is weaker, ...the results are weaker compared with previous works.

Our response: Our (μ,ϵ)(\mu,\epsilon)-L2L_2-regularized stationarity criterion is introduced to simplify the convergence analysis of SGDM while retaining the favorable properties of Goldstein stationarity. It is motivated in a similar spirit to the (c,ϵ)(c,\epsilon)-stationarity introduced by Zhang & Cutkosky (2024), which enables more flexible algorithm design for O2NC. Under this relaxed stationarity notion, we are able to directly analyze the convergence of vanilla SGDM for nonsmooth nonconvex optimization — a task that was previously unattainable under standard Goldstein stationarity without extra algorithmic modifications.

Your comment: In particular, it is not entirely clear what conclusions can be drawn from comparisons such as the one presented in Table 1.

Our response: The primary takeaway from Table 1 is: our analysis establishes state-of-the-art complexity bounds for vanilla SGDM on both weakly convex and second-order smooth functions, while simultaneously accommodating constant, time-decaying, and adaptive learning rate schedules. This capability distinguishes our work from the competing baselines. We have included a brief remark in the revised manuscript to emphasize this conclusion.

Your comment: Also, I think this new L2L_2-Goldstein stationary concept deserved a little more study. For instance, cannot we build examples...for some c=O(1)c=O(1)?

Our response: Thanks for this valuable suggestion. Yes, such examples can indeed be constructed. Consider the one-dimensional function f(w)=min⁡1,max⁡w,0f(w)=\min\\{1,\max\\{w,0\\}\\}, and take w=0.5w=0.5. For any ϵ∈(0,1)\epsilon\in(0,1), let XX a random variable with probability distribution P(X=1)=1−ϵ\mathbb{P}(X=1)=1-\epsilon and P(X=0.25)=ϵ\mathbb{P}(X=0.25)=\epsilon. Then E(∥w−X∥2)=0.25−3ϵ16\mathbb{E}(\|w-X\|^2) = 0.25 -\frac{3\epsilon}{16}. Let δ=0.25−3ϵ/16\delta=\sqrt{0.25-3\epsilon/16}. Clearly δ<0.5\delta<0.5, so w=0.5w=0.5 is a (δ,1)(\delta,1)-Goldstein point but not (δ,ϵ)(\delta,\epsilon)-Goldstein, since f′(w)≡1f'(w)\equiv1 over the interval (w−δ,w+δ)(w-\delta, w+\delta). By contrast, E(∥w−X∥2)=δ2\mathbb{E}(\|w-X\|^2) =\delta^2 and ∣E[f′(X]∣=∣(1−ϵ)f′(1)+ϵf′(0.25)∣=∣(1−ϵ)×0+ϵ×1∣=ϵ| \mathbb{E} [f'(X] | =|(1-\epsilon)f'(1)+\epsilon f'(0.25)|=|(1-\epsilon)\times0+\epsilon\times1|=\epsilon. This shows that ww is a (δ,ϵ)(\delta, \epsilon)-L2L_2-Goldstein point, while not being a (δ,ϵ)(\delta,\epsilon)-Goldstein stationary point.

Your comment: To my understanding the analysis is tightly linked to this choice of randomized output, such that it is not clear whether it can be relaxed.

Our response: It is true that our proposed geometric‑CDF-based randomized output scheme is essential to our analysis of SGDM. To our knowledge, nearly all prior analyses of stochastic subgradient methods for nonsmooth nonconvex functions rely on randomized output schemes. Analyzing the last iterate of SGDM under the Goldstein stationarity criterion would indeed be an interesting yet challenging direction for future work.

Your question: There is an important point I would like to clarify. ...in this nonsmooth case it is not that trivial to exhibit a good point.

Our response: Your observation is entirely valid. Unlike in the smooth setting, identifying an ϵ\epsilon-stationary point (or even a neighborhood around it) for a nonsmooth objective is computationally intractable (Kornowski & Shamir, 2022).

Your question: If I understand well, another way to present your contribution is that... build the average of subgradients (in aweighted mean-square sense).

Our response: Yes, this interpretation indeed captures the core intuition behind our relaxed notions of Goldstein stationarity from Definitions 1 and 2.

Your question: If I indeed understood well, could you explain why you chosed to introduce the idea through this L2L_2 point of view which involves possibly arbitrary distributions PP?

Our response: We would like to clarify that, under Definition 1, a point satisfies (δ,ϵ)(\delta,\epsilon)-L2L_2-Goldstein stationarity if there merely exists a set VV, a random variable v∼P∈P(V)v\sim P \in \mathcal{P}(V), and subgradients g(v)∈∂f(v)g(v)\in \partial f(v) almost surely such that ∣E[g(v)]∣≤ϵ\\|\mathbb{E}[g(v)] \\| \le \epsilon and E[∣v−w∣2]≤δ2\mathbb{E}[\\|v-w\\|^2] \le \delta^2. For our SGDM-Geo$^2$ algorithm, we just take V=wtt=1TV=\\{w_t\\}_{t=1}^T, with the sampling distribution constructed from the squared CDF of a geometric distribution, as detailed in Options I and II.

References

Qinzi Zhang and Ashok Cutkosky. (2024). Random scaling and momentum for non-smooth non-convex optimization. ICML.

Guy Kornowski and Ohad Shamir. (2022). Oracle complexity in nonsmooth nonconvex optimization. JMLR.

Thank you for this feedback, but I don't think you answered my main question. I understood that your definition requires only the existence of some set and random variable. What I do not understand is why introducing such a formalism if, in the end, you just fix it to one specific instance. Thank you for finding this example of function that is L2 Goldstein stationary while not being Goldstein stationary. Yet, such example is a good example that, to me, the relevance of introducing such a formalism is not entirely clear, as it may allow for weird examples.

AuthorsOpenReview ↗

Response to Reviewer 5MGn

Thank you for this thoughtful follow-up question. We are glad to clarify that the general formalism with arbitrary distributions PP is not meant to characterize our specific sampling rule, but serves as a unified analytical abstraction for iteration-complexity analysis. This separation distinguishes (1) the probabilistic stationarity criterion (Definitions 1 and 2), a general target for output rules; and (2) our concrete SGDM-Geo$^2$ sampler, one feasible distribution achieving this target.

We agree that unrestricted PP may lead to pathological cases, as you pointed out. Still, our optimality lower bound is built within this broad class, which is required to prove order-optimality: the lower bound applies to all valid PP, and our upper bound matches it. Restricting the formulation exclusively to our geometric sampler would prevent us from stating a general minimax rate and confine our analysis to this one heuristic.

Thank you for this clarification, I think it answers my question. I am happy to keep my positive score.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General response

We are grateful to all reviewers for their insightful reviews. Guided by their constructive comments, we have carefully revised the manuscript, with a summary of key changes provided as follows:

  1. Key assumptions (Section 2.3). We have refined the core assumptions for our analysis. Specifically, for Theorems 1 and 2, the original sample-wise Lipschitz loss condition is relaxed to a second-moment bounded oracle condition, introduced as our new Assumption 2.

  2. Optimality claims (Title, Abstract, Section 1.2 and 3.5). We now claim order‑optimality solely for the bound in Corollary 1 under constant learning rates. To reflect this revision, we have removed “(adaptive)” from the paper title.

  3. Comparison with prior Goldstein results (Section 3.6). We have explicitly highlighted the relaxation of the stationarity target and added a brief remark to underscore the conclusions drawn from the comparisons in Table 1.

  4. Experiments (Section 4) In the newly introduced Section 4, we have added a set of preliminary experiments to demonstrate the effectiveness of our proposed squared‑geometric‑CDF randomized output rule for SGDM.

  5. We have corrected the typos and other minor issues noted in the reviews.

All major revisions are highlighted in red text for easy reference. We sincerely hope that the concerns raised by the reviewers have been satisfactorily addressed in both the revised manuscript and our point-by-point responses.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.