# A Linearly-Convergent Stochastic L-BFGS Algorithm

arXiv: https://arxiv.org/abs/1508.02087 · HTML: https://mlsanity.com/paper/1508.02087/

## Key facts

- Cited by 39 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Aug 2015.

## Built on by (most cited first, 30 of 39)

- [An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methods](https://mlsanity.com/paper/2211.07937/) (2022)
- [SP2: A Second Order Stochastic Polyak Method](https://mlsanity.com/paper/2207.08171/) (2022)
- [Stochastic Variance-Reduced Newton: Accelerating Finite-Sum Minimization with Large Batches](https://mlsanity.com/paper/2206.02702/) (2022)
- [SketchySGD: Reliable Stochastic Optimization via Randomized Curvature Estimates](https://mlsanity.com/paper/2211.08597/) (2022)
- [Curvature-Aware Training for Coordinate Networks](https://mlsanity.com/paper/2305.08552/) (2023)
- [Nys-Newton: Nystr"om-Approximated Curvature for Stochastic Optimization](https://mlsanity.com/paper/2110.08577/) (2021)
- [mL-BFGS: A Momentum-based L-BFGS for Distributed Large-Scale Neural Network Optimization](https://mlsanity.com/paper/2307.13744/) (2023)
- [SOFIM: Stochastic Optimization Using Regularized Fisher Information Matrix](https://mlsanity.com/paper/2403.02833/) (2024)
- [SAPPHIRE: Preconditioned Stochastic Variance Reduction for Faster Large-Scale Statistical Learning](https://mlsanity.com/paper/2501.15941/) (2025)
- [FedSSO: A Federated Server-Side Second-Order Optimization Algorithm](https://mlsanity.com/paper/2206.09576/) (2022)
- [Stochastic Variable Metric Proximal Gradient with variance reduction for non-convex composite optimization](https://mlsanity.com/paper/2301.00631/) (2023)
- [MLPGradientFlow: going with the flow of multilayer perceptrons (and finding minima fast and accurately)](https://mlsanity.com/paper/2301.10638/) (2023)
- [Exponential Quantum Communication Advantage in Distributed Inference and Learning](https://mlsanity.com/paper/2310.07136/) (2023)
- [Second-order Information Promotes Mini-Batch Robustness in Variance-Reduced Gradients](https://mlsanity.com/paper/2404.14758/) (2024)
- [ONER: Online Experience Replay for Incremental Anomaly Detection](https://mlsanity.com/paper/2412.03907/) (2024)
- [Quasi-Newton Quasi-Monte Carlo for variational Bayes](https://mlsanity.com/paper/2104.02865/) (2021)
- [Exploiting Local Convergence of Quasi-Newton Methods Globally: Adaptive Sample Size Approach](https://mlsanity.com/paper/2106.05445/) (2021)
- [Stochastic Steffensen method](https://mlsanity.com/paper/2211.15310/) (2022)
- [Incremental Quasi-Newton Methods with Faster Superlinear Convergence Rates](https://mlsanity.com/paper/2402.02359/) (2024)
- [TabNSA: Native Sparse Attention for Efficient Tabular Data Learning](https://mlsanity.com/paper/2503.09850/) (2025)
- [Adaptive First- and Second-Order Algorithms for Large-Scale Machine Learning](https://mlsanity.com/paper/2111.14761/) (2021)
- [On the efficiency of Stochastic Quasi-Newton Methods for Deep Learning](https://mlsanity.com/paper/2205.09121/) (2022)
- [Communication-Efficient {Federated} Learning Using Censored Heavy Ball Descent](https://mlsanity.com/paper/2209.11944/) (2022)
- [Sharpened Lazy Incremental Quasi-Newton Method](https://mlsanity.com/paper/2305.17283/) (2023)
- [A Stochastic Quasi-Newton Method for Non-convex Optimization with Non-uniform Smoothness](https://mlsanity.com/paper/2403.15244/) (2024)
- [A neural network approach for solving the Monge-Amp`ere equation with transport boundary condition](https://mlsanity.com/paper/2410.19496/) (2024)
- [An Evaluation Framework for Product Images Background Inpainting based on Human Feedback and Product Consistency](https://mlsanity.com/paper/2412.17504/) (2024)
- [DexAvatar: 3D Sign Language Reconstruction with Hand and Body Pose Priors](https://mlsanity.com/paper/2512.21054/) (2025)
- [Neural-network methods for two-dimensional finite-source reflector design](https://mlsanity.com/paper/2604.02184/) (2026)
- [SPIRAL: A superlinearly convergent incremental proximal algorithm for nonconvex finite sum minimization](https://mlsanity.com/paper/2207.08195/) (2022)

## Abstract (arXiv)

We propose a new stochastic L-BFGS algorithm and prove a linear convergence rate for strongly convex and smooth functions. Our algorithm draws heavily from a recent stochastic variant of L-BFGS proposed in Byrd et al. (2014) as well as a recent approach to variance reduction for stochastic gradient descent from Johnson and Zhang (2013). We demonstrate experimentally that our algorithm performs well on large-scale convex and non-convex optimization problems, exhibiting linear convergence and rapidly solving the optimization problems to high levels of precision. Furthermore, we show that our algorithm performs well for a wide-range of step sizes, often differing by several orders of magnitude.