# Second-order Information Promotes Mini-Batch Robustness in Variance-Reduced Gradients

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 50 references that are in the map.
- First posted on arXiv 23 Apr 2024.

## Builds on (most cited first, 30 of 31)

- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [Minimizing Finite Sums with the Stochastic Average Gradient](https://mlsanity.com/paper/1309.2388/) (2013)
- [Katyusha: The First Direct Acceleration of Stochastic Gradient Methods](https://mlsanity.com/paper/1603.05953/) (2016)
- [A Proximal Stochastic Gradient Method with Progressive Variance Reduction](https://mlsanity.com/paper/1403.4699/) (2014)
- [Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergence](https://mlsanity.com/paper/1505.02250/) (2015)
- [CoCoA: A General Framework for Communication-Efficient Distributed Optimization](https://mlsanity.com/paper/1611.02189/) (2016)
- [Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loop](https://mlsanity.com/paper/1901.08689/) (2019)
- [A Universal Catalyst for First-Order Optimization](https://mlsanity.com/paper/1506.02186/) (2015)
- [A Progressive Batching L-BFGS Method for Machine Learning](https://mlsanity.com/paper/1802.05374/) (2018)
- [Variance Reduced Stochastic Gradient Descent with Neighbors](https://mlsanity.com/paper/1506.03662/) (2015)
- [A Linearly-Convergent Stochastic L-BFGS Algorithm](https://mlsanity.com/paper/1508.02087/) (2015)
- [Exact and Inexact Subsampled Newton Methods for Optimization](https://mlsanity.com/paper/1609.08502/) (2016)
- [Convergence rates of sub-sampled Newton methods](https://mlsanity.com/paper/1508.02810/) (2015)
- [A Multi-Batch L-BFGS Method for Machine Learning](https://mlsanity.com/paper/1605.06049/) (2016)
- [An Asynchronous Parallel Stochastic Coordinate Descent Algorithm](https://mlsanity.com/paper/1311.1873/) (2013)
- [Stochastic Block BFGS: Squeezing More Curvature out of Data](https://mlsanity.com/paper/1603.09649/) (2016)
- [An Investigation of Newton-Sketch and Subsampled Newton Methods](https://mlsanity.com/paper/1705.06211/) (2017)
- [Solving Ridge Regression using Sketched Preconditioned SVRG](https://mlsanity.com/paper/1602.02350/) (2016)
- [Katyusha X: Practical Momentum Method for Stochastic Sum-of-Nonconvex Optimization](https://mlsanity.com/paper/1802.03866/) (2018)
- [Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergence](https://mlsanity.com/paper/2204.09266/) (2022)
- [Semi-Stochastic Gradient Descent Methods](https://mlsanity.com/paper/1312.1666/) (2013)
- [Accelerating Stochastic Sequential Quadratic Programming for Equality Constrained Optimization using Predictive Variance Reduction](https://mlsanity.com/paper/2204.04161/) (2022)
- [Stochastic Variance-Reduced Cubic Regularization for Nonconvex Optimization](https://mlsanity.com/paper/1802.07372/) (2018)
- [IQN: An Incremental Quasi-Newton Method with Local Superlinear Convergence Rate](https://mlsanity.com/paper/1702.00709/) (2017)
- [Accelerating Variance-Reduced Stochastic Gradient Methods](https://mlsanity.com/paper/1910.09494/) (2019)
- [Stochastic Variance-Reduced Newton: Accelerating Finite-Sum Minimization with Large Batches](https://mlsanity.com/paper/2206.02702/) (2022)
- [A Variance Reduced Stochastic Newton Method](https://mlsanity.com/paper/1503.08316/) (2015)
- [Acceleration of SVRG and Katyusha X by Inexact Preconditioning](https://mlsanity.com/paper/1905.09734/) (2019)
- [Batch-Expansion Training: An Efficient Optimization Framework](https://mlsanity.com/paper/1704.06731/) (2017)

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

- [SAPPHIRE: Preconditioned Stochastic Variance Reduction for Faster Large-Scale Statistical Learning](https://mlsanity.com/paper/2501.15941/) (2025)
- [Design Criteria for SGD Preconditioners: Local Conditioning, Noise Floors, and Basin Stability](https://mlsanity.com/paper/2511.19716/) (2025)
- [SVRG and Beyond via Posterior Correction](https://mlsanity.com/paper/2512.01930/) (2025)

## Abstract (arXiv)

We show that, for finite-sum minimization problems, incorporating partial second-order information of the objective function can dramatically improve the robustness to mini-batch size of variance-reduced stochastic gradient methods, making them more scalable while retaining their benefits over traditional Newton-type approaches. We demonstrate this phenomenon on a prototypical stochastic second-order algorithm, called Mini-Batch Stochastic Variance-Reduced Newton (textttMb-SVRN), which combines variance-reduced gradient estimates with access to an approximate Hessian oracle. In particular, we show that when the data size n is sufficiently large, i.e., ngg α2kappa, where kappa is the condition number and α is the Hessian approximation factor, then textttMb-SVRN achieves a fast linear convergence rate that is independent of the gradient mini-batch size b, as long b is in the range between 1 and bmax=O(n/(α log n)). Only after increasing the mini-batch size past this critical point bmax, the method begins to transition into a standard Newton-type algorithm which is much more sensitive to the Hessian approximation quality. We demonstrate this phenomenon empirically on benchmark optimization tasks showing that, after tuning the step size, the convergence rate of textttMb-SVRN remains fast for a wide range of mini-batch sizes, and the dependence of the phase transition point bmax on the Hessian approximation factor α aligns with our theoretical predictions.