First-ish Order Methods: Hessian-aware Scalings of Gradient Descent
This addresses the problem of expensive tuning in optimization for machine learning practitioners, though it is incremental as it builds on existing gradient descent methods.
The paper tackles the sensitivity of gradient descent to learning rate tuning by incorporating Hessian information to scale the gradient direction, achieving linear convergence with a unit step size near local minima and validating results on convex and nonconvex tasks.
Gradient descent is the primary workhorse for optimizing large-scale problems in machine learning. However, its performance is highly sensitive to the choice of the learning rate. A key limitation of gradient descent is its lack of natural scaling, which often necessitates expensive line searches or heuristic tuning to determine an appropriate step size. In this paper, we address this limitation by incorporating Hessian information to scale the gradient direction. By accounting for the curvature of the function along the gradient, our adaptive, Hessian-aware scaling method ensures a local unit step size guarantee, even in nonconvex settings. Near a local minimum that satisfies the second-order sufficient conditions, our approach achieves linear convergence with a unit step size. We show that our method converges globally under a significantly weaker version of the standard Lipschitz gradient smoothness assumption. Even when Hessian information is inexact, the local unit step size guarantee and global convergence properties remain valid under mild conditions. Finally, we validate our theoretical results empirically on a range of convex and nonconvex machine learning tasks, showcasing the effectiveness of the approach.