TY - JOUR
T1 - I-LAMM for sparse learning
T2 - Simultaneous control of algorithmic complexity and statistical error
AU - Fan, Jianqing
AU - Liu, Han
AU - Sun, Qiang
AU - Zhang, Tong
N1 - Funding Information:
Supported in part by NIH Grants 5R01-GM072611-11, R01-GM100474-04, R01-MH102339, R01-GM083084 and R01-HG06841, NSF Grants DMS-1206464-04, DMS-1308566, DMS-1454377, DMS-1206464,IIS-1408910, IIS-1332109 and the Science and Technology Commission of Shanghai Municipality 16JC1402600.
Publisher Copyright:
© Institute of Mathematical Statistics, 2018.
PY - 2018/4
Y1 - 2018/4
N2 - We propose a computational framework named iterative local adaptive majorize-minimization (I-LAMM) to simultaneously control algorithmic complexity and statistical error when fitting high-dimensional models. I-LAMM is a two-stage algorithmic implementation of the local linear approximation to a family of folded concave penalized quasi-likelihood. The first stage solves a convex program with a crude precision tolerance to obtain a coarse initial estimator, which is further refined in the second stage by iteratively solving a sequence of convex programs with smaller precision tolerances. Theoretically, we establish a phase transition: the first stage has a sublinear iteration complexity, while the second stage achieves an improved linear rate of convergence. Though this framework is completely algorithmic, it provides solutions with optimal statistical performances and controlled algorithmic complexity for a large family of nonconvex optimization problems. The iteration effects on statistical errors are clearly demonstrated via a contraction property. Our theory relies on a localized version of the sparse/restricted eigenvalue condition, which allows us to analyze a large family of loss and penalty functions and provide optimality guarantees under very weak assumptions (e.g., I-LAMM requires much weaker minimal signal strength than other procedures). Thorough numerical results are provided to support the obtained theory.
AB - We propose a computational framework named iterative local adaptive majorize-minimization (I-LAMM) to simultaneously control algorithmic complexity and statistical error when fitting high-dimensional models. I-LAMM is a two-stage algorithmic implementation of the local linear approximation to a family of folded concave penalized quasi-likelihood. The first stage solves a convex program with a crude precision tolerance to obtain a coarse initial estimator, which is further refined in the second stage by iteratively solving a sequence of convex programs with smaller precision tolerances. Theoretically, we establish a phase transition: the first stage has a sublinear iteration complexity, while the second stage achieves an improved linear rate of convergence. Though this framework is completely algorithmic, it provides solutions with optimal statistical performances and controlled algorithmic complexity for a large family of nonconvex optimization problems. The iteration effects on statistical errors are clearly demonstrated via a contraction property. Our theory relies on a localized version of the sparse/restricted eigenvalue condition, which allows us to analyze a large family of loss and penalty functions and provide optimality guarantees under very weak assumptions (e.g., I-LAMM requires much weaker minimal signal strength than other procedures). Thorough numerical results are provided to support the obtained theory.
KW - Algorithmic statistics
KW - Iteration complexity
KW - Local adaptive MM
KW - Nonconvex statistical optimization
KW - Optimal rate of convergence
UR - http://www.scopus.com/inward/record.url?scp=85045203424&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85045203424&partnerID=8YFLogxK
U2 - 10.1214/17-AOS1568
DO - 10.1214/17-AOS1568
M3 - Article
C2 - 29930436
AN - SCOPUS:85045203424
SN - 0090-5364
VL - 46
SP - 814
EP - 841
JO - Annals of Statistics
JF - Annals of Statistics
IS - 2
ER -