Research map / Optimization / Nonconvex and smooth optimization
Random Scaling and Momentum for Non-smooth Non-convex Optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that SGD with momentum plus a per-step exponential random scaling of the update achieves optimal rates for non-smooth non-convex stochastic optimization under a relaxed (c,ε)-stationarity criterion, via an exponentiated online-to-non-convex conversion.
Problem
Convergence of stochastic gradient methods for non-smooth, non-convex (non-weakly-convex) objectives, where classical SGDM analysis requires smoothness or convexity and Goldstein stationarity requires conservative exploration.
Approach
Scale each update by an Expo(1) random variable so that the expected function change equals the expected gradient inner product at the new iterate; combine with exponentially weighted gradients and a variance regularizer in an online-to-non-convex conversion. Unconstrained OGD in this framework recovers SGDM with random scaling.
Key results
- On CIFAR-10 with ResNet-18, SGDM with random scaling reaches 94.4% ± 0.2 test accuracy versus 94.6% ± 0.1 for standard SGDM (best iterate, three trials).
- Theory: the Exponentiated O2NC with unconstrained OGD finds a (c,ε)-stationary point in O(max{(G+σ)^3 ε^-3, F*(G+σ)^2 c^{1/2} ε^{-7/2}}) iterations, recovering the optimal O(ε^-4) rate for smooth and O(ε^-7/2) for second-order smooth objectives.
- A matching lower bound Ω(F* G^2 c^{1/2} ε^{-7/2}) is shown for finding (c,ε)-stationary points.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add exponential random scaling to SGDM updates | SGDM on ResNet-18 · CIFAR-10 train | train loss (×10^-4): 9.82 ± 0.21 -> 9.55 ± 0.37 | Helped |
| Add exponential random scaling to SGDM updates | SGDM on ResNet-18 · CIFAR-10 train | train accuracy (%): 100.0 ± 0.0 -> 100.0 ± 0.0 | No clear effect |
| Add exponential random scaling to SGDM updates | SGDM on ResNet-18 · CIFAR-10 test | test loss (×10^-2): 21.6 ± 0.1 -> 22.0 ± 0.4 | Hurt |
| Add exponential random scaling to SGDM updates | SGDM on ResNet-18 · CIFAR-10 test | test accuracy (%): 94.6 ± 0.1 -> 94.4 ± 0.2 | Hurt |
Surprising findings
- The random scaling change to SGDM is minimal yet yields optimal non-smooth non-convex guarantees without any explicit smoothness-based analysis of SGDM.
Limitations
- Experiments are limited to a single architecture and dataset (ResNet-18 on CIFAR-10) with no significant performance gain shown.
- The (c,ε)-stationarity criterion is a relaxation of Goldstein stationarity and requires assumptions such as Lipschitzness and well-behaved functions.
- Adaptive (Adam-like) extension is left as an open problem.
Experimental setup
Datasets: CIFAR-10
Benchmarks: CIFAR-10
Metrics: train loss train accuracy test loss test accuracy
Baselines: SGDM without random scaling
Builds on: online-to-non-convex conversion (O2NC) Goldstein stationarity online mirror descent online gradient descent
Closest papers by meaning
- An Improved Analysis of Stochastic Gradient Descent with Momentum (NeurIPS 2020 · similarity 0.93)
- High Probability Bounds for Non-Convex Stochastic Optimization with Momentum (ICLR 2026 · similarity 0.91)
- The Marginal Value of Momentum for Small Learning Rate SGD (ICLR 2024 · similarity 0.90)
- Better SGD using Second-order Momentum (NeurIPS 2022 · similarity 0.90)
- Gradient correlation is a key ingredient to accelerate SGD with momentum (ICLR 2025 · similarity 0.90)
- Dimension-adapted Momentum Outscales SGD (NeurIPS 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.