Linear Convergence of SVRG in Statistical Estimation

In this paper we establish fast convergence rate of stochastic variance reduction gradient (SVRG) for a class of problems motivated by applications in high dimensional statistics where the problems are not strongly convex, or even non-convex. High-dimensional statistics has achieved remarkable success in the last decade, including results on consistency and rates for various estimator under non-asymptotic high-dimensional scaling, especially when the problem dimensionp is larger than the number of datan [e.g., Negahban et al., 2009, Cand es and Recht, 2009, and many others [Candes et al., 2006, Wainwright, 2006, Chen et al., 2011]] . It is now well known that while this setup appears ill-posed, the estimation or recovery is indeed possible by exploiting the underlying structure of the parameter space - notable examples include sparse vectors, low-rank matrices, and structured regression functions, among others. Recently, estimators leading to non-convex optimizations have gained fast growing attention. Not only it typically has better statistical properties in the high dimensional regime, but also in contrast to common belief, under many cases there exist efficient algorithms that provably find near-optimal solutions Loh and Wainwright [2011], Zhang and Zhang [2012], Loh and Wainwright [2013] . Computation challenges of statistical estimators and machine learning algorithms have been an active area of study, thanks to countless applications involving big data - datasets where both p and n are large.