标题： i-LAMM用于稀疏学习：算法复杂度和统计误差的同时控制 显示英文标题

标题： i-LAMM for Sparse Learning: Simultaneous Control of Algorithmic Complexity and Statistical Error

摘要： 我们提出一种名为迭代局部自适应主要最小化（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.