Accelerating incremental gradient optimization with curvature information
Accelerating incremental gradient optimization with curvature information
复制标题
DOI：
10.1007/s10589-020-00183-1
复制
发表时间：
2018-05
影响因子：
2.2
通讯作者：
Hoi-To Wai;Wei Shi;César A. Uribe;A. Nedić;A. Scaglione
中科院分区：
文献类型：
--
作者：
Hoi-To Wai;Wei Shi;César A. Uribe;A. Nedić;A. Scaglione
本文研究了一种利用曲率信息求解强凸有限和优化问题的增量聚集梯度法加速技术。这些令人感兴趣的优化问题出现在大规模学习应用中。我们的技术利用曲率辅助梯度跟踪步骤，使用Hessian信息逐步产生准确的梯度估计。我们提出并分析了两种利用新技术的方法，即曲率辅助IAG （CIAG）方法和加速CIAG （A-CIAG）方法，这两种方法分别类似于梯度法和Nesterov加速梯度法。设为目标函数的条件数，证明了ciagmethod和a - ciagmethod的线性收敛速率，其中常数与初始点到最优解的距离成反比。当初始迭代接近最优解时，线性收敛率与梯度和加速梯度方法相匹配，尽管ciaganda - ciaga在增量设置中运行，计算复杂度严格降低。数值实验证实了我们的发现。本文使用的源代码可以在http://github.com/hoitowai/ciag/上找到。
This paper studies an acceleration technique for incremental aggregated gradient (IAG) method through the use ofcurvatureinformation for solving strongly convex finite sum optimization problems. These optimization problems of interest arise in large-scale learning applications. Our technique utilizes a curvature-aided gradient tracking step to produce accurate gradient estimates incrementally using Hessian information. We propose and analyze two methods utilizing the new technique, the curvature-aided IAG (CIAG) method and the accelerated CIAG (A-CIAG) method, which are analogous to gradient method and Nesterov’s accelerated gradient method, respectively. Settingto be the condition number of the objective function, we prove theRlinear convergence rates offor theCIAGmethod, andfor theA-CIAGmethod, whereare constants inversely proportional to the distance between the initial point and the optimal solution. When the initial iterate is close to the optimal solution, theRlinear convergence rates match with the gradient and accelerated gradient method, albeitCIAGandA-CIAGoperate in an incremental setting with strictly lower computation complexity. Numerical experiments confirm our findings. The source codes used for this paper can be found on http://github.com/hoitowai/ciag/.