Global solutions to high-dimensional sparse estimation problems with a folded concave penalty (FCP) have been shown to be statistically desirable but are strongly NP-hard to compute which implies the non-existence of pseudopolynomial time global optimization schemes in the worst case. This paper shows that, with high probability, a global solution to generalized linear models with minimax concave penalty (MCP), a specific type of FCP, coincides with a stationary point characterized by the significant subspace second order necessary conditions (S 3 ONC). Given that the desired S 3 ONC solution admits a fully polynomialtime randomized approximation scheme (FPRAS), we are able to demonstrate the existence of an FPRAS for this strongly NP-hard problem. We further demonstrate two versions of the FPRAS for generating the desired S 3 ONC solutions. One follows the paradigm of an interior point trust region algorithm and the other is the well-studied local linear approximation (LLA). Our analysis thus provides new techniques for global optimization of certain NP-Hard problems and new insights on the effectiveness of LLA.
Summary:  The paper studies the problem of global optimization of high-dimensional sparse estimators regularized by PCP (folded concave penalty). The main result is showing that under certain conditions, with high probability, the desired global solution is an oracle stationary point satisfying the so-called S^3ONC conditions. In light of this result and an existing polynomial-time algorithm for finding an S^3ONC solution, the global solution can be recovered with polynomial computational complexity. Numerical evidence is provided to show the theoretical predictions. 
Strong points:
-S1. The global optimization of non-convex (regularized) sparse learning models is a fundamental and challenging problem worth investigating.
-S2. The paper is well organized and clearly presented in general.  
Weak points:
-W1. The loss function in Equation (1) is lacking in explanation. It is claimed that “traditional statistical learning schemes often resort to” such a formulation. However, it looks like only the logistic loss explicitly admits such a form while some other widely used ones such as squared/hinge/exponential loss do not. So are there any concrete statistical learning models other than logistic loss falling exactly into this framework? It could be beneficial to provide a reference, if any, to this particular problem formulation in machine learning literature. 
-W2. The nominal generative model is not clearly defined. Usually, a key component of high-dimensional statistical analysis is to define a nominal statistical model for data generalization. I note the parameter vector of such a model is denoted as $\beta^{true}$ in this paper. However, the related data generation procedure seems completely missing in the statement of problem setups. Particularly, what’s the definition of the residuals W appeared in the assumption A2? 
-W3. The overall novelty of theory is limited. The main result established in Theorem looks closely related to the excess risk bounds established in [Liu & Ye 2019]. Actually, provided that the risk function $L(\beta)$ has (restricted) strong convexity in $\beta$, it follows immediately based on the first excess bound in Theorem 1 of [Liu & Ye 2019] that $\|\beta^* - \beta^{true}\|$ is well bounded from above. Thus if the minimum non-zero absolute value of $\beta^{true}$ is sufficiently larger than that upper bound, then it is naturally true that $\beta^*$ shares the same supporting set as $\beta^{true}$ which in turn implies that $\beta^*$ is an oracle solution and also is globally optimal under some more stringent conditions. Unless the author(s) can justify the value-added beyond the results in [Liu & Ye 2019] as sufficient, the degree of novelty of the current theory seems fairly low given that prior work.  
-W4. The proof of Theorem 1 has flaws. The proof of main result relies largely on Lemma 5 which basically bounds the cardinality $\|\beta^*-\beta^{true}\|_0$. However, when invoking Lemma 5, such a $L_0$ bound shifts to an $L_2$-norm one. This misleading point needs to be clarified.
-W5. The numerical study can be improved. The majority of the reported results is about the advantage of FCP over Lasso and ridge regression, which however is less relevant to the global recovery theory developed in the paper. I think the numerical study needs to be re-designed to put more focus on the effects of some key factors, e.g , the sample size n and the signal strength $\beta_\min$, on the global optimization performance. 
-W6. Concerning the fitness to venue, although somewhat relevant,  I am not sure the main topic of this paper (i.e., statistical analysis of high-dimensional GLM) would gain significant interests in the community of ICLR. Actually in my opinion, the novelty/importance of this work is more suitable to be evaluated in a high-dimensional learning theory intensive journal or conference rather than in a DL/RL conference.  
Minor issues: 
- M1. Check the correctness of notation $\beta$ in Definition 1. 
- M2. Equation (3): Why not directly writing out “$0 \in 1/n\sum_{i=1}^n…$”?
- M3. Statement of Theorem 1: satisfy -> satisfies. The quantities $t$ and $t’$ appeared in Theorem1 are hard to understand without further explanation. 
=== update after author response ===
Thank you for the response which is helpful for clarifying some of my concerns. However, after reading the revised paper, I am still not quite convinced that the current theoretical analysis is particularly novel given the results in [Liu & Ye 2019]. Also, it seems that the noconvexity of the considered problem mainly arises from the regularization term rather than the loss term, and thus can hard to be claimed as "central to ICLR".  In view of these, I choose to maintain my assessment of this paper as borderline leaning to rejection.