Introduction
In high-dimensional statistics, we frequently encounter scenarios where the number of features ($p$) vastly exceeds the number of samples ($n$). To ensure models remain interpretable and computationally feasible, practitioners often impose a cardinality constraint, such as $\|w\|_0 \leq k$, forcing the model to select only the most relevant features. Iterative Hard Thresholding (IHT) has emerged as a premier greedy algorithm for these problems due to its efficiency and scalability. However, while its ability to recover true parameters has been well-studied, its generalization performance—how well it performs on unseen data—remained a significant theoretical gap. This research addresses that gap by providing the first comprehensive generalization analysis for IHT through the lens of algorithmic stability.
Methodology: Stability over Uniform Convergence
Traditional statistical learning theory often relies on uniform convergence arguments, which can become loose or fail entirely in high-dimensional, non-convex settings like those defined by $\ell_0$ constraints. Instead, this paper utilizes algorithmic stability. The core intuition is that if an algorithm's output changes minimally when a single training point is modified, it is likely to generalize well to the population distribution.
To bridge the gap between stability theory and the discrete nature of hard thresholding, the authors analyze IHT under two key assumptions:
- Restricted Strongly Convexity (RSC) and Restricted Lipschitz Smoothness (RLS): These ensure the loss function behaves predictably when restricted to sparse vectors.
- Regularization Proxy: The authors theoretically examine an $\ell_2$-regularized version of the problem to stabilize the feature selection process during analysis.
Theoretical Results
The paper establishes three primary theorems that characterize the risk bounds of IHT under different model specifications. These results distinguish between "slow" rates ($O(n^{-1/2})$) and "fast" rates ($O(n^{-1})$).
Slow vs. Fast Convergence
- Theorem 1 (Slow Rate): For general misspecified models where the true relationship may not be perfectly sparse, IHT achieves a rate of $\tilde{O}(\sqrt{k/n})$. This confirms that IHT is statistically robust even when the underlying model assumptions are slightly violated.
- Theorem 2 & 3 (Fast Rates): Under a "strong-signal condition" (where important features are easily distinguishable from noise) or in well-specified models (where the true model is actually sparse), the rate improves significantly to $\tilde{O}(k/n)$. This jump in efficiency occurs because, under these conditions, IHT eventually identifies the correct support set, allowing it to behave like a standard convex optimizer on that subset.
Empirical Validation and Implications
The authors validated these theoretical bounds using synthetic sparse logistic regression ($p=1000, \bar{k}=50$). By varying the sample size $n$ and sparsity level $k$, they observed that the empirical excess risk closely followed the slopes predicted by their theorems.
Beyond sparse estimation, this stability-based framework offers a potential roadmap for analyzing other non-convex optimization problems. Specifically, the authors suggest these techniques could be extended to deep neural network pruning, where IHT-like methods are used to create efficient, sparse versions of massive models. Applying rigorous generalization bounds to the non-convex regime of deep learning remains a promising frontier for future research.
Summary updated