# SAPPHIRE: Preconditioned Stochastic Variance Reduction for Faster Large-Scale Statistical Learning

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 39 of its 62 references that are in the map.
- First posted on arXiv 27 Jan 2025.

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

- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [SGD: General Analysis and Improved Rates](https://mlsanity.com/paper/1901.09401/) (2019)
- [Datamodels: Predicting Predictions from Training Data](https://mlsanity.com/paper/2202.00622/) (2022)
- [Stochastic Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1603.06160/) (2016)
- [Katyusha: The First Direct Acceleration of Stochastic Gradient Methods](https://mlsanity.com/paper/1603.05953/) (2016)
- [Challenges in Training PINNs: A Loss Landscape Perspective](https://mlsanity.com/paper/2402.01868/) (2024)
- [Neural Networks are Convex Regularizers: Exact Polynomial-time Convex Optimization Formulations for Two-layer Networks](https://mlsanity.com/paper/2002.10553/) (2020)
- [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)
- [Variance Reduction for Faster Non-Convex Optimization](https://mlsanity.com/paper/1603.05643/) (2016)
- [Sub-sampled Cubic Regularization for Non-convex Optimization](https://mlsanity.com/paper/1705.05933/) (2017)
- [Stochastic Cubic Regularization for Fast Nonconvex Optimization](https://mlsanity.com/paper/1711.02838/) (2017)
- [Natasha 2: Faster Non-Convex Optimization Than SGD](https://mlsanity.com/paper/1708.08694/) (2017)
- [A Progressive Batching L-BFGS Method for Machine Learning](https://mlsanity.com/paper/1802.05374/) (2018)
- [Newton-Type Methods for Non-Convex Optimization Under Inexact Hessian Information](https://mlsanity.com/paper/1708.07164/) (2017)
- [A Linearly-Convergent Stochastic L-BFGS Algorithm](https://mlsanity.com/paper/1508.02087/) (2015)
- [Catalyst Acceleration for First-order Convex Optimization: from Theory to Practice](https://mlsanity.com/paper/1712.05654/) (2017)
- [Exact and Inexact Subsampled Newton Methods for Optimization](https://mlsanity.com/paper/1609.08502/) (2016)
- [RSN: Randomized Subspace Newton](https://mlsanity.com/paper/1905.10874/) (2019)
- [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)
- [Global linear convergence of Newton's method without strong-convexity or Lipschitz gradients](https://mlsanity.com/paper/1806.00413/) (2018)
- [Fixed-Rank Approximation of a Positive-Semidefinite Matrix from Streaming Data](https://mlsanity.com/paper/1706.05736/) (2017)
- [On the Complexity Analysis of Randomized Block-Coordinate Descent Methods](https://mlsanity.com/paper/1305.4723/) (2013)
- [Optimal Black-Box Reductions Between Optimization Objectives](https://mlsanity.com/paper/1603.05642/) (2016)
- [Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation](https://mlsanity.com/paper/1910.04920/) (2019)
- [Sketched Newton-Raphson](https://mlsanity.com/paper/2006.12120/) (2020)
- [PROMISE: Preconditioned Stochastic Optimization Methods by Incorporating Scalable Curvature Estimates](https://mlsanity.com/paper/2309.02014/) (2023)
- [Local Convergence Properties of SAGA/Prox-SVRG and Acceleration](https://mlsanity.com/paper/1802.02554/) (2018)
- [ControlBurn: Feature Selection by Sparse Forests](https://mlsanity.com/paper/2107.00219/) (2021)

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

- [Faster Low-Rank Approximation and Kernel Ridge Regression via the Block-Nystr"om Method](https://mlsanity.com/paper/2506.17556/) (2025)
- [SVRG and Beyond via Posterior Correction](https://mlsanity.com/paper/2512.01930/) (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)

## Abstract (arXiv)

Regularized empirical risk minimization (rERM) has become important in data-intensive fields such as genomics and advertising, with stochastic gradient methods typically used to solve the largest problems. However, ill-conditioned objectives and non-smooth regularizers undermine the performance of traditional stochastic gradient methods, leading to slow convergence and significant computational costs. To address these challenges, we propose the textttSAPPHIRE (Sketching-based Approximations for Proximal Preconditioning and Hessian Inexactness with Variance-REeduced Gradients) algorithm, which integrates sketch-based preconditioning to tackle ill-conditioning and uses a scaled proximal mapping to minimize the non-smooth regularizer. This stochastic variance-reduced algorithm achieves condition-number-free linear convergence to the optimum, delivering an efficient and scalable solution for ill-conditioned composite large-scale convex machine learning problems. Extensive experiments on lasso and logistic regression demonstrate that textttSAPPHIRE often converges 20 times faster than other common choices such as textttCatalyst, textttSAGA, and textttSVRG. This advantage persists even when the objective is non-convex or the preconditioner is infrequently updated, highlighting its robust and practical effectiveness.