Accelerating Incremental Gradient Optimization with Curvature Information

Code

• github.com/hoitowai/ciag
  OfficialIn papernone★ 0

Abstract

This paper studies an acceleration technique for incremental aggregated gradient ( IAG) method through the use of curvature information 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. Setting to be the condition number of the objective function, we prove the R linear convergence rates of 1 - 4c_0 (+1)^2 for the CIAG method, and 1 - c_12 for the A-CIAG method, where c_0,c_1 1 are constants inversely proportional to the distance between the initial point and the optimal solution. When the initial iterate is close to the optimal solution, the R linear convergence rates match with the gradient and accelerated gradient method, albeit CIAG and A-CIAG operate 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/.

Reproductions