Adaptive Low-Rank Hessian Approximation for Large-Scale Optimization: Theory, Algorithms, and Applications

We introduce the Adaptive Low-rank Hessian Approximation (ALHA) algorithm, a novel quasi-Newton method that dynamically adjusts the rank of the Hessian approximation based on local curvature information and approximation quality. Unlike classical limited-memory BFGS (L-BFGS) which maintains a fixed memory parameter m, ALHA adaptively increases or decreases the effective rank to balance computational efficiency with approximation accuracy. We establish rigorous convergence guarantees under standard assumptions: for L-smooth and µ-strongly convex functions, ALHA achieves linear convergence at rate O((1 − µ/L)^k), matching the optimal rate for first-order methods with curvature information. Our analysis introduces a novel spectral approximation quality metric that governs rank adaptation and provides explicit bounds on the approximation error. We prove that the adaptive mechanism maintains bounded rank while ensuring sufficient descent at each iteration. Comprehensive numerical experiments on quadratic optimization, logistic regression on MNIST, Rosenbrock function minimization, and neural network training demonstrate that ALHA consistently outperforms fixed-rank methods, achieving up to 40% reduction in iterations while maintaining comparable per-iteration cost. The algorithm is particularly effective for ill-conditioned problems where adaptive rank selection captures essential curvature directions.