Research map / Optimization / Nonconvex and smooth optimization
Stochastic Weakly Convex Optimization beyond Lipschitz Continuity
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 adaptive regularization (stepsize) strategies let stochastic model-based weakly convex methods, including SGD, keep an O(1/sqrt(K)) rate with constant failure probability when the Lipschitz constant grows with the iterate norm, including an unknown-growth variant using reference Lipschitz estimates.
Problem
Stochastic weakly convex optimization where the local Lipschitz constant of the stochastic model is not globally bounded (it can grow with ||x||), so standard fixed-stepsize analyses and stability guarantees fail.
Approach
Choose the proximal regularization weight gamma_k adaptively, proportional to a growth function G(||x^k||) (or to a clipped local Lipschitz estimate from an independent sample), so that the potential reduction error stays controlled; a probabilistic argument with Markov-type tail bounds then shows iterates stay in a bounded ball with high probability, yielding an O(1/sqrt(K)) rate with constant fa
Key results
- Adaptive stepsizes with known growth G converge robustly where vanilla SGD diverges for theta around 1e8 on the high-order polynomial regression problem r2.
- The reference-Lipschitz adaptive stepsize never diverged in experiments, though it is conservative on mildly growing problems such as r1.
- Theory gives O(1/sqrt(K)) rate for min E||grad Moreau envelope||^2 with probability at least 1-p, p in (2delta,1).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use adaptive stepsizes based on the known growth function | SGD for robust nonlinear regression · r2 high-order polynomial | convergence stability | Helped |
| Use the reference-Lipschitz adaptive stepsize estimated from an independent sample | SGD for robust nonlinear regression · Robust nonlinear regression | divergence frequency | Helped |
| Use the proposed adaptive stepsize approaches instead of mirror descent | Robust nonlinear regression · Robust nonlinear regression | convergence performance | Helped |
| Use the reference-Lipschitz adaptive stepsize | SGD for robust nonlinear regression · r1 mild-growth problem | stepsize conservativeness | Hurt |
Surprising findings
- Adaptive stepsize with unknown growth is sometimes overly conservative on mild-growth problems such as phase retrieval.
- The paper reports SGD diverging for large stepsize on the polynomial model r2, indicating standard constant stepsizes are unsafe.
Limitations
- Guarantee holds with constant (not high) probability; repeated runs suggested but not analyzed.
- Analysis uses convex model functions and bounded level sets of the Moreau envelope.
- Unknown-growth variant can be conservative on mildly non-Lipschitz problems.
Experimental setup
Datasets: synthetic robust nonlinear regression data (m=300, n=100)
Benchmarks: synthetic robust phase retrieval synthetic high-order polynomial regression synthetic exponential regression
Metrics: iterations to reach objective within 1.2 of optimal value divergence rate over stepsize grid
Baselines: SGD mirror descent constant stepsize SGD
Builds on: stochastic model-based optimization gradient clipping Moreau envelope analysis mirror descent
Closest papers by meaning
- Minibatch and Momentum Model-based Methods for Stochastic Weakly Convex Optimization (NeurIPS 2021 · similarity 0.90)
- Last-Iterate Convergence of Single-Loop Stochastic Methods for Constrained Convex-Concave Minimax Problems (NeurIPS 2026 · similarity 0.89)
- Universal Gradient Methods for Stochastic Convex Optimization (ICML 2024 · similarity 0.89)
- Adaptive Proximal Gradient Methods Are Universal Without Approximation (ICML 2024 · similarity 0.88)
- Adaptive and Optimal Second-order Optimistic Methods for Minimax Optimization (NeurIPS 2024 · similarity 0.87)
- Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods (ICLR 2024 · similarity 0.87)
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.