Fast global convergence rates of gradient methods for high-dimensional statistical recovery
Fast global convergence rates of gradient methods for high-dimensional statistical recovery
复制标题
DOI：
--
复制
发表时间：
2010-12
期刊：
影响因子：
--
通讯作者：
Alekh Agarwal;S. Negahban;M. Wainwright
中科院分区：
文献类型：
--
作者：
Alekh Agarwal;S. Negahban;M. Wainwright
许多统计M-估计是基于凸优化问题形成的损失函数与范数为基础的正则化的加权和我们分析的收敛速度的一阶梯度方法解决这样的问题在一个高维框架，允许数据维度d增长（并可能超过）的样本大小n。这种高维结构排除了通常的全局假设-即强凸性和光滑性条件-这是经典优化分析的基础。我们定义了适当的限制这些条件的版本，并表明，他们满足各种统计模型的高概率。在这些条件下，我们的理论保证Nesterov的一阶方法[12]具有全局几何收敛速度，达到模型的统计精度，这意味着真实未知参数θ* 和最优解^θ之间的典型欧几里得距离。这种全局线性速率大大快于以前的分析，只产生次线性速率的特定方法的全局收敛。我们的分析适用于广泛的M-估计量和统计模型，包括使用Lasso的稀疏线性回归（l1-正则化回归），组Lasso，块稀疏性和使用核范数正则化的低秩矩阵恢复。总的来说，这个结果揭示了一个有趣的高维估计的统计精度和计算效率之间的联系。
Many statistical M-estimators are based on convex optimization problems formed by the weighted sum of a loss function with a norm-based regularizes We analyze the convergence rates of first-order gradient methods for solving such problems within a high-dimensional framework that allows the data dimension d to grow with (and possibly exceed) the sample size n. This high-dimensional structure precludes the usual global assumptions— namely, strong convexity and smoothness conditions—that underlie classical optimization analysis. We define appropriately restricted versions of these conditions, and show that they are satisfied with high probability for various statistical models. Under these conditions, our theory guarantees that Nesterov's first-order method [12] has a globally geometric rate of convergence up to the statistical precision of the model, meaning the typical Euclidean distance between the true unknown parameter θ* and the optimal solution ^θ. This globally linear rate is substantially faster than previous analyses of global convergence for specific methods that yielded only sublinear rates. Our analysis applies to a wide range of M-estimators and statistical models, including sparse linear regression using Lasso (l1-regularized regression), group Lasso, block sparsity, and low-rank matrix recovery using nuclear norm regularization. Overall, this result reveals an interesting connection between statistical precision and computational efficiency in high-dimensional estimation.