aiqbench analysis
This research introduces a sparse data augmentation technique for geometric machine learning that significantly reduces computational costs by reusing a fixed sample of transformations rather than sampling fresh ones at every iteration. Theoretically, this approach achieves superior convergence guarantees with fewer oracle queries compared to standard group stochastic gradient descent methods. Such efficiency improvements are critical for scaling invariant models in complex nonconvex optimization landscapes where full data augmentation is prohibitively expensive.
Sparse Data Augmentation for Optimization with Provable Guarantees
arXiv:2609.08133v1 Announce Type: new Abstract: 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-\delta$, gradient descent (GD) on the resulting sparsely augmented objective returns an $\varepsilon$-stationary point of the fully augmented objective using $\mathcal{O}\bigl((\log |G|+\log(1/\delta))/\varepsilon^2\bigr)$ group-transformation-oracle queries. By comparison, standard group stochastic gradient descent (group-SGD), which samples a fresh transformation at every iteration, uses $\mathcal{O}(1/\varepsilon^4)$ 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.
Abstract: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-\delta$, gradient descent (GD) on the resulting sparsely augmented objective returns an $\varepsilon$-stationary point of the fully augmented objective using $\mathcal{O}\bigl((\log |G|+\log(1/\delta))/\varepsilon^2\bigr)$ group-transformation-oracle queries. By comparison, standard group stochastic gradient descent (group-SGD), which samples a fresh transformation at every iteration, uses $\mathcal{O}(1/\varepsilon^4)$ 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.
32 pages, 1 figure. Published at IEEE CDC 2026
Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Optimization and Control (math.OC)
arXiv:2609.08133 [cs.LG]
(or arXiv:2609.08133v1 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2609.08133 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 300 words
Related coverage
Corey O’Meara (E.ON): Finding Real Quantum Advantage in Grid Optimization
The Quantum Insider · Oct 10, 2026
Optimality of Sub-network Laplace Approximations: New Results and Methods
arXiv · Jul 30, 2026
Training and Finetuning Multi-Vector Embedding Models with Sentence Transformers
Hugging Face · Aug 26, 2026
Probabilistic Linear Explanations
arXiv · Sep 17, 2026