Linear Convergence of Stochastic Iterative Greedy Algorithms with Sparse Constraints

Abstract

Motivated by recent work on stochastic gradient descent methods, we develop two stochastic variants of greedy algorithms for possibly non-convex optimization problems with sparsity constraints. We prove linear convergence in expectation to the solution within a specified tolerance. This generalized framework applies to problems such as sparse signal recovery in compressed sensing, low-rank matrix recovery, and covariance matrix estimation, giving methods with provable convergence guarantees that often outperform their deterministic counterparts. We also analyze the settings where gradients and projections can only be computed approximately, and prove the methods are robust to these approximations. We include many numerical experiments which align with the theoretical analysis and demonstrate these improvements in several different settings.

References in corpus (3)

• Large-Scale Convex Minimization with a Low-Rank Constraint
• Decoding by Linear Programming
• Iteration Complexity of Randomized Block-Coordinate Descent Methods for Minimizing a Composite Function

Cited by in corpus (8)

• Analog to Digital Cognitive Radio: Sampling, Detection and Hardware
• A Tight Bound of Hard Thresholding
• Nonconvex Sparse Learning via Stochastic Optimization with Progressive Variance Reduction
• A Hybrid Method of Combinatorial Search and Coordinate Descent for Discrete Optimization
• Inexact Gradient Projection and Fast Data Driven Compressed Sensing
• Efficient Relaxed Gradient Support Pursuit for Sparsity Constrained Non-convex Optimization
• Greedy methods, randomization approaches and multi-arm bandit algorithms for efficient sparsity-constrained optimization
• On The Projection Operator to A Three-view Cardinality Constrained Set