Data Augmentation: A Fourier Analysis Perspective

Data augmentation, which supplements a dataset with transformed copies of each datum according to a known symmetry group, provides a model-agnostic approach to enforcing invariances, in contrast to methods that encode symmetries directly into the model. Although data augmentation has proven effective in theory and practice, full group-sized augmentation is often computationally infeasible, prompting the question: Can sublinear augmentation still achieve the same performance as full augmentation in terms of generalization bounds and sample complexity? In this paper, we develop a theoretical framework based on Fourier analysis, showing that sublinear data augmentation can achieve the full statistical benefits achieved via full data augmentation. To our knowledge, this is the first proof of the efficacy of sublinear augmentation, highlighting an underexplored aspect of why augmentation remains a powerful and widely applicable strategy, even when performed only partially.