Research map / Optimization / Nonconvex and smooth optimization
A Parameter-Free and Near-Optimal Zeroth-Order Algorithm for Stochastic 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.
Proposes POEM, a parameter-free stochastic zeroth-order method for convex stochastic optimization that uses a DoG-style distance-over-gradient step size and an adaptive smoothing parameter, achieving near-optimal SZO complexity.
Problem
Zeroth-order stochastic convex minimization where step size and smoothing parameter typically require knowledge of Lipschitz constant, diameter, and iteration budget; tuning-free methods are needed.
Approach
Extends DoG-style parameter-free step size (distance from initial point over sum of squared finite-difference norms) to zeroth-order setting, and sets the smoothing parameter adaptively as mu_t = rbar_t * sqrt(d/(t+1)), so both step size and smoothing are tuning-free.
Key results
- POEM achieves SZO complexity tilde-O(d L^2 D^2 / epsilon^2) in bounded domains, matching the stated lower bound and sharper than the O(d^2 L^2 s0^2/epsilon^2) of RSNSO.
- In the unbounded setting, POEM attains tilde-O(d L^2 s0^2/epsilon^2) with modified step sizes and smoothing, but requires knowledge of s0 and an overestimate of L.
- Experiments on mushrooms, a9a, and w8a show POEM converges faster than TPGE-T and TPBCO-T and is more robust to r_epsilon than baselines to 1/L settings.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use POEM instead of TPGE-T or TPBCO-T | Stochastic zeroth-order optimization · mushrooms, a9a, and w8a | Convergence speed | Helped |
| Use POEM instead of TPGE-E or TPBCO-E | Stochastic zeroth-order optimization · mushrooms, a9a, and w8a | Convergence speed | No clear effect |
| Vary the initial movement r_epsilon over the tested settings (ablation) | POEM · mushrooms, a9a, and w8a | Objective function value at the last iteration | No clear effect |
| Use POEM's adaptive parameter scheme instead of baseline parameter settings | POEM and stochastic zeroth-order baselines · mushrooms, a9a, and w8a | Robustness to parameter settings | Helped |
| Use POEM for bounded-domain stochastic convex optimization | POEM · Stochastic convex optimization, bounded domain | SZO complexity: \tilde\fO\left(\dfrac{dL^2 D_\fX^2}{\epsilon^2}\right); lower bound: \Omega\left(\dfrac{dL^2 D_\fX^2}{\epsilon^2}\right) | Helped |
Surprising findings
- Theoretically, a parameter-free zeroth-order method cannot fully avoid dependence on problem estimates in unbounded domains; a lower bound shows a sqrt(d) L s0/sqrt(T) limit under valid estimates.
- POEM with well-tuned baselines performs comparably, so the advantage over tuned baselines is mainly robustness rather than peak performance.
Limitations
- Unbounded-domain result requires knowledge of s0 or an overestimate of L and s0 bounds, so it is not fully parameter-free.
- Analysis is for the Euclidean norm and convex stochastic setting; extension to minimax, bilevel, or finite-sum settings is left open.
- Experiments are limited to linear SVM-type binary classification on three LIBSVM datasets.
Experimental setup
Datasets: mushrooms a9a w8a
Benchmarks: mushrooms a9a w8a
Metrics: function value gap vs. SZO complexity final objective value across parameter settings
Baselines: TPGE TPBCO RSNSO
Builds on: DoG (Distance over Gradients) TPGE TPBCO randomized smoothing
Closest papers by meaning
- Stochastic Zeroth-Order Optimization Under Heavy-Tailed Noise (NeurIPS 2026 · similarity 0.88)
- Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity (NeurIPS 2024 · similarity 0.87)
- Universal Gradient Methods for Stochastic Convex Optimization (ICML 2024 · similarity 0.87)
- Zeroth-Order Methods for Constrained Nonconvex Nonsmooth Stochastic Optimization (ICML 2024 · similarity 0.86)
- Last-Iterate Convergence of Single-Loop Stochastic Methods for Constrained Convex-Concave Minimax Problems (NeurIPS 2026 · similarity 0.86)
- Guided Zeroth-Order Methods for Stochastic Non-convex Problems with Decision-Dependent Distributions (ICML 2025 · similarity 0.85)
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.