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
(For example, I-LAMM requires much weaker minimal signal strength than other
procedures). Thorough numerical results are provided to support the obtained
theory.

这篇论文提出了一个名为 I-LAMM 的计算框架，旨在同时控制算法复杂度和统计误差，在拟合高维模型时具有最优的统计性能和可控的算法复杂度，本理论依赖于一种局部稀疏 / 受限特征值条件，可以分析大量的损失和惩罚函数，并在非常微弱的假设下提供最优性保证。