# Double Variance Reduction: A Smoothing Trick for Composite Optimization Problems without First-Order Gradient

arXiv: https://arxiv.org/abs/2405.17761 · HTML: https://mlsanity.com/paper/2405.17761/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 35 references that are in the map.
- First posted on arXiv 28 May 2024.

## Builds on (most cited first, 24 of 24)

- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Fine-Tuning Language Models with Just Forward Passes](https://mlsanity.com/paper/2305.17333/) (2023)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [A Primer on Zeroth-Order Optimization in Signal Processing and Machine Learning](https://mlsanity.com/paper/2006.06224/) (2020)
- [Stochastic Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1603.06160/) (2016)
- [AutoZOOM: Autoencoder-based Zeroth Order Optimization Method for Attacking Black-box Neural Networks](https://mlsanity.com/paper/1805.11770/) (2018)
- [PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization](https://mlsanity.com/paper/2008.10898/) (2020)
- [Zeroth-Order Stochastic Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1805.10367/) (2018)
- [Variance-Reduced Methods for Machine Learning](https://mlsanity.com/paper/2010.00892/) (2020)
- [A Proximal Stochastic Gradient Method with Progressive Variance Reduction](https://mlsanity.com/paper/1403.4699/) (2014)
- [DeepZero: Scaling up Zeroth-Order Optimization for Deep Model Training](https://mlsanity.com/paper/2310.02025/) (2023)
- [Variance Reduction for Faster Non-Convex Optimization](https://mlsanity.com/paper/1603.05643/) (2016)
- [Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loop](https://mlsanity.com/paper/1901.08689/) (2019)
- [A Theoretical and Empirical Comparison of Gradient Approximations in Derivative-Free Optimization](https://mlsanity.com/paper/1905.01332/) (2019)
- [Improved Zeroth-Order Variance Reduced Algorithms and Analysis for Nonconvex Optimization](https://mlsanity.com/paper/1910.12166/) (2019)
- [A Comprehensive Linear Speedup Analysis for Asynchronous Stochastic Parallel Optimization from Zeroth-Order to First-Order](https://mlsanity.com/paper/1606.00498/) (2016)
- [Stochastic Quasi-Gradient Methods: Variance Reduction via Jacobian Sketching](https://mlsanity.com/paper/1805.02632/) (2018)
- [Faster Gradient-Free Algorithms for Nonsmooth Nonconvex Stochastic Optimization](https://mlsanity.com/paper/2301.06428/) (2023)
- [Hessian-Aware Zeroth-Order Optimization for Black-Box Adversarial Attack](https://mlsanity.com/paper/1812.11377/) (2018)
- [L-SVRG and L-Katyusha with Arbitrary Sampling](https://mlsanity.com/paper/1906.01481/) (2019)
- [Zeroth-Order Algorithms for Stochastic Distributed Nonconvex Optimization](https://mlsanity.com/paper/2106.02958/) (2021)
- [Faster Gradient-Free Proximal Stochastic Methods for Nonconvex Nonsmooth Optimization](https://mlsanity.com/paper/1902.06158/) (2019)
- [Decentralized Gradient-Free Methods for Stochastic Non-Smooth Non-Convex Optimization](https://mlsanity.com/paper/2310.11973/) (2023)

## Built on by (most cited first, 1 of 1)

- [Poor Man's Training on MCUs: A Memory-Efficient Quantized Back-Propagation-Free Approach](https://mlsanity.com/paper/2411.05873/) (2024)

## Abstract (arXiv)

Variance reduction techniques are designed to decrease the sampling variance, thereby accelerating convergence rates of first-order (FO) and zeroth-order (ZO) optimization methods. However, in composite optimization problems, ZO methods encounter an additional variance called the coordinate-wise variance, which stems from the random gradient estimation. To reduce this variance, prior works require estimating all partial derivatives, essentially approximating FO information. This approach demands O(d) function evaluations (d is the dimension size), which incurs substantial computational costs and is prohibitive in high-dimensional scenarios. This paper proposes the Zeroth-order Proximal Double Variance Reduction (ZPDVR) method, which utilizes the averaging trick to reduce both sampling and coordinate-wise variances. Compared to prior methods, ZPDVR relies solely on random gradient estimates, calls the stochastic zeroth-order oracle (SZO) in expectation O(1) times per iteration, and achieves the optimal O(d(n + kappa)log (frac1ε)) SZO query complexity in the strongly convex and smooth setting, where kappa represents the condition number and ε is the desired accuracy. Empirical results validate ZPDVR's linear convergence and demonstrate its superior performance over other related methods.