Iterative Hard Thresholding with Adaptive Regularization: Sparser Solutions Without Sacrificing Runtime

Kyriakos Axiotis, Maxim Sviridenko

TL;DR

This paper introduces Regularized IHT, a simple yet powerful modification to the classic Iterative Hard Thresholding algorithm. By adding an adaptive regularization term, the authors improve the theoretical sparsity guarantee from $O(s\kappa^2)$ to $O(s\kappa)$—a significant leap for ill-conditioned problems—while maintaining the lightning-fast runtime that makes IHT a favorite for large-scale machine learning.

What Problem Does This Paper Address?

Sparse optimization is a cornerstone of modern data science. Whether you are trying to make a neural network smaller (model compression), interpret a genomic dataset, or recover a signal from limited measurements (compressed sensing), the goal is the same: minimize a convex function $f(x)$ subject to the constraint that the solution $x$ has at most $s$ non-zero entries.

The "gold standard" for speed in this area is Iterative Hard Thresholding (IHT), which essentially performs gradient descent and then "prunes" the smallest values to maintain sparsity. However, IHT has a theoretical weakness: its performance depends heavily on the condition number ($\kappa$) of the function—a measure of how "stretched" or "squashed" the optimization landscape is.

Standard IHT guarantees a solution with a relaxed sparsity of $O(s\kappa^2)$. For ill-conditioned problems (where $\kappa$ is large), this means the algorithm might return a solution that isn't actually very sparse. Previous attempts to fix this (like the ARHT algorithm) achieved better sparsity ($O(s\kappa)$) but were computationally expensive, requiring complex re-optimization at every single step.

Methods

The authors propose a "surprisingly simple tweak" to IHT. Instead of optimizing the original function $f(x)$, they optimize a regularized version: $$g(x) = f(x) + \frac{\beta}{2} \sum_{i=1}^n w_i x_i^2$$ where $\beta$ is a smoothness constant and $w$ is a vector of non-negative weights.

The magic lies in how these weights are handled. The algorithm uses an adaptive regularization framework:

  1. Start Uniform: All weights $w_i$ start at 1, effectively penalizing all entries equally.
  2. Learn the Support: In each iteration, the weights are updated based on the current solution. If an entry $x_i$ is large, its corresponding weight $w_i$ is decreased.
  3. Bias Toward Zero: The regularization term biases the solution toward zero, but as the algorithm "learns" which entries are important for the optimal solution, it lifts the penalty on those specific entries.

Unlike previous methods, this version is deterministic, does not require knowing the optimal function value $f(x^*)$ in advance, and avoids the "outer binary search" overhead.

Datasets

The authors evaluated their algorithm on both synthetic and real-world benchmarks:

  • Real-world Data:
    • UCI "YearPredictionMSD": A regression dataset used to predict the release year of songs.
  • rcv1: A large-scale binary classification dataset of newswire articles.
  • Synthetic Data:
    • Hard IHT Instances: Specifically constructed "adversarial" functions where standard IHT is known to get stuck in local minima.
  • Random Linear Measurements: Standard compressed sensing setups using Gaussian measurement matrices.

Key Insights and Ideas

  • Breaking the $\kappa^2$ Barrier: The move from quadratic to linear dependence on the condition number ($\kappa$) is the headline result. In practical terms, if a problem has a condition number of 10, the new algorithm might require 10 times fewer non-zero entries than standard IHT to reach the same accuracy.
  • Local Minima Characterization: The authors provide a clever proof showing that if the algorithm gets "stuck" (i.e., doesn't make progress on the regularized function), it must be because the current solution is highly correlated with the true, hidden sparse support. This "failure" actually provides the exact information needed to update the weights and escape the local minimum.
  • Generalization to Low-Rank Optimization: The framework isn't just for vectors. The authors show it can be extended to matrices (low-rank optimization), improving the rank dependence from $\kappa^2$ to $\kappa$ there as well.

Key Results

  • Better Accuracy at Same Sparsity: On the UCI and rcv1 datasets, Regularized IHT achieved roughly 17% lower excess loss than standard IHT for the same fixed sparsity level.
  • Robustness to Initialization: In "hard" synthetic instances where standard IHT failed to make any progress (getting stuck at 100% error), Regularized IHT successfully reduced the loss by over 80%.
  • Efficiency: The authors implemented the algorithm in Python (using NumPy) and confirmed that the per-iteration runtime is essentially identical to standard IHT, requiring only $O(n)$ additional time to update weights.

Limitations and Future Work

  • Parameter Tuning: The algorithm introduces a weight step size parameter ($c$). While the authors provide a theoretical value, they note that in practice, tuning $c$ presents a tradeoff between runtime and accuracy.
  • Matrix Complexity: While the theory for low-rank optimization is improved, the matrix version still requires multiple Singular Value Decompositions (SVDs) per iteration. Transforming this into a more efficient "Matrix IHT" style algorithm is flagged as an interesting future direction.
  • Logarithmic Dependence: In the low-rank case, there is still a $\log(1/\epsilon)$ dependence on the error parameter that the authors suspect could be removed with a more refined analysis of operator non-commutativity.

Summary updated

Abstract

We propose a simple modification to the iterative hard thresholding (IHT) algorithm, which recovers asymptotically sparser solutions as a function of the condition number. When aiming to minimize a convex function $f(x)$ with condition number $\kappa$ subject to $x$ being an $s$-sparse vector, the standard IHT guarantee is a solution with relaxed sparsity $O(s\kappa^2)$, while our proposed algorithm, regularized IHT, returns a solution with sparsity $O(s\kappa)$. Our algorithm significantly improves over ARHT which also finds a solution of sparsity $O(s\kappa)$, as it does not require re-optimization in each iteration (and so is much faster), is deterministic, and does not require knowledge of the optimal solution value $f(x^*)$ or the optimal sparsity level $s$. Our main technical tool is an adaptive regularization framework, in which the algorithm progressively learns the weights of an $\ell_2$ regularization term that will allow convergence to sparser solutions. We also apply this framework to low rank optimization, where we achieve a similar improvement of the best known condition number dependence from $\kappa^2$ to $\kappa$.
BibTeX
@inproceedings{axiotis2022iterative,
  author = {Kyriakos Axiotis and Maxim Sviridenko},
  title = {{Iterative Hard Thresholding with Adaptive Regularization: Sparser Solutions Without Sacrificing Runtime}},
  booktitle = {International Conference on Machine Learning},
  year = {2022},
  url = {https://openreview.net/forum?id=YOQGweED3l},
}
Figure