Fully Polynomial-Time Randomized Approximation Schemes for Global Optimization of High-Dimensional Folded Concave Penalized Generalized Linear Models
Authors: Charles Hernandez
Hungyi Lee
Hongchen Liu
Venue:  (2020)
Keywords: statistical learning
FPRAS
global optimization
folded concave penalty
GLM
high dimensional learning

Abstract: 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 a pseudo-polynomial time global optimization schemes in the worst case. This paper shows that, with high probability, a global solution to the formulation for a FCP-based high-dimensional generalized linear model coincides with a stationary point characterized by the significant subspace second order necessary conditions (S$^3$ONC). Since the desired S$^3$ONC solution admits a fully polynomial-time approximation schemes (FPTAS), we thus have shown the existence of fully polynomial-time randomized approximation scheme (FPRAS) for a 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.

Under review as a conference paper at ICLR 2020
FULLY POLYNOMIAL-TIME RANDOMIZED APPROXI- MATION SCHEMES FOR GLOBAL OPTIMIZATION OF HIGH-DIMENSIONAL MINIMAX CONCAVE PENALIZED GENERALIZED LINEAR MODELS
Anonymous authors Paper under double-blind review
ABSTRACT
Global solutions to high-dimensional sparse estimation problems with a folded concave penalty (FCP) have been shown be statistically desirable but are strongly NP-hard to compute which implies the non-existence of pseudo- polynomial time global optimization schemes in the worst case. This paper shows that, with high probability. global solution to generalized linear models with minimax concave penalty (MCP), a specific type of FCP. coincides with a station- ary point characterized by the significant subspace second order necessary condi- tions ONCC) Given that the desired SNNC solution admits a fully polynomial- time randomized approximation scheme (FPRAS), existence of an FPRAS for this strongly NP-hard problem. We further demonstrate two versions of the FPRAS for generating the desired SON solutions. One fol- lows 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 the effectiveness of L.A.
able to demonstrate the
INTRODUCTION
This paper concerns global optimization of a folded concave penalized formulation of high- dimensional learning generalized linear models, which belongs to statistical/macchnee learning prob- lems such that the number of dimensions (or number of fitting parameters) is (much) larger than the number of samples n. This type of problem has recently become very common in a variety of engineering and scientific applications (Fan et al. 2014a Fan & Li 2006) including computational biology, speech recognition and image processing (Huang et al. 2016;) Algamal & Lee 2015 Xing et al. 2001; Palmer & Ostendorf 2001 Bagaria al. [012]] Paul et 2013). Globally minimal solutions to such a nonconvex learning formulation have been shown effective to guarantee desirable statistical performance in order address high dimensionality (Zhang & Zhang 2012). Nonethe- less, generating a global solution admits no pseudo polynomial-time algorithm, unless "p= NP Indeed, global optimality is shown strongly NP-hard to achieve by (Chen al. 2017 Huo & Chen 2010) while Chhen et al. (2014) show similar results for several related problems in regularized min- imization. In contrast the existing pessimistic result, we derive herein a fully polynomial-time randomized approximation scheme (FPRAS, as defined in 4 that theoretically ensures global mini- mality to to with high probability.
Specifically, consider a high- nigh-dimensional generalized linear model (GLM) as follows. Let X (1), "...,,,)) be the nxp design matrix with x; = (Ma, ..., Tip) i 1,.., n, and Y =(y). (y,,..., TT) be the n--imensional response vector. We will assume the design matrix X is fixed, while the mean of the response is given by Ely.] = va(x, 3true) for some known link function vb ; θ + R, where θ C R and gtrue = (gtrue, .... gerue) is the unknown vector of true parameters of the model. Such a setup can be seen as a generalization of linear regression models with the link function allowing for nonlinear transformations that enable more flexible approach to model estimation. The high-dimensional regression problem to estimate ztrue given knowledge of X, Y. and & in the undesirable scenario where p > 0. To that end, traditional statistical learning schemes

---

Under review as a conference paper at ICLR 2020
often resort to the following formulation:
1 Σ [x]x yr
(
Σ E(vi. Fs B)
(1)
which, according to traditional statistical theories, would result in over fitting in general under the high-dimensional setting.
To resolve over fitting, modern statistical theories favor modified formulation as below:
min B
2= :-
Σ PA()B)
where Px(1-D 1) is sparsity-inducing regularization term that penalizes any nonzero dimensions in the minimizer, and À > 0 is tuning parameter. Under the assumption that the true regression parameter grrue is sparse, a global optimizer to equation 2 has been shown effective to address over fitting for many choices of specific regularization functions Px. Indeed, of the most successful choices of Px is the much studied Lasso-based regularized (Tibshirani] 1996). aka, the & (-norm) penalty, which has been demonstrated entail desirable statistical properties (Bickel et al.) 2009) Negahban et al. 2012). Another admirable property of the Lasso is that, especially when applied to least squares linear regression, it yields an extremely tractable problem via variety of algorithms (Friedman et al. 2008; 2010). However, per (Zhao & Yu 2006; Fan & Li] (001)), Lasso is not selection consistent without strong irrepresentable condition and may sometimes introduce non- trivial estimation bias.
As a popular alternative to Lasso, the folded concave penalty (FCP) was first introduced by (Fan & Li 200T). There are mainstream examples of FCP functions, including the SCAD by (Fan & 2001) and MCP by (Zhang 2010). This paper will focus on MCP, defined as Px(
_0 [ax-sl+ ds for some fixed parameter a O. In contrast to the Lasso, the FCP regulaizations achieve variable selection consistency non-contingent on the irrepresentable condition and is demon- strated to be unbiased (Fan & Li 2001). Furthermore, (Zhang & Zhang 2012) demonstrated that the global solution to the FCP-regularized formulation leads to desirable recovery of the oracle solution.
Nonetheless, FCP problems are significantly harder to solve than Lasso, the new penalty term moves the problem outside the realm of convex optimization, (Chen et al.) (017)) even showed that any estimation problem with convex loss and folded concave regularization to be strongly NP-hard, ruling out the possibility of pseudo-polynomin pomlaalll-- global optimization algorithm. (Liu et al., 2016) were seemingly the first to propose a global approach to the problem called MIPGO which reformulates the problem into mixed integer program. Yet, the worst-case complexity of MIPGO in exponential time.
Perhaps for this reason, current literature tends to focus on local algorithms for the FCP-regularized learning problems. The local quadratic approximation algorithm by (Fan & Li 2001) is an exam- ple of majorization minimization algorithm, approach which is also related to the local linear approximation (LLA) algorithm proposed by (Zou& & Li 2008). LLA was further explored by (Fan) ct al. 2014b) showing the oracle property can be obtained with high probability despite the local ap- proach. (Mazumder et al., 2011 Fan & Lv 2011) demonstrate coordinate optimization approaches for FCP while (Wang al. 2014) used approximate regularization falh-following algorithm to obtain the optimal convergence rate to statistically desirable local solution. (Wang et al. 2013) analyzed the CCCP algorithm and showed under certain conditions that it asymptotically finds the oracle estimator. (Liu et al., 2017) took an algorithm agnostic approach by analyzing local solutions satisfying second order KKT conditions and showed desirable statistical properties like recovering the oracle solution and sparisty. These results discussed above primarily relate to FCP-regularized linear regression, a special case of GL.M where specifically the identity function. For analyses which encompass GLM's M's with FCP regularizers, (Fan & Lv Lv] (01T) showed that GLM's, even in ultra high dimensional variable selection problems, have oracle properties when using FCP regularization and demonstrated a coordinate optimization algorithm for finding local solutions. In the area of M- estimators, which is a further generalization our estimation method beyond even GLMs, (Loh & Wainwright 2013 Loh et al., 2017a) showed that under certain conditions all local solutions must be within statistical precision of the true parameter and its support while (Loh et al., 2017b) demon- strate two-step algorithm involving composite gradient descent to find local solution. Bian &
2

---

