Research map / Optimization / Nonconvex and smooth optimization
Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity
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.
Gives the first tight minimax simple-regret characterization (upper and lower bounds ~ d·rho^{2/3}/M · T^{-2/3}) for zeroth-order optimization of strongly convex functions with Lipschitz Hessian, using a bootstrapping stage plus a hyperellipsoid-sampling Newton-like final stage.
Problem
Noisy zeroth-order (bandit) optimization of strongly convex functions with Lipschitz Hessian; the minimax simple regret rate is unknown.
Approach
A sharp bias/variance analysis of spherical/hyperellipsoid-sampling gradient estimators under Lipschitz Hessian (bias bound r*rho*sqrt(d)/(2(d+2))), combined with a bootstrapping stage that finds a rough minimizer and a final stage doing a preconditioned, Newton-like step using a sampled Hessian and ellipsoidal gradient estimates.
Key results
- Upper bound: limsup T^{2/3} * minimax simple regret <= C * rho^{2/3} d / M via a two-stage algorithm, matching the lower bound.
- Lower bound: liminf T^{2/3} * minimax simple regret >= C * rho^{2/3} d / M under standard Gaussian noise, using a KL-divergence hard-instance construction.
- Gradient estimator bias bounded by lambda_Z^3 rho sqrt(d)/(2(d+2)), improving prior O(r^2) isotropic bounds, and sharp for cubic polynomials.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Combine strong convexity with Lipschitz Hessian smoothness | Stochastic zeroth-order optimization · Strongly convex, Lipschitz-Hessian functions | sample complexity: \widetilde O(\varepsilon^{-2}) -> O(\varepsilon^{-1.5}) | Helped |
| Combine strong convexity with Lipschitz Hessian smoothness | Stochastic zeroth-order optimization · Strongly convex, Lipschitz-Hessian functions | sample complexity: \widetilde O(\varepsilon^{-(2+d/3)}) -> O(\varepsilon^{-1.5}) | Helped |
| Use the proposed two-stage algorithm with non-isotropic hyperellipsoid sampling in the final stage | Proposed two-stage algorithm · Strongly convex, Lipschitz-Hessian functions | minimax simple regret: O(d^{\frac{5}{3}}T^{-\frac{2}{3}}M^{-1}) -> O(dT^{-\frac{2}{3}}M^{-1}) | Helped |
Limitations
- Analysis restricted to additive noise with bounded variance and subgaussian assumption (removal only by citing other mean-estimation methods).
- Results are asymptotic in T; non-asymptotic constants and finite-sample behavior are loose (e.g., conditions requiring large T).
- Only simple regret considered; the average-regret online setting is left open.
Experimental setup
Metrics: simple regret (expected f(x_T)-f*) asymptotic rate T^{2/3} scaling
Baselines: Gradient-descent-based higher-order smoothness bandit algorithms (Lipschitz-grad Isotropic sampling gradient estimators
Builds on: Newton's method KL-divergence lower bound technique (Proposition 7 in cited work)
Closest papers by meaning
- Stochastic Zeroth-Order Optimization Under Heavy-Tailed Noise (NeurIPS 2026 · similarity 0.91)
- A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees (NeurIPS 2026 · similarity 0.89)
- The Sample Complexity of Gradient Descent in Stochastic Convex Optimization (NeurIPS 2024 · similarity 0.89)
- Zeroth-Order Optimization Finds Flat Minima (NeurIPS 2025 · similarity 0.89)
- Improved Lower Bounds for First-order Stochastic Non-convex Optimization under Markov Sampling (ICML 2025 · similarity 0.88)
- Single-Loop Stochastic Algorithms for Difference of Max-Structured Weakly Convex Functions (NeurIPS 2024 · similarity 0.88)
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.