On Iterative Hard Thresholding Methods for High-dimensional M-Estimation
Prateek Jain∗ Ambuj Tewari† Purushottam Kar∗ ∗Microsoft Research, INDIA †University of Michigan, Ann Arbor, USA
Abstract
The use of M-estimators in generalized linear regression models in high dimensional settings requires risk minimization with hard $L_{0}$ constraints. Of the known methods, the class of projected gradient descent (also known as iterative hard thresholding (IHT)) methods is known to offer the fastest and most scalable solutions. However, the current state-of-the-art is only able to analyze these methods in extremely restrictive settings which do not hold in high dimensional statistical models. In this work we bridge this gap by providing the first analysis for IHT-style methods in the high dimensional statistical setting. Our bounds are tight and match known minimax lower bounds. Our results rely on a general analysis framework that enables us to analyze several popular hard thresholding style algorithms (such as HTP, CoSaMP, SP) in the high dimensional regression setting. We also extend our analysis to a large family of “fully corrective methods” that includes two-stage and partial hard-thresholding algorithms. We show that our results hold for the problem of sparse regression, as well as low-rank matrix recovery.
中文速览
在高维统计场景下，当变量数远超样本数时，用M估计量（M-estimator）做稀疏回归或低秩矩阵恢复需要求解带硬约束的非凸优化，而最实用的迭代硬阈值（Iterative Hard Thresholding，IHT）类算法此前只有在"受限等距条件数接近1"这一极苛刻假设下才有理论保证，现实中变量高度相关时条件数可以任意大，已有分析因此完全失效。本文的核心贡献是首次在仅要求损失函数满足受限强凸（RSC）和受限强光滑（RSS）的宽松条件下，为IHT及HTP、CoSaMP、SP等一系列硬阈值算法建立了统一的收敛理论——关键技巧在于把投影步的稀疏度放宽到真实稀疏度的$O((L/\alpha)^2)$倍，从而让硬阈值操作产生足够强的压缩效果。理论结果表明，这些方法在稀疏线性回归和低秩矩阵恢复中均能达到已知的极小极大最优统计误差界，与$L_1$凸松弛方法相当，但实验显示其速度可快出数个量级，从而真正打通了IHT类算法在高维统计推断中的理论与实践之间的鸿沟。
原文 arXiv:1410.5137;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1410.5137v2