# Sparse Data Augmentation for Optimization with Provable Guarantees

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 51 of its 65 references that are in the map.
- First posted on arXiv 8 Sep 2026.

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

- [Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges](https://mlsanity.com/paper/2104.13478/) (2021)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [E(3)-Equivariant Graph Neural Networks for Data-Efficient and Accurate Interatomic Potentials](https://mlsanity.com/paper/2101.03164/) (2021)
- [Momentum-Based Variance Reduction in Non-Convex SGD](https://mlsanity.com/paper/1905.10018/) (2019)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [Frame Averaging for Invariant and Equivariant Network Design](https://mlsanity.com/paper/2110.03336/) (2021)
- [Stochastic Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1603.06160/) (2016)
- [Lorentz Group Equivariant Neural Network for Particle Physics](https://mlsanity.com/paper/2006.04780/) (2020)
- [Artificial Intelligence for Science in Quantum, Atomistic, and Continuum Systems](https://mlsanity.com/paper/2307.08423/) (2023)
- [PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization](https://mlsanity.com/paper/2008.10898/) (2020)
- [Random Reshuffling: Simple Analysis with Vast Improvements](https://mlsanity.com/paper/2006.05988/) (2020)
- [Equivariance with Learned Canonicalization Functions](https://mlsanity.com/paper/2211.06489/) (2022)
- [A Kernel Theory of Modern Data Augmentation](https://mlsanity.com/paper/1803.06084/) (2018)
- [Provably Strict Generalisation Benefit for Equivariant Models](https://mlsanity.com/paper/2102.10333/) (2021)
- [Learning with invariances in random features and kernel models](https://mlsanity.com/paper/2102.13219/) (2021)
- [Automatic Symmetry Discovery with Lie Algebra Convolutional Network](https://mlsanity.com/paper/2109.07103/) (2021)
- [Residual Pathway Priors for Soft Equivariance Constraints](https://mlsanity.com/paper/2112.01388/) (2021)
- [SGD with shuffling: optimal rates without component convexity and large epoch requirements](https://mlsanity.com/paper/2006.06946/) (2020)
- [Learning Symmetric Embeddings for Equivariant World Models](https://mlsanity.com/paper/2204.11371/) (2022)
- [Equivariant Frames and the Impossibility of Continuous Canonicalization](https://mlsanity.com/paper/2402.16077/) (2024)
- [Invariance Learning in Deep Neural Networks with Differentiable Laplace Approximations](https://mlsanity.com/paper/2202.10638/) (2022)
- [Generative Adversarial Symmetry Discovery](https://mlsanity.com/paper/2302.00236/) (2023)
- [Relaxing Equivariance Constraints with Non-stationary Continuous Filters](https://mlsanity.com/paper/2204.07178/) (2022)
- [Sample Efficiency of Data Augmentation Consistency Regularization](https://mlsanity.com/paper/2202.12230/) (2022)
- [The Exact Sample Complexity Gain from Invariances for Kernel Regression](https://mlsanity.com/paper/2303.14269/) (2023)
- [Grounding inductive biases in natural images:invariance stems from variations in data](https://mlsanity.com/paper/2106.05121/) (2021)
- [A Canonicalization Perspective on Invariant and Equivariant Learning](https://mlsanity.com/paper/2405.18378/) (2024)
- [The good, the bad and the ugly sides of data augmentation: An implicit spectral regularization perspective](https://mlsanity.com/paper/2210.05021/) (2022)
- [Lie Algebra Canonicalization: Equivariant Neural Operators under arbitrary Lie Groups](https://mlsanity.com/paper/2410.02698/) (2024)

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

- [Dimension-Free Scaling Laws for Size Generalization: An Exponential Separation](https://mlsanity.com/paper/2610.19279/) (2026)

## Abstract (arXiv)

In nonconvex optimization problems arising in geometric machine learning, data augmentation is commonly used to promote invariance by averaging empirical losses over transformations of the data. Computing the fully augmented objective, however, requires access to every element of the transformation group G, which may be prohibitively expensive when G is large or accessible only through sampling. We study whether full augmentation can instead be approximated using a small, fixed sample of transformations acquired before optimization and reused thereafter. Under suitable regularity conditions, we show that, with probability at least 1-δ, gradient descent (GD) on the resulting sparsely augmented objective returns an varepsilon-stationary point of the fully augmented objective using Obigl((log |G|+log(1/δ))/varepsilon2bigr) group-transformation-oracle queries. By comparison, standard group stochastic gradient descent (group-SGD), which samples a fresh transformation at every iteration, uses O(1/varepsilon4) transformation queries. Therefore, gradient descent with fixed sparse augmentation requires fewer transformation queries than both GD applied to the fully augmented objective and group-SGD. Our proof techniques, which may be of independent interest, establish a uniform approximation of the full group-averaged gradient field by a random group average using spectral properties of group-induced operators and tools from representation theory.