标题： 稀疏学习的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.