Convergence rates of sub-sampled Newton methods
Murat A. Erdogdu Andrea Montanari∗, Department of Statistics, Stanford UniversityDepartment of Electrical Engineering, Stanford University
Abstract
We consider the problem of minimizing a sum of $n$ functions via projected iterations onto a convex parameter set ${\mathcal{C}}\subset{\mathbb{R}}^{p}$ where $n\gg p\gg 1$ . In this regime, algorithms which utilize sub-sampling techniques are known to be effective. In this paper, we use sub-sampling techniques together with eigenvalue thresholding to design a new randomized batch algorithm which possesses comparable convergence rate to Newton’s method, yet has much smaller per-iteration cost. The proposed algorithm is robust in terms of starting point and step size, and enjoys a composite convergence rate, namely, quadratic convergence at start and linear convergence when the iterate is close to the minimizer. We develop its theoretical analysis which also allows us to select near-optimal algorithm parameters. Our theoretical results can be used to obtain convergence rates of previously proposed sub-sampling based algorithms as well. We demonstrate how our results apply to well-known machine learning problems. Lastly, we evaluate the performance of our algorithm on several datasets under various scenarios.
中文速览
大规模机器学习中，用牛顿法（Newton's Method）求解包含海量样本的优化问题时，每次迭代都要计算完整的Hessian矩阵，代价高达O(np²)，根本用不起。为此，研究者提出了一种名为NewSamp的新算法：先随机抽取一个子集来估计Hessian矩阵，再对这个近似Hessian做截断特征值处理（eigenvalue thresholding），把小特征值统一替换为第r+1大的特征值，从而既保留了主要的曲率信息，又避免了小特征值带来的数值不稳定。理论分析证明，NewSamp具有"复合收敛"特性——迭代初期呈二次收敛（像牛顿法一样快），接近极小值时转为线性收敛，且线性收敛的条件数由全谱的条件数缩减为仅涉及第r+1大特征值的局部条件数，对谱结构明显的数据集提升显著。这项工作首次给出了子采样二阶方法的量化收敛率保证，并在多个真实数据集上验证了算法的高效性，填补了该领域长期缺乏严格理论分析的空白。
原文 arXiv:1508.02810;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1508.02810v2