OPTIMAL COMPUTATIONAL AND STATISTICAL RATES OF CONVERGENCE FOR SPARSE NONCONVEX LEARNING PROBLEMS.
OPTIMAL COMPUTATIONAL AND STATISTICAL RATES OF CONVERGENCE FOR SPARSE NONCONVEX LEARNING PROBLEMS.
复制标题
DOI：
10.1214/14-aos1238
复制
发表时间：
2014
影响因子：
4.5
通讯作者：
Zhang T
中科院分区：
文献类型：
--
作者：
Wang Z;Liu H;Zhang T
我们提供了惩罚 M 估计量的统计和计算特性的理论分析，这些 M 估计量可以表述为可能的非凸优化问题的解决方案。许多重要的估计量都属于这一类，包括具有非凸正则化的最小二乘回归、具有非凸正则化的广义线性模型和稀疏椭圆随机设计回归。对于这些问题，由于非凸公式，计算全局解是很困难的。在本文中，我们提出了一种近似正则化路径跟踪方法，用于解决具有非凸目标函数的各种学习问题。在统一的分析框架下，我们同时为算法获得的任何局部解提供明确的统计和计算收敛率。在计算上，我们的算法获得了用于计算完整正则化路径的全局几何收敛率，这在所有一阶算法中是最优的。与大多数现有方法仅获得单个正则化参数的几何收敛率不同，我们的算法以相同的迭代复杂度计算完整的正则化路径。特别是，我们提供了精炼的迭代复杂度，可以清晰地表征正则化路径上每个阶段的性能。从统计上讲，我们为正则化路径上的所有近似局部解提供了清晰的样本复杂性分析。特别是，我们的分析通过提供更精细的样本复杂度界限以及最终估计器的精确支持恢复结果来改进现有结果。这些结果表明，由于使用了非凸惩罚，最终的估计器获得了预言机统计特性。
We provide theoretical analysis of the statistical and computational properties of penalized M-estimators that can be formulated as the solution to a possibly nonconvex optimization problem. Many important estimators fall in this category, including least squares regression with nonconvex regularization, generalized linear models with nonconvex regularization and sparse elliptical random design regression. For these problems, it is intractable to calculate the global solution due to the nonconvex formulation. In this paper, we propose an approximate regularization path-following method for solving a variety of learning problems with nonconvex objective functions. Under a unified analytic framework, we simultaneously provide explicit statistical and computational rates of convergence for any local solution attained by the algorithm. Computationally, our algorithm attains a global geometric rate of convergence for calculating the full regularization path, which is optimal among all first-order algorithms. Unlike most existing methods that only attain geometric rates of convergence for one single regularization parameter, our algorithm calculates the full regularization path with the same iteration complexity. In particular, we provide a refined iteration complexity bound to sharply characterize the performance of each stage along the regularization path. Statistically, we provide sharp sample complexity analysis for all the approximate local solutions along the regularization path. In particular, our analysis improves upon existing results by providing a more refined sample complexity bound as well as an exact support recovery result for the final estimator. These results show that the final estimator attains an oracle statistical property due to the usage of nonconvex penalty.