Improved SVRG for Non-Strongly-Convex or Sum-of-Non-Convex Objectives

By Zeyuan Allen-Zhu, Yang Yuan. 2015

210 citations recorded by the source corpus.

Many classical algorithms are found until several years later to outlive the confines in which they were conceived, and continue to be relevant in unforeseen settings. In this paper, we show that SVRG is one such method: being originally designed for strongly convex objectives, it is also very robust in non-strongly convex or sum-of-non-convex settings. More precisely, we provide new analysis to improve the state-of-the-art running times in both settings by either applying SVRG or its novel variant. Since non-strongly convex objectives include important examples such as Lasso or logistic regression, and sum-of-non-convex objectives include famous examples such as stochastic PCA and is even believed to be related to training deep neural nets, our results also imply better performances in these applications.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

An Alternative View: When Does SGD Escape Local Minima? (2018, background): “Therefore, for the standard empirical risk minimizing problems with n points and smoothness L , to get to (cid:15) -close to x ∗ , GD needs O ( Ln/(cid:15) ) gradient evaluations [24], but SGD with reduced variance only needs O ( n log 1 + ) gradient evaluations [17, 4, 26, 1].”
SGD: General Analysis and Improved Rates (2019, methodology): “In the last experiment (Section 6.3) we focus on the problem of principal component analysis (PCA) which by construction can be seen as a problem with a strongly convex objective f but with non-convex functions f i (Allen-Zhu & Yuan, 2016; Garber & Hazan, 2015; Shalev-Shwartz, 2016).”
Katyusha: the first direct acceleration of stochastic gradient methods (2016, background): “In practice, it was reported that even for SVRG, choosing average works better than choosing the last iterate (Allen-Zhu and Yuan, 2016).”
AdaGrad stepsizes: Sharp convergence over nonconvex landscapes, from any initialization (2018, methodology): “In the noisy setting, faster rates than O ( 1/ √ N ) are also possible using accelerated SGD methods (Ghadimi and Lan, 2016; Allen-Zhu and Yang, 2016; Reddi et al., 2016; Allen-Zhu, 2017; Xu et al., 2017; Carmon et al., 2018).”
Fast Stochastic Methods for Nonsmooth Nonconvex Optimization (2016, methodology): “(13) To further analyze (13), we set up a recursion for which we use the following Lyapunov function: Rs+1t := E[F (x s+1 t ) + ct‖xs+1t − x̃s‖2].”
Natasha 2: Faster Non-Convex Optimization Than SGD (2017, background): “; of variance reduction is by ShalevShwartz [43], who assumes that each fi(x ) is nonconvex but their average f (x ) is still convex. This result was slightly improved to several more rened settings [10]. The rst truly nonconvex use of variance reduction (i.e., for f (x ) being also nonconvex) is in”
SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient (2017, background): “In addition, theoretical results for complexity of the methods or their variants when applied to general convex functions have been derived (Schmidt et al., 2016; Defazio et al., 2014; Reddi et al., 2016; Allen-Zhu & Yuan, 2016; Allen-Zhu, 2017).”
Differentially Private Empirical Risk Minimization Revisited: Faster and More General (2018, background): “For such cases, [5] has recently showed that SVRG++ has less gradient complexity than Accelerated Gradient Descent.”
L ] 1 0 A pr 2 01 9 AdaGrad-Norm convergence over nonconvex landscapes AdaGrad stepsizes : sharp convergence over nonconvex landscapes , from any initialization (2019, methodology): “In the noisy setting, faster rates than O ( 1/ √ N ) are also possible using accelerated SGD methods (Ghadimi and Lan, 2016; Allen-Zhu and Yang, 2016; Reddi et al., 2016; Allen-Zhu, 2017; Xu et al., 2017; Carmon et al., 2018).”
Stochastic Chebyshev Gradient Descent for Spectral Optimization (2018, methodology): “The proof of the above theorem is given in the supplementary material, where we utilize the recent analysis of SVRG for the sum of smooth non-convex objectives [10, 3].”
Follow the Compressed Leader: Faster Online Learning of Eigenvectors and Faster MMWU (2017, methodology): “− Since k∇ 2 f i ( x ) 2 ≤ ηk for each i , one can apply the SVRG method [10, 36] to minimize f ( x ) which gives running time O nnz ( Σ k 1 ) + ( ηk ) 2 max i [ k 1] { nnz ( A i ) . e − ∈ − Then, using the Catalyst/APPA acceleration scheme [18, 28], the above running time can be improved to O nnz…”
Non-convex Finite-Sum Optimization Via SCSG Methods (2017, unknown): “In recent years, complexity results have been derived for both gradient methods [13, 2, 8, 9] and stochastic gradient methods [12, 13, 6, 4, 24, 25, 3].”
Less than a Single Pass: Stochastically Controlled Stochastic Gradient (2016, background): “For general convex functions an alternative approach has been presented by [3] (they generate Nj by a different scheme in line 4), who also establish a computation rate O ( n ) .”
Variance Reduction for Faster Non-Convex Optimization (2016, background): “, 2014) as well as their accelerations (Shalev-Shwartz & Zhang, 2014; Lin et al., 2014; Zhang & Xiao, 2015; Allen-Zhu et al., 2016; Allen-Zhu, 2016) have been proposed in the past a few years.”
Guaranteed Sufficient Decrease for Stochastic Variance Reduced Gradient Optimization (2018, methodology): “These techniques include importance sampling [4], exploiting neighborhood structure in the training data to share and re-use information about past stochastic gradients [15], incorporating Nesterov’s acceleration techniques [16, 17] or momentum acceleration tricks [18], reducing the number of gradie”
Optimal Black-Box Reductions Between Optimization Objectives (2016, result): “This is opposed to results such as [4, 25] where the authors develop ad hoc techniques to tweak specific algorithms, rather than all algorithms, and apply them to other settings without losing extra factors and without introducing bias.”