# PROMISE: Preconditioned Stochastic Optimization Methods by Incorporating Scalable Curvature Estimates

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 55 references that are in the map.
- First posted on arXiv 5 Sep 2023.

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

- [Global linear convergence of Newton's method without strong-convexity or Lipschitz gradients](https://mlsanity.com/paper/1806.00413/) (2018)
- [Stochastic Newton and Cubic Newton Methods with Simple Local Linear-Quadratic Rates](https://mlsanity.com/paper/1912.01597/) (2019)
- [Stochastic Variance-Reduced Newton: Accelerating Finite-Sum Minimization with Large Batches](https://mlsanity.com/paper/2206.02702/) (2022)

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

- [MARS: Unleashing the Power of Variance Reduction for Training Large Models](https://mlsanity.com/paper/2411.10438/) (2024)
- [Recent and Upcoming Developments in Randomized Numerical Linear Algebra for Machine Learning](https://mlsanity.com/paper/2406.11151/) (2024)
- [Gradient Methods with Online Scaling](https://mlsanity.com/paper/2411.01803/) (2024)
- [MARS-M: When Variance Reduction Meets Matrices](https://mlsanity.com/paper/2510.21800/) (2025)
- [SAPPHIRE: Preconditioned Stochastic Variance Reduction for Faster Large-Scale Statistical Learning](https://mlsanity.com/paper/2501.15941/) (2025)
- [Decoupling Variance and Scale-Invariant Updates in Adaptive Gradient Descent for Unified Vector and Matrix Optimization](https://mlsanity.com/paper/2602.06880/) (2026)
- [Turbocharging Gaussian Process Inference with Approximate Sketch-and-Project](https://mlsanity.com/paper/2505.13723/) (2025)
- [Faster Low-Rank Approximation and Kernel Ridge Regression via the Block-Nystr"om Method](https://mlsanity.com/paper/2506.17556/) (2025)
- [On-Average Stability of Multipass Preconditioned SGD and Effective Dimension](https://mlsanity.com/paper/2603.11989/) (2026)
- [GPU-Enabled Large-Scale Optimization Using Randomized Linear Algebra](https://mlsanity.com/paper/2609.08136/) (2026)
- [BLOKS: Scaling Kernel Solvers with Sketched Block Preconditioning](https://mlsanity.com/paper/2610.13382/) (2026)

## Abstract (arXiv)

This paper introduces PROMISE (Preconditioned Stochastic Optimization Methods by Incorporating Scalable Curvature Estimates), a suite of sketching-based preconditioned stochastic gradient algorithms for solving large-scale convex optimization problems arising in machine learning. PROMISE includes preconditioned versions of SVRG, SAGA, and Katyusha; each algorithm comes with a strong theoretical analysis and effective default hyperparameter values. In contrast, traditional stochastic gradient methods require careful hyperparameter tuning to succeed, and degrade in the presence of ill-conditioning, a ubiquitous phenomenon in machine learning. Empirically, we verify the superiority of the proposed algorithms by showing that, using default hyperparameter values, they outperform or match popular tuned stochastic gradient optimizers on a test bed of 51 ridge and logistic regression problems assembled from benchmark machine learning repositories. On the theoretical side, this paper introduces the notion of quadratic regularity in order to establish linear convergence of all proposed methods even when the preconditioner is updated infrequently. The speed of linear convergence is determined by the quadratic regularity ratio, which often provides a tighter bound on the convergence rate compared to the condition number, both in theory and in practice, and explains the fast global linear convergence of the proposed methods.