Research map / Optimization / Nonconvex and smooth optimization
How Free is Parameter-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.
Studies whether fully parameter-free stochastic optimization is possible; shows hyperparameter search yields fully parameter-free non-convex and noisy-function-value convex methods, proves a lower bound barring full parameter-freeness for convex SGD-oracle settings, and gives a partially parameter-free convex method.
Problem
Parameter-free stochastic optimization: existing methods still require non-trivial knowledge of problem parameters (gradient norm/noise bounds, distance to minimizer, smoothness, suboptimality), so it is unclear when fully parameter-free methods exist.
Approach
A simple grid search over SGD stepsizes, with candidate selection via stochastic gradient or function-value estimates, gives fully parameter-free non-convex and convex methods; a lower bound shows that with gradient-only access, convex parameter-free methods must incur an unavoidable sigma_max/T term.
Key results
- Non-convex: a grid search over SGD stepsizes with gradient-norm-based selection achieves a rate matching tuned SGD up to poly-log factors, with only log dependence on the stepsize range.
- Convex with noisy function values: fully parameter-free method matches tuned SGD rate up to poly-log factors and a sigma_0/sqrt(T) term.
- Lower bound: for gradient-only convex SCO, any deterministic algorithm incurs an Omega(D sigma_max / T) term unless the ranges are restricted, so full parameter-freeness is impossible; the proposed method is parameter-free up to sigma_max tolerance O(sqrt(T)).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Grid-search fixed SGD stepsizes and select a candidate using stochastic gradient estimates | Non-convex smooth SGD · Non-convex smooth stochastic optimization | squared gradient norm: matches the rate of fully-tuned SGD up to logarithmic factors | Helped |
| Tune the projection diameter over a grid using adaptive projected SGD | Convex Lipschitz SGD with stochastic gradients only · Convex Lipschitz, stochastic gradients only | function suboptimality: \frac{\norm{w_1-w^\star} \sigma_{\max}}{T} | Mixed |
| Tune the projection diameter over a grid using adaptive projected SGD | Convex smooth SGD with stochastic gradients only · Convex smooth, stochastic gradients only | function suboptimality: \sigma_{\max} \frac{\widetilde C \norm{w_1-w^\star}\sqrt{\log \tfrac{T}{\delta}}}{T} | Mixed |
| Use noisy function values to select among grid-searched SGD candidates | Convex Lipschitz SGD · Convex Lipschitz, stochastic first-order oracle | function suboptimality: \frac{\sigma_{0}}{\sqrt{T}} | Helped |
| Optimize with uncertain distance and gradient-noise ranges and no function values | Convex stochastic gradient optimization · Convex Lipschitz, stochastic gradients only | function suboptimality lower bound: \frac{D_\star \sigma_{\max}}{6 T} | Hurt |
Surprising findings
- Full parameter-freeness is impossible for convex stochastic gradient oracles without additional range knowledge, a negative result for the stochastic gradient setting.
- A simple hyperparameter search outperforms sophisticated adaptive SGD bounds in the non-convex setting.
Limitations
- No empirical experiments are reported in the excerpt; contributions are theoretical.
- Gradient-only convex method retains an unavoidable sigma_max/T term unless noise bound is known up to O(sqrt(T)) tolerance.
- Poly-logarithmic overhead from grid search over stepsize ranges.
Experimental setup
Metrics: high-probability convergence rate bound
Baselines: tuned SGD AdaGrad-norm SGD Ghadimi-Lan SGD analysis parameter-free SCO methods (Cutkosky and Orabona style)
Builds on: SGD AdaGrad-norm two-phase SGD parameter-free online convex optimization
Closest papers by meaning
- Tuning-Free Stochastic Optimization (ICML 2024 · similarity 0.89)
- Derivatives of Stochastic Gradient Descent in parametric optimization (NeurIPS 2024 · similarity 0.88)
- Accelerated Distance-adaptive Methods for Hölder Smooth and Convex Optimization (NeurIPS 2025 · similarity 0.87)
- Universal Gradient Methods for Stochastic Convex Optimization (ICML 2024 · similarity 0.87)
- The Sample Complexity of Gradient Descent in Stochastic Convex Optimization (NeurIPS 2024 · similarity 0.87)
- Projection-Free Variance Reduction Methods for Stochastic Constrained Multi-Level Compositional Optimization (ICML 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.