# A Sketch-and-Project Analysis of Subsampled Natural Gradient Algorithms

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 62 references that are in the map.
- First posted on arXiv 28 Aug 2025.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [When and why PINNs fail to train: A neural tangent kernel perspective](https://mlsanity.com/paper/2007.14527/) (2020)
- [New insights and perspectives on the natural gradient method](https://mlsanity.com/paper/1412.1193/) (2014)
- [Ab-Initio Solution of the Many-Electron Schr"odinger Equation with Deep Neural Networks](https://mlsanity.com/paper/1909.02487/) (2019)
- [Handbook of Convergence Theorems for (Stochastic) Gradient Methods](https://mlsanity.com/paper/2301.11235/) (2023)
- [Determinantal Point Processes in Randomized Numerical Linear Algebra](https://mlsanity.com/paper/2005.03185/) (2020)
- [Gram-Gauss-Newton Method: Learning Overparameterized Neural Networks for Regression Problems](https://mlsanity.com/paper/1905.11675/) (2019)
- [Exact and Inexact Subsampled Newton Methods for Optimization](https://mlsanity.com/paper/1609.08502/) (2016)
- [Efficient Subsampled Gauss-Newton and Natural Gradient Methods for Training Neural Networks](https://mlsanity.com/paper/1906.02353/) (2019)
- [A Kaczmarz-inspired approach to accelerate the optimization of neural network wavefunctions](https://mlsanity.com/paper/2401.10190/) (2024)
- [Monte Carlo Markov Chain Algorithms for Sampling Strongly Rayleigh Distributions and Determinantal Point Processes](https://mlsanity.com/paper/1602.05242/) (2016)
- [Kronecker-Factored Approximate Curvature for Physics-Informed Neural Networks](https://mlsanity.com/paper/2405.15603/) (2024)
- [Position: Optimization in SciML Should Employ the Function Space Geometry](https://mlsanity.com/paper/2402.07318/) (2024)
- [SDNA: Stochastic Dual Newton Ascent for Empirical Risk Minimization](https://mlsanity.com/paper/1502.02268/) (2015)
- [Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decomposition](https://mlsanity.com/paper/2208.09585/) (2022)
- [Sampling from a k-DPP without looking at all items](https://mlsanity.com/paper/2006.16947/) (2020)
- [Geometry of learning neural quantum states](https://mlsanity.com/paper/1910.11163/) (2019)
- [Sketched Newton-Raphson](https://mlsanity.com/paper/2006.12120/) (2020)
- [Improving Energy Natural Gradient Descent through Woodbury, Momentum, and Randomization](https://mlsanity.com/paper/2505.12149/) (2025)
- [Convergence Analysis of Block Coordinate Algorithms with Determinantal Sampling](https://mlsanity.com/paper/1910.11561/) (2019)
- [Solving Dense Linear Systems Faster Than via Preconditioning](https://mlsanity.com/paper/2312.08893/) (2023)
- [Accelerated Stochastic Matrix Inversion: General Theory and Speeding up BFGS Rules for Faster Second-Order Optimization](https://mlsanity.com/paper/1802.04079/) (2018)
- [Sketchy Empirical Natural Gradient Methods for Deep Learning](https://mlsanity.com/paper/2006.05924/) (2020)
- [Stochastic Dual Ascent for Solving Linear Systems](https://mlsanity.com/paper/1512.06890/) (2015)
- [A Randomized Coordinate Descent Method with Volume Sampling](https://mlsanity.com/paper/1904.04587/) (2019)
- [Have ASkotch: A Neat Solution for Large-scale Kernel Ridge Regression](https://mlsanity.com/paper/2407.10070/) (2024)
- [Accurate Ab-initio Neural-network Solutions to Large-Scale Electronic Structure Problems](https://mlsanity.com/paper/2504.06087/) (2025)
- [Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems](https://mlsanity.com/paper/2405.05818/) (2024)
- [ANaGRAM: A Natural Gradient Relative to Adapted Model for efficient PINNs learning](https://mlsanity.com/paper/2412.10782/) (2024)

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

- [Stochastic Reconfiguration as Statistical Filtering for Overparameterized Neural Quantum States](https://mlsanity.com/paper/2609.23334/) (2026)
- [Randomized Advantage Transformation (RAT): Computing Natural Policy Gradients via Direct Backpropagation](https://mlsanity.com/paper/2605.18591/) (2026)

## Abstract (arXiv)

Subsampled natural gradient descent (SNG) has been used to enable high-precision scientific machine learning, but standard analyses based on stochastic preconditioning fail to provide insight into realistic small-sample settings. We overcome this limitation by instead analyzing SNG as a sketch-and-project method. Motivated by this lens, we discard the usual theoretical proxy which decouples gradients and preconditioners using two independent mini-batches, and we replace it with a new proxy based on squared volume sampling. Under this new proxy we show that the expectation of the SNG direction becomes equal to a preconditioned gradient descent step even in the presence of coupling, leading to (i) global convergence guarantees when using a single mini-batch of any size, and (ii) an explicit characterization of the convergence rate in terms of quantities related to the sketch-and-project structure. These findings in turn yield new insights into small-sample settings, for example by suggesting that the advantage of SNG over SGD is that it can more effectively exploit spectral decay in the model Jacobian. We also extend these ideas to explain a popular structured momentum scheme for SNG, known as SPRING, by showing that it arises naturally from accelerated sketch-and-project methods.