Nonconvex Sparse Learning via Stochastic Optimization with Progressive Variance Reduction

We propose a stochastic variance reduced optimization algorithm for solving a class of large-scale nonconvex optimization problems with cardinality constraints, and provide sufficient conditions under which the proposed algorithm enjoys strong linear convergence guarantees and optimal estimation accuracy in high dimensions. We further extend our analysis to an asynchronous variant of the approach, and demonstrate a near linear speedup in sparse settings. Numerical experiments demonstrate the efficiency of our method in terms of both parameter estimation and computational performance.