- 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 -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 , or under the corresponding relaxed -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 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 -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
- 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?
- 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?
- Can the authors give a representative learning objective that satisfies the stated global assumptions, or narrow the discussion of applications accordingly?
3 comments
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 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 where is convex and -Lipschitz continuous, and is -smooth. Such compositions are generally neither convex nor smooth, yet they are -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 , with a convex prediction head such as cross‑entropy and 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
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.
Our response: Thank you for your appreciation of our proposed (μ,ϵ)-L2-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.
Our response: Thanks for this valuable comment.
For Theorem 1 with constant learning rates, the original sample-wise G-Lipschitz loss condition in Assumtion 1 can be relaxed to a second-moment bounded oracle condition E[∣g^(w;Z)∣2∣w]≤G2, under which our upper bound still holds. The hard instance f in Theorem 4 is G-Lipschitz and satisfies E[∣∇f(w)−g^(w;Z)∣2∣w]≤G2. This yields E[∣g^(w;Z)∣2∣w]≤E[∣∇f(w)−g^(w;Z)∣2∣w]+∣∇f(w)∣2≤2G2, 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) 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.
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.
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.