IHT dies hard: Provable accelerated Iterative Hard Thresholding

2017/12/26 by Rajiv Khanna, Anastasios Kyrillidis, Khanna, Rajiv +1 · 4 citations
Computer Science · Engineering · #Blind Source Separation Techniques #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Image and Signal Denoising Methods #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Numerical Analysis (math.NA) #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques

paper · pdf · doi:10.48550/arxiv.1712.09379

openalex publication_date 2017/12/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study --both in theory and practice-- the use of momentum motions in classic iterative hard thresholding (IHT) methods. By simply modifying plain IHT, we investigate its convergence behavior on convex optimization criteria with non-convex constraints, under standard assumptions. In diverse scenaria, we observe that acceleration in IHT leads to significant improvements, compared to state of the art projected gradient descent and Frank-Wolfe variants. As a byproduct of our inspection, we study the impact of selecting the momentum parameter: similar to convex settings, two modes of behavior are observed --"rippling" and linear-- depending on the level of momentum.

Citations

• Atomic Decomposition by Basis Pursuit
• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Approximation Algorithms for Model-Based Compressive Sensing
• On Iterative Hard Thresholding Methods for High-dimensional M-Estimation
• Faster Rates for the Frank-Wolfe Method over Strongly-Convex Sets
• Gradient descent with nonconvex constraints: local concavity determines convergence
• Accelerated Methods for Non-Convex Optimization
• Iterative hard thresholding for compressed sensing

Cited by

• Sparse Polyak with optimal thresholding operators for high-dimensional M-estimation
• A Recovery Guarantee for Sparse Neural Networks
• Sparse Polyak: an adaptive step size rule for high-dimensional M-estimation
• Between hard and soft thresholding: optimal iterative thresholding algorithms
• One Rank at a Time: Cascading Error Dynamics in Sequential Learning

Related

• Dual Iterative Hard Thresholding: From Non-convex Sparse Minimization to Non-smooth Concave Maximization
• Between hard and soft thresholding: optimal iterative thresholding algorithms
• Robustly Stable Accelerated Momentum Methods With A Near-Optimal L2 Gain and H_∞ Performance
• Rethinking Hard Thresholding Pursuit: Full Adaptation and Sharp Estimation
• Iterative Hard Thresholding with Adaptive Regularization: Sparser Solutions Without Sacrificing Runtime