Under review as a conference paper at ICLR 2020
Chen 20144) demonstrate optimality conditions for class of nonconvex optimization problems
using nonlipseitz regularization.
From the numerous results pertaining to local solution schemes above, our research question is why local solutions are repetitively successful. In other words, are there certain geometric properties of the learning formulation equation with FCP that allow all local schemes perform well indepen- dent of the specific designs of the algorithmic procedures? Our answer to this question is affirma- tive; we show herein that all local solutions within an efficiently achievable sub-level set actually globally optimal. Those local solutions are characterized by the significant subspace second-order necessary conditions ONC) provable admit FPRAS's. The SONNC are weaker conditions than the standard second-order KKT conditions. As per this result, all S'ONN-guarantecing algorithms (which include large spectrum of local algorithms) belong to the class of FPRAS's s for global op- timization of the strongly NP-hard FCP-based learning problem. We subsequently develop theories for two specific algorithms of this type: one gradient- based method and the other is the same as the LLA.
worth noting that (Zhang 2010) provides conditions to establish the uniqueness of local so- lutions to FCP-based learning. When local solutions are unique, then any local optimization al- gorithms would ensure global optimality. However, a few critical assumptions are necessary to achieve the uniqueness result and, furthermore, many report numerical experiments, e.g., those in (Fan et al.] 2014b, Liu et al. 2017 2016) Fan & Li 2001) indicate the non-uniqueness of local so- lutions, instead. In contrast, our results in this paper imposes only standard assumptions commonly shared by flexible set of high-dimensiooal GLMs and are applicable even if the local solutions are non-unique. To our knowledge, this is the first geometric proof that global solutions coincide with pseudo-polynomial-ine computable local solutions in an FCP-based regression formulation with high probability. The resulting algorithms are the first few FPRAS's to this problem.
Two works with notable relations to our own are Liu et al. (2017) and Liu & Ye (2019). The first applies similar analytical framework to linear regression problems however our generalization to GLMs adds significant flexibility and it was unknown for their result that the oracle solution implies global optimality since was only as ohanh & Zhang (2012) that global optimality was known to potentially imply the oracle solution. Further, it is nontrivial to extend their existing result to global optimal results. (Liu & Ye 2019) on the other hand is a more general setup than our own though the tradeoff is that our rate is better and ONC solutions do not ensure global optimality to the in-sample training error for their setup.
The rest of this paper is organized follows. Section 2 goes through specific problem assumptions and explains the SONNC Section I contains our main result for global optimality and uses it to make additional claims for LLA. Section 4 contains numerical results verify theoretical findings. Section 3 provides concluding remarks.
In this paper will use Il-Ilp to denote the number of nonzero entries, | to denote the E -nomr if the argument is a vector, or cardinality if the argument is a set, ||-|| to denote the f2-norm, Il-Ilmaz denote the maximum norm and |l-IIman to denote the absolute value of the entry with the smallest magnitude. (-)+ is used equivalently to max(0, .). For any vector Vo is intended as (ez: :j E Q).
For any set Q, we denote the complement as ② In particular, let S be the true support set, that is, S == (j Srrue + 0} and its complement is S We occasionally use the term the "oracle solution" to refer the solution goracle defined as goracle E arg min 3:3,=0, VjęS
L(3). The oracle solution
a hypothetical solution which assumes prior knowledge the true support set and thus can be considered a theoretical benchmark.
SETUPS, PRELIMINARIES, AND ASSUMPTIONS
2.1
SETUPS AND ASSUMPTIONS
Our analysis will focus on sparse GLMs that have a fixed design matrix and satisfy the following assumptions:
(A1) Assume that
3

---

