Research map / Optimization / Nonconvex and smooth optimization
Isotropic Noise in Stochastic and Quantum 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.
Introduces isotropic stochastic gradient noise (ISGO) for Lipschitz convex minimization, gives a stochastic cutting-plane method achieving Õ(R²σ²/ε²+d) queries, matching lower bounds, and a quantum isotropifier yielding Õ(dRσ_V/ε) quantum SCO.
Problem
Stochastic convex optimization of d-dimensional Lipschitz convex functions with variance-bounded or sub-exponential stochastic gradient oracles, where the dimension-dependent query complexity of VSGO-based methods is suboptimal; also quantum SCO with variance-bounded quantum gradient oracles.
Approach
Defines isotropic noise (bounded in every fixed direction w.h.p.), shows a stochastic cutting-plane method with marginal approximate gradients needs only directional accuracy toward the optimum, saving a factor d over VSGO; builds a quantum isotropifier that converts a variance-bounded quantum sampling oracle into an unbiased estimator with isotropic error via boosted phase estimation and MLMC.
Key results
- Isotropic-noise SCO solvable with Õ(R²σ_I²/ε² + d) queries to an ISGO, matched by a lower bound up to polylog factors.
- Sub-exponential noise (ESGO) achieves Õ(R²σ_E²/ε² + d) queries, with matching lower bound Ω̃(R²σ_E²/ε² + min{R²L²/ε², d}).
- Quantum SCO under σ_V-QVSGO solved with Õ(dRσ_V/ε) queries, improving on prior Õ(d^{3/2}σ_V R/ε) and Õ(d^{5/8}((L+σ_V)R/ε)^{3/2}) bounds.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use isotropic noise assumptions instead of only a variance bound | SCO · High-precision, low-variance regimes | oracle queries: O(R^2 \sigma^2 / \epsilon^2 + R^2 L^2 / \epsilon^2) -> \tilde{O} \inparen*{R^2 \sigma^2 / \epsilon^{2} + d} | Helped |
| Use a σ_E-ESGO rather than a σ_V-VSGO | ISGO-based SCO method · SCO | oracle queries: \tilde{O}(d R^2 \sigma_V^2 / \epsilon^2 + d) -> \tilde{O}(R^2 \sigma_E^2 / \epsilon^2 + d) | Helped |
| Use a quantum isotropifier with the stochastic cutting plane method | Quantum SCO with QVSGO · Quantum SCO | oracle queries: \tilde{O}(d^{3/2}\sigma_VR/\epsilon) -> \tilde{O}(dR\sigma_V/\epsilon) | Helped |
| Convert variance-bounded quantum samples into unbiased estimates with isotropic error | Quantum isotropifier · Quantum SCO with QVSGO | oracle queries: \tilde{O}(dR\sigma_V/\epsilon) | Helped |
Limitations
- VSGO-based rate Õ(dR²σ_V²/ε²+d) remains a factor d worse than the conjectured rate; the open problem is only solved under the stronger isotropic/sub-exponential noise model.
- Upper bound requires δ inverse-polynomially small and polylogarithmic factors are hidden.
Experimental setup
Metrics: query complexity
Baselines: SGD quantum SCO algorithm with Õ(d^{3/2}(L+σ_V)R/ε) queries quantum SCO algorithm with Õ(d^{5/8}((L+σ_V)R/ε)^{3/2}) queries
Builds on: center of gravity cutting plane method stochastic cutting plane method of Carmon et al.-style quantum SCO analysis quantum sub-Gaussian mean estimation multilevel Monte Carlo
Closest papers by meaning
- Quantum Algorithms for Non-smooth Non-convex Optimization (NeurIPS 2024 · similarity 0.90)
- Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise (NeurIPS 2026 · similarity 0.89)
- Stochastic Quantum Sampling for Non-Logconcave Distributions and Estimating Partition Functions (ICML 2024 · similarity 0.88)
- Near-Optimal Quantum Algorithm for Minimizing the Maximal Loss (ICLR 2024 · similarity 0.88)
- Quantum Algorithms and Lower Bounds for Finite-Sum Optimization (ICML 2024 · similarity 0.87)
- Generalization of noisy SGD in unbounded non-convex settings (ICML 2025 · 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.