Exploiting Local Convergence of Quasi-Newton Methods Globally: Adaptive Sample Size Approach
Exploiting Local Convergence of Quasi-Newton Methods Globally: Adaptive Sample Size Approach
复制标题
DOI：
--
复制
发表时间：
2021-06
期刊：
影响因子：
--
通讯作者：
Qiujiang Jin;Aryan Mokhtari
中科院分区：
文献类型：
--
作者：
Qiujiang Jin;Aryan Mokhtari
在本文中，我们研究了准Newton方法在大型数据集中定义的经验风险最小化（ERM）问题的应用。可以执行传统的确定性和随机准Newton方法来解决此类问题；但是，众所周知，它们的全球收敛速率可能不比一阶方法更好，而其本地超级线性收敛仅在学习过程结束时才出现。在本文中，我们使用一种自适应样本大小方案，该方案利用全球及整个学习过程中准牛顿方法的超线性收敛性。所提出的自适应样本量算法的主要思想是从一小部分数据点开始，并在其统计精度内解决其相应的ERM问题，然后将样本量几何地数放大，并使用与较小的问题相对应的最佳解决方案设置为使用更多样本解决后续ERM问题的初始点。我们表明，如果初始样本量足够大，并且我们使用准Newton方法来求解每个子问题，那么子问题可以快速求解超线性（最多三个迭代之后），因为我们保证迭代始终在社区中留在一个社区中，准Newton方法会收敛。各种数据集上的数值实验证实了我们的理论结果，并证明了我们方法的计算优势。
In this paper, we study the application of quasi-Newton methods for solving empirical risk minimization (ERM) problems defined over a large dataset. Traditional deterministic and stochastic quasi-Newton methods can be executed to solve such problems; however, it is known that their global convergence rate may not be better than first-order methods, and their local superlinear convergence only appears towards the end of the learning process. In this paper, we use an adaptive sample size scheme that exploits the superlinear convergence of quasi-Newton methods globally and throughout the entire learning process. The main idea of the proposed adaptive sample size algorithms is to start with a small subset of data points and solve their corresponding ERM problem within its statistical accuracy, and then enlarge the sample size geometrically and use the optimal solution of the problem corresponding to the smaller set as an initial point for solving the subsequent ERM problem with more samples. We show that if the initial sample size is sufficiently large and we use quasi-Newton methods to solve each subproblem, the subproblems can be solved superlinearly fast (after at most three iterations), as we guarantee that the iterates always stay within a neighborhood that quasi-Newton methods converge superlinearly. Numerical experiments on various datasets confirm our theoretical results and demonstrate the computational advantages of our method.