Global solutions to folded concave penalized nonconvex ...

1 [ ] 24 Mar 2016 The Annals of Statistics2016, Vol. 44, No. 2, 629 659 Institute of Mathematical Statistics, 2016 Global solutions TO folded concave PENALIZEDNONCONVEX LEARNINGBy Hongcheng Liu1, Tao Yao1and Runze Li2 Pennsylvania State UniversityThis paper is concerned with solving nonconvex learning prob-lems with folded concave penalty. Despite that their globalsolutionsentail desirable statistical properties, they lack optimization tech-niques that guarantee Global optimality in a general setting. In thispaper, we show that a class of nonconvex learning problems are equiv-alent to general quadratic programs. This equivalence facilitates us indeveloping mixed integer linear programming reformulations, whichadmit finite algorithms that find a provably Global optimal refer to this reformulation-based technique as the mixedinte-ger programming-based Global optimization (MIPGO).

2 To ourknowl-edge, this is the first Global optimization scheme with a theoreticalguarantee for folded concave penalized nonconvex learningwith theSCAD penalty [J. Amer. Statist. (2001) 1348 1360] and theMCP penalty [Ann. (2001) 894 942]. Numerical results in-dicate a significant outperformance of MIPGO over the state-of-the-art solution scheme, local linear approximation and other alternativesolution techniques in literature in terms of solution recovery is of great interest in high-dimensionalstatistical learning. Among the most investigated sparse recovery techniquesare LASSO and the nonconvex penalty methods, especially folded concavepenalty techniques [see Fan and Lv (2011), for a general definition].

3 AlthoughLASSO is a popular tool primarily because its Global optimalsolution is ef-ficiently computable, recent theoretical and numerical studies reveal thatReceived July 2014; revised June by Penn State Grace Woodward Collaborative Engineering/Medicine Re-search grant, NSF Grant CMMI 1300638, Marcus PSU-Technion Partnership grant andMid-Atlantic University Transportation Centers by NSF Grant DMS-15-12422 and National Institute ofHealth Grants P50DA036107 and P50 2000 subject 62J05; secondary words and concave penalties, Global optimization, high-dimensional statistical learning, MCP, nonconvex quadratic programming, SCAD,sparse is an electronic reprint of the original article published by theInstitute of Mathematical StatisticsinThe Annals of Statistics,2016, Vol.

4 44, No. 2, 629 659. This reprint differs from the original in paginationand typographic LIU, T. YAO AND R. LIthis technique requires a critical irrepresentable condition to ensure statisti-cal performance. In comparison, the folded concave penaltymethods requireless theoretical regularity and entail better statisticalproperties [Zou (2006),Meinshausen and B uhlmann (2006), Fan, Xue and Zou (2014)]. In particular,Zhang and Zhang (2012) showed that the Global solutions to the folded con-cave penalized learning problems lead to a desirable recovery , these penalties cause the learning problems to be nonconvex andrender the local solutions to be nonunique in solution schemes in literature focus on solving a nonconvex learn-ing problem locally.

5 Fan and Li (2001) proposed a local quadratic approxima-tion (LQA) method, which was further analyzed by using majorization min-imization algorithm-based techniques in Hunter and Li (2005). Mazumder,Friedman and Hastie (2011) and Breheny and Huang (2011) developed dif-ferent versions of coordinate descent algorithms. Zou and Li (2008) proposeda local linear approximation (LLA) algorithm and Zhang (2010) proposed aPLUS algorithm. Kim, Choi and Oh (2008) developed the concave Convexprocedure (CCCP). To justify the use of local algorithms, conditions wereimposed for the uniqueness of a local solution [Zhang (2010), Zhang andZhang (2012)]; or, even if multiple local minima exist, the strong oracle prop-erty can be attained by LLA with wisely (but fairly efficiently) chosen initialsolutions [Fan, Xue and Zou (2014)].

6 Huang and Zhang (2012) showed that amultistage framework that subsumes the LLA can improve the solution qual-ity stage by stage under some conditions. Wang, Kim and Li (2013) provedthat calibrated CCCP produces a consistent solution path which containsthe oracle estimator with probability approaching one. Lohand Wainwright(2015) established conditions for all local optima to lie within statisticalprecision of the true parameter vector, and proposed to employ the gradientmethod for composite objective function minimization by Nesterov (2007)to solve for one of the local solutions . Wang, Liu and Zhang (2014) incor-porated the gradient method by Nesterov (2007) into a novel approximateregularization path following algorithm, which was shown to converge lin-early to a solution with an oracle statistical property.

7 Nonetheless, none ofthe above algorithms theoretically ensure Global this paper, we seek to solve folded concave penalized nonconvex learn-ing problems in a direct and generic way: to derive a reasonably efficientsolution scheme with a provable guarantee on Global optimality. Denote bynthe sample size, and bydthe problem dimension. Then the folded concavepenalized learning problem of our discussion is formulatedas following:min L( ) :=L( ) +ndXi=1P (| i|),( )whereP ( ) :R Ris a penalty function with tuning parameter . Ourproposed procedure is directly applicable for settings allowing ito haveGLOBAL solutions TO nonconvex LEARNING3different ior different penalty. For ease of presentation and without lossof generality, we assumeP ( ) is the same for all coefficients.

8 FunctionL( ) :Rd Ris defined as a quadratic function,L( ) :=12 Q +q ,which is an abstract representation of a proper (quadratic)statistical lossfunction withQ Rd dandq Rddenoting matrices from data by :={ Rd:A b}the feasible region defined by a set oflinear constraints withA Rd mandb Rmfor some properm: 0 m < throughout the paper thatQis symmetric,Ais full rank and isnonempty. Notice that under this assumption, the loss function does nothave to be convex. We instead stipulate that problem ( ) is well defined,that is, there exists a finite Global solution to ( ). To ensure the well-definedness, it suffices to assume that the statistical loss functionL( ) isbounded from below on . As we will discuss in , penalized lin-ear regression (least squares), penalized quantile regression, penalized linearsupport vector machine, penalized corrected linear regression and penalizedsemiparametric elliptical design regression can all be written in the unifiedform of ( ).

9 Thus, the problem setting in this paper is general enough tocover some new applications that are not addressed in Fan, Xue and Zou(2014). Specifically, the discussions in Fan, Xue and Zou (2014) coveredsparse linear regression, sparse logistic regression, sparse precision matrixestimation and sparse quantile regression. All these estimation problems in-trinsically have convex loss functions. Wang, Liu and Zhang(2014) and Lohand Wainwright (2015) considered problems with less regularity by allowingthe loss functions to be nonconvex . Their proposed approaches are, there-fore, applicable to corrected linear regression and semiparametric ellipticaldesign regression. Nonetheless, both works assumed different versions of re-stricted strong convexity.

10 (See Section4for more discussions about restrictedstrong convexity.) In contrast, our analysis does not make assumptions ofconvexity, nor of any form of restricted strong convexity, on the statisticalloss function. Moreover, the penalized support vector machine problem hasbeen addressed in none of the above assumeP ( ) to be either one of the two mainstream folded concavepenalties: (i) smoothly clipped absolute deviation (SCAD)penalty [Fan andLi (2001)], and (ii) minimax concave penalty [MCP, Zhang (2010)]. Noticethat both SCAD and MCP are nonconvex and nonsmooth. To facilitateour analysis and computation, we reformulate ( ) into three well-knownmathematical programs: first, a general quadratic program;second, a lin-ear program with complementarity constraints; and finally,a mixed integer(linear) program (MIP).