# Stochastic Gradient Methods with Preconditioned Updates

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 35 references that are in the map.
- First posted on arXiv 1 Jun 2022.

## Builds on (most cited first, 21 of 21)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [On the Convergence of Adam and Beyond](https://mlsanity.com/paper/1904.09237/) (2019)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [ADAHESSIAN: An Adaptive Second Order Optimizer for Machine Learning](https://mlsanity.com/paper/2006.00719/) (2020)
- [A Simple Convergence Proof of Adam and Adagrad](https://mlsanity.com/paper/2003.02395/) (2020)
- [Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimization](https://mlsanity.com/paper/1308.6594/) (2013)
- [PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization](https://mlsanity.com/paper/2008.10898/) (2020)
- [A Proximal Stochastic Gradient Method with Progressive Variance Reduction](https://mlsanity.com/paper/1403.4699/) (2014)
- [Non-convex Finite-Sum Optimization Via SCSG Methods](https://mlsanity.com/paper/1706.09156/) (2017)
- [Variance Reduced Stochastic Gradient Descent with Neighbors](https://mlsanity.com/paper/1506.03662/) (2015)
- [ProxSARAH: An Efficient Algorithmic Framework for Stochastic Composite Nonconvex Optimization](https://mlsanity.com/paper/1902.05679/) (2019)
- [ZeroSARAH: Efficient Nonconvex Finite-Sum Optimization with Zero Full Gradient Computation](https://mlsanity.com/paper/2103.01447/) (2021)
- [A Unified Analysis of Stochastic Gradient Methods for Nonconvex Federated Optimization](https://mlsanity.com/paper/2006.07013/) (2020)
- [Doubly Adaptive Scaled Algorithm for Machine Learning Using Second-Order Information](https://mlsanity.com/paper/2109.05198/) (2021)
- [L-SVRG and L-Katyusha with Arbitrary Sampling](https://mlsanity.com/paper/1906.01481/) (2019)
- [Semi-Stochastic Gradient Descent Methods](https://mlsanity.com/paper/1312.1666/) (2013)
- [Scaling Up Quasi-Newton Algorithms: Communication Efficient Distributed SR1](https://mlsanity.com/paper/1905.13096/) (2019)
- [SONIA: A Symmetric Blockwise Truncated Optimization Algorithm](https://mlsanity.com/paper/2006.03949/) (2020)

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

- [Stochastic Gradient Descent with Preconditioned Polyak Step-size](https://mlsanity.com/paper/2310.02093/) (2023)
- [Local Methods with Adaptivity via Scaling](https://mlsanity.com/paper/2406.00846/) (2024)
- [Just a Simple Transformation is Enough for Data Protection in Vertical Federated Learning](https://mlsanity.com/paper/2412.11689/) (2024)
- [AdaCubic: An Adaptive Cubic Regularization Optimizer for Deep Learning](https://mlsanity.com/paper/2604.09437/) (2026)
- [SVRG and Beyond via Posterior Correction](https://mlsanity.com/paper/2512.01930/) (2025)

## Abstract (arXiv)

This work considers the non-convex finite sum minimization problem. There are several algorithms for such problems, but existing methods often work poorly when the problem is badly scaled and/or ill-conditioned, and a primary goal of this work is to introduce methods that alleviate this issue. Thus, here we include a preconditioner based on Hutchinson's approach to approximating the diagonal of the Hessian, and couple it with several gradient-based methods to give new scaled algorithms: Scaled SARAH and Scaled L-SVRG. Theoretical complexity guarantees under smoothness assumptions are presented. We prove linear convergence when both smoothness and the PL condition are assumed. Our adaptively scaled methods use approximate partial second-order curvature information and, therefore, can better mitigate the impact of badly scaled problems. This improved practical performance is demonstrated in the numerical experiments also presented in this work.