Data Augmentation: A Fourier Analysis Perspective
Behrooz Tahmasebi, Melanie Weber, Stefanie Jegelka · 2026
Read Data Augmentation: A Fourier Analysis Perspective by Behrooz Tahmasebi, Melanie Weber, Stefanie Jegelka (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-24418.txt.
Introduction
Tahmasebi, Weber, and Jegelka ask whether augmenting training data with only some symmetry transformations works as well as using all of them. Data augmentation copies each training sample through the transformations of a group acting on the input space. Full augmentation explodes computationally when the group is large. That motivates the question their 2026 framework answers.
Fourier analysis and the representation theory of finite groups supply the tools. For a broad class of classical learning problems, partial augmentation using a randomly sampled subset of group elements matches full augmentation's minimax rates. Those are the best possible worst case guarantees. An approximation error is the only gap, and it vanishes as the subset grows. Symmetry, in other words, can be enforced approximately at a fraction of the cost, without surrendering statistical performance. Tahmasebi's result explains a practice machine learning already relies on.
Catalog record
| CREATOR | Behrooz Tahmasebi, Melanie Weber, Stefanie Jegelka |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 108 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.24418
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Data Augmentation: A Fourier Analysis Perspective Behrooz Tahmasebi, Melanie Weber, Stefanie Jegelka Abstract Data augmentation is a simple and model-agnostic approach for exploiting known invariances in learning problems. Given a group acting on the input space, one augments the training set with transformed copies of each sample. Because it exploits symmetries without modifying the underlying learning algorithm, data augmentation can be applied broadly across learning methods. However, this universality comes at a computational cost: when the group is large, full group-sized augmentation quickly becomes computationally infeasible. This raises a fundamental question: Can partial data augmentation achieve the same statistical benefits as full augmentation in terms of generalization and sample complexity? We develop a general framework for investigating this question using Fourier analysis and the representation theory of finite groups. We show that, for a broad class of classical learning problems, partial data augmentation based on a randomly sampled subset of group elements achieves the same minimax rates as full augmentation, up to an approximation error that vanishes as the subset size increases. Our results provide a theoretical explanation for why partial augmentation can retain the statistical benefits of full augmentation despite enforcing symmetry only approximately, and shed light on a recently raised question in learning with symmetries ( 14 ) : whether statistically optimal learning under general group invariances can be achieved using computationally scalable methods. Moreover, we prove a complementary impossibility result: enforcing exact invariance via data augmentation requires averaging over the entire group, and cannot be achieved by any strict subset when the hypothesis space is sufficiently expressive. Together, these results provide a unified perspective on full and partial data augmentation, as well as exact and approximate symmetry enforcement. Keywords: data augmentation, invariance, symmetry, sample complexity, representation theory 1 Introduction One of the most widely used model-agnostic techniques for exploiting structure in machine learning is data augmentation . In data augmentation, the training dataset is enriched with transformed copies of each sample according to known structure inherent in the task. In learning problems with invariances, this structure is often described by a group of symmetries acting on the data domain, and augmentation with group transformations is used to encourage invariance and improve generalization to unseen data. Due to its simplicity and broad applicability, data augmentation has become a standard tool across a wide range of domains, including physics, materials science, molecular and drug discovery, computer vision, and image processing. Unlike approaches that enforce invariance through the model architecture, data augmentation exploits symmetries without modifying the underlying learning algorithm. Despite these advantages, full data augmentation quickly becomes computationally infeasible when the underlying group of invariances is large. This situation arises frequently in practice: for example, permutation and sign-flip groups grow exponentially in size with the data dimension, making full group-sized augmentation prohibitively expensive. In such settings, practitioners typically resort to partial data augmentation, where only a subset of group elements is used, often chosen heuristically. However, the theoretical understanding of when and why partial augmentation succeeds and whether it can match the statistical benefits of full augmentation remains limited. In this paper, we initiate a rigorous study of this question by asking: Can partial data augmentation, using a substantially smaller subset of the group, achieve statistical performance comparable to that of full group augmentation? We address this question in the classical settings of density estimation and regression using finite-dimensional projection estimators. Somewhat surprisingly, we show that even very small randomly sampled subsets of the group suffice to uniformly recover the full statistical benefits of data augmentation, despite enforcing symmetry only approximately. Our analysis draws on tools from Fourier analysis on groups and representation theory, and provides a principled explanation for the empirical success of partial data augmentation. 1.1 Our Contributions We summarize the main contributions of this paper. Statistical optimality of partial data augmentation. In Theorem 4.1 , we analyze partial data augmentation for projection-based density and regression estimators. We prove that partial augmentation using a randomly sampled subset S\subseteq G achieves the same minimax-optimal sample complexity as full group-sized augmentation, provided that the number of sampled group elements satisfies |S|\;\gtrsim\;\frac{r}{r_{\mathrm{inv}}}, where r denotes the dimension of the full feature space and r_{\mathrm{inv}} is the dimension of the invariant subspace induced by the symmetries. Indeed, the required size of the augmentation subset depends only on the invariant dimension r_{\mathrm{inv}} and is independent of the group size. Consequently, statistically optimal rates can be achieved without averaging over the entire group, which may be large or even infinite. This sheds light on a question raised in recent work ( 14 ) concerning whether statistical optimality can be reconciled with computational scalability in learning under general symmetry groups. Uniform and reusable partial data augmentation. In Theorem 4.2 and Theorem 4.3 , we further study the role of partial data augmentation from a uniform generalization perspective. Specifically, we ask whether a single randomly chosen augmentation set S can be reused across multiple learning tasks and still achieve minimax-optimal rates with high probability. Our main finding is that enforcing uniformity over the entire function class \mathcal{F} incurs only a mild logarithmic overhead. Concretely, Theorem 4.3 shows that it suffices to choose |S|\;\gtrsim\;\frac{r\,\log\!\big(\min\{r,|G|\}\big)}{r_{\mathrm{inv}}}, where r=\dim(\mathcal{F}) and r_{\mathrm{inv}}=\dim(\mathcal{F}^{G}) . Thus, the cost of reusing a single partial augmentation set is only a \log(\min\{r,|G|\}) factor, which remains small even when the function space dimension r is large or the group G is infinite. Impossibility of exact invariance via partial augmentation. Finally, in Theorem 4.5 , we establish an impossibility result highlighting a fundamental computational limitation of data augmentation. While partial data augmentation is sufficient for achieving statistical optimality, we show that enforcing exact invariance to a group G is computationally intractable in general. Specifically, assuming the hypothesis space is sufficiently rich to represent all irreducible symmetry modes, exact G -invariance via data augmentation requires averaging over the entire group and thus no strict subset S\subsetneq G can suffice. Taken together, our results reveal a sharp separation between partial and full data augmentation: Partial data augmentation over a small subset of a large symmetry group is sufficient to attain the full statistical benefits of symmetry, while exact invariance cannot be guaranteed when augmentation is restricted to a strict subset of the group. 2 Related Work Geometric machine learning and symmetries. Geometric machine learning has emerged as a powerful framework for incorporating symmetries and structure into learning algorithms, with applications spanning quantum systems, atomistic modeling, continuum mechanics, and beyond ( 58 ; 4 ; 7 ; 41 ; 3 ; 54 ) . From a theoretical perspective, the statistical benefits of exploiting symmetries have been studied for group averaging ( 45 ; 48 ) , as well as for canonicalization-based approaches ( 46 ) . Related work has also examined the role of regularization in symmetric models ( 47 ) and the problem of testing for and identifying invariances ( 12 ; 43 ; 49 ) . In parallel, recent studies have investigated generalization ( 5 ; 27 ) and the computational complexity ( 44 ; 42 ; 20 ) of learning under invariances, highlighting algorithmic barriers that complement statistical considerations. Approximation-theoretic guarantees for equivariant learning architectures have also been developed ( 34 ; 30 ) . Alternatives to