# SketchySGD: Reliable Stochastic Optimization via Randomized Curvature Estimates

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 69 references that are in the map.
- First posted on arXiv 16 Nov 2022.

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [OpenML: networked science in machine learning](https://mlsanity.com/paper/1407.7722/) (2014)
- [The generalization error of random features regression: Precise asymptotics and double descent curve](https://mlsanity.com/paper/1908.05355/) (2019)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Information-theoretic analysis of generalization capability of learning algorithms](https://mlsanity.com/paper/1705.07809/) (2017)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [SGD: General Analysis and Improved Rates](https://mlsanity.com/paper/1901.09401/) (2019)
- [Katyusha: The First Direct Acceleration of Stochastic Gradient Methods](https://mlsanity.com/paper/1603.05953/) (2016)
- [The Landscape of Empirical Risk for Non-convex Losses](https://mlsanity.com/paper/1607.06534/) (2016)
- [Generalization Error Bounds for Noisy, Iterative Algorithms](https://mlsanity.com/paper/1801.04295/) (2018)
- [Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergence](https://mlsanity.com/paper/1505.02250/) (2015)
- [Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent](https://mlsanity.com/paper/2005.08898/) (2020)
- [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)
- [Dimensionality Reduction for k-Means Clustering and Low Rank Approximation](https://mlsanity.com/paper/1410.6801/) (2014)
- [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)
- [Practical sketching algorithms for low-rank matrix approximation](https://mlsanity.com/paper/1609.00048/) (2016)
- [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)
- [Oracle Complexity of Second-Order Methods for Smooth Convex Optimization](https://mlsanity.com/paper/1705.07260/) (2017)
- [Fixed-Rank Approximation of a Positive-Semidefinite Matrix from Streaming Data](https://mlsanity.com/paper/1706.05736/) (2017)
- [Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation](https://mlsanity.com/paper/1910.04920/) (2019)
- [Adaptive Newton Sketch: Linear-time Optimization with Quadratic Convergence and Effective Hessian Dimensionality](https://mlsanity.com/paper/2105.07291/) (2021)
- [Convergence of trust-region methods based on probabilistic models](https://mlsanity.com/paper/1304.2808/) (2013)
- [Optimal mini-batch and step sizes for SAGA](https://mlsanity.com/paper/1902.00071/) (2019)
- [Newton-MR: Inexact Newton Method With Minimum Residual Sub-problem Solver](https://mlsanity.com/paper/1810.00303/) (2018)

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

- [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)
- [Newton Meets Marchenko-Pastur: Massively Parallel Second-Order Optimization with Hessian Sketching and Debiasing](https://mlsanity.com/paper/2410.01374/) (2024)
- [Accelerating Natural Gradient Descent for PINNs with Randomized Numerical Linear Algebra](https://mlsanity.com/paper/2505.11638/) (2025)
- [NysAct: A Scalable Preconditioned Gradient Descent using Nystrom Approximation](https://mlsanity.com/paper/2506.08360/) (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)

SketchySGD improves upon existing stochastic gradient methods in machine learning by using randomized low-rank approximations to the subsampled Hessian and by introducing an automated stepsize that works well across a wide range of convex machine learning problems. We show theoretically that SketchySGD with a fixed stepsize converges linearly to a small ball around the optimum. Further, in the ill-conditioned setting we show SketchySGD converges at a faster rate than SGD for least-squares problems. We validate this improvement empirically with ridge regression experiments on real data. Numerical experiments on both ridge and logistic regression problems with dense and sparse data, show that SketchySGD equipped with its default hyperparameters can achieve comparable or better results than popular stochastic gradient methods, even when they have been tuned to yield their best performance. In particular, SketchySGD is able to solve an ill-conditioned logistic regression problem with a data matrix that takes more than 840GB RAM to store, while its competitors, even when tuned, are unable to make any progress. SketchySGD's ability to work out-of-the box with its default hyperparameters and excel on ill-conditioned problems is an advantage over other stochastic gradient methods, most of which require careful hyperparameter tuning (especially of the learning rate) to obtain good performance and degrade in the presence of ill-conditioning.