Under review as a conference paper at ICLR 2020
(i) bu 2 (x.
2 by 0 for all x E θ;
(ii) There exists K > 0 such that the design matrix satisfies A ||Xi11 < K for all j E [p]- Let the tuning parameter a in PA satisfy K < (bya)=
(A2) The vector of residuals W E R such that W = Ely X] is subgaussian( which means it satisfies that
P([(W, v)} 2 f] - rexp(-t//20") for all V: ||||| and any > 0;
(A3) There exists a sequence {ra 2 0: 1,,2, 1,2,....PP p} such that the following are satisfied:
(i) For any d1, d2 :1 < di S d2 S p,, we have rd, Td2i
(ii) There exists some p² 2|S] 5 - such that rp- > 0;
(iii) For all d: 1 d p, it holds that n || ra ra |/11 for any B E Re 11 S d.
Remark 1. Part [ of (AI) states that our link function is both strongly convex and continuously differentiable: that is, the gradient being Lipschitz continuous. Many types of traditional GLM problems satisfy this constraint including those for normal (linear regression), categorical (logistic regression), binomial, gamma and Poisson distributions, although in some cases the mild assumption on the boundedness of O has to be made. Even though the original domain of the link function can be unbounded, one may still consider its bounded subset given that it contains the vector of true parameters. Part [i) of (Al) can be assumed without loss of generality by normalizing the design matrix columns.
Remark 2. [A2) is a common assumption in the literature, for example (Negahban et al. 2012) WWang& et al. 2013)
Remark 3. Both (i) and [A2] are satisfied by a number of GLM setups, one example is linear regression. In such a setup, the response Y takes gaussian distribution, while the gradient of the link function (encoding E. X)) is the identity. Note, it is difficult to have one without the other, since the loss formulation]] is simply a log-likelihood maximization applied to a distribution within the class of exponential dispersion models (Jørgensen) [187]] Another classic example is logistic regression which is used for Bernoulli or binomial distributed Y along with a logit link function. It should be noted that we treat the matrix X as fixed, so its generative distribution is not important to the analysis outside of whether satisfies the assumptions and constraints mentioned. In the numerical experiments in Section 4 we use i..d. gaussian generation method since, discussed for Definition [ it means our design matrices will satisfy (A3] with high probability.
be understood to be a lower bound on the eigenvalues for principal sub-matrices of X X of dimension d x d for all E [p). For every d S V", the lower bounds are positive, meaning thut the smallest eigenvalues of the d x d principal sub-matrices are assumed positive.
Remark 4. [asumption[A3)]r
According to [Liu et al. 2017). Assumption [A3) for certain parameters, is provably a weaker condition than the restricted eigenvalue (RE) condition, as defined in Definition) [ below and first introduced by (Bickel et al. 2009 plausible assumption to allow for the desired recovery quality of Lasso. The RE condition is a common assumption in the high- dimensionn learning literature, such (Zhang et al. (0144) and (Fan et al.) (014bb).
Definition 1. (RE condition (Zhang et al. 2014)) The matrix X E REEP is said to satisfy the RE
condition if. for some Te > 0, it holds that 1 || 2 re ||811 for all 8 E U C($) where
C($) = {6- == (6,) E R² : 16g.1 < 318g1}. 8g.- == (8, j E Sr). and 85 := (6 E 5). Furthermore, the largest possible is said to be the restricted eigenvalue constant of X.
Random design matrices with with i..d rows generated following subgaussian distributions as in [A2] have been shown. to satisfy the RE condition with high probubility iZhou 2009) while propo- sition in Loh & Wainwright (2013) includes a proof that with high probability, restricted strong convexity (RSC) is satisfied for setup equivalent to own. Note that satisfaction RSC implies the RE condition above. Thus, within our setup. (A3) is also satisfied with high probability for our setting.
2.2 PRELIMINARIES ON S'NN
Our results focus on the OCC solutions, which has been formerly introduced by (Luu et al. 2017) in the special case of high high-dimensional linear regression as relaxation of the standard second-order
4

---

Under review as a conference paper at ICLR 2020
KKT conditions. The definition of ONC depends on the notion of first order necessary conditions (FONC) as below.
Definition (FONC), A solution 3 satisfies the first order necessary conditions (FONC) if
E 1/m Σ (xTTT) Vil x4 (P((0))000))) 1
(3)
where a(1 denotes the subdifferential I-
Definition 3 (S$ONC), A solution 3* satisfies the significant subspace second-order necessary con-
dition ONC) if satisfies FONC and for all j E ;)::0 [J: #0,
Q
20
(4)
(03,)² 1==8"
if the second derivative exists.
Remark The ONC can be intuited as the second order necessary condition applied only the dimensions where By * 0, i.e., the significant dimensions. Since the SNONC is weaker than the stan- dard second-ordes KKT conditions, any algorithm that guarantees the second-order KKT conditions be used to obtain SONC solution, by requiring be slower than necessary. One specifically SOCC guaranteeing approach, presented in (Liu Ye 2019) utilizes an interior point trust region algorithm in order guarantee an S C solution in polynomial time. This is the scheme which will be used later in Section 4
stringent optimality condition, may
3
MAIN RESULTS
We now present our theoretical results for global optimization of FCP penalized GLMs. All proofs can be found in the appendix. We will make use of short-hand notation:
BLasso E Earg min L(B) A/81.
(5)
Theorem Suppose assumptions (AI)
(A2) and (A3) with any 8' : 2/5).
Let 8r be
an arbitrary 3 OONC solution to equation with Px specified as the MCP. Assume that ((5*) S
Q (Btrue) + T for an arbitrary r
(1) Let the sub-optimality gap satisfies T Pa(ad)
(5- + +2pptt++ + 2t): (ii) choose (a(a 21 + 2 + +t' + - =11(0-2/7+20)+11 and
-
(iii) assume that the minimal signal strength satisfy
802 Trpbfn
8 rzbi
[ {1 Tp
|| min
22+
+
min
[S), PA(aA)|S++T
then the following statements hold
(a) 3 is an oracle solution with probability at least 1 - exp(-t
In (n(Fe) exp(-(0' +
1)(t' -mp)) T-exp(-- +11))pp)
(b) 3 is both an oracle solution and an globally optimal solution to equation with probability 1-2exp(-t p In( (f 2 exx + 1)(t' Inp)) 1-expl
(t' pi)
1 I-exp( ll)p)
Remark 6. Theorem 7 (especially in the second statement) is perhaps the first result that establishes set of conditions for any SONC solution be globally optimal with high probability. Further, this result algorithu independent which allows for greater flexibility compared to most existing results as in (Loh al.) 2017b) and Fan & Lv (011) which rely on specific algorithm choice.
Remark 7. The second part follows quite easily from the first due to the uniqueness of goracte as well as the fact that gopt must also an 3 ONC solution. Thus by applying the first part of the Theorem to Bopt are able to show that both our arbitrary 3 and gopt coincide with the unique goracte
5

---

Under review as a conference paper at ICLR 2020
Remark 8. The above constraints on I, Pa(a)) and [|03 may initially seem disparate but can all be converted to constraints on the sample size n as is shown in Corollary [ below. This is possible because I' can be bounded by some function of n1 for some Y > 0. Given that, it can be seen that the lesser side of inequalities (i),(i)) and (iii) go to 0 as n grows. Further discussion of how this is achieved for Corollary can be found in Remark [2
Corollary 1. Assume I 2 1, by S 1, and 2 1. Let 3 be an ONC solution to equation 2 Let assumptions (AI)
[A2] and the RE condition as defined in Definition 1 hold. Assume that 2(8*) S (BBLas80 almost surely, where 3Lusso is the optimal solution to the Lasso problem with Imp penalty coefficient XLasso =oV n²-572 where Y E [0, 1] is an arbitrary scalar. Let X -2
Iup 2a12
and a E [8,1)) There exist problem independent constants C1 >> 0,C² > O and C2 > 0 such that if
2/7
Ci bi
8 bi
80² Imp
11 > max
C2
C3 Btrue
(6)
1
1
B8rd
min
Then 3" is the global solution to with probability at least - C4 exp(p In Cg exp(-Crbun In(p)) for problem independent constants Ca. Cs Co and C7
Remark 9. Corollary | indicates that for 7 > O, the global optimal solution coincides with com- putable SONC solution with overwhelming probability given that the sample size meets certain requirements. It should specifically be noted that the relationship between and p require only
Ing O1), which ensures the applicahility to the high-dimensional setting even if n. p.
w7/2
Remark 10. &Liu & Ye 2019) has derived gradient-bat based algorithm that provably ensures an S ONC solution at grendo-polynomiae -ime complexity. When is property large, this pseudo- polynomial aonomial-time algorithm enables a straightforward design of an FPRAS for generating the global optimal solution as follows.
FPRAS: A pseudo-polynomial-ine time algorithm that generates global optimum at high probability
Step Initialize the parameters 6, >, a, à, and / by solving equation 5
Step 2. If Case 1: 1,811 E (0, aA) for some j = 1,..... P. then choose an arbitrary & E {j : 18/ E
(0, aA)} and solve
3 arg min (in 8 PX((8))
s.t. (8- - 0/2 s 82
and let get1 = =/ Vj + t. Go to Step 3.
Else Case 2: If 3/ & (0, aA) for all j = 1, ..., p then for all j = 1, M..,;:
If B8 0 then g à ||[ (( }1r1 - > sign(-[VL
If |18| 2 aA, then 3/+ B3 à [V Go to Step 3.
Step 3. Algorithm stops if |8/] & (0, ad) and || - f || < 8. Otherwise, let k := k + 1 and go to Step 2.
Remark 11. Here, the above algorithm has iteration complexity of O ( -
(((rrt))
(ax((1)())) b,./2)-1,,00 2b (1/a-ba/2))1) b1 1/5²) for any 7-accuracy ONC solution. In this iteration complexity, all the quantities are verifiably upper bounded by polynomial function of dimensionality p and the desired accuracy 1/7. Furthermore, BLasso solution to a convex problem, which be generated within polynomial time and the per-iteration problem admits closed form, whose complexity is strongly in polynomial--ie time. Therefor, this algorithm is an FPRAS in generating an S ONC (global) solution where the term FPRAS is defined in Desinition 4
Definition 4. (FPRAS) Let f :: L - Rt be a function representing the optimal solution to a problem. Let A be probabilistic algorithm, which takes as an input an instance of the problem x E L, and a parameter e > O. We call A a fully polynomial randomized approximation scheme, if it has the following properties

---

Under review as a conference paper at ICLR 2020
the algorithm returns value within the required precision with probability at least 1/2.
[(x) ((a)) =f(()] 1/2
the running time of A is polynomial in both the size of the input and the precision 1/c
Note that the specific probability bound is fairly arbitrary as long it is constant probability bounded away from 1/2 (Vazirani 2013).
Remark 12. We are able to remove from the result by bounding the performance difference between gtrue and glosso using similar techniques in Bickel et al. (2009). In order to this bound for our ONC solution, we require that 2(3²) S ((BLasso).. However, this can generally be obtained by inifializing any S ONC guaranteeing algorithm with BLosso in similar fashion to Fan et al. 2014b) for LLA. The FPRAS above follows the same initialization scheme.
Remark 13. The above specification of values for X and X Laass can be thought of as examples rather than strict requirements. A closer examination of the proof for Corollary [ will reveal that the values for X and X LLasso can be chosen in much more flexible fashion, though the corresponding values of Ci through C7 may be different for different combinations of X and Lasss
The techniques used in the proof of Theorem I can be used to provide insights into other optimiza- tion schemes. As example, we apply the same analysis the state-of-the-art FCP-based algorithm, LLA, using the framework in (Fan et al. 2014b) as a starting point.
LLA: local linear approximation.
Step 1. Set k 0. Initialize the algorithm with , B Faasso where GLasse is generated by solving equation Let N be the maximal iteration number.
Step 2. For all 1, ..... N, solve the following convex program to generate g3++1
gkt1 E arg min C(B) +
Σ
PX(1)) 18,1,
JE(p]
where PK is the first derivative of Pa. Let k +
We can show that in fact the LLA is another FPRAS that achieves the global optimal solution. The proof of this can be found in the appendix.
Corollary 2. For problem equation
(a + 1)2, A and the RE condition in Definition by by
If
113g gtrue Ilmin
max( (3 taxaamo 22/2 st 20 st2stt 26,
bire holds, the following holds.
bilan/bu))/2
(a) The LLA algorithm initialized with 3Lasso converges to the oracle solution in two iterations with probability 1 Φ0 Φ1 02 where
do = p grruel max A) $ epe
-(2 (2 2nbba
8
P[| s5 (Boracte)
P(
mar A) S 1e)) expp(tt)) exxp(
-X3ab,n)
62 = P([ min
< <a))= < 25 exp(
(b) If in addition (AI) and (A2) holds, while the parameters of (a, satisfy that x² +15( and the and Px(aA) > -1((-11
Pa(a)) > 2nh; (1 T + 2ta) +
bin (p + +2 2ts) and let the minimal signal strength satisfy [1,ggael| Ummn 880 8o" (i- 22 2ts) + rghh min X2 [)) (a then the LLA algorithm ini- V roffi
tialized by gLasso converges to the global solution in two iterations with probability at least 20 ②1 62 03

---

Under review as a conference paper at ICLR 2020
where
Ø = P(Borade + B expl -ts + +p" Im( (n)))
+ cxp(-(0" + 1)(ta In 1
-mp)) (7)
1-exp(-t, + Imp)
and t1, 12, 13, 14 > are arbitrary constants.
Remark 14. Since each iteration of the LLA solves convex program, which can be done within polynomial-tines When n is properly large, the above theorem then indicates that the LLA another FPRAS in globally optimizing the FCP-based nonconvex formulation.
4 NUMERICAL EXPERIMENTS
4.1 EXPERIMENTAL SETUP
We focus tests sparse logistic regression. Our problem and data are implemented in a similar
way as (aa et al. 2014b). We construct gtrue as below: Firstly, Sigu is constructed randomly by choosing 10 elements of 3 and choosing the magnitude of each be uniform value within [1, 2]. Each value is chosen to be negative with probability .5. Then, the remaining entries Sgeu are set to be O. The design matrix X R=*X is constructed by generating iterations of x; (0, Σ)
where = (.5li 1oll Dxpp- We then generate using a Bernoulli distribution where P(y: = 1) = (1 + -- )-1 With this data, we train logistic regression model by invoking Algorithm 1 in solving equation 2 with MCP for SCONC solutions initialized with Lasso implemented in Python 3. The tuning parameters À and are obtained by cross validation following (Fan et al. 2014b).
We would like to ascertain whether our FCP classifier, obtained using SONCC methods, is actually the global optimal solution. We do this by taking each element of the FCP classifier and perturbing it to find a new potential solution. Each element's 's perturbation is independent and generated by a -raadoo N ( 1/)) rrandom variable. We then check if this perturbed classifier has better FCP regularized
performance on the training data than the FCP classifier. If not, repeat until either better solution found, or until 2000 perturbations have been tried.
Additionally, we compare solution's 's statistical performance to those of other popular regulariza- tion methods. Using the data generation method above, we obtain two sets of data, both with 100 samples. One set is for training the model, and the other is the test set for out-of-sample tests. We repeat the above process for 100 times to generate 100 training-and-test instances, each with 100 samples. We compare those trained using the method described above with Lasso solutions gener- ated by the global minimizer to equation 5 and an estimator generated by solving equation ( whenn when PA is substantiated by lg penalty, The Lasso and &a classifiers are solved using the scikit learn python library.
We compare the above estimators in terms of statistical performance for both l loss: 18 gtrue] and Eg loss: 1|3 gtrwel.. ||.
4.2 NUMERICAL RESULTS
Table I: Percent of time FCP beat all perturbations
n 100
100
n 100
n 100
p 500
p 1000
p 1500
p 2000
% Best FCP
100%
100%
100%
100%
Table I contains the numbers from optimality analysis. This technique did not yield single per- turbed solution that could beat the FCP classifier obtained from the FPRAS in any of our thousands of iterations.
shble the numerical results for the statistical performance measurements. We show the two performance measures for each of the three classifiers for tphree different problem types.
8

---

Under review as a conference paper at ICLR 2020
Table 2: Statistical performance of the four classifiers.
π = 100, p = 1000
100, =
1500
7 100, p = 2000
Classifier
Measure
Mean
Std. dev
Mean
Std. dev
Mean
Std. dev
MCP
E loss
13,909907
1,471911
14.818059
1.698191
14.506226
1,480686
l2 loss
4.108019
0.320061
4.304993
0.374453
4.489184
0.399441
Lasso
E loss
15.015975
1.039529
15.882654
1.29422
17.079414
1.545309
lg loss
4.3255
0.25996
4.397969
0.326336
4.433467
0.362707
l2 penalty
l loss
22.211963
0.791955
26.026067
0,966091
28.485075
0.993699
l loss
4.734209
0.241683
4.738025
0.296726
4.755959
0.296746
As expected, the FCP classifier generally outperformed the lasso and &y classifiers. The margins are fairly thin between FCP and lasso, especially compared to the standard deviation. Other values of and were tried but the results generally followed the same pattern.
As result tentatively conclude that numerical results align with theoretical results though further testing the global optimality probability would be valuable.
5 CONCLUSIONS
This paper investigates both the theoretical and empirical performance of FPRAS's on MCP regu- larized GLMs. Despite such problem being strongly NP-Hard, we have shown two FPRAS that achieve global optimality. To our knowledge this is the first probability bound for global optimiza- tion of FCP regularized GLMs using FPRAS. Further, the same technique other results in order to obtain global optimization bounds for wide variety of problems.
be used to extend
Though this paper focuses GLMs, further exploration will focus the question whether similar results can be found for more general problem classes under weaker assumptions. High-dimensional M-estimation problems could potentially be future avenue of investigation.
REFERENCES
Zakariya Yahya Algamal and Muhammad Hisyam Lee. Penalized logistic regression with the adap- tive lasso for gene selection in high-dimensional cancer classification. Expert Systems with Ap- plications, 42(23):9326 00029922662222-2222 2015.
Anurag Bagaria, Victor Jaravine, Yuanpeng J Huang, Gaetano T Montelione, and Peter Güntert. Protein structure validation by generalized linear model root-mean-square deviation prediction. Protein Science, 21(2):229-255 2012.
Wei Bian and Xiaojun Chen. Optimality conditions and complexity for non-lipschitz constrained optimization problems. Preprint, 2014.
Peter J Bickel, Yaacov Ritov, Alexandre Tsybakov, et al. Simultaneous analysis of lasso and dantzig selector. The Annals of Statistics, 37(4): 1705):1705-1733 2009.
Xiaojun Chen, Dongdong Ge, Zizhuo Wang, and Yinyu Ye. Complexity of unconstrained 12-1p minimization. Mathematical Programming, 143(1-2):711-83,, 2014.
Yichen Chen, Dongdong Ge, Mengdi Wang. Zizhuo Wang, Yinyu Ye, and Hao Yin. Strong np- hardness for sparse optimization with concave penalty functions. In Proceedings of the 34th International Conference on Machine Learning-Volune Volume 70, pp. 740-747. JMLR. org, 2017.
Jianqing Fan and Runze Li. Variable selection via nonconcave penalized likelihood and its oracle properties. Journal of the American statistical Association, 96(456):1348-131 2001.
Jianqing Fan and Runze Li. Statistical challenges with high dimensionality: Feature selection in knowledge discovery. arXiv preprint math/0602133, 2006.

---

Under review as a conference paper at ICLR 2020
Jianqing Fan and Jinchi Lv. Nonconcave penalized likelihood with np-dimensionality. IEEE Trans- actions on Information Theory, 57(8):5467- 2011.
Jianqing Fan, Fang Han, and Han Liu. Challenges of big data analysis. National science review, (2):293-33 314,,,34,,40 2014a.
Jianqing Fan, Lingzhou Xue, and Hui Zou. Strong oracle optimality of folded concave penalized estimation. Annals of statistics, 42(3):819, 2014b.
Jerome Friedman, Trevor Hastie, and Robert Tibshirani. Sparse inverse covariance estimation with the graphical lasso. Biostatistics, 9(3):432-441, 2008.
Jerome Friedman, Trevor Hastie, and Rob Tibshirani. Regularization paths for generalized linear models via coordinate descent. Journal of statistical software, 33(1):1, 2010.
Daniel Hsu, Sham Kakade, Tong Zhang, et al. A tail inequality for quadratic forms of subgaussian random vectors. Electronic Communications Probability, 17, 2012.
Hai-Hui Huang, Xiao Ying Liu, and Yong Liang. Feature selection and cancer classification via sparse logistic regression with the hybrid 11/2+ 2 regularization. PloS one, 11(5):0144675, 2016.
Xiaoming Huo and Jie Chen. Complexity of penalized likelihood estimation. Journal of Statistical Computation and Simulation, 80(7):747-759, 2010.
Bent Jørgensen. Exponential dispersion models. Journal of the Royal Statistical Society: Series (Methodological), 49(2):127-145, 1987.
Hongcheng Liu and Yinyu Ye. High-dimensional learning under approximate sparsity: A uni- fying framework for nonsmooth learning and regularized neural networks. arXiv preprint arXiv:1903.00616. 2019.
Hongcheng Liu, Tao Yao, and Runze Li. Global solutions folded concave penalized nonconvex learning. Annals of statistics, 44(2):629, 2016.
Hongcheng Liu, Tao Yao, Runze Li, and Yinyu Ye. Folded concave penalized sparse linear regres- sion: sparsity, statistical performance, and algorithmic theory for local solutions. Mathematical programming, 166(1-2):207-
2017.
Po-Ling Loh and Martin J Wainwright. Regularized m-estimators with nonconvexity: Statistical and algorithmic theory for local optima. In Advances in Neural Information Processing Systems, pp. 476-484, 2013.
Po-Ling Loh, Martin J Wainwright, et al. Support recovery without incoherence: A case for non- convex regularization. The Annals of Statistics, 45(6))2455-2482, 20
Po-Ling Loh al. Statistical consistency and asymptotic normality for high-dimensional robust m-estimators. The Annals of Statistics, 45(2):866-896, 2017b.
Rahul Mazumder, Jerome H Friedman, and Trevor Hastie. Sparsenet: Coordinate descent with nonconvex penalties. Journal the American Statistical Association, 106(495):1 1138, 2011.
Sahand N Negahban, Pradeep Ravikumar, Martin Wainwright, Bin Yu, et unified frame- work for high-dimensional analysis of m-estimators with decomposable regularizers. Statistical Science, 27(4):538-557, 2012.
David D Palmer and Mari Ostendorf. Improving information extraction by modeling errors in speech recognizer output. In Proceedings of the first international conference Human language tech- nology research, pp. 1-5, Association for Computational Linguistics, 2001.
Grégory Paul, Janick Cardinale, and Ivo F Sbalzarini. Coupling image restoration and segmentation: generalized linear model/bregman perspective. International journal of computer vision, 104 (1):69-93, 2013.
Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society. Series B (Methodological), pp. 267-288, 1996.
10

---

Under review as a conference paper at ICLR 2020
Vijay V Vazirani. Approximation algorithms. Springer Science & Business Media, 2013.
Lan Wang, Yongdai Kim, and Runze Li. Calibrating non-convex penalized regression in ultra- dimension. Annals of statistics, 41(55:2505, 2013.
Zhaoran Wang, Han Liu, and Tong Zhang. Optimal computational and statistical rates of conver- gence for sparse nonconvex learning problems. Annals of statistics, 42(6):2164, 2014.
Eric P Xing, Michael Jordan, Richard Karp, et al. Feature selection for high-dimensional genomic microarray data. In ICML, volume 1, pp. 601-608. Citeseer, 2001.
Cun-Hui Zhang. Nearly unbiased variable selection under minimax concave penalty. The Annals of statistics, 38(2):894-94,, 2010.
Cun-Hui Zhang and Tong Zhang. A general theory of concave regularization for high-dimensiinaal sparse estimation problems. Statistical Science, 27(4):576-53,, 2012.
Yuchen Zhang, Martin Wainwright, and Michael Jordan. Lower bounds on the performance of polynomial-time algorithms for sparse linear regression. In Conference on Learning Theory, pp- 921-948, 2014.
Peng Zhao and Bin Yu. On model selection consistency of lasso. Journal of Machine learning research, 7(Nov):2541-2566 2006.
Shuheng Zhou, Restricted eigenvalue conditions on subgaussian random matrices. arXiv preprint arXhv:0912.4045,, 2009.
Hui Zou and Runze Li. One-step sparse estimates in nonconcave penalized likelihood models. Annals of statistics, 36(4):1509, 2008.
A
APPENDIX
The Appendix is organized as below: Section A.1 presents the proofs for the main results, Sections A.2 and A.3 present central lemmata to be useful Section A.l
A.1
PROOF OF MAIN RESULTS
useful relationship in our proofs that, for an SONN solution 3rt within (,- 2 (Btrac)) + +I'} for any I > O. we have the following useful inequality under Assumption (AI)
b 2n
1 WTX8 + PACEDD < PA D) +r,
(8)
JES
JES
where 8* = 8" grrue This is obtained by invoking the strong convexity of th which leads to (x 2 (xx gtrue) + v/ (x: grrwe (xx 3r x! 3tree) 0.5 bi(x.] B x7 geruey?
Proof of Theorem First, given our assumption that (A1) holds, that (i) pr
2(S), (ii) 3 is
S8ONC satisfying ((3*) S Q(3true) + T for some r 2 0. and (iii) Pa(a)) > 2nh, (1 2/7 +
2(') 2(')+ 6 -1-28)
we can apply Lemma with p = ~" This means that | -trurelllee 11o S
6 with probability at least 1 exp(-(p) (f* 1)(t' In p)) --exp(-(p--")c'" ((( (lp)) From this, given
the additional assumption that (A3) holds, we can apply the second part of Lemma with P = 5
to get that for any f > 0, X(8* 312 < 8
b7n (ø* + + + 2t) + by (
|| Il)) (A(a))((S) - 11 ll)) + Т} holds with probability at least 1 exp(-t + 8r In 5
Given that for 2 arbitrary sets A and B
11

---

Under review as a conference paper at ICLR 2020
P(ANB) = (()) = (1-
=1- B[A P(B) P(B))(A41))
= - P(AIB)- P( P(A B)) 2 1- -
- P(B))
(9)
- exp(-10" + Therefor they hold simultancous with probability at least 1 - exp(-t exp(=+++ln(())) 1)(t' p)) 1-exp(-2 -t+hpp
The same sequence of arguments can be used to show that 3rr also satisfies || gtrue 11 S p t. and " || g(rue))l*
(i" + 2 +
) ,x (aa))((S))
(l))+)) with the same probability. Using again the union bound and DeMorgan's law, say 8 and fopt satisfy the above conditions simultaneously with probability - 2 exp( p In( +
2 exp + 1)( p))- 1-exp(-(p- (ppppp(--p">) (Ir'-Inp)) p]] With this, our I' assumption and our minimal
1-exp(-('+tn)
signal strength assumption, we can apply Lemma to show that 8 8opt with probability least
(= 1 - 2 exp( -t + 5r In )) 2 exp((- + 1)(t' - Imp)) T-exp( #1n)))
Proof of Corollary (3)
7 First need to bound r. In order to do this the lasso problem EiEN UB, Iz x..8.) +
Σ
Mlsss /y] as well as the concavity of MCP over positive
jEP
values to get the following 2 inequalities
lasso
(aa00gBlaae (glassn) < ② Ilsss Qlassn(gtrur)
(BJasss Is, Ir. y1) - E(8rruc 24, vi) S
Σ jEP
Jasso (18)rue - 1
(10)
iEN
X Jasso 3lass - grmue]
13g
jEP
and
Σ Pattrue
Σ
Pa
(glasso)
)11 - -18/a080) S
A|alaseo
grrue
-
JEP
JEP
JEP
JEP
(11)
We also need 2 results from the proof for do in Corollary
2 which shows that both 10% S 3/8%)
and || < 3 conditional on A where 8 Blaseo girue Given our restricted
|gg|
|
eigenvalue assumption
n| Te. this can be used to show
5 2
|801 2
10$1 < 4
< 4
<
4
|88
(12)
4/5
X8
A/5 3A tlass 8'5s
4/8
31lasco
Vs
5'6l
S
T,n
|88
by
Te
by
which means 881
<
12x
with conditional on A which occurs with probability at least 1
2pexp( - (Aineen)2 byre
_
Finally are able to bound gamma by combining the above
12

---

Under review as a conference paper at ICLR 2020
P Σ - 2(8truc)
< 2( -
- 2(3truc)
(13)
1 { Iz. vi)
Σ Paluaso))
Σ
(3(rrc)))
(14)
iEN
JEP
iEN
jEP
() lasso /3
Struct + A 1|3
(15)
JEP
12Alasso
S (A (Aless0 + +11881 S (X + A)
(16)
bire
Next consider the conditions necessary to apply Theorem I
We have assumptions (AI) and (A2)
and [A3) per our assumption that the RE condition holds combined with 7 That leaves the 3 re-
quirements on r, Px(aA) and [
min-
We will convert each of these to inequalities on n
Utilizing and substituting À
Qa
Inp
and Alasso V
n 772 where Q, > 0 are arbitrary
In
Te
n7/z
constants, and setting 1³ 4s,
n0 Inp, l' =17/2 Inp we get the following
0²
+ 2 s +1(+2 + 26" + lb;
Pa(a)) > 11+2V7 26')+
(17)
2nbi
bi(5" -2s + 1)
8 + 126² + +12eQ = C2/bi
>
(18)
blal2
T < Px(a))
1" + 2 222/0+++2
(19)
bn
T-y
12e
20 + 12c2
8
C2 8
>>>>>
+
(20)
aQ
aQ²
1i
bi
8a²
X2 S|, Pa(a))|S|+
||
1r0 + +22/"L + 21)
+ min
+D}
(21)
min
1
rpbinn
rpbi
rp
so² Inp
2/7
so² Inp
2/7
n
(160 + 8Q2)
(113g I| mai T4a byr
=
Css
mén rasbira)
(22)
For some constants C1, C2 and C3s
We can then apply Theorem I (conditional on A) substitute our values and simplify to get that , is the global solution with probability at least
1- 2exp(_t
f0 In( pC - 2eeppeepp- + -lp0)))))) 7-
1 expl-(p- - 5²)((' - In p))
1 exp(- (ppp--t-- -t + lnp)
8-8"
21 - 2exp(-(n0712 1)dslnn) - 2
Σ
exp(- + +x)(10/2-11))) lmp)
k=1
21
1)4slnp) - 2
+ 1)(n 1) - -1]mpp
1 C. exxp(Csssn 1/2 lnpp))
(23)
We then use the same technique as in Theorem D to combine this number with the probability of AA to get the final non-conditional probability that 3 is the global solution with probability at least
13

---

Under review as a conference paper at ICLR 2020
2 - C4 Inp) 2pe (Alaseo)
80²
exp( - (e2b - 8) lmp
(24)
2 1 - C4 p 72 Imp)
2 eexp((CCssnn - exp(- 712 (n(p))
For some constants C4. Os C6 and C7.
Note that these constants, as well as C1. C2 and C3, are dependent only on the value of a Q and c, as far as problem dependencies are concerned. Thus given that a Q and are chosen to be any positive constant value, as the statement of Corollary [ C1 through C7 are problem independent, which is the desired result.
Proof of Corollary 2 The first result is simply Corollary 2 in (Fan et al. 2014b). If we initialize the LLA algorithm with Blasso the solution LASSO using X Xdass as the LASSO constant, then the LLA algorithm converges to the oracle solution in 2 iterations with probability 1- - 6o- Φ1 02-
However we still need to solve for the actual values of do, Φi, d2 for GLM.
First consider Φu =
- -gruell mar ao Similar to Lemma B.I. in Bickel et al.
2009), to bound this we will start by noticing that for the lasso penalized loss function Qlasso LieN 1(3, Z4, yi) + Xlasso ΣjEP |3,1 we have that Qlasso I Qlasso (gtrue).
If we then
let 8º = glasso - girue we can use the same tactic as in the derivation of to get
bn 2m |x
WTX8 < Alasso Ejep 1 [8/asso which can then be rearranged to get.
b1
|
WT NVTX,1188 S
lasso Σ
18frue
|
(25)
2n
JEP
JEP
Next let A = 1e W S Massa /2..
We can combine this with 25 to get that by || | 1|2 +
Alasso /2 /2ΣnEp |glasso - _frue] I lasso ΣjEP Blasso - -gfree] + Masso jep |8]rue
conditional on A. From this notice that the right term goes to zero when 3true 0 so we then have
that 2n | Using the triangle inequality and the definition of 8 we can simplify this to
d1 |x01| + Alasso/2 /2 EjEP 18fasso @frue| S Xlasso Ejes 18lasso gyruel + 18grue
by 2n
Alasso
[X + 2
1891 < 21
(26)
conditional on A. By relaxing different parts of the equation, this can be further simplified to both & || <
1a < g/2 la and 16% 318g|- Note that the second of these
shows that 8 satisfies the constraint for the RE condition Therefor have that ||x
n 1 2 Te-
If this is combined with the first of the two equations, we can get that conditional on A.
1 7/7Z ||x801|
< 3A 3Alazoo be(re))
Next, using this we can show that conditional on A we have that |150 Iaa S | /[[|5=| nrra) S 11/2 < aod if X > 3alnnsog11" This is the inverse of the con- braote
||88||
bite
dition that defines Φu- Thus, can bound do with Φ I P(A)) P(U 1 WTX,I
Xlasso /2) P(USEP |
nillasso (2lasso/(21|Xx111 S pP(KW,,))
Alasson
2
PP(KWWe)) u/)l (nnnso(nb a) < 2p exp -(X10000) which uses both (A1) (ii and (A2) long
802
as A 32l00s0,3/2 per (A2)
brap(re)
Next consider Φ1 = V en (goracle
2 a1
max
14

---

Under review as a conference paper at ICLR 2020
6 P 7 sp cn ( (gorade)
2 a11)
(27)
-P(3j P: 1y 2 a11)
(28)
-P(J E P; = Σ [vb'(r (x.] (orrace)arss. Mhttall 2 a1
(29)
iEN
-P(3j P:
(x) (II] goracte) - (x} (o + Wotesll a1
(30)
EN
<P( X3 (V (X gorade) - (X + W) 2 a1a)
(31)
SP 11
X3 (X gorade)) v ((((
+ |TTX|| 2 a11)
(32)
<P XX,| || (X gorade) (t |TXx 2 211)
(33)
PP | (X.goaad)))) - &8 (8 + / | 2 "
(34)
< P( (X
18( (X ||
+ | |X,|| 2 (ab..))//231)
(35)
< P(b || X gorade - -x + | 2 (ab_n)1/233)
(36)
P(b || + | 2 (ab.n)) //2 (ab.n)1//221))
(37)
where v E R is some vector with ||0||
indicated in (A2) and σ0 = forade gtrue
From this, using Demorgan's law and the union bound, we notice that P(A+ B C) S P(A2 C/2) P(B Z C/2) which can be used to further simplify
11 < P(b. | + |W 2 a1) + P([TT 2 (a/2)a
(38)
S P(1X660 2
(39)
We can then simplify both terms individually. For the first term, P(b, || (1/2)a; 1/2), given the fact that the oracle solution and true solution have the same sup- port, the oracle solution must be in the r O level set of the true solution. Using simi- lar arguments Lemma 5 we have that b |x < LWT From here Lemma can be applied since we know goracle gtrue lo S 8.
>
2n
With some simplification this gives that
|| S & (maxsg:15p1=>
ÜT w/) Utilizing Lemma Sq
3 with s in place of P shows that
P max max by
| W
2
811 8 2/ + 2/
S (29) exp(-11). This is the first half
of Φi as long as (1/2)a A(an) Mann/b.) /222 > 2ov' 3 2 st + 2f which is equivalent to the as- sumed condition A > P[[TT]] 2 (1/2)a1\(abun)) 1/2) < 2eexp(
l0y veV22v/s1+22 Next, the second term can be casily bounded using (A2) bia (an/bb))
afx²abun, 8a2
ofX2ab_n 802
Therefor Φ1 1 ( ( exp(-ti) + 2 exp((
Next consider d2 = Pg[|sgract min < aλ) First, given the assumption [| > (a +
1)A see that Φ P( P([ min S ad) S P[[]agracke Strue max
2) S
P[]]aoracle - Birue] ||2 > A) 1(18%) > A). Next, since we know that the support of goracle
and gerue is S, we know that |88, = 0 I 3,5g| which is the constraint for the RE condition.
Therefor we know that 1' 2 2 Te. With this and similar line of argument as in Φ1 we get
that Φ2 5 P([10)I > A) < P( > \vnra) < P(Z (maxs Ü w| > AvTrr)) =
15

---

Under review as a conference paper at ICLR 2020
u p( Spl=s 1/3 W > 2
2 ov 4//2 + 262) - ( exp( -22 assuming that
biyerr 20 + which equivalent the condition 20 seVssavaat222. b
This, combined with the fact that for MCP, do = d1 = d2 shows the first result.
The second result can be seen by first noting all assumptions of Theorem [ part 2 are satisfied,
where (A3) with T4a is implied by 7 Thus by using the same arguments as in Theorem | part which shows that the oracle solution is unique and that the global solution is the oracle solution with some probability. since the global solution is almost surely SONC with r = 0. we use t = ts and t' t4 we get that the probability that the global solution is not the oracle solution as
d3 S exp(- (13 + ( + exp( 1 (f" + 1)(14 - In 1-exp(-(p-fi (1t((t-Inp))) This combined
I 1-exp(-(a (tsp(-(++inp)
with the first result shows that the LLA algorithm converges to the global solution in iterations Φ0 Φ1- - d2 Φ3 which is the second result.
with probability
A.2 CENTRAL LEMMAS AND THEIR PROOFS
Lemma 1. Let 8r be SONC Pl|sği & (0, a)), Vj p1/
solution
2
If
assumption
A1
holds,
then
Proof of Lemmal 7 First, define events 7 and 6, as
= QQ)())
2
(40)
(03,)² 3=9
8, = {1851 E (0,
(41)
First, for any given j E P. we solve for P(7j n 65) given our assumptions. We can start with 0 (3)
A= 2 which gives us 1/n Σ 3 (x. 3*) x² + 1X 2 0. We can rearrange this
TOB,Y 7
n/a where we get the leftmost inequality from assumption (AD (i) and the rightmost equality from the definition of MCP. More concisely have that bu |X, 2 n/a which contradiets (A1) part (ii). Therefor we know Phy n 5 0. It should also be noted that Phi] 0 since 3 satisfies S3ONC conditions. Thus, by applying Demorgan's 's law and then the union bound, can be obtained that
to get by
"aTT")) 2 -
0 = Phy [6 = - Phe U 0f 2 1- Phj] P| = - Ploy] = P[oy].
(42)
We can then apply this result to all indices to get that P(6,] 0 for all j {1, p}. which is the desired result.
Lemma 2. Consider an arbitrary SONC solution 8r to with MCP. Given the event that for some
integer p: ||8* - gtruello llo S p. then W < maxx 1J w () || a.s.
Where
(Uspy if E Ss
(Üss) =
(0
else
and Usg R is defined as the following Thin SVD: Xs; = Us Dsg Vsg
Proof. Denote 8* := (87) 3- gtrue Sp == (j 83 # 0) C P. 83, == =63 j Sp) and Xs, = (zij E Sp). By assumption, we know that 1 < S P.
First decompose Ns, using Thin SVD to get Xs; Us, Ds, Vs, where Us, Paxz
Note that since and ULJUs, Usp T have that for any E Rd have (DssVssuul
16

---

Under review as a conference paper at ICLR 2020
(Dss Vs, Vs, u V D3g UJ, Us, Us, can obtain that
u X Xs,U X || therefor Ss
1 | Xy, 13, $ ||TUspl11 Dsp Vs,
(43)
= 13 W
[ /|
| wI) ||x8%1,, a.s.
max
Sp
Where
(USp
j Sp
(Usp)is
00
else
Lemma 3. Consider an arbitrary
SONC solution 33 to 2 with MCP. (f holds, then for some
integer p S p. P maaxs: U7g W/ s <ov 2
2t
2 1 ( exp(-t). Where
(Üs,)ss = (USp ij E Sp
(0,
else
and Us, E R is defined as in the following Thin SVD: Xs; = UUS Dsp Vsp
Proof. We attempt to bound (maxs Sp w|)) Given that we now have W multiplied by square matrix, can apply Lemma 9 In the Lemma, let E., Üs ÜT. The fact that E,E, Ev means that Σ., is idempotent matrix with ||E,|| < 1 and Tr(E.) = rank (En) I rank((Usp) S rank(Us;)) < P. Lemma then states that that P [| W S Sovō+ 2 20 > 1- exxp(--)). From this we can show that
UJ w|1 S oo p+ 2 pt + 2t
(2) (
exp exp(-t) 2 1 - ( )a exp( -t). (44)
P
max Sp
2 1 -
Where the first inequality can seen by noting that if m/s E R² is a sequence of i.i.d random variables and 0 R is a scalar, by applying De Morgan's Law and then using the union bound, it can be obtained that Pfmax*eK 7k S 6) P[nke 7 < 0 = 111 P ne 2 0] 2 1=EE Pln 2
0 = - [1 Pink- S O)) which yields the same inequality as 44
This is the desired result.
Lemma 4. Consider an arbitrary OON solution 3 to with MCP. Let Assumptions
(Al and
(A2) hold. Given the simultaneous occurrence of (i) the event that (33") < (5trrue)
holds
for some r 2 0; (ii) the event that for some integer p 11.3* gtrue Il S p. Then for any 0,
8 [ - -gtrue>lf )|| < 402 ( +t) +
by min min PX(18) (115))13311
т} holds with probability at least 1 - exp( -t t + pln( (l)()))) )).
If in addition (A3) holds with 5" 2 ú. then 1 I| - 3true)11 21²
<
s N.
( + 2/ + 21) +
& minn(2((S))
1lor Pa (a))((8)) (13) + r} holds where rp 0 for any I 0 with
probability least exp( - in pe )).
Proof. First, denote 8" = (87) = 8 grrue, Sp = (j:83 - 0) CP. 85, = (0) jj jje Sp) and
Xs, == (xiz : N.j E Sp). By assumption, we know that 118* < |Sp = p. Further, let us denote
17

---

Under review as a conference paper at ICLR 2020
T1 == min Σ PXC33D1135 E - 35 - +r jES
(45)
We now start to define the desired bound by applying the second part of Lemma simplified using the above definitions becomes
g
The result
by
| - + Ti, a.s.
(46)
2n
Next, since all assumptions for Lemma are satisfied, we can apply it to get
bt
max | S n Sp:1Ssl=p
Üū w//l
|| TT.
(47)
2n
We can then complete the square, solving for
1 Vn
| to get
1 vn
1
5
max bi bi
Sp:18s1
ÜT W Sp
v
Sp: 18p
max
=
53
w|)
2 Ti
(48)
Ü W 1)
2
2
<2
max bivn Sp-18al=5
+
TT.
(49)
by
where the last inequality holds due to the value inside the square root being larger than the term outside. From here, squaring both sides gives us
1 X6
Üū wl)
max S5:18p1=
+ T
(50)
bi
bi
Finally, by applying the second part of Lemma we get
1 _ 1x00 =
402
bin (5+2V + + TT.
8
(51)
n
bn
With probability at least 1 (5 yd exp(-t) Thus by the definition of Tı, the first result of the lemma has been shown.
For the second part we look to bound the central term of Tı. We first notice (a) that since assumption (A1) holds, Corollary 4 indicates that if B3 + 0 = | 2 aA for all E P; (b) that for this range
of Bj. PX(1)) O; (c) that per the definition of MCP < (1(1)) < X for any 3 E R. If we
combine these observations with 45 and the definition of 5*, we can see that Ti S Σ (X 8
JES
< < B3 || From this, given that assumption that, for this second result (A3) holds with 5r 2 p. and rp 2 rp- 2 we can use (A3) part (iii) to show that Ti S Av/ST
1 I
x
v
Since this holds almost surely, it can then be combined with 47 to get
by | 2n
< n
max $5:15a1
JU wI)
+ A ||
|
|
(52)
/nrp
We can then multiply by 2 //
| || to get
| v
2 max
[ W Sp
21
||
|
(53)
b, by
Sy11,
=p
18

---

Under review as a conference paper at ICLR 2020
We then square both sides and use the rule that (A+ B)² = + 2B to get
1
2
2X
|x8*
max
ÜT 5g
+
| - |
(54)
Th
bi
S5-1pp1
bi T
8
|2
8A²
Sp
W
+
(1S)
|
(55)
of
Sp
birp
Combining this with yields that
1 1 I
X2 {
max
w/
+ bi
min
1 ((S) - || loo: T1
(56)
72
nn Sp: spl=p
Tp
Finally, by applying the second part of Lemma and noting from 45 that Ti S Pa(aA)(IS) || (lo) + I' see that
! |X S bin o2 pt + 2t) + by
min X2 (IS) - P.aN)()))
n
rp
(57)
With probability at least 1 - (PC ) exp( t) which is the desired result.
Lemma 5. Let Assumptions (AI) and (A2) hold. Consider a solution 3r satisfying S3ONC of
Assume that 2(8*)= 2(3trae gtrue) +I' holds for an arbitrary I >> 0. For any integer p 2|8| SsSp
if the penalty parameters (a, X) satisfy that Px(a)) Tuby (1 2/F + 2t) + (1
b(p41-2(81)
for an arbitrary t > 0, then ||3 gtrue llo S p with probability least 1 exp(-ppppp (5 + 1)
In p)) 1-expl (t-m)(t-mpp)))
Proof. We start from the useful inequality defined in g
bi 2n
1 1 WTX8* + Σ PACSSD S Σ PA 1) +1,
(58)
jES
jES
where 8* 3" gtrue Next, conditioning on the fact (i) that 8 is SONC, (ii) that all as- sumptions for Corollary 4 are satisfied (which implies that Px(13]I) E {0. Ps (aX))) and (iii) that (1 I Pa(a) we have that
b
| WT + 1188% PA(aA) S |S] PA(a)) +r 2n
(59)
T
Now consider an event & := [11,8* - glr = f p + k} for an arbitrary integer l: 1 < k S p p Conditioning on this event, may denote and Sp+* S P such that 07 + 0 for all S By assumption we ensure that 1St+kl ÿ k. Also denote by Xsp (æi : E N. E Sp+1) (0] j Sp+k)- Note that conditional
and let 65p
ε,, the first part of Lemma (using Additionally, by definition 3 ll 2 p + k SS]. This
p + k in place of p in Lemma 1) be used to bound W in 59
|| = [)] and conditional on E we can apply the substitution
gives us
X8* Vn
max Sppnc
UU Spon
wI)
X8* Vn
<
- PA(a)) +r (60)
2
Vn
In order for this equation to be feasible, we know that the quadratic formula must have real roots. Therefor
19

---

Under review as a conference paper at ICLR 2020
ÜT W 2 Sp+t
1)²
max (ppt:15p==\=pt
4/66/211(6 2|8)) PA(a)) - 20 (61)
Vn
Now consier another event (1) == {max |p+*|= ||
Sp+h W|| S <ov V 1 2V + 2/3
for an arbitrary & 0. Conditioning on the occurence of &l n E2(t) we can show, using first
2
133 p+a
w
(1) and then 61. that s ('(p+)) + 22- + 21) 2
max
2b +
4: 2| Px (ax) - r] almost surely, which contradicts with the assumption the parameters
(a, x). This can be seen starting from our original assumption that Px(aA) >
2ndi (1 + 2vF +
o²
o² 26) + = 15( 2 2nb (1 1 2/7 + 21) 1500
bx($+-1-1181)) We can then multiply both (outer) sides by 2b 2|S]) and rearrange to get ( k) (1 2-1++2+)))))) 2t) (p - 2|8] +
b1(5-1-2181)
k) (a -. Given this contradiction, we know that PlE, (t)) = 0. Therefore, again using the union bound combined with DeMorgan's 's law we get that P 2 1- P - (t))
which, can be simplified to
P(E(()) P[&]
(62)
Since all assumptions of the Lemma 3 are satisfied, we can next use it bound P(E)(t)). By taking the compliment of the result in the second half of Lemma 1, we get,
for some t,, that P mnaxspniiSptaa > exp(p S woth exp( (1)). If we then
| w||
2 o (p+ k) + 2/200
(p + k)t + 21' S
let
= (p + k)L we get pē+* exp( ( 1p k)t).
P max (=(++)) |15 W 2 2oop VI+
+ 2t
Thus we have that pātk exp(
exp(-(0+ (p+ k)t) 2 (() which can be combined with 62 to show
** k exp(-(f ky
PI] - 11 = + k]
v
(63)
With this, we solve for our desired value
P [[]]8 - lltruello S Ss
=1 P [1]8* geruell 11. 2 1++1==1 =1 Σ
[|| g 11 = =5+ ki)
> 1 - Σ
exp((f k)(npp 1))
k=1
1 - exp( - (ū + 1)(1 - Inp)) 1 exp(pcp (p-(-ppppptt (t- Inp))
exp(ptte Inp)
(64)
Which is the desired result.
Lemma 6. Consider an arbitrary S9ONC solution 3* to with MCP. Let Assumptions
(Al and
(A3)
with 8* 2 P hold. Assume the satisfaction of || grrue] llo < 6 and Event {p(p)
[[ - gtrue I11 <
80"
(p+ (5+ 2 2t) + hy min ( (15)- 5 1lo),
11o)+
b7
Т). If the sub-optimality gap satisfies 1 < Pa(a))= d²
byn (i 2 + 21). If the minimum signal
strength satisfies [| Umin
Fpbpn (p+ 2 + 26) + bg min N/
then
3 is the oracle solution to
20

---

Under review as a conference paper at ICLR 2020
in addition we have the satisfaction of 1| 3trell S p and the event Es(p) Sa"
( [ _rtue))l
(p+ (p+22 2/ + 2t) +
by rp ((S) 11) Px(a)) ([S)
8 min
8fn
19) + [] then (3r is both the oracle solution and the global solution to 2
Proof. First, let us denote 8" garue = 8" We start by combining & (p) and (A3) ii, which is
possible due our assumption 18* gtru llo S p. This gives
802
8
X2
25+2Vin jt + +21) in
min (IS) 118) Pa(a)) (IS) 113* + +
b rB
(65)
X ス 110-11 a.s.
n
From here if we relax |S| - |/8/ to just (S], the definition of 8" and note that |81|| 2 obtain the following
|0 we
802 V rzbff
X2 Pa(a)) + r
(5+2v 2 pt + +20 + min
S),
rpbi
Tp
(66)
2 ||
2 1 - |831.
almost surely. From this we can bound |3و| using the square root term and |/8trej, so we know that
S0" if [ V rgbfn this we can obtain the inequality
(p + 2 pt 21) +
8 min X² (S], Pa(a))|SI + + > 0 then |88] > 0. From rabi
Tp
163311 2 ΣI
802
(p+2
ptt 2t)
+
8
min
(S) (a +1} >
Tpbin
rzbi
Ti
JES
(67)
almost surely. We can then combine this with our minimum signal strength assumption get that
0 lo = |S| a.s.
(68)
We can combine this with equation 65 by focusing on the second part of the minimum term and noting the right side is always positive get
80² bR
8 b
p 2 + +2 + (-Pa(a))) +1) 2 aa.s.
(69)
which can be simplified into
a²
(p+2 2++2V/++77 2t) + +1> (a(a)) 1/ a.s.
(70)
byn
thus, it can be seen that if Px(a)) > satisfied by the assumption that Px(a)) d² (5 1 2
2 (p+2Vpt + 2t) - r then 1 > | llo = 0. This is pt 2t) > r.
byn
Finally, because 8" is an OON solution, has to satisfy FONC. Per 2 this means that 3" arg inf EieN {(B, Fi, wi) + EjEr (X D1 3 E R2), Due to Corollary 4, we know that the penalty term goes to 0 since either 88 = or P'(18) P' P'([a\)) 0. Further we know that 93 0 for all j E S Threfore we know that
1 Σ n2 iEN
3* E arginnf
E(8, vi) B R V, E St) a.s.
(71)
21

---

Under review as a conference paper at ICLR 2020
Given that the expression the right is the definition of the oracle solution, have shown the first result.
Next, Consider gopt which is the global optimal solution to 2 Given that the ONNC conditions are necessary, gopt must be an O'NCC' solution. With this fact and the assumption of & we have the same set of assumptions for goot as we had for 3 Thus the same sequence of arguments can be used to show that
gept E arg (- Σ (18,0,,1)) B R = 0, 8 a.s.
(72)
iEN
Finally, per the strict convexity of our loss function implied by (A1) we can see that the infimum of the above problem is unique. Therefor
3 = arg inf Σ
((3, B BER, 0, Vj E E = 3opt a.s.
(73)
ENN
Which is the second result.
A.3 ADDITIONAL LEMMAS
Lemma 7, The RE condition in 7 implies (A3) with r4s 2 re > 0 and fr 2 4s.
Proof. As in Lemma in (Liu al. 2017)
Lemma 8. Let 3 be S3NNC solution to Given (Al) and that 2(3*) S Q(Birue) + I holds
for some I 2 then
b 2m
1X80 WTX8
< min
Σ PX(1531113 Strue,, P3(a))((S)- - 111881)) +r +rJ. a.s.
jES
jES
(74)
a Proof. First, we know that 5" E arg min Σ 8(, v.) + Σ P1(1+1)11113 because the KKT
conditions are the same as FONC which 3 satisfics. This gives us that Σ 2(8",a0 x, 9:) +
Σ PX DI871 x Σ e(gtrue 91) + Σ P1 This can used along the
1=1
same lines as the level set inequality in the derivation for 8 to get
b || LWTX8 s 2n
( 187))
The first two terms of the min function are easily obtained from this. The last term can be obtained
from 8 by noting that due to Corollary 4, S & (0, ax) and that (x(a) (x) v 2 aX. This gives us that 2n 2 - < (S +I is the final term complete the desired result.
Lemma 9, Consider a subgaussian ñi-dimensional random vector W E R as defined in (A2) Then for any V E Raxa and E, VTV then Pl] vW S o². (Tr(E.) + 2 Tr(E3)t + E. t)] >
1 exp( -t) for any > 0 where Tr(.) denotes the trace matrix.
22

---

Under review as a conference paper at ICLR 2020
Proof. We apply Theorem 2.1 in (Hsu al. 2012) where our W. V. and E, are equivalent their I, A and Σ. Note their expectation condition is equivalent to our (A2) with = ElW] = 0. This gives that for all > 0
P[Irwip > o². (tr(Ex) + 2 tr( + 1
(75)
E.
+ (r(Enpp)) (1 2
13/3 S exp(-())
Given that 1a 0, the term involving ir (r() goes and therefor the statement in 9 can be obtained by taking the complement of the probability bound.
23


Reviews:
[{"review_id": "rklfq4Jf5S", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "=Summary=\nThe authors study the high-dimensional sparse estimation problems, which is one of the fundamental topics in both machine learning and optimization communities. In the literature, the folded concave penalty (FCP) methods have been shown to enjoy the strong oracle property for high-dimensional sparse estimation.  While LASSO solutions can be easily computed, such solutions do not admit unbiasedness and oracle property or require strong conditions. Therefore,  the problems with FCP have received much attentions and been studied in terms of hardness and approximability of the problems recently .\nIn the paper, the authors focus on the minimax concave penalty (MCP) that is a special class of FCP. \nInspire of the problem being NP-hard, they proposed pseudo-polynomial time algorithms and showed the global optimality; using the characterization of a significant subspace second-order necessary condition (S^3ONC), they showed that all local solutions within an efficiently achievable sub-level set are globally optimal. They also investigates the empirical evaluation of proposed methods.\n\n\n\n=Significance=\nIn the technical view,  the part of (a) in Theorem 1 is very similar to Theorem 4 in [Hongcheng Liu, Tao Yao, Runze Li, and Yinyu Ye (Mathematical programming, 2017)]. The main result of this paper may be the part of (b) on Theorem 1. \nHowever, the motivation why the authors wish to compute global optimization is not clear to me.\nIndeed,  for FCP,  [Liu et al, 2017] showed that\n1. Any local solution is a sparse estimator.\n2. Any local solution satisfying a significant subspace second-order necessary condition yields a bounded error in approximating the true parameter with high probability\n3. For MCP (with restricted eigenvalue condition), S^3ONC solution has oracle property.\nTherefore, the global optimality is not necessarily stipulated to ensure the recovery quality.\nI would like to confirm the motivation of this work.\n\n=Missing references=\nAlthough the topic addressed in the paper is related to the complexity of the sparse estimation problems, the following papers are not included in the references.\n\nHuo, X. and Chen, J. Complexity of penalized likelihood estimation. Journal of Statistical Computation and Simulation, 80(7):747–759, 2010.\n\nBian, W. and Chen, X. Optimality conditions and complexity for non-lipschitz constrained optimization problems.\n\nChen, X., Ge, D., Wang, Z., and Ye, Y. Complexity of unconstrained L2 − Lp minimization. Mathematical Programming, 143(1-2):371–383, 2014.\n\n\n\n=Questions or comments=\n\n1. Time complexity:\nWhy and how the running time of the proposed algorithm can be polynomial time from pseudo-polynomial time?\nWhere is the time complexity of the proposed algorithm explicitly presented in the paper?\nAt least, the definitions of FPTAS and FPRAS and other technical terms of the complexity are missing in the paper. If the author wants to publish the paper in this conference, the definitions of them should be written in the paper, since many of readers in machine learning areas may not know the exact definitions.\n\n2. Can the results presented in the paper extend to the case for SCAD? Since SCAD and MCP are shared with similar properties, I’d like to see more discussion on SCAD case. \n\n3. About the problem setting: \nAll the inputs and parameters are assumed to be rational number?\nAre there any assumption on the loss function?\n\n4. After the definition 1,  “some independence assumptions “ or  “the same setting” are unclear. Please clarify the assumptions or setting to be self contained.\n\n\n\n=Minor comments=\n\nAbout the title: If the paper did not provide any results on SCAD, it is better to use the term \"the minimax concave penalized\" not \"folded concave penalized\"\n\n(Page 3: “The oracle solution is a hypothetical assumes the prior knowledge on the true support set…” is grammatically wrong?)\n\nRemark 1: remove  one “gradient\"\n\nRemark 4: S^3ONC\n\nReferences: Cun-Hui Zhang, Tong Zhang, et al. \n-> add \"and\", remove \"et al.\"\n\nReferences: Cun-Hui Zhang et al. => remove et al.\n\nPage 18:  delete the memo “ move to intro somehwere?”\n\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SygBM7unKH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nSummary:  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. \n\nStrong points:\n\n-S1. The global optimization of non-convex (regularized) sparse learning models is a fundamental and challenging problem worth investigating.\n\n-S2. The paper is well organized and clearly presented in general.  \n\nWeak points:\n\n-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. \n\n-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? \n\n-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.  \n\n-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.\n\n-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. \n\n-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.  \n\nMinor issues: \n\n- M1. Check the correctness of notation $\\beta$ in Definition 1. \n\n- M2. Equation (3): Why not directly writing out “$0 \\in 1/n\\sum_{i=1}^n…$”?\n\n- M3. Statement of Theorem 1: satisfy -> satisfies. The quantities $t$ and $t’$ appeared in Theorem1 are hard to understand without further explanation. \n\n=== update after author response ===\n\nThank 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.\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HJlcKC0P5S", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This is a theory heavy paper. My only concern is relevance for this conference, but other than that the results are interesting and useful. \n\nIt seems the authors have focused on a particular case of folded convex penalty (Minimax Concave Penalty or MCP --- the authors should provide the full form of the abbreviation before using it). The major contribution of this work is the analysis, while the algorithmic setup can be borrowed from previous works (e.g. Liu/Ye 2019). \n\nRemark 10 is not clear to me. Why is the assumption that \\beta^\\star has a lower value than \\beta^{Lasso} reasonable ? Also, the assumption is to hold almost surely, which I am assuming is over possible instantiation of the randomized scheme ? In that case, this assumption seems very strong in general, unless I am missing something. \n\nI would suggest authors expand the paper to be self-sufficient, instead of referring to other works (e.g. Algorithm 1 in Liu/Ye 2019, and proof of Lemma 9 ). Please proof read e.g. above equation 62. \n\nIt would be nice if the authors also provide discussions on how just the sample complexity being large enough is sufficient for assumptions of Theorem 1. I had to spend a lot of time to understand the relationship and intuition wrt \\Gamma implying from sample complexity. That should add to the readability of the paper.\n\n\n\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Thanks for your detailed feedback to the reviewers, which clarified us a lot in many respects.
However, the novelty of this paper is rather marginal and given the  high competition at ICLR2020, this paper is unfortunately below the bar.
We hope that the reviewers' comments are useful for improving the paper for potential future publication.

Decision: Reject