I-LAMM FOR SPARSE LEARNING: SIMULTANEOUS CONTROL OF ALGORITHMIC COMPLEXITY AND STATISTICAL ERROR.
I-LAMM FOR SPARSE LEARNING: SIMULTANEOUS CONTROL OF ALGORITHMIC COMPLEXITY AND STATISTICAL ERROR.
复制标题
DOI：
10.1214/17-aos1568
复制
发表时间：
2018-04
影响因子：
4.5
通讯作者：
Zhang T
中科院分区：
文献类型：
--
作者：
Fan J;Liu H;Sun Q;Zhang T
我们提出了一种名为迭代局部自适应多数最小化（I-LAMM）的计算框架，以在拟合高维模型时同时控制算法复杂性和统计误差。 I-LAMM 是折叠凹惩罚拟似然族局部线性逼近的两阶段算法实现。第一阶段求解具有粗精度公差的凸程序以获得粗略的初始估计器，该初始估计器在第二阶段通过迭代求解具有较小精度公差的凸程序序列来进一步细化。理论上，我们建立一个相变：第一阶段具有亚线性迭代复杂度，而第二阶段实现了改进的线性收敛速度。尽管该框架完全是算法性的，但它为大量非凸优化问题提供了具有最佳统计性能和受控算法复杂性的解决方案。迭代对统计误差的影响可以通过收缩属性清楚地证明。我们的理论依赖于稀疏/受限特征值条件的局部版本，这使我们能够分析大量的损失和惩罚函数，并在非常弱的假设下提供最优性保证（例如，I-LAMM 需要比其他程序弱得多的最小信号强度）。提供了全面的数值结果来支持所获得的理论。
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.