Research map / Optimization / Nonconvex and smooth optimization
General framework for online-to-nonconvex conversion: Schedule-free SGD is also effective for nonconvex 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.
Builds a general online-to-nonconvex conversion framework and shows that schedule-free SGD, obtained as one special case, achieves optimal (λ,ε)-stationarity complexity for nonsmooth nonconvex stochastic optimization.
Problem
Theoretical understanding of schedule-free methods, which have been analyzed only in the convex setting, for nonsmooth nonconvex stochastic optimization (finding approximate Goldstein stationary points).
Approach
A general online-to-nonconvex conversion scheme where the x-iterates are chosen freely; choosing x_t = x_{t-1} + (1/ζ)δ_t with discounted OMD as the online learner recovers schedule-free SGD exactly, and the iterate x_t stays close to w_{t-1}, so the loss-decrement telescoping still applies. Also uses a new random EMA output index.
Key results
- Schedule-free SGD with tuned parameters achieves E||(lambda,epsilon)-stationarity|| <= 5 epsilon with T = O(lambda^{1/2} epsilon^{-7/2}) stochastic gradient calls, matching the optimal rate.
- The random EMA output index improves the iteration bound from O((G+sigma)^3 eps^-3) to O((G+sigma)^2 eps^-2) in the second term relative to prior conversion.
- Theory suggests kappa_t should be near 1 and the step size should be Theta((G+sigma)^2/eps^2) times the OMD step size, explaining empirical choices.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the Option III conversion, equivalent to schedule-free SGD, with the stated parameter choices | Schedule-free SGD · Nonsmooth nonconvex optimization | stationarity residual: 4ε -> 5ε | Helped |
| Choose κ_t close to 1, specifically uniformly from [ζ⋆, 1] | Schedule-free SGD · Nonsmooth nonconvex optimization | stationarity residual: 1 - \Theta\left(\frac{\varepsilon^2}{(G + \sigma)^2}\right) \leq \kappa_t \leq 1 | Helped |
| Use a base SGD step size larger than the OMD step size | Schedule-free SGD · Nonsmooth nonconvex optimization | stationarity residual: \Theta\left(\frac{(G + \sigma)^2}{\varepsilon^2}\right) times larger | Helped |
| Use the designed random EMA index τ rather than selecting the output uniformly | Online-to-nonconvex conversion · Nonsmooth nonconvex optimization | stochastic gradient oracle iterations: \OO{(G + \sigma)^3 \varepsilon^{-3}} -> \OO{(G + \sigma)^2 \varepsilon^{-2}} | Helped |
Surprising findings
- Schedule-free SGD, derived from the framework, is optimal for nonconvex losses despite being designed and analyzed for convex optimization.
Limitations
- Analysis requires distinct parameter settings for step size and c_t depending on whether F is convex or nonconvex.
- Does not explain why schedule-free methods remove the need for learning rate schedules.
- Adaptive (schedule-free Adam) variant is not covered by the analysis.
Experimental setup
Metrics: iteration complexity (lambda,epsilon)-stationarity
Baselines: previous online-to-nonconvex conversion (Cutkosky et al. 2023) SGD with momentum Adam anchoring scheme
Builds on: online-to-nonconvex conversion (Cutkosky et al. 2023) schedule-free SGD (Defazio et al. 2024) discounted-to-dynamic regret conversion online-to-batch conversion
Closest papers by meaning
- Improving Online-to-Nonconvex Conversion for Smooth Optimization via Double Optimism (ICLR 2026 · similarity 0.89)
- Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimization (NeurIPS 2022 · similarity 0.89)
- Optimistic Online-to-Batch Conversions for Accelerated Convergence and Universality (NeurIPS 2025 · similarity 0.88)
- An Online Optimization Perspective on First-Order and Zero-Order Decentralized Nonsmooth Nonconvex Stochastic Optimization (ICML 2024 · similarity 0.87)
- Random Scaling and Momentum for Non-smooth Non-convex Optimization (ICML 2024 · similarity 0.87)
- Taking the Road Less Scheduled with Adaptive Polyak Steps (NeurIPS 2026 · similarity 0.86)
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.