An efficient low-complexity stochastic BFGS algorithm using matrix diagonal approximations for nonconvex optimization in machine learning

doi:10.1016/j.cam.2025.117242

An efficient low-complexity stochastic BFGS algorithm using matrix diagonal approximations for nonconvex optimization in machine learning

2026-05-15

0

PRE

AI

DOI：10.1016/j.cam.2025.117242

Original

Original request for help

Save

Abstract

En 中文

Second-order optimization methods are often limited by their high computational cost in largescale machine learning. To address this, we propose a computationally efficient diagonal approximation of the BFGS correction matrix, replacing matrix-vector products with vector-vector products and treating the coefficient of the BFGS correction term as a tunable hyperparameter. These adjustments collectively yield a reduction in per-iteration complexity. Additionally, we simplify the coefficients in the nonlinear conjugate gradient (CG) direction into a single hyperparameter, integrating it into our modified BFGS framework to accelerate convergence. Theoretically, we establish the convergence of the last iteration of the proposed BFGS method under nonconvex settings-a better guarantee than those typically derived for the average or best iterate. Finally, we demonstrate the efficacy of our approach through experiments on benchmark datasets, comparing it against widely-used first-order and quasi-Newton baselines.

Keywords:

Stochastic optimization

Low-complexity

Quasi-Newton

Non-ergodic convergence

Nonconvex optimization

An efficient low-complexity stochastic BFGS algorithm using matrix diagonal approximations for nonconvex optimization in machine learning

Abstract

Journal

Organization