# A Variance Controlled Stochastic Method with Biased Estimation for Faster Non-convex Optimization

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 40 references that are in the map.
- First posted on arXiv 19 Feb 2021.

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

- [Very Deep Convolutional Networks for Large-Scale Image Recognition](https://mlsanity.com/paper/1409.1556/) (2014)
- [ImageNet Large Scale Visual Recognition Challenge](https://mlsanity.com/paper/1409.0575/) (2014)
- [FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling](https://mlsanity.com/paper/1801.10247/) (2018)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [Stochastic Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1603.06160/) (2016)
- [Lower Bounds for Finding Stationary Points I](https://mlsanity.com/paper/1710.11606/) (2017)
- [Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programming](https://mlsanity.com/paper/1310.3787/) (2013)
- [Variance Reduction for Faster Non-Convex Optimization](https://mlsanity.com/paper/1603.05643/) (2016)
- [Non-convex Finite-Sum Optimization Via SCSG Methods](https://mlsanity.com/paper/1706.09156/) (2017)
- [Natasha 2: Faster Non-Convex Optimization Than SGD](https://mlsanity.com/paper/1708.08694/) (2017)
- [Biased Stochastic First-Order Methods for Conditional Stochastic Optimization and Applications in Meta Learning](https://mlsanity.com/paper/2002.10790/) (2020)
- [Less than a Single Pass: Stochastically Controlled Stochastic Gradient Method](https://mlsanity.com/paper/1609.03261/) (2016)
- [Stochastic Gradient Descent with Biased but Consistent Gradient Estimators](https://mlsanity.com/paper/1807.11880/) (2018)
- [Stop Wasting My Gradients: Practical SVRG](https://mlsanity.com/paper/1511.01942/) (2015)
- [A Lower Bound for the Optimization of Finite Sums](https://mlsanity.com/paper/1410.0723/) (2014)
- [Non-convex Conditional Gradient Sliding](https://mlsanity.com/paper/1708.04783/) (2017)
- [A Stochastic Gradient Method with Biased Estimation for Faster Nonconvex Optimization](https://mlsanity.com/paper/1905.05185/) (2019)

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

- [AdaBest: Minimizing Client Drift in Federated Learning via Adaptive Bias Estimation](https://mlsanity.com/paper/2204.13170/) (2022)
- [GhostShiftAddNet: More Features from Energy-Efficient Operations](https://mlsanity.com/paper/2109.09495/) (2021)

## Abstract (arXiv)

In this paper, we proposed a new technique, em variance controlled stochastic gradient (VCSG), to improve the performance of the stochastic variance reduced gradient (SVRG) algorithm. To avoid over-reducing the variance of gradient by SVRG, a hyper-parameter λ is introduced in VCSG that is able to control the reduced variance of SVRG. Theory shows that the optimization method can converge by using an unbiased gradient estimator, but in practice, biased gradient estimation can allow more efficient convergence to the vicinity since an unbiased approach is computationally more expensive. λ also has the effect of balancing the trade-off between unbiased and biased estimations. Secondly, to minimize the number of full gradient calculations in SVRG, a variance-bounded batch is introduced to reduce the number of gradient calculations required in each iteration. For smooth non-convex functions, the proposed algorithm converges to an approximate first-order stationary point (i.e. mathbbE|nablaf(x)|2≤ε) within O(min1/ε3/2,n1/4/ε) number of stochastic gradient evaluations, which improves the leading gradient complexity of stochastic gradient-based method SCS (O(min1/ε5/3,n2/3/ε). It is shown theoretically and experimentally that VCSG can be deployed to improve convergence.