When stochastic memoryless BFGS meets nonmonotone line search: A way for efficient over-parameterized learning

Most existing stochastic L-BFGS methods employ constant or diminishing step-size schedules, which may limit their capability to exploit curvature information and adapt to the local geometry effectively. In this work, we propose SMBFGS, a stochastic memoryless BFGS method that incorporates the nonmonotone line search for over-parameterized learning problems. The method employs a damped quasi-Newton update to preserve the positive definiteness of the inverse Hessian approximation, thereby ensuring the descent property of resulting search directions. Its step size is then selected adaptively through the stochastic nonmonotone line search. We establish the linear convergence of SMBFGS in the general nonconvex setting under suitable interpolation assumptions. Numerical experiments on training deep neural networks demonstrate that SMBFGS outperforms representative stochastic L-BFGS methods and widely used optimizers, including Adam and AdamW, in most cases.