Fast curvature matrix-vector products for second-order gradient descent.

Area of Science:

• Machine Learning
• Optimization Algorithms
• Numerical Analysis

Background:

• Second-order gradient methods (Newton, Gauss-Newton, Levenberg-Marquardt, natural gradient) are crucial for optimization but computationally intensive.
• Existing acceleration techniques for on-line learning, such as matrix momentum and stochastic meta-descent (SMD), have been developed through distinct theoretical frameworks.

Purpose of the Study:

• To introduce a generic, computationally efficient method for approximating various second-order gradient steps.
• To provide a unified perspective on existing acceleration techniques and derive potential improvements.

Main Methods:

• Developing a method to approximate second-order gradient steps using specialized curvature matrix-vector products.
• Achieving linear time complexity per iteration for these approximations, with matrix-vector products computable in O(n).
• Demonstrating that matrix momentum and stochastic meta-descent (SMD) are specific instances of this generic approach.

Main Results:

• The proposed method enables efficient iterative approximation of Newton, Gauss-Newton, Levenberg-Marquardt, and natural gradient steps.
• The computational cost per iteration is reduced to linear time.
• The unified framework provides novel insights into the operation of matrix momentum and SMD, leading to enhanced performance for SMD.

Conclusions:

• A generic and efficient method for approximating second-order gradient steps has been successfully proposed.
• This work unifies and improves upon existing on-line learning acceleration techniques, particularly SMD.
• The findings offer a new perspective on the interplay between optimization algorithms and acceleration methods in machine learning.