Linear Convergence of Stochastic Iterative Greedy Algorithms With Sparse Constraints

DOI10.1109/TIT.2017.2749330MaRDI QIDQ4566535zbMATH OpenOpenAlexFDO

Authors

Publication date 27 June 2018

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1407.0088

Mathematics Subject Classification ID

Stochastic programming (90C15) Applications of mathematical programming (90C90) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

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.

Cited in

(17)

• Stochastic greedy algorithms for multiple measurement vectors
• Consistent online Gaussian process regression without the sample complexity bottleneck
• Weighted thresholding homotopy method for sparsity constrained optimization
• scientific article; zbMATH DE number 6982922 (Why is no real title available?)
• A tight bound of hard thresholding
• Decomposable norm minimization with proximal-gradient homotopy algorithm
• Dual iterative hard thresholding
• scientific article; zbMATH DE number 7307474 (Why is no real title available?)
• Improved RIP-based bounds for guaranteed performance of two compressed sensing algorithms
• Iterative hard thresholding for low CP-rank tensor models
• Stochastic privacy-preserving methods for nonconvex sparse learning
• Iterative singular tube hard thresholding algorithms for tensor recovery
• Stochastic variance reduced gradient for affine rank minimization problem
• The stochastic proximal distance algorithm
• Maximal residual coordinate descent method with k-means clustering for solving large linear least-squares problems
• A novel framework for online supervised learning with feature selection
• Linear convergence of reshuffling Kaczmarz methods with sparse constraints

This page was built for publication: Linear Convergence of Stochastic Iterative Greedy Algorithms With Sparse Constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4566535)