Sparse Data Augmentation for Optimization with Provable Guarantees
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−δ, gradient descent (GD) on the resulting sparsely augmented objective returns an ε-stationary point of the fully augmented objective using 𝒪((log |G|+log(1/δ))/ε2) group-transformation-oracle queries. By comparison, standard group stochastic gradient descent (group-SGD), which samples a fresh transformation at every iteration, uses 𝒪(1/ε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.
Related
- Quasi-Static Fault-Tolerant Feedback Control of a Quadrotor under Rotor Failure with Provable Safety Guarantees
- Provable Guarantees and Efficient Learning of Structural Equation Models with Latent Confounders
- Adapt or Forget: Provable Tradeoffs Between Adam and SGD in Nonstationary Optimization
- A note on the convergence guarantees of RLT-based algorithms for polynomial optimization
- From Consensus-Based Optimization to Particle Swarm Optimization: Convergence Guarantees under Drift-Diffusion Coupling
BibTeX
@misc{tahmasebi2026sparse,
title = {{Sparse Data Augmentation for Optimization with Provable Guarantees}},
author = {Behrooz Tahmasebi and Melanie Weber},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.08133},
eprint = {2609.08133},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.08133},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Sparse Data Augmentation for Optimization with Provable Guarantees
AU - Behrooz Tahmasebi
AU - Melanie Weber
PY - 2026
DA - 2026/09/16
PB - arXiv
DO - 10.48550/arxiv.2609.08133
UR - https://arxiv.org/abs/2609.08133
AB - 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 ε-stationary point of the fully augmented objective using 𝒪((log |G|+log(1/δ))/ε^2) group-transformation-oracle queries. By comparison, standard group stochastic gradient descent (group-SGD), which samples a fresh transformation at every iteration, uses 𝒪(1/ε^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.
ER -