Nonconvex Sparse Learning via Stochastic Optimization with Progressive Variance Reduction
arXiv:1605.02711
Abstract
We propose a stochastic variance reduced optimization algorithm for solving sparse learning problems with cardinality constraints. Sufficient conditions are provided, under which the proposed algorithm enjoys strong linear convergence guarantees and optimal estimation accuracy in high dimensions. We further extend the proposed algorithm to an asynchronous parallel variant with a near linear speedup. Numerical experiments demonstrate the efficiency of our algorithm in terms of both parameter estimation and computational performance.
References in corpus (5)
- Nearly unbiased variable selection under minimax concave penalty
- SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
- A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
- Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
- A Tight Bound of Hard Thresholding
Cited by in corpus (15)
- Fast Stochastic Methods for Nonsmooth Nonconvex Optimization
- Estimating Differential Latent Variable Graphical Models with Applications to Brain Connectivity
- VR-SGD: A Simple Stochastic Variance Reduction Method for Machine Learning
- Stochastic Alternating Direction Method of Multipliers with Variance Reduction for Nonconvex Optimization
- A Unified Framework for Low-Rank plus Sparse Matrix Recovery
- A Universal Variance Reduction-Based Catalyst for Nonconvex Low-Rank Matrix Recovery
- Fast Low-Rank Matrix Estimation without the Condition Number
- A Hybrid Method of Combinatorial Search and Coordinate Descent for Discrete Optimization
- Linear convergence of SDCA in statistical estimation
- Federated Nonconvex Sparse Learning
- Stochastic Variance-reduced Gradient Descent for Low-rank Matrix Recovery from Linear Measurements
- SAGA and Restricted Strong Convexity
- Variance-Reduced Proximal Stochastic Gradient Descent for Non-convex Composite optimization
- Larger is Better: The Effect of Learning Rates Enjoyed by Stochastic Optimization with Progressive Variance Reduction
- A Knowledge Transfer Framework for Differentially Private Sparse Learning