CAO: Curvature-Adaptive Optimization via Periodic Low-Rank Hessian Sketching

2025/11/16 by Wenqi Du, Du, Wenzhang
Computer Science · Engineering · #3D Shape Modeling and Analysis #65K05 #68T07 #90C26 #90C30 #FOS: Computer and information sciences #G.1.6 #I.2.6 #I.5.1 #Machine Learning (cs.LG) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2511.12548

openalex publication_date 2025/11/16 · openalex created_date 2025/11/19 · openalex updated_date 2026/07/28

Abstract

First-order optimizers are reliable but slow in sharp, anisotropic regions. We study a curvature-adaptive method that periodically sketches a low-rank Hessian subspace via Hessian--vector products and preconditions gradients only in that subspace, leaving the orthogonal complement first-order. For L-smooth non-convex objectives, we recover the standard O(1/T) stationarity guarantee with a widened stable stepsize range; under a Polyak--Lojasiewicz (PL) condition with bounded residual curvature outside the sketch, the loss contracts at refresh steps. On CIFAR-10/100 with ResNet-18/34, the method enters the low-loss region substantially earlier: measured by epochs to a pre-declared train-loss threshold (0.75), it reaches the threshold 2.95x faster than Adam on CIFAR-100/ResNet-18, while matching final test accuracy. The approach is one-knob: performance is insensitive to the sketch rank k across 1,3,5, and k=0 yields a principled curvature-free ablation. We release anonymized logs and scripts that regenerate all figures and tables.

Citations

• An Investigation into Neural Net Optimization via Hessian Eigenvalue\n Density
• Shampoo: Preconditioned Stochastic Tensor Optimization
• Empirical Analysis of the Hessian of Over-Parametrized Neural Networks
• How to Escape Saddle Points Efficiently
• Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Łojasiewicz Condition
• Deep Residual Learning for Image Recognition
• Optimizing Neural Networks with Kronecker-factored Approximate Curvature
• Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition
• Adam: A Method for Stochastic Optimization
• On the difficulty of training Recurrent Neural Networks
• A Stochastic Approximation Method

Related

• Curvature-Adaptive Perturbation and Subspace Descent for Robust Saddle Point Escape in High-Dimensional Optimization
• First-ish Order Methods: Hessian-aware Scalings of Gradient Descent
• Self-Tuning Stochastic Optimization with Curvature-Aware Gradient Filtering
• Local Curvature Descent: Squeezing More Curvature out of Standard and Polyak Gradient Descent
• Directional Curvature from Armijo Backtracking: A Low-Cost Sharpness Probe and a Calibration-Free Learning-Rate Safeguard for Adam