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

Kyriakos Axiotis, Maxim Sviridenko

Introduction

In machine learning and signal processing, finding a sparse solution—a model where most parameters are exactly zero—is crucial for creating smaller, faster, and more interpretable models. The standard workhorse for this task is Iterative Hard Thresholding (IHT). While IHT is incredibly fast and widely used in large-scale applications, it suffers from a theoretical weakness: its sparsity guarantee degrades quadratically with the problem's condition number.

This paper introduces Regularized Iterative Hard Thresholding (RegIHT), a clever modification that finds significantly sparser solutions without increasing computational cost. By adaptively "learning" regularization weights during optimization, RegIHT improves the theoretical sparsity guarantee from a quadratic dependence on the condition number ($O(s\kappa^2)$) to a linear one ($O(s\kappa)$), matching the best-known bounds while remaining drastically faster than previous state-of-the-art methods.

The Bottleneck in Sparse Optimization

Standard IHT operates by performing a gradient descent step followed by a "hard thresholding" operation that retains only the top $s$ largest values. To guarantee convergence to a good solution, IHT requires a "relaxed" sparsity level of $O(s\kappa^2)$, where $\kappa$ is the condition number (a measure of how "stretched" the function is).

Previous attempts to improve this bound, such as the ARHT algorithm, successfully achieved a tighter $O(s\kappa)$ sparsity. However, they were painfully slow in practice because they required solving a computationally expensive mini-optimization problem at every single iteration. The authors of RegIHT sought to achieve the best of both worlds: the tight sparsity bound of ARHT and the raw speed of standard IHT.

Adaptive Regularization: The Core Innovation

The primary innovation in RegIHT is Adaptive Regularization. Instead of strictly minimizing the original function $f(x)$, the algorithm minimizes a regularized version: $$g(x) = f(x) + \frac{\beta}{2} \|x\|^2_{w,2}$$ where $w$ is a vector of non-negative weights.

The algorithm dynamically adjusts these weights through a three-step process:

  1. Initialization: All weights start at 1, penalizing all features equally.
  2. The Step: A modified IHT step biases the solution toward zero based on the current weights.
  3. The Update: If the algorithm fails to make sufficient progress on the main objective, it uses this stall as a signal. It assumes the current solution is pointing toward the "true" support of the optimal solution and decreases the weights for the active features. This effectively "learns" which parts of the vector should be allowed to remain non-zero.

This deterministic approach avoids the expensive re-optimization loops of previous methods and does not require prior knowledge of the optimal function value. The authors also successfully extended this framework to Low-Rank Optimization for finding sparse matrix spectrums.

Key Insights

  • Local Minima as Signals: The most profound insight of RegIHT is that "getting stuck" is not a failure, but valuable information. The authors prove that if IHT stops making progress on the regularized function, a significant portion of the current solution's "mass" must reside within the true optimal support.
  • Weighting vs. Dropping: Unlike previous algorithms that randomly dropped features to escape local minima, RegIHT uses a continuous, deterministic weighting system, resulting in a much more stable optimization path.

Empirical Results

The authors evaluated RegIHT on both real-world datasets (YearPredictionMSD, rcv1) and synthetic tasks, yielding impressive results:

  • Sparsity Efficiency: RegIHT successfully achieves the $O(s\kappa)$ sparsity bound, bridging a significant theoretical gap in sparse optimization.
  • Real-World Performance: On the year and rcv1 datasets, RegIHT reduced the excess loss by approximately 17% compared to standard IHT at the same sparsity level.
  • Robustness on Hard Instances: In specially constructed synthetic cases where standard IHT completely failed (getting stuck at 1.0 error), RegIHT successfully reduced the loss by over 70-80%.
  • Computational Speed: By avoiding re-optimization, RegIHT is roughly $s$ times faster than ARHT in terms of gradient evaluations.

Limitations and Future Directions

While RegIHT represents a major step forward, the authors note a few limitations. The algorithm introduces a weight step size parameter, $c$. Although a theoretical value is provided, it requires practical tuning to perfectly balance runtime and accuracy.

Additionally, while the low-rank matrix extension is theoretically superior (improving condition number dependence from $\kappa^2$ to $\kappa$), it currently requires multiple Singular Value Decompositions (SVDs) and projections per iteration. Transforming this into a more efficient "Matrix IHT" style algorithm remains an exciting direction for future research. Finally, the low-rank case still exhibits a logarithmic dependence on the error parameter $\epsilon$, which the authors believe could be removed with more refined analysis.

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 [Axiotis & Sviridenko, 2021] which also achieves $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 l_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