cs.LGJun 23, 2026

Data Augmentation: A Fourier Analysis Perspective

Authors: Behrooz Tahmasebi, Melanie Weber, Stefanie Jegelka

Organizations: Harvard John A. Paulson School of Engineering and Applied Sciences, Harvard University, Cambridge, MA 02138, USA. · Technical University of Munich (CIT, MCML, MDSI) · MIT Computer Science and Artificial Intelligence Laboratory (CSAIL)

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: 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.

Explore similar work

CardsList
Sep 8, 2026cs.LG

Sparse Data Augmentation for Optimization with Provable Guarantees

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 GG, which may be prohibitively expensive when GG 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−δ1-δ, gradient descent (GD) on the resulting sparsely augmented objective returns an ε\varepsilon-stationary point of the fully augmented objective using O((log⁡∣G∣+log⁡(1/δ))/ε2)\mathcal{O}\bigl((\log |G|+\log(1/δ))/\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 O(1/ε4)\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.
Behrooz Tahmasebi, Melanie Weber
Convex OptimizationData AugmentationStochastic Gradient DescentOptimal Sample ComplexityProbabilistic Verification
AskPDF
May 11, 2026stat.ML

Characterizing the Generalization Error of Random Feature Regression with Arbitrary Data-Augmentation

This paper aims at analyzing the regularization effect that data augmentation induces on supervised regression methods in the proportional regime, where the number of covariates grows proportionally to the number of samples. We provide a tight characterization of the test error, measured in mean squared error, in terms only of the population quantities of the true data, as well as first and second order statistics of the augmentation scheme. Our results are valid under misspecified feature maps, and for any network architecture where only the last readout layer is trained, and the rest of the network is either frozen or randomly initialized. We specify our results in the case of Gaussian data, and show that our asymptotic characterization is tight in this setting.
Lucas Morisset, Alain Durmus, Adrien Hardy
RegressionRegularization MethodsData AugmentationFeature LearningErrors3D Gaussian Splatting
AskPDF
Jul 8, 2026cs.LG

Fast Rates for Semi-Supervised Learning via Data-Augmentation Graph Regularization

Self-supervised learning matches supervised accuracy from a fraction of the labels, but the labeled-sample efficiency behind this has lacked a theoretical explanation. We provide one. Data augmentation induces a similarity graph on the unlabeled data, so downstream learning on that graph is graph-Laplacian-regularized learning. We prove a fast transductive rate, O(1/nL)O(1/n_L) in the number of labels, in place of the supervised O(1/nL)O(1/\sqrt{n_L}), by carrying the leave-one-out stability apparatus of Johnson and Zhang (JMLR 2007) over to the augmentation graph, and without the unrealistic assumptions of limit-based analyses (exact kernel, generalizing features). The bound makes augmentation quality explicit: the expected error is at most C/nL+RDA(y)C/n_L + R_{\mathrm{DA}}(y), where the data-augmentation alignment error RDA(y)R_{\mathrm{DA}}(y) is proportional to the graph-cut mass of augmentations that cross a label boundary, so good augmentations let few labels suffice. The analysis uses a streamlined loss that drops the projector, negative-sample, and orthogonality overhead of standard objectives yet still recovers the top-KK ideal features in the infinite-data limit, the augmentation-kernel eigenspace studied by Zhai et al. The bound gives a mechanistic account of the accuracy-versus-label-count curve through augmentation quality, verified in a controlled model where the constants are known.
Adam M. Oberman
Semi-Supervised LearningData AugmentationRegularization MethodsGraph LearningRepresentation-Alignment Loss
AskPDF