More Like this

1. Stabilized SVRG: Simple Variance Reduction for Nonconvex Optimization.

   Ge, Rong; Li, Zhize; Wang, Weiyao; Wang, Xiang (June 2019, The 32’nd Annual Conference on Learning Theory (COLT 2019))

   Variance reduction techniques like SVRG provide simple and fast algorithms for optimizing a convex finite-sum objective. For nonconvex objectives, these techniques can also find a first-order stationary point (with small gradient). However, in nonconvex optimization it is often crucial to find a second-order stationary point (with small gradient and almost PSD hessian). In this paper, we show that Stabilized SVRG (a simple variant of SVRG) can find an \eps-second-order stationary point using only O(n^{2/3}/\eps^2+n/\eps^{1.5}) stochastic gradients. To our best knowledge, this is the first second-order guarantee for a simple variant of SVRG. The running time almost matches the known guarantees for finding \eps-first-order stationary points. 

   more » « less
2. Acceleration of SVRG and Katyusha X by Inexact Preconditioning

   Yanli Liu, Fei Feng (January 2019, International Conference on Machine Learning (ICML))
3. Acceleration of SVRG and Katyusha X by inexact preconditioning

   Liu, Yanli; Feng, Fei; Yin, Wotao (January 2019, Proceedings of Machine Learning Research)
4. Principal Component Projection and Regression in Nearly Linear Time through Asymmetric {SVRG}

   Jin, Yujia; Sidford, Aaron (December 2019, Advances in neural information processing systems)
5. Dissipativity Theory for Accelerating Stochastic Variance Reduction: A Unified Analysis of SVRG and Katyusha Using Semidefinite Programs

   Hu, B; Wright, S; Lessard, L (July 2018, Proceedings of Machine Learning Research)

   Techniques for reducing the variance of gradient estimates used in stochastic programming algorithms for convex finite-sum problems have received a great deal of attention in recent years. By leveraging dissipativity theory from control, we provide a new perspective on two important variance-reduction algorithms: SVRG and its direct accelerated variant Katyusha. Our perspective provides a physically intuitive understanding of the behavior of SVRG-like methods via a principle of energy conservation. The tools discussed here allow us to automate the convergence analysis of SVRG-like methods by capturing their essential properties in small semidefinite programs amenable to standard analysis and computational techniques. Our approach recovers existing convergence results for SVRG and Katyusha and generalizes the theory to alternative parameter choices. We also discuss how our approach complements the linear coupling technique. Our combination of perspectives leads to a better understanding of accelerated variance-reduced stochastic methods for finite-sum problems. 

   more » « less