Stability and Risk Bounds of Iterative Hard Thresholding

Xiao-Tong Yuan, Ping Li

Abstract

This paper provides the first comprehensive theoretical analysis of the generalization performance of the Iterative Hard Thresholding (IHT) algorithm. By leveraging the framework of algorithmic stability, the authors prove that IHT—a computationally efficient greedy method—achieves generalization bounds comparable to the exact (but NP-hard) best subset selection, even when the underlying model is misspecified.

Introduction

In high-dimensional statistics, the objective is often to identify a sparse model that utilizes only a few features ($k$) from a large pool ($p$). While $\ell_0$-constrained Empirical Risk Minimization ($\ell_0$-ERM) is the gold standard, solving it exactly is NP-hard. Iterative Hard Thresholding (IHT) serves as a popular greedy alternative, alternating between gradient descent and a hard thresholding step. Although IHT's parameter recovery properties are well-studied in compressed sensing, its predictive performance on unseen data remained an open question. This research fills that gap by establishing risk bounds specifically for the IHT algorithm, accounting for its iterative nature and potential for local optima.

Methodology: Algorithmic Stability

The authors utilize Algorithmic Stability as their primary analytical tool. An algorithm is considered stable if small changes in the training data do not significantly alter the resulting model. The primary challenge with IHT is the potential instability of its "support set" (the indices of non-zero features). To address this, the authors propose two strategies:

  1. Union Probability Argument: Analyzing IHT as a regularized variant and applying a union bound over all possible $k$-sparse support sets.
  2. IHT-Stability: Introducing a new condition that quantifies the sensitivity of the hard-thresholding operation to perturbations. If the population risk is IHT-stable, support recovery becomes significantly more robust.

Theoretical Risk Bounds

The paper establishes several tiers of convergence rates for "excess risk"—the difference between the IHT model's error and the best possible sparse model's error. These results are summarized in the table below.

Summary of risk bounds for Iterative Hard Thresholding under various conditions.

The analysis reveals that IHT achieves "fast" generalization rates under specific conditions, such as high signal-to-noise ratios. In general misspecified cases, a "slow" rate of $\tilde{O}\left(\sqrt{\frac{k \log n \log p}{n}}\right)$ is guaranteed. However, with IHT-stability or strong-signal conditions, these rates improve significantly, sometimes removing the explicit dependence on $k$ or achieving $1/n$ scaling.

Empirical Validation

To validate these theoretical findings, the authors conducted experiments using synthetic datasets:

  • Sparse Logistic Regression: Features sampled from a multivariate Gaussian distribution with labels generated via a sigmoid function.
  • Sparse Linear Regression: Standard linear models with Gaussian noise.

These controlled environments allowed for precise manipulation of sparsity ($k$), dimension ($p$), and sample size ($n$), confirming the predicted scaling laws.

Discussion and Limitations

A key insight of this work is that IHT is not merely a heuristic but a statistically principled method. Its generalization capability is intrinsically tied to the stability of the features it selects. When the signal is strong enough to make feature selection "decisive," the error decreases much faster.

However, the theory relies on Restricted Strong Convexity (RSC) and Restricted Lipschitz Smoothness (RLS) conditions, which can be difficult to verify for complex loss functions. Furthermore, the "fast rates" necessitate a "strong-signal" condition, which may not hold in real-world datasets with weak or decaying signals. Future work could involve extending this stability-based framework to non-convex settings like deep neural network pruning, where IHT is frequently applied.

Summary updated

BibTeX
@inproceedings{yuan2021stability,
  author = {Xiao-Tong Yuan and Ping Li},
  title = {{Stability and Risk Bounds of Iterative Hard Thresholding}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2021},
}
Figure