Research map / Optimization / Nonconvex and smooth optimization
Tuning-Free Stochastic 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.
Formalizes tuning-free stochastic optimization, proves impossibility over unbounded domains for smooth/Lipschitz convex and for high-probability-tight nonconvex rates, and shows DoG/DoWG and a restarted SGD variant are tuning-free under benign noise or weaker guarantees.
Problem
Hyperparameter tuning of SGD is costly; the question is whether an optimizer can match optimally-tuned SGD up to polylogarithmic factors given only loose bounds (hints) on problem parameters, in stochastic convex and nonconvex optimization.
Approach
Defines tuning-free algorithms via hints on optimal parameters; shows tuning-free SGD is possible on bounded domains and for DoG/DoWG under sub-gaussian noise with high signal-to-noise, but impossible on unbounded domains in the stochastic setting; gives a restarted SGD with leader finding that matches the high-probability nonconvex SGD rate up to polylog cost.
Key results
- Proves no polylogarithmic tuning-free algorithm exists for L-smooth convex or G-Lipschitz convex functions over unbounded domains in the stochastic setting.
- Shows DoG and DoWG are tuning-free on bounded domains and on unbounded domains under sub-gaussian noise with sufficiently large signal-to-noise ratio via minibatch variance estimation.
- Restarted SGD with FindLeader matches the best-known high-probability nonconvex SGD rate up to polylogarithmic factors using only hints, while no algorithm can match the in-expectation tuned SGD rate with high probability.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use DoG or DoWG with only parameter hints on a bounded domain | DoG and DoWG · Bounded-domain convex optimization | convergence error | Helped |
| Allow an unbounded domain with stochastic gradients for smooth convex optimization | Tuning-free SGD matching · Unbounded smooth convex optimization | convergence error | Hurt |
| Allow an unbounded domain with stochastic gradients for Lipschitz convex optimization | Tuning-free SGD matching · Unbounded Lipschitz convex optimization | convergence error | Hurt |
| Use T-DoG or T-DoWG with variance estimation under sufficiently high signal-to-noise ratio | T-DoG and T-DoWG · Unbounded convex optimization with benign noise | convergence error | Helped |
| Use restarted SGD with Leader Finding and parameter hints | SGD · Smooth nonconvex optimization, high-probability convergence | squared gradient norm | Helped |
| Require matching tuned SGD's expected convergence rate with high probability | Any tuning-free algorithm · Smooth nonconvex optimization | squared gradient norm | Hurt |
Surprising findings
- Tuning-free optimization is impossible over unbounded domains in the stochastic convex setting, even though it is possible in the deterministic setting.
- Matching the in-expectation nonconvex SGD rate with high probability is impossible for any algorithm, though the weaker high-probability rate is achievable.
Limitations
- Upper bounds require stringent noise assumptions (bounded or sub-gaussian norm), not general expected smoothness.
- Unbounded-domain convex tuning-free results hold only under high signal-to-noise noise distributions; small SNR makes optimization impossible.
- Dependence on dimension via logarithmic factor for sub-gaussian noise.
Experimental setup
Baselines: SGD with tuned stepsize restarted SGD with bisection (Carmon & Hinder) AdaGrad-like restarted SGD Coin betting with online Newton step hints
Builds on: DoG DoWG Polyak stepsize Adaptive Polyak
Closest papers by meaning
- Stab-SGD: Noise-Adaptivity in Smooth Optimization with Stability Ratios (NeurIPS 2025 · similarity 0.91)
- How Free is Parameter-Free Stochastic Optimization? (ICML 2024 · similarity 0.89)
- Towards Noise-adaptive, Problem-adaptive (Accelerated) Stochastic Gradient Descent (ICML 2022 · similarity 0.89)
- Derivatives of Stochastic Gradient Descent in parametric optimization (NeurIPS 2024 · similarity 0.88)
- Error Analysis Affected by Heavy-Tailed Gradients for Non-Convex Pairwise Stochastic Gradient Descent (AAAI 2025 · similarity 0.87)
- Adaptive Algorithms with Sharp Convergence Rates for Stochastic Hierarchical Optimization (NeurIPS 2025 · 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.