# Stochastic Block BFGS: Squeezing More Curvature out of Data

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

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Mar 2016.

## Built on by (most cited first, 24 of 24)

- [An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methods](https://mlsanity.com/paper/2211.07937/) (2022)
- [Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policies](https://mlsanity.com/paper/2210.01400/) (2022)
- [Tensor Normal Training for Deep Learning Models](https://mlsanity.com/paper/2106.02925/) (2021)
- [SP2: A Second Order Stochastic Polyak Method](https://mlsanity.com/paper/2207.08171/) (2022)
- [Globally Convergent Multilevel Training of Deep Residual Networks](https://mlsanity.com/paper/2107.07572/) (2021)
- [Stochastic Variance-Reduced Newton: Accelerating Finite-Sum Minimization with Large Batches](https://mlsanity.com/paper/2206.02702/) (2022)
- [Learning Physics Informed Neural ODEs With Partial Measurements](https://mlsanity.com/paper/2412.08681/) (2024)
- [A Mini-Block Fisher Method for Deep Neural Networks](https://mlsanity.com/paper/2202.04124/) (2022)
- [Covering Number of Real Algebraic Varieties and Beyond: Improved Bounds and Applications](https://mlsanity.com/paper/2311.05116/) (2023)
- [Kronecker-factored Quasi-Newton Methods for Deep Learning](https://mlsanity.com/paper/2102.06737/) (2021)
- [Towards a Better Theoretical Understanding of Independent Subnetwork Training](https://mlsanity.com/paper/2306.16484/) (2023)
- [mL-BFGS: A Momentum-based L-BFGS for Distributed Large-Scale Neural Network Optimization](https://mlsanity.com/paper/2307.13744/) (2023)
- [Non-Euclidean Broximal Point Method: A Blueprint for Geometry-Aware Optimization](https://mlsanity.com/paper/2510.00823/) (2025)
- [Stochastic Variable Metric Proximal Gradient with variance reduction for non-convex composite optimization](https://mlsanity.com/paper/2301.00631/) (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)
- [SASSHA: Sharpness-aware Adaptive Second-order Optimization with Stable Hessian Approximation](https://mlsanity.com/paper/2502.18153/) (2025)
- [Quasi-Newton Quasi-Monte Carlo for variational Bayes](https://mlsanity.com/paper/2104.02865/) (2021)
- [Incremental Quasi-Newton Methods with Faster Superlinear Convergence Rates](https://mlsanity.com/paper/2402.02359/) (2024)
- [qNBO: quasi-Newton Meets Bilevel Optimization](https://mlsanity.com/paper/2502.01076/) (2025)
- [Learning-Augmented Sketches for Hessians](https://mlsanity.com/paper/2102.12317/) (2021)
- [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)

## Abstract (arXiv)

We propose a novel limited-memory stochastic block BFGS update for incorporating enriched curvature information in stochastic approximation methods. In our method, the estimate of the inverse Hessian matrix that is maintained by it, is updated at each iteration using a sketch of the Hessian, i.e., a randomly generated compressed form of the Hessian. We propose several sketching strategies, present a new quasi-Newton method that uses stochastic block BFGS updates combined with the variance reduction approach SVRG to compute batch stochastic gradients, and prove linear convergence of the resulting method. Numerical tests on large-scale logistic regression problems reveal that our method is more robust and substantially outperforms current state-of-the-art methods.