On Iterative Hard Thresholding Methods for High-dimensional M-Estimation
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. Finally, we extend our analysis to the problem of low-rank matrix recovery.
This paper presents a theoretical framework for analyzing hard thresh-holding methods for high dimensional inference. These methods take the general recipe of (in one interpretation) (1) taking a gradient step and (2) projecting this result onto a space such that the result is sparse (typically, the s largest entries of the result). The framework proceeds in a similar fashion as Negahban et al (2012), with smoothness and restricted strong convexity assumptions placed on the objective. The authors first present some general results, and next applications of the results to various relevant problem areas. A small section on related methods to projected gradient (which add an additional 'corrective' step of maximizing the objective on a restricted set). The paper concludes with some simulation studies comparing some thresholding methods to greedy and L_1 methods, which are popular sparsity approaches.On quality:Overall, extremely good. The results here are very interesting, and very general. The methods covered by these results are practical, and the applications covered argue strongly for the relevance of the general framework. I can only make a small criticism that the sub-section on GLMs was left as "should be possible"; my intuition is that this should not be a serious challenge, but might also not enough on its own for another paper.On clarity:This paper is quite dense, with a large number of both results and pages of supplemental material. The results are substantial and insightful, but there is a lack of text spent on exposing their meaning, or comparing these results to those obtained for other popular approaches (basically I'm thinking of regularized approaches). There is a little of this sort of discussion in the introduction. As far as the framework is considered, the authors did well giving insight in the proof sketch of Theorem 1. However, some key details are left to the appendix for Theorem 3. In particular, they claim that the loss need not be convex is not expanded upon. The application to noisy data is a key use case of this property, but that part of the proof is given an implication of another proof in the appendix: is there an insight to be gained from it this that could be stated there? There could be a reference that would give insight into where we have restricted convexity but not convexity.The experiments mostly showed improvements on run-time versus other common classes of approaches. This sort of analysis seems a little out of place given the area of study of the rest of the paper. While many of the results were given in terms of a iteration of a certain order of the algorithm, these ideas can't exactly be lined up with ideas from regularized methods (I admit to not looking up the FoBa results, which might have a similar quality). I'm not really sure that anything better could be done here anyway.On originality and significance:Overall, the paper offers highly original and highly significant results. Some parts of the main approach of the framework here are not entirely original. I do not see this as a major detraction from the ideas: I find it sensible that the notions of smoothness and restricted convexity are fundamental here as well.