On Quadratic Convergence of DC Proximal Newton Algorithm in Nonconvex Sparse Learning
We propose a DC proximal Newton algorithm for solving nonconvex regularized sparse learning problems in high dimensions. Our proposed algorithm integrates the proximal newton algorithm with multi-stage convex relaxation based on the difference of convex (DC) programming, and enjoys both strong computational and statistical guarantees. Specifically, by leveraging a sophisticated characterization of sparse modeling structures (i.e., local restricted strong convexity and Hessian smoothness), we prove that within each stage of convex relaxation, our proposed algorithm achieves (local) quadratic convergence, and eventually obtains a sparse approximate local optimum with optimal statistical properties after only a few convex relaxations. Numerical experiments are provided to support our theory.
Summary:
This paper considers a DC (difference of convex) approach to solve *sparse* ERM problems with a non-convex regularization (in high dimensions). The specific non-convex regularizer studied in this paper is the capped l1 penalty. Now, given a particular convex relaxation via the DC approach, this paper proposes to solve the problem using proximal Newton. 
The paper analyses the l2 convergence of their solution (at any step of the convex relaxation) to the truth, and shows that it enjoys quadratic convergence to stastical rates. The analysis is contingent on a Sparse Eigenvalue (similar to RSC) condition and a restricted Hessian smoothness condition. 
Comments:
Overall, this is a well written paper and the results presented seem sound. I do however have the following questions/comments:
1. What is T in the warm initialization step of the proposed algorithm ? What does it scale as i.e. what is its dependence on other constants involved in the proof ?
2. It would be good if the authors could provide a more detailed comparison with [36] in the related work. It seems that [36] also considers proximal Newton. However, [36] only considers a convex regularizer. Is another consequence of this work also that the analysis of [36] can be improved with weaker conditions of this paper ?
3. Theorem 6 shows that for large enough K, and small s' (i.e. none or few weak signals), the algo in this paper can yield a l2-rate of O(\sqrt{s*/n}). However, if I am not wrong, there is also a minimax lower bound of O(\sqrt{s* log d / n}) i.e. an extra log d factor (for example, see Theorem 1(b) in https://arxiv.org/abs/0910.2042). Am I missing something here ? How can these two rates be reconciled ?
4. In the experiments, the authors should specify how \beta (the tuning parameter for capped l1) was chosen.
EDIT: I have seen the authors' response, and my rating stands.