Research map / Optimization / Nonconvex and smooth optimization
Double Variance Reduction: A Smoothing Trick for Composite Optimization Problems without First-Order Gradient
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 ZPDVR, a zeroth-order proximal variance reduction method that uses averaging-based gradient estimation to remove both sampling and coordinate-wise variance in composite optimization, needing O(1) function evaluations per iteration in expectation.
Problem
Zeroth-order composite finite-sum optimization (smooth strongly convex plus non-smooth regularizer) where random directional gradient estimates leave a non-vanishing coordinate-wise variance at the optimum, and prior fixes need O(d) function evaluations per step.
Approach
Builds a gradient estimator h updated with an averaging trick along random Gaussian directions (sketch-and-project view), updated only when the SVRG reference point changes (loopless), so the coordinate-wise variance vanishes without ever computing all partial derivatives.
Key results
- ZPDVR achieves SZO query complexity O(d(n+kappa)log(1/epsilon)) with O(1) expected SZO calls per iteration, versus O(dn kappa log(1/epsilon)) for SEGA and PGD.
- In experiments on four LIBSVM datasets (a9a, w8a, covtype, gisette), ZPDVR shows linear convergence and the best objective gap versus number of SZO calls.
- ZPSVRG stagnates near F(x*) at radius 1e-4 due to non-vanishing coordinate-wise variance.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use ZPDVR instead of PGD | Binary logistic classification on a9a, w8a, covtype, and gisette · a9a, w8a, covtype, gisette | objective gap | Helped |
| Use ZPDVR instead of SEGA | Binary logistic classification on a9a, w8a, covtype, and gisette · a9a, w8a, covtype, gisette | objective gap | Helped |
| Use ZPDVR instead of ZPSVRG | Binary logistic classification on a9a, w8a, covtype, and gisette · a9a, w8a, covtype, gisette | objective gap | Helped |
| Add the averaging-based gradient estimator that refines estimates along random directions | ZPDVR · Composite optimization | coordinate-wise variance | Helped |
Surprising findings
- The zeroth-order ZPSVRG baseline stalls above the optimum because of coordinate-wise variance, while the proposed method keeps converging linearly.
Limitations
- Convergence bound depends on a smoothing constant v that must be very small (v = O(sqrt(epsilon/(kappa^2 d^3 n)))), and the analysis uses approximate unbiasedness with error terms.
- Experiments are limited to a single logistic regression objective on four LIBSVM datasets.
- Per-iteration cost analysis assumes the full-pass refresh with probability p = 1/n.
Experimental setup
Datasets: a9a w8a covtype gisette
Benchmarks: a9a w8a covtype gisette
Metrics: objective gap F(x)-F(x*) SZO query complexity
Baselines: PGD ZPSVRG SEGA
Builds on: SVRG Loopless SVRG ZPSVRG SEGA Gaussian smoothing zeroth-order gradient estimation
Closest papers by meaning
- Improved Zeroth-Order Variance Reduced Algorithms and Analysis for Nonconvex Optimization (ICML 2019 · similarity 0.91)
- Zeroth-Order Stochastic Variance Reduction for Nonconvex Optimization (NeurIPS 2018 · similarity 0.90)
- Refining Adaptive Zeroth-Order Optimization at Ease (ICML 2025 · similarity 0.89)
- Projection-Free Variance Reduction Methods for Stochastic Constrained Multi-Level Compositional Optimization (ICML 2024 · similarity 0.88)
- Revisiting Zeroth-Order Optimization: Minimum-Variance Two-Point Estimators and Directionally Aligned Perturbations (ICLR 2025 · similarity 0.88)
- Adaptively Incorporating Directional Hints into Zeroth-Order Optimization (NeurIPS 2026 · 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.