Data Augmentation: A Fourier Analysis Perspective Behrooz Tahmasebi∗
Melanie Weber∗
Stefanie Jegelka†
arXiv:2606.24418v1 [cs.LG] 23 Jun 2026
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 (Díaz et al., 2025): 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
∗
Harvard John A. Paulson School of Engineering and Applied Sciences, Harvard University, Cambridge, MA 02138, USA. Emails: {behrooz_tahmasebi,mweber}@seas.harvard.edu † Technical University of Munich (CIT, MCML, MDSI) and MIT Computer Science and Artificial Intelligence Laboratory (CSAIL). Email: [email protected]
1
Contents 1 Introduction 1.1 Our Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3 3
2 Related Work
4
3 Problem Statement 3.1 Data Domain, Symmetry Groups, and Actions . . . . . . . . . . . . . . . . . . . . . . 3.2 Function Spaces and Lifted Group Actions . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Learning Tasks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Data Augmentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 Objectives and Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.6 Projection Estimators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5 5 6 6 6 7 7
4 Main Results
8
5 Interpreting the Regimes of Partial Augmentation 11 5.1 Extension to Binary Classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 6 Projection Estimators on the Sphere
14
7 Conclusion
15
A Preliminaries 20 A.1 Spherical Harmonics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 A.2 Gegenbauer Polynomials, Zonal Kernels, and Projection Kernels . . . . . . . . . . . . 21 A.3 Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 A.4 Group Actions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 A.5 Group Representations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 A.6 Projection Estimators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 A.7 Projection Estimators on Sphere . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 A.8 Approximate Projection via Random Group Averaging . . . . . . . . . . . . . . . . . 28 A.9 Uniform Bounds for Partial Data Augmentation . . . . . . . . . . . . . . . . . . . . . 30 A.10 Baseline Excess Risk of Projection Estimators (No Augmentation) . . . . . . . . . . 33 B Proof of Theorem 4.1
34
C Proof of Theorem 4.3
36
D Proof of Theorem 4.5
38
E Extensions to Ordinary Least Squares (OLS) and Infinite-Dimensional Hypothesis Classes 39 E.1 Projection Estimators Versus Ordinary Least Squares (OLS) . . . . . . . . . . . . . . 40 E.2 Infinite-Dimensional Hypothesis Classes . . . . . . . . . . . . . . . . . . . . . . . . . 41
2
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 ⊆ G achieves the same minimax-optimal sample complexity as full group-sized augmentation, provided that the number of sampled group elements satisfies r |S| ≳ , rinv where r denotes the dimension of the full feature space and rinv 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 rinv 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 (Díaz et al., 2025) concerning whether statistical optimality can be reconciled with computational scalability in learning under general symmetry groups.
3
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 F incurs only a mild logarithmic overhead. Concretely, Theorem 4.3 shows that it suffices to choose r log min{r, |G|} |S| ≳ , rinv where r = dim(F ) and rinv = dim(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 ⊊ 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 (Zhang et al., 2025; Batzner et al., 2022; Bronstein et al., 2017; Smidt, 2021; Batzner et al., 2023; Weber, 2025). From a theoretical perspective, the statistical benefits of exploiting symmetries have been studied for group averaging (Tahmasebi and Jegelka, 2023; Tahmasebi and Weber, 2026a), as well as for canonicalization-based approaches (Tahmasebi and Jegelka, 2025b). Related work has also examined the role of regularization in symmetric models (Tahmasebi and Jegelka, 2025a) and the problem of testing for and identifying invariances (Dehmamy et al., 2021; Soleymani et al., 2025c; Tahmasebi and Weber, 2026b). In parallel, recent studies have investigated generalization (Bietti et al., 2021; Mei et al., 2021) and the computational complexity (Soleymani et al., 2025b,a; Kiani et al., 2024) of learning under invariances, highlighting algorithmic barriers that complement statistical considerations. Approximation-theoretic guarantees for equivariant learning architectures have also been developed (Petrache and Trivedi, 2023; Pacini et al., 2025). Alternatives to data augmentation. While data augmentation is a widely used mechanism for enforcing symmetry, several works have proposed alternative strategies that encode invariance directly into the learning algorithm. Canonicalization methods (Kaba et al., 2023; Ma et al., 2024; 4
Dym et al., 2024; Shumaylov et al., 2025) aim to map inputs to a canonical representative of their orbit, while frame averaging (Puny et al., 2022) provides a related approach based on averaging over structured feature representations. These methods avoid explicit data augmentation but often require careful design or additional computational assumptions. Theoretical perspectives on data augmentation. In contrast to the extensive literature on equivariant and invariant models, the theoretical understanding of data augmentation itself remains comparatively limited. Existing work has studied data augmentation from several viewpoints, including its impact on training dynamics in neural networks (Shen et al., 2022), its role as an implicit form of regularization (Lin et al., 2024; Yang et al., 2023b), and its group-theoretic foundations (Chen et al., 2020). Most closely related to our setting, Dao et al. (2019) developed a kernel-based analysis of data augmentation, with further refinements and extensions in (Patil and Du, 2023; Mei et al., 2021). However, these works do not address the question of whether partial augmentation can recover the full statistical benefits of symmetry. Adaptive and task-driven augmentation. Beyond passive augmentation schemes, several recent works have explored generative, active, or adaptive data augmentation strategies (Zheng et al., 2023; Dong et al., 2023; Chen et al., 2024). These approaches aim to optimize augmentation policies based on the data or learning objective, but they are largely orthogonal to the questions studied in this paper. For broader perspectives, surveys are available for image augmentation in deep learning (Shorten and Khoshgoftaar, 2019), reinforcement learning (Ma et al., 2025), and natural language processing (Li et al., 2022; Pellicer et al., 2023). Additional application-focused studies include image classification (Mikołajczyk and Grochowski, 2018), graph learning (Zhao et al., 2022), and other domains (Mumuni and Mumuni, 2022). It is also important to note that data augmentation can sometimes be detrimental, as discussed in Kirichenko et al. (2023). The partial enforcement of symmetry has a long history in applications where symmetry is either intrinsically approximate (Finzi et al., 2021; Romero and Lohit, 2022; van der Ouderaa et al., 2022; Kim et al., 2023; Park et al., 2025; Wang et al., 2022), or unknown and therefore must be discovered from data (Yang et al., 2024, 2023a; van der Ouderaa et al., 2023; Huh, 2025; Desai et al., 2022; Dehmamy et al., 2021; Shaw et al., 2024). Invariant kernels. Recent work on invariant kernels (Díaz et al., 2025) studies the statistical and computational properties of learning with symmetry-enforced kernels and raises open questions about achieving minimax-optimal rates for general groups without explicitly averaging over the full group. Our results partially address these questions by showing that partial data augmentation can recover optimal statistical performance while avoiding full group-sized averaging.
3
Problem Statement
We formalize the learning problems considered in this paper and set up the notation used throughout.
3.1
Data Domain, Symmetry Groups, and Actions
Let (X , µ) be a measurable space, where µ denotes a reference probability measure on X . We assume that a group G acts on X via measurable maps (g, x) 7→ gx,
g ∈ G, x ∈ X ,
5
satisfying ex = x and g(hx) = (gh)x for all g, h ∈ G, where e denotes the identity element. Throughout the paper, we assume that the action of G on X is measure-preserving, meaning that µ(gA) = µ(A) for all measurable sets A ⊆ X and all g ∈ G. This framework captures a wide range of symmetries arising in practice, including permutations, sign flips, rotations, reflections, and combinations thereof. We allow G to be finite or infinite (compact); when sampling from G is required, we assume there is an oracle access to the uniform sampling for the canonical (Haar) probability measure on the group.
3.2
Function Spaces and Lifted Group Actions
Let F ⊂ L2 (X , µ) be a finite-dimensional linear subspace with dim(F ) = r. Let ΠF denote the L2 (X )-orthogonal projection onto F ⊂ L2 (X , µ). We assume that F is closed under the action of G, meaning that for every f ∈ F and every g ∈ G, the function x 7→ f (g −1 x) also belongs to F . This closure property induces a lifted action of G on F . Specifically, for each g ∈ G, define a linear operator Tg : F → F by (Tg f )(x) := f (g −1 x). Under our assumptions, each Tg is unitary with respect to the L2 (X ) inner product, and the map g 7→ Tg defines a finite-dimensional unitary representation of G on F (Appendix A.5). A central object in this paper is the subspace of G-invariant functions, defined as F G := {f ∈ F : Tg f = f for all g ∈ G}. We denote its dimension by rinv := dim(F G ). Intuitively, rinv measures the effective dimension of the function class after accounting for the symmetries.
3.3
Learning Tasks
We study two classical statistical learning problems. Density estimation. We observe unlabeled samples x1 , . . . , xn ∈ X drawn i.i.d. from an unknown density f ⋆ with respect to µ, where f ⋆ ∈ L2 (X , µ)∩L∞ (X , µ). The goal is to estimate f ⋆ in squared L2 (X ) risk. Supervised regression. We observe labeled samples {(xi , yi )}ni=1 generated according to yi = f ⋆ (xi ) + εi , where xi ∼ µ i.i.d., the noise variables εi are independent, mean-zero, and satisfy E[ε2i ] = σ 2 . The regression function f ⋆ is assumed to belong to L2 (X , µ) ∩ L∞ (X , µ). Performance is measured in squared L2 (X ) error. Remark 3.1 (Approximation bias). We do not assume that f ⋆ ∈ F. Rather, F serves only as the hypothesis class used for estimation, so the best achievable target in L2 (X , µ) is the projection of f ⋆ onto F. This yields an approximation bias, which can be decreased by enlarging F, at the cost of increased variance. Thus, as usual, the choice of F reflects a bias–variance trade-off. For both settings, we focus on projection estimators, which estimate f ⋆ by projecting empirical moments onto the finite-dimensional space F. These estimators are classical, minimax-optimal, and serve as a clean testbed for studying the effect of symmetry and data augmentation.
3.4
Data Augmentation
Given a set of group elements S ⊆ G, data augmentation proceeds by transforming each observed sample using elements of S. Concretely, the augmented sample is given by {g −1 xi : i ∈ [n], g ∈ S},
{(g −1 xi , yi ) : i ∈ [n], g ∈ S}, 6
in the density estimation and regression settings, respectively. We distinguish two regimes: • Full data augmentation, where S = G. • Partial data augmentation, where S is a (typically random) strict subset of G. Full augmentation can enforce exact invariance but is often computationally infeasible when G is large or infinite. Partial augmentation is computationally efficient and more practical, but its statistical benefits are less well understood.
3.5
Objectives and Questions
Our goal is to understand the trade-offs between statistical efficiency, computational cost, and symmetry enforcement when using partial data augmentation. We address the following questions: • Statistical efficiency. Can partial data augmentation achieve the same minimax-optimal rates as full data augmentation for density estimation and regression? • Reusability and uniformity. Can a single randomly chosen augmentation set S be reused across tasks or estimators, while still providing uniform generalization guarantees? • Exact versus approximate invariance. Is it possible to enforce exact G-invariance via partial data augmentation, or is full group-sized augmentation fundamentally necessary?
3.6
Projection Estimators
A central object in this paper is the class of projection estimators for density estimation and regression. These estimators are classical, minimax-optimal over finite-dimensional function classes, and provide a transparent setting for investigating the effect of symmetry and data augmentation. Extensions to ordinary least squares and infinite-dimensional hypothesis classes are discussed in Appendix E. Density estimation. Let (ϕℓ )rℓ=1 be a fixed L2 (X )-orthonormal basis of F . Suppose we observe unlabeled samples x1 , . . . , xn drawn i.i.d. from an unknown density f ⋆ with respect to µ, where f ⋆ ∈ L2 (X , µ) ∩ L∞ (X , µ). The population projection of f ⋆ onto F is ΠF f ⋆ =
r X
θ ℓ ϕℓ ,
θℓ := E[ϕℓ (x)].
ℓ=1
The coefficients θℓ can be estimated unbiasedly from data by empirical averages, leading to the projection density estimator 1 θbℓ := n
n X
ϕℓ (xi ) =⇒ fb :=
i=1
r X
θbℓ ϕℓ ∈ F.
ℓ=1
Regression. In the regression setting, we observe labeled samples (xi , yi )ni=1 with yi = f ⋆ (xi ) + εi ,
E[εi ] = 0,
E[ε2i ] = σ 2 .
The population projection of the regression function f ⋆ onto F is again ΠF f ⋆ , with coefficients βℓ := E[y ϕℓ (x)]. 7
Estimating these moments empirically yields the projection regression estimator fb :=
r X ℓ=1
βbℓ ϕℓ ,
1 βbℓ := n
n X
yi ϕℓ (xi ).
i=1
Statistical properties. Projection estimators achieve minimax-optimal rates over r-dimensional classes, with expected L2 (X ) error of order r/n in both density estimation and regression. Moreover, their linear structure makes them particularly amenable to analysis under group actions and data augmentation, as averaging over group transformations corresponds to linear operators acting on the coefficient representation. For these reasons, projection estimators serve as a canonical and analytically tractable setting for studying the statistical role of partial and full data augmentation under symmetries. Remark 3.2 (Black-box augmentation). A key caveat is that we study partial augmentation as a black-box mechanism for promoting symmetry. If the estimator itself can be modified, then symmetry may instead be incorporated directly into classical projection estimation via group-constrained optimization, which can be done in polynomial time (Soleymani et al., 2025b); such procedures are not black-box. Thus, to isolate the role of data augmentation, we decouple invariance from the estimator and treat augmentation as a model-agnostic preprocessing step. Projection estimators provide a clean testbed for this purpose: the estimator is fixed, and the subset S ⊆ G is the only mechanism used to promote symmetry. This lets us study how S controls statistical gains and the transition from approximate to exact invariance. Remark 3.3 (Augmentation and group averaging). Projection estimators are linear in the dataset, |D2 | b 1| b meaning that if D1 and D2 are two datasets and D = D1 ∪ D2 , then fbD = |D |D| fD1 + |D| fD2 . Hence, for projection estimators, augmenting the dataset by S ⊆ G is equivalent to applying the subset1 P averaging operator ΠS f (x) := |S| g∈S f (g −1 x) to the unaugmented estimator fb. In this sense, data augmentation as preprocessing and subset-group averaging as post-processing are dual ways of imposing approximate symmetry. Details on group averaging are provided in Appendix A.8.
4
Main Results
We begin by studying the statistical effect of partial data augmentation for classical projection-based estimators. Our first main result shows that, for projection estimators in both density estimation and regression, partial data augmentation is sufficient to recover the full statistical gains of symmetry, up to a controllable approximation error that depends only on the size of S. Theorem 4.1 (Partial data augmentation for projection estimators). Let F ⊂ L2 (X , µ) be a finitedimensional space of dimension r, closed under the action of a group G, and let F G denote its invariant subspace with dimension rinv . Assume f ⋆ ∈ L2 (X ) ∩ L∞ (X ). Let x1 , . . . , xn ∼ µ be i.i.d., and let S = {g1 , . . . , g|S| } be i.i.d. uniform samples from G. Let fbS be the projection estimator obtained by augmenting each sample xi by {gxi : g ∈ S}. Then, the expected excess L2 (X ) error over F G satisfies ⋆ ∥f ∥∞ r ⋆ 2 b E ∥fS − ΠF G f ∥L2 (X ) ≤ C rinv + , n n|S| for some absolute constant C > 0. The same holds for projection regression estimators, with ∥f ⋆ ∥∞ rinv /n replaced by (∥f ⋆ ∥2∞ + σ 2 )rinv /n. Moreover, this upper bound is tight up to absolute constants. 8
The bound in Theorem 4.1 decomposes the excess risk into two terms with clear interpretations. The first term, rinv /n, corresponds to the estimation error within the invariant subspace F G and matches the minimax-optimal rate achieved by full data augmentation. The second term, r/(n |S|), quantifies the error due to using only a subset of group elements and vanishes as the size of the partial augmentation set increases. In particular, as soon as |S| ≳ r/rinv , the contribution of partial augmentation becomes negligible, and the estimator achieves the same statistical performance as if full group-sized augmentation were used. Notably, this guarantee holds regardless of the size of the group G, which may be exponentially large or infinite. Thus, partial data augmentation can retain the full statistical benefits of symmetry while dramatically reducing computational cost; beyond this point, additional augmentation provides only redundant information. The guarantees in Theorem 4.1 control the performance of partial data augmentation for a fixed estimator, in expectation over the random choice of the augmentation set S. In many settings, however, one would like to draw a single augmentation set once and reuse it across multiple learning tasks, datasets, or algorithms. This raises a stronger question: Can partial data augmentation provide uniform guarantees that hold simultaneously for all functions in the hypothesis space, with high probability over the choice of S? Our next result answers this question in the affirmative. It shows that a single randomly chosen augmentation set S suffices to approximate full data augmentation uniformly over the entire function class, at the cost of only a mild logarithmic factor. Theorem 4.2 (Informal version of Theorem A.2: uniform partial data augmentation). With high probability over the choice of a random augmentation set S ⊆ G of size |S|, partial data augmentation using S provides a uniform approximation to full data augmentation over the entire hypothesis space F. Specifically, for all functions f ∈ F with bounded L2 (X ) norm, the output obtained by averaging f using S is close to s the output obtained by averaging using the full group G, with approximation log(min{r, |G|}) error on the order of , where r = dim(F). As a consequence, a single randomly |S| chosen augmentation set S can be reused across all learning algorithms whose outputs lie in F, incurring only a vanishing worst-case error as |S| grows. Theorem 4.2 shows that partial data augmentation can be made reusable: once a random subset S of group elements is sampled, it can be applied across all predictors in F without sacrificing statistical guarantees. Compared to the expectation-based bounds of Theorem 4.1, the price of uniformity is only a log(min{r, |G|}) factor. In particular, if |S| grows slightly faster than log(min{r, |G|}, the approximation error due to partial augmentation becomes negligible. This result provides a theoretical justification for practical pipelines in which a single, fixed augmentation set is reused across tasks or models, and highlights a distinction between expected and uniform guarantees for partial data augmentation. Proof sketch for Theorem 4.2: At a high level, the proof views data augmentation through its dual subset-averaging operator. Representation theory (Fourier analysis over the group) decomposes this operator into harmonic components, or symmetry modes, corresponding to the group action on F. Full augmentation removes all nontrivial modes, while partial augmentation only approximately cancels them. For a random subset S, each mode is controlled by a large-deviation bound, and a union bound over the relevant modes gives the logarithmic factor log(min{r, |G|}). We now specialize this uniform guarantee to the concrete setting of projection estimators for density estimation and regression. This allows us to translate uniform approximation of augmen9
tation operators directly into high-probability excess risk bounds for learning, while retaining the computational advantages of partial augmentation. In particular, the next theorem shows that a single randomly chosen augmentation set S can be reused for projection-based learning, yielding minimax-optimal rates up to a logarithmic factor that quantifies the cost of uniformity. Theorem 4.3 (Uniform partial data augmentation for projection estimators). Let F ⊂ L2 (X , µ) be a finite-dimensional space of dimension r, closed under the action of a group G, and let F G denote its invariant subspace with dimension rinv . Assume f ⋆ ∈ L2 (X ) ∩ L∞ (µ). Let x1 , . . . , xn ∼ µ be i.i.d., and let S = {g1 , . . . , g|S| } be i.i.d. uniform samples from G. Let fbS denote the projection estimator obtained via partial data augmentation using S. Then, for any δ ∈ (0, 1), with probability at least 1 − δ over the draw of S, the following bound holds simultaneously for all f ⋆ ∈ F G with ∥f ⋆ ∥∞ ≤ B: ! h i r log min{r, |G|}/δ r 2 inv ⋆ E fbS − ΠF G f L2 (X ) S ≤ C , + n n|S| where C > 0 depends only on B. The same bound holds for projection regression estimators under additive zero-mean noise with variance σ 2 , with C also depending on σ 2 . Theorem 4.3 refines Theorem 4.1 by providing a high-probability, reusable guarantee for partial data augmentation. In particular, the augmentation set S is reusable: on the same high-probability event, the bound holds uniformly even if f ⋆ ∈ F G is chosen adversarially after observing S. Compared to the expectation-based bound, the only additional cost is a log(min{r, |G|}) factor, which arises from enforcing uniform control over the entire function space F . Importantly, this logarithmic dependence remains mild even when the group G is large or infinite, since its dependence on the ambient dimension of the data can be benign. Thus, uniform partial data augmentation simultaneously achieves statistical efficiency, reusability, and computational scalability. Remark 4.4 (Random versus structured augmentation sets). Although group-specific designs for the subset S ⊆ G can sometimes yield sharper bounds than a random choice, improving over the logarithmic factor log |G|, constructing such designs is often combinatorial and remains an active area of research; see, e.g., (Alon and Lovett, 2013; Bourgain and Gamburd, 2008). Our results show that random augmentation sets already provide uniform guarantees with only logarithmic dependence on |G|. This relies on the expansion properties of random subsets of groups (Alon and Roichman, 1994). The preceding results demonstrate that partial data augmentation is sufficient to achieve the full statistical benefits of symmetry, both in expectation and uniformly with high probability. This naturally raises a complementary question: Can partial data augmentation also be used to enforce exact invariance under a symmetry group? Our final result shows that this is fundamentally impossible in general. While partial augmentation can approximate full augmentation arbitrarily well, exact invariance places a much stronger requirement that cannot be met without averaging over the entire group. Theorem 4.5 (Informal version of Theorem D.1: exact invariance requires full augmentation). For finite groups, partial data augmentation cannot enforce exact G-invariance unless the full group is used. More precisely, if a learning procedure based on averaging over a subset S ⊆ G produces outputs that are exactly invariant under all elements of G, and if the hypothesis space is rich enough to represent all irreducible symmetry modes of G, then S must coincide with the full group. Equivalently, exact symmetry enforcement via data augmentation fundamentally requires averaging over all group elements; partial augmentation can only yield approximate invariance. 10
Phase I: Statistical interpolation
Phase II: Statistical optimality
Phase III: Uniform reusability
Phase IV: Exact invariance
Excess risk
r/n
rinv /n
1
r/rinv
r log D/rinv
D+1
|S|
Figure 1: Phase diagram for partial augmentation. The risk decreases from the ordinary rate r/n to the invariant rate rinv /n, and saturates once |S| ≍ r/rinv . Larger augmentation sets may still be required for stronger guarantees, such as uniform reusability and exact invariance. Theorem 4.5 establishes a sharp separation between approximate and exact symmetry enforcement via data augmentation. In contrast to the statistical guarantees obtained with partial augmentation, exact G-invariance requires full group-sized augmentation whenever the hypothesis space is sufficiently expressive. Remark 4.6. The preceding result should be interpreted within the black-box augmentation framework described earlier. It does not preclude specialized methods that exploit the group structure directly and bypass augmentation altogether (Soleymani et al., 2025b). Rather, our aim here is to isolate the effect of the augmentation subset S when the estimator is fixed.
5
Interpreting the Regimes of Partial Augmentation
Our results reveal several distinct regimes for partial data augmentation. These regimes are all governed by the size of the augmentation set S, but they correspond to different goals: statistical optimality, uniform reusability, and exact invariance. A key message is that these goals do not coincide. In particular, the statistical risk can already match that of full augmentation well before the augmentation operator is reusable uniformly over the whole function class, and far before it enforces exact invariance. To make this distinction explicit, consider the projection-estimator setting with r = dim(F ) and rinv = dim(F G ). Without augmentation, the estimation error scales as r/n. Full augmentation reduces the effective dimension to rinv , yielding the invariant rate rinv /n. Partial augmentation r interpolates between these two rates. Indeed, the augmentation error is controlled by n|S| , so the rinv r total error behaves as n + n|S| . Thus, when |S| is small, partial augmentation only partially suppresses the non-invariant directions, and the risk lies between the ordinary rate r/n and the invariant rate rinv /n. The first critical threshold is therefore |S|stat ≍
11
r . rinv
Once |S| ≳ r/rinv , the augmentation error is of the same order as, or smaller than, the invariant estimation error. In this regime, partial augmentation is statistically indistinguishable from full augmentation, up to constants. This threshold is optimally characterized by our upper bound: below this scale, the additional augmentation error is unavoidable, while above it the minimax rate saturates at the invariant rate. Thus, r/rinv marks the statistical phase transition, beyond which increasing |S| no longer improves the minimax rate. A stronger requirement is uniform reusability. Rather than controlling the risk of a fixed estimator in expectation, one may want a single sampled set S to work uniformly over all functions in F. This requires high-probability control of the operator norm ∥ΠS − ΠG ∥op . Our uniform bound shows that this incurs only a logarithmic overhead: ∥ΠS − ΠG ∥2op ≲
log N , |S|
N := min{r, |G|}.
More sharply, N may be replaced by a representation-theoretic Fourier complexity X D := d2λ ≤ min{r, |G| − 1}, λ∈Λ
where Λ denotes the set of nontrivial irreducible representations of G that appear in F , and dλ is the dimension of the irrep λ. For background on group representations, see Appendix A.5. Consequently, the reusable-uniform regime begins once r |S| ≳ log(min{N, D}), rinv Equivalently, the transition size satisfies the upper bound r |S|unif ≲ log(min{N, D}). rinv This logarithmic factor is the price of reusing the same random augmentation set uniformly over many Fourier modes. It is unavoidable in worst-case representations (e.g., in case of commutative groups), although the exact instance-wise threshold can depend on finer group-theoretic structure. Finally, exact invariance is a still stronger requirement. Statistical optimality and uniform reusability require ΠS to approximate ΠG , whereas exact invariance requires equality of averaging operators: ΠS = ΠG on F . This can force S = G when F is sufficiently expressive, for example when it contains all irreducible symmetry modes. Thus exact symmetry enforcement can be much more expensive than statistical optimality. Moreover, if weighted augmentation is allowed, one can obtain a general upper bound using Carathéodory’s theorem. Let the complexified representation of G on F decompose as M FC ∼ Cm λ ⊗ V λ , = FCG ⊕ λ∈Λ
where Λ contains only the nontrivial irreducible representations appearing in F. A weighted augmentation rule X X ν= ws δ s , ws ≥ 0, ws = 1, s∈S
s∈S
satisfies Πν = ΠG on F if and only if X ws ρλ (s) = 0
for every λ ∈ Λ.
s∈S
12
Equivalently, the origin must be written as a convex combination of the Fourier feature vectors g 7−→ ρλ (g) λ∈Λ . P These vectors lie in a real vector space of dimension at most D = λ∈Λ d2λ , up to the standard realification of complex matrix coefficients. Since Haar averaging places the origin in their convex hull, Carathéodory’s theorem implies that there exists a weighted exact augmentation rule with |S|exact ≤ D + 1. This is a bound for weighted augmentation only; it does not imply the existence of an unweighted subset of the same size. Moreover, the exact threshold is problem-dependent. It can be as large as |G| in representation-complete settings, while it can be much smaller in special incomplete representations. In summary, partial augmentation exhibits a hierarchy of increasingly stringent requirements: |S|stat ≲ |S|unif ≲ |S|exact . The first threshold governs statistical optimality, the second governs uniform reusability, and the third governs exact invariance. The statistical risk, however, already saturates at the first threshold: E∥fbS − ΠF G f ⋆ ∥2L2 (X ) ≍
rinv . n
The later thresholds provide stronger guarantees, but they do not improve the statistical rate.
5.1
Extension to Binary Classification
Although our results are stated for regression and density estimation, they also immediately imply guarantees for binary classification through a standard plug-in argument. We assume that (X, Y ) ∼ P , where Y ∈ {±1}, and the optimal prediction rule is the Bayes classifier induced by the regression function f ⋆ (x) := E[Y | X = x]. The Bayes classifier is
y ⋆ (x) := sign(f ⋆ (x)).
Given an estimator fb of f ⋆ , we form the plug-in classifier yb(x) := sign(fb(x)) ∈ {±1}. Then the excess classification risk is controlled by the regression error: P(b y (X) ̸= Y ) − P(y ⋆ (X) ̸= Y ) ≤ EX |fb(X) − f ⋆ (X)| ≤ ∥fb − f ⋆ ∥L2 (X ) . Indeed, the excess risk can be written as h i EX |f ⋆ (X)|1{b y (X) ̸= y ⋆ (X)} . On the event yb(X) ̸= y ⋆ (X), the signs of fb(X) and f ⋆ (X) disagree, and hence |f ⋆ (X)| ≤ |fb(X) − f ⋆ (X)|. 13
Thus, the claimed bound follows. Consequently, the regression guarantees in this paper directly imply classification guarantees for the corresponding plug-in classifiers. For example, if fbS denotes the partially augmented projection estimator and the target lies in the invariant class, then the same argument used for our regression bounds shows that rinv r E ∥fbS − f ⋆ ∥2L2 (X ) ≲ + n n|S| which implies
1/2 h i r r inv ⋆ E P(b yS (X) ̸= Y ) − P(y (X) ̸= Y ) ≲ + . n n|S|
Thus, the same augmentation regimes appear in binary classification: partial augmentation interpolates between the ordinary and invariant rates, and once |S| ≳ r/rinv , the plug-in classifier achieves the same classification rate as the fully augmented estimator, up to constants. Moreover, the same uniform reusability guarantee applies: a single randomly chosen augmentation set S can be reused across classifiers whose underlying regression estimates lie in F.
6
Projection Estimators on the Sphere
We briefly specialize our framework to the unit sphere Sd−1 , where projection estimators admit a simple and efficient implementation via spherical harmonics. This setting illustrates that our results apply naturally to symmetry subgroups of the orthogonal group G ⊆ O(d) and that partial data augmentation is computationally tractable, in contrast to full group-sized augmentation. For more details and explanations on applications to the sphere, see Appendices A.1, A.2, and A.7. Let X = Sd−1 with µ the uniform probability measure. For each degree ℓ ≥ 0, let Hℓ denote the space of spherical harmonics of degree ℓ, with dimension Pk Nℓ . For a cutoff k ≥ 0, define2 the Lk H with r := dim(F) = truncated space F := ℓ=0 Nℓ , and let Π≤k denote the L (µ)ℓ=0 ℓ orthogonal projection onto F. Each Hℓ is invariant under O(d), and hence F is closed under the action of any subgroup G ⊆ O(d), with invariant subspace F G of dimension rinv . Projection estimators for density estimation andPregression on Sd−1 admit kernel representa′ ℓ tions. Define the degree-ℓ zonal kernel Zℓ (x, x′ ) := N j=1 ϕℓ,j (x)ϕℓ,j (x ), and the truncated kernel P k Π≤k (x, x′ ) := ℓ=0 Zℓ (x, x′ ). By the addition theorem for spherical harmonics, Zℓ (x, x′ ) depends only on ⟨x, x′ ⟩ and has a closed-form expression in terms of Gegenbauer polynomials. Consequently, Π≤k can be evaluated using only inner products, with computational cost O(k) per evaluation via standard three-term recurrences. As a result, projection estimators take the form 1 fb(x) = n
n X
Π≤k (x, xi ) (density estimation),
i=1
1 fb(x) = n
n X
yi Π≤k (x, xi ) (regression).
i=1
For large or continuous groups G ⊆ O(d), full data augmentation, averaging over all group elements, is computationally infeasible. In contrast, partial data augmentation using a small random subset S ⊆ G is efficient and compatible with the kernel form above. Our main results show that such partial augmentation suffices to recover the full statistical benefits of symmetry, with rates governed by rinv rather than the size of G.
14
7
Conclusion
In this paper, we studied the statistical and computational role of data augmentation for learning problems with known symmetries. Focusing on classical density estimation and regression with finite-dimensional projection estimators, we developed a general theoretical framework for understanding when and how partial data augmentation can replace full group-sized augmentation. Our results show that partial data augmentation is surprisingly powerful. In expectation, augmenting with a small random subset of group elements is sufficient to recover the full statistical benefits of symmetry, achieving minimax-optimal rates identical to those obtained with full augmentation. Moreover, we proved that a single randomly chosen augmentation set can be reused uniformly across all functions in the hypothesis space, incurring only a mild logarithmic overhead. At the same time, we establish a complementary impossibility result: when the hypothesis space is sufficiently expressive, enforcing exact invariance through data augmentation requires averaging over the entire group. This result reveals a sharp separation between approximate and exact symmetry enforcement, and highlights an inherent computational–statistical trade-off. Together, our findings also shed light on recent questions about the statistical role of invariance in learning, and suggest that approximate symmetry may often be the right computational target (Díaz et al., 2025).
Acknowledgments BT and MW were partially supported by NSF Award CBET-2112085 and DMS-2406905. MW acknowledges partial funding from an Alfred P. Sloan Fellowship in Mathematics and the AI2050 program at Schmidt Sciences (Grant G-25-69786). SJ acknowledges support from an Alexander von Humboldt Professorship.
References Noga Alon and Shachar Lovett. Almost k-wise vs. k-wise independent permutations, and uniformity for general group actions. Theory of Computing, 9(15):559–577, 2013. 10 Noga Alon and Yuval Roichman. Random cayley graphs and expanders. Random Structures & Algorithms, 5(2):271–284, 1994. 10 Simon Batzner, Albert Musaelian, Lixin Sun, Mario Geiger, Jonathan P Mailoa, Mordechai Kornbluth, Nicola Molinari, Tess E Smidt, and Boris Kozinsky. E(3)-equivariant graph neural networks for data-efficient and accurate interatomic potentials. Nature communications, 13(1):2453, 2022. 4 Simon Batzner, Albert Musaelian, and Boris Kozinsky. Advancing molecular simulation with equivariant interatomic potentials. Nature Reviews Physics, 5(8):437–438, 2023. 4 Alberto Bietti, Luca Venturi, and Joan Bruna. On the sample complexity of learning under geometric stability. In Advances in Neural Information Processing Systems (NeurIPS), 2021. 4 Jean Bourgain and Alex Gamburd. Uniform expansion bounds for cayley graphs of SL2 (Fp ). Annals of Mathematics, pages 625–642, 2008. 10 Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geometric deep learning: going beyond euclidean data. IEEE Signal Processing Magazine, 34(4): 18–42, 2017. 4 15
Shuxiao Chen, Edgar Dobriban, and Jane H Lee. A group-theoretic framework for data augmentation. Journal of Machine Learning Research, 21(245):1–71, 2020. 5 Yunhao Chen, Zihui Yan, and Yunjie Zhu. A comprehensive survey for generative data augmentation. Neurocomputing, 600:128167, 2024. 5 Feng Dai. Approximation theory and harmonic analysis on spheres and balls. Springer, 2013. 20, 27 Tri Dao, Albert Gu, Alexander Ratner, Virginia Smith, Chris De Sa, and Christopher Ré. A kernel theory of modern data augmentation. In Int. Conference on Machine Learning (ICML), 2019. 5 Nima Dehmamy, Robin Walters, Yanchen Liu, Dashun Wang, and Rose Yu. Automatic symmetry discovery with lie algebra convolutional network. In Advances in Neural Information Processing Systems (NeurIPS), 2021. 4, 5 Krish Desai, Benjamin Nachman, and Jesse Thaler. Symmetry discovery with deep learning. Physical Review D, 105(9):096031, 2022. 5 Mateo Díaz, Dmitriy Drusvyatskiy, Jack Kendrick, and Rekha R Thomas. Invariant kernels: Rank stabilization and generalization across dimensions. arXiv preprint arXiv:2502.01886, 2025. 1, 3, 5, 15 Yijun Dong, Yuege Xie, and Rachel Ward. Adaptively weighted data augmentation consistency regularization for robust optimization under concept shift. In Int. Conference on Machine Learning (ICML), 2023. 5 Nadav Dym, Hannah Lawrence, and Jonathan W Siegel. Equivariant frames and the impossibility of continuous canonicalization. In Int. Conference on Machine Learning (ICML), 2024. 5 Marc Finzi, Gregory Benton, and Andrew G Wilson. Residual pathway priors for soft equivariance constraints. In Advances in Neural Information Processing Systems (NeurIPS), 2021. 5 Dongsung Huh. Discovering group structures via unitary representation learning. In Int. Conference on Learning Representations (ICLR), 2025. 5 Sékou-Oumar Kaba, Arnab Kumar Mondal, Yan Zhang, Yoshua Bengio, and Siamak Ravanbakhsh. Equivariance with learned canonicalization functions. In Int. Conference on Machine Learning (ICML), 2023. 4 Bobak Kiani, Thien Le, Hannah Lawrence, Stefanie Jegelka, and Melanie Weber. On the hardness of learning under symmetries. In International Conference on Learning Representations, volume 2024, pages 25956–26003, 2024. 4 Hyunsu Kim, Hyungi Lee, Hongseok Yang, and Juho Lee. Regularizing towards soft equivariance under mixed symmetries. In Int. Conference on Machine Learning (ICML), 2023. 5 Polina Kirichenko, Mark Ibrahim, Randall Balestriero, Diane Bouchacourt, Shanmukha Ramakrishna Vedantam, Hamed Firooz, and Andrew G Wilson. Understanding the detrimental class-level effects of data augmentation. In Advances in Neural Information Processing Systems (NeurIPS), 2023. 5 Bohan Li, Yutai Hou, and Wanxiang Che. Data augmentation approaches in natural language processing: A survey. Ai Open, 3:71–90, 2022. 5 16
Chi-Heng Lin, Chiraag Kaushik, Eva L Dyer, and Vidya Muthukumar. The good, the bad and the ugly sides of data augmentation: An implicit spectral regularization perspective. Journal of Machine Learning Research, 25(91):1–85, 2024. 5 George Ma, Yifei Wang, Derek Lim, Stefanie Jegelka, and Yisen Wang. A canonicalization perspective on invariant and equivariant learning. In Advances in Neural Information Processing Systems (NeurIPS), 2024. 4 Guozheng Ma, Zhen Wang, Zhecheng Yuan, Xueqian Wang, Bo Yuan, and Dacheng Tao. A comprehensive survey of data augmentation in visual reinforcement learning. International Journal of Computer Vision, pages 1–38, 2025. 5 Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Learning with invariances in random features and kernel models. In Conference on Learning Theory (COLT), 2021. 4, 5 Agnieszka Mikołajczyk and Michał Grochowski. Data augmentation for improving deep learning in image classification problem. In 2018 international interdisciplinary PhD workshop (IIPhDW), pages 117–122. IEEE, 2018. 5 Alhassan Mumuni and Fuseini Mumuni. Data augmentation: A comprehensive survey of modern approaches. Array, 16:100258, 2022. 5 Marco Pacini, Mircea Petrache, Bruno Lepri, Shubhendu Trivedi, and Robin Walters. On universality of deep equivariant networks. arXiv preprint arXiv:2510.15814, 2025. 4 Jung Yeon Park, Sujay Bhatt, Sihan Zeng, Lawson L.S. Wong, Alec Koppel, Sumitra Ganesh, and Robin Walters. Approximate equivariance in reinforcement learning. In Int. Conference on Artificial Intelligence and Statistics (AISTATS), 2025. 5 Pratik Patil and Jin-Hong Du. Generalized equivalences between subsampling and ridge regularization. In Advances in Neural Information Processing Systems (NeurIPS), 2023. 5 Lucas Francisco Amaral Orosco Pellicer, Taynan Maier Ferreira, and Anna Helena Reali Costa. Data augmentation techniques in natural language processing. Applied Soft Computing, 132:109803, 2023. 5 Mircea Petrache and Shubhendu Trivedi. Approximation-generalization trade-offs under (approximate) group equivariance. In Advances in Neural Information Processing Systems (NeurIPS), 2023. 4 Omri Puny, Matan Atzmon, Heli Ben-Hamu, Ishan Misra, Aditya Grover, Edward J Smith, and Yaron Lipman. Frame averaging for invariant and equivariant network design. In Int. Conference on Learning Representations (ICLR), 2022. 5 David W Romero and Suhas Lohit. Learning partial equivariances from data. In Advances in Neural Information Processing Systems (NeurIPS), 2022. 5 Ben Shaw, Abram Magner, and Kevin Moon. Symmetry discovery beyond affine transformations. In Advances in Neural Information Processing Systems (NeurIPS), 2024. 5 Ruoqi Shen, Sébastien Bubeck, and Suriya Gunasekar. Data augmentation as feature manipulation. In Int. Conference on Machine Learning (ICML), 2022. 5 17
Connor Shorten and Taghi M Khoshgoftaar. A survey on image data augmentation for deep learning. Journal of big data, 6(1):1–48, 2019. 5 Zakhar Shumaylov, Peter Zaika, James Rowbottom, Ferdia Sherry, Melanie Weber, and CarolaBibiane Schönlieb. Lie algebra canonicalization: Equivariant neural operators under arbitrary lie groups. In Int. Conference on Learning Representations (ICLR), 2025. 5 Tess E Smidt. Euclidean symmetry and equivariance in machine learning. Trends in Chemistry, 3 (2):82–85, 2021. 4 Ashkan Soleymani, Behrooz Tahmasebi, Patrick Jaillet, and Stefanie Jegelka. From finite to infinite groups: A polynomial-time algorithm for learning with exact invariances. In NeurIPS 2025 Workshop on Symmetry and Geometry in Neural Representations, 2025a. 4 Ashkan Soleymani, Behrooz Tahmasebi, Stefanie Jegelka, and Patrick Jaillet. Learning with exact invariances in polynomial time. In Int. Conference on Machine Learning (ICML), 2025b. 4, 8, 11 Ashkan Soleymani, Behrooz Tahmasebi, Stefanie Jegelka, and Patrick Jaillet. A robust kernel statistical test of invariance: Detecting subtle asymmetries. In Int. Conference on Artificial Intelligence and Statistics (AISTATS), 2025c. 4 Behrooz Tahmasebi and Stefanie Jegelka. The exact sample complexity gain from invariances for kernel regression. In Advances in Neural Information Processing Systems (NeurIPS), 2023. 4 Behrooz Tahmasebi and Stefanie Jegelka. Regularity in canonicalized models: A theoretical perspective. In Int. Conference on Artificial Intelligence and Statistics (AISTATS), 2025a. 4 Behrooz Tahmasebi and Stefanie Jegelka. Generalization bounds for canonicalization: A comparative study with group averaging. In Int. Conference on Learning Representations (ICLR), 2025b. 4 Behrooz Tahmasebi and Melanie Weber. Achieving approximate symmetry is exponentially easier than exact symmetry. In Int. Conference on Learning Representations (ICLR), 2026a. 4, 28 Behrooz Tahmasebi and Melanie Weber. Adaptive symmetry discovery for dynamical system identification. In Int. Conference on Machine Learning (ICML), 2026b. 4 Joel A Tropp. User-friendly tail bounds for sums of random matrices. Foundations of computational mathematics, 12(4):389–434, 2012. 32 Tycho van der Ouderaa, David W Romero, and Mark van der Wilk. Relaxing equivariance constraints with non-stationary continuous filters. In Advances in Neural Information Processing Systems (NeurIPS), 2022. 5 Tycho van der Ouderaa, Alexander Immer, and Mark van der Wilk. Learning layer-wise equivariances automatically using gradients. In Advances in Neural Information Processing Systems (NeurIPS), 2023. 5 Rui Wang, Robin Walters, and Rose Yu. Approximately equivariant networks for imperfectly symmetric dynamics. In Int. Conference on Machine Learning (ICML), 2022. 5 Melanie Weber. Geometric machine learning. AI Magazine, 46(1):e12210, 2025. 4
18
Jianke Yang, Robin Walters, Nima Dehmamy, and Rose Yu. Generative adversarial symmetry discovery. In Int. Conference on Machine Learning (ICML), 2023a. 5 Jianke Yang, Nima Dehmamy, Robin Walters, and Rose Yu. Latent space symmetry discovery. In Int. Conference on Machine Learning (ICML), 2024. 5 Shuo Yang, Yijun Dong, Rachel Ward, Inderjit S Dhillon, Sujay Sanghavi, and Qi Lei. Sample efficiency of data augmentation consistency regularization. In Int. Conference on Artificial Intelligence and Statistics (AISTATS), 2023b. 5 Xuan Zhang, Limei Wang, Jacob Helwig, Youzhi Luo, Cong Fu, Yaochen Xie, Meng Liu, Yuchao Lin, Zhao Xu, Keqiang Yan, et al. Artificial intelligence for science in quantum, atomistic, and continuum systems. Foundations and Trends® in Machine Learning, 18(4):385–912, 2025. 4 Tong Zhao, Wei Jin, Yozen Liu, Yingheng Wang, Gang Liu, Stephan Günnemann, Neil Shah, and Meng Jiang. Graph data augmentation for graph machine learning: A survey. arXiv preprint arXiv:2202.08871, 2022. 5 Chenyu Zheng, Guoqiang Wu, and Chongxuan Li. Toward understanding generative data augmentation. In Advances in Neural Information Processing Systems (NeurIPS), 2023. 5
19
A
Preliminaries
A.1
Spherical Harmonics
We briefly review basic facts about spherical harmonics on the unit sphere (Dai, 2013). Let n o Sd−1 := x ∈ Rd : ∥x∥2 = 1 be the unit sphere in Rd , equipped with the normalized surface measure µ, so that For functions f, h : Sd−1 → R, we define the L2 inner product Z ⟨f, h⟩L2 (Sd−1 ) := f (x) h(x) dµ(x),
R
Sd−1 dµ(x) = 1.
Sd−1
and denote by L2 (Sd−1 ) the associated Hilbert space. The (Euclidean) Laplacian on Rd is defined by ∆ :=
d X ∂2 i=1
∂x2i
.
In contrast, the Laplace–Beltrami operator ∆Sd−1 is the intrinsic Laplacian associated with the Riemannian metric on the sphere. While ∆ acts on functions defined in Rd , ∆Sd−1 acts on functions defined on Sd−1 and can be viewed as the restriction of ∆ to tangential directions along the sphere. Let −∆Sd−1 denote the (positive semidefinite) Laplace–Beltrami operator on Sd−1 . Its spectrum is discrete and indexed by ℓ = 0, 1, 2, . . ., with eigenvalues λℓ := ℓ(ℓ + d − 2). Spherical harmonics. The eigenspace corresponding to λℓ is denoted by Hℓ and consists of the restrictions to Sd−1 of homogeneous harmonic polynomials of degree ℓ in Rd , namely o n Hℓ := p|Sd−1 : p is homogeneous of degree ℓ and ∆p = 0 in Rd . The spaces {Hℓ }ℓ≥0 are mutually orthogonal in L2 (Sd−1 ) and yield the orthogonal decomposition 2
d−1
L (S
)=
∞ M
Hℓ .
ℓ=0
Let us denote the multiplicity of the eigenvalue λℓ as d+ℓ−1 d+ℓ−3 Nℓ := dim(Hℓ ) = − ℓ ℓ−2 ℓ For each ℓ, let {ϕℓ,m }N m=1 be an orthonormal basis of Hℓ .
Asymptotics of the multiplicities. For fixed degree ℓ and dimension d → ∞, the multiplicity Nℓ satisfies dℓ + Oℓ dℓ−1 . Nℓ = ℓ! 20
where the implicit constant depends only on ℓ. In particular, Nℓ grows polynomially in d with leading order dℓ . Moreover, the dimension of the space of spherical harmonics of degree at most k satisfies k X d+k−1 d+k−2 Nℓ = + , k k−1 ℓ=0
In particular, for fixed k and d → ∞, k X
dk + Ok dk−1 , k!
Nℓ =
ℓ=0
where the implicit constant depends only on k. Harmonic expansion. Every function f ∈ L2 (Sd−1 ) admits the convergent expansion f=
Nℓ ∞ X X
fℓ,m := ⟨f, ϕℓ,m ⟩L2 (Sd−1 ) .
fℓ,m ϕℓ,m ,
ℓ=0 m=1
Truncating the expansion at degrees ℓ ≤ k yields the L2 -orthogonal projection of f onto the space of spherical polynomials of degree at most k, and provides the best L2 approximation of f within this class.
A.2
Gegenbauer Polynomials, Zonal Kernels, and Projection Kernels
A zonal function Z : Sd−1 × Sd−1 → R is a function that only depends on the inner product, i.e., Z(x, y) = ζ(⟨x, y⟩),
x, y ∈ Sd−1 ,
for some ζ : [−1, 1] → R. (λ)
Gegenbauer polynomials. Let λ := d−2 2 . The Gegenbauer polynomials {Cℓ }ℓ≥0 form an 1 orthogonal family on [−1, 1] with respect to the weight (1 − t2 )λ− 2 . Zonal harmonics (reproducing kernels). For each ℓ ≥ 0, let Hℓ be the eigenspace of the ℓ Laplace–Beltrami operator −∆Sd−1 with eigenvalue λℓ = ℓ(ℓ + d − 2), and let {ϕℓ,m }N m=1 be an 2 d−1 orthonormal basis of Hℓ in L (S ). Define the zonal harmonic (also called the reproducing kernel of Hℓ ) by Nℓ X Zℓ (x, y) := ϕℓ,m (x)ϕℓ,m (y). m=1
Note that Zℓ (x, y) is a function of ⟨x, y⟩ and can be written explicitly as Zℓ (x, y) =
ℓ + λ (λ) Cℓ (⟨x, y⟩), λ
In particular, Zℓ (x, x) = Nℓ is constant in x.
21
λ=
d−2 . 2
Projection kernel to degree ≤ k. Let Π≤k denote the L2 (Sd−1 )-orthogonal projector onto the L space kℓ=0 Hℓ of spherical polynomials of degree at most k. Then Π≤k is an integral operator with kernel k k X X ℓ + λ (λ) Π≤k (x, y) := Cℓ (⟨x, y⟩), Zℓ (x, y) = λ ℓ=0
so that
ℓ=0
Z (Π≤k f )(x) =
Π≤k (x, y) f (y) dσ(y). Sd−1
Hence, the projection depends only on inner products and can be evaluated efficiently: for fixed (λ) x, computing Π≤k (x, y) reduces to evaluating Cℓ (t) for t = ⟨x, y⟩ and ℓ = 0, . . . , k, which can be done in O(k) time using Gegenbauer polynomials.
A.3
Groups
A group is a pair (G, ·) where G is a set and · : G × G → G is a binary operation (often written as multiplication) such that: • (Associativity) (g · h) · k = g · (h · k) for all g, h, k ∈ G. • (Identity) There exists an element e ∈ G such that e · g = g · e = g for all g ∈ G. • (Inverse) For every g ∈ G there exists g −1 ∈ G such that g · g −1 = g −1 · g = e. Throughout the paper, we omit the “·” notation and write gh for the group product for all g, h ∈ G. Here we list a number of example groups. • Permutation group. The symmetric group Sd is the set of all bijections π : {1, . . . , d} → {1, . . . , d} with group operation given by composition. Equivalently, each π ∈ Sd is a permutation of the indices {1, . . . , d}. • Sign-flipping group. The sign-flipping group consists of all vectors ε = (ε1 , . . . , εd ) with εi ∈ {+1, −1}, equipped with componentwise multiplication. • Hyperoctahedral group (signed permutations). The hyperoctahedral group Bd is the group of all signed permutation matrices in Rd×d , i.e., matrices Q such that each row and each column contains exactly one nonzero entry, and every nonzero entry equals +1 or −1. Equivalently, each element of Bd can be specified by a pair (π, ε) where π ∈ Sd and ε ∈ {±1}d . This group models invariance under the reordering of coordinates, together with independent sign flips. • Cyclic group. The cyclic group of order d, denoted Cd , is generated by a single element r with relation rd = e: Cd := {e, r, r2 , . . . , rd−1 },
ra rb = ra+b (mod d) .
A canonical example is the group of circular shifts on d coordinates. • Dihedral group. The dihedral group of order 2d, denoted Dd , is the symmetry group of a regular d-gon. It contains d rotations and d reflections, and can be presented by generators r (a rotation by 2π/d) and s (a reflection) satisfying rd = e,
s2 = e, 22
srs = r−1 .
Each element of Dd can be written uniquely as either rk or srk for some k ∈ {0, 1, . . . , d − 1}. In applications on d-tuples, one may realize r as a cyclic shift and s as reversal (a “flip”), generating both shifts and flip-symmetries. We also frequently encounter infinite groups: • Orthogonal group. The orthogonal group O(d) is O(d) := {Q ∈ Rd×d : Q⊤ Q = Id }, i.e., the set of linear maps of Rd that preserve Euclidean inner products (and hence distances). These include rotations and reflections. • Special orthogonal group. The special orthogonal group SO(d) is the subgroup SO(d) := {Q ∈ O(d) : det(Q) = 1}, consisting of proper rotations (orientation-preserving orthogonal transformations). • Unitary group. The unitary group U(d) is U(d) := {U ∈ Cd×d : U ∗ U = Id }, where U ∗ denotes the conjugate transpose of U . Equivalently, U(d) consists of all linear maps of Cd that preserve the complex inner product. • Translation group. The translation group (Rd , +) acts on Rd by t · x = x + t. This models translation invariance in Euclidean spaces. For compact groups G, there exists a unique probability measure on G, called the Haar measure, which is invariant under left group translations. Sampling g ∈ G therefore corresponds to sampling a group element uniformly at random throughout the paper. We write Eg [·] to denote expectation with respect to uniform sampling from the group.
A.4
Group Actions
Let (X , µ) be a measured space. A (left) group action of a group G on X is a map (g, x) 7→ gx satisfying ex = x and (g1 g2 )x = g1 (g2 x), ∀g1 , g2 ∈ G, ∀x ∈ X . We assume that the action is isometric, i.e., µ(gA) = µ(A) for all measurable A ⊆ X and g ∈ G. Lifted action on function spaces. Let F ⊂ L2 (X , µ) be a finite-dimensional vector space of continuous functions. Let {ϕℓ }rℓ=1 be a fixed orthonormal basis of F, where r := dim(F). Therefore, we may identify F with Rr . With a slight abuse of notation, each function f ∈ F is identified with a vector f ∈ Rr . We say that F is closed under the group action if, for any f ∈ F, we have x 7→ f (gx) ∈ F for all g ∈ G. Throughout, we assume that F is closed under the group action. The action of G on X induces a natural action on F defined by (Tg f )(x) := f (g −1 x),
∀g ∈ G,
where Tg : F → F are unitary operators (matrices), due to the isometry assumption. When F is finite-dimensional, we can identify each Tg with a matrix of dimension dim(F ), and thus Tg ∈ Rr×r for all g ∈ G, where r := dim(F ). In particular, Te = Ir , where e ∈ G denotes the identity element and Ir ∈ Rr×r is the identity matrix, and we have Tg Th = Tgh for all g, h ∈ G. 23
Invariant functions and projection. The G-invariant subspace of F is \ F G := {f ∈ F : Tg f = f ∀g ∈ G} = ker(Tg − I). g∈G
We identify F G ⊆ F with a finite-dimensional vector subspace of Rr , where rinv := dim(F G ). For compact groups G, the orthogonal projection onto the invariant subspace F G is given by ΠG f := Eg [ Tg f ] .
A.5
Group Representations
A (unitary) representation of a group G on a finite-dimensional Hilbert space H is a map ρ : G → U(H), from G to the group of unitary operators on H, such that ρ(e) = IH
and
ρ(gh) = ρ(g)ρ(h) for all g, h ∈ G.
Indeed, the group multiplication in G is represented by the composition of unitary operators on H. A subspace W ⊆ H is said to be G-invariant if ρ(g)w ∈ W
for all w ∈ W and all g ∈ G,
that is, the action of the group does not move vectors in W outside of W . A representation ρ is called irreducible if the only closed G-invariant subspaces of H are the trivial ones, namely {0} and H itself. Otherwise, the representation is said to be reducible. Finite groups and harmonic decompositions. For finite groups, every finite-dimensional unitary representation decomposes orthogonally into irreducible components: M H ∼ Cmλ ⊗ Vλ , = b λ∈G
b denotes the set of inequivalent irreducible representations, Vλ is an irreducible reprewhere G sentation of dimension dλ ∈ N, and mλ ∈ Z≥0 is its multiplicity. The number of irreducible representations equals the number of conjugacy classes of G, and their dimensions satisfy X d2λ = |G|. b λ∈G
b ≤ |G| for all finite groups G. In particular, |G| This decomposition is the finite-group analogue of the harmonic decompositions appearing in classical settings (e.g., spherical harmonics), and induces an orthogonal decomposition of F into isotypic components.
24
Matrix structure under a change of coordinates. Let ρ : G → U(H) be a finite-dimensional unitary representation. There exists an orthonormal basis of H under which each operator ρ(g) takes a block-diagonal form consistent with the above decomposition: M g ∈ G, ρ(g) ∼ Imλ ⊗ ρλ (g), = b λ∈G
where ρλ : G → U (Vλ ) denotes an irreducible representation of dimension dλ , and Imλ is the identity operator on the multiplicity space Cmλ . In this basis, each irreducible representation appears mλ times, and the action of G is identical across these copies. This block structure plays a central role in characterizing invariant subspaces and projection operators in finite-dimensional models. Invariant subspaces in finite-dimensional models. Specializing the above discussion to H = F, we note that each operator Tg is unitary on F, and the map g 7→ Tg defines a finite-dimensional unitary representation ρ : G → U (r) on F (or, equivalently, on Rr ). The trivial irreducible representation of G is the one-dimensional representation in which every group element acts as the identity, i.e., ρtriv (g) = 1 ∈ R for all g ∈ G. Functions lying in the trivial isotypic component are exactly those that are fixed by the action of G, and therefore correspond precisely to G-invariant functions F G , and can be obtained via orthogonal projection.
A.6
Projection Estimators
In this subsection, we review projection-based estimators for density estimation and regression in a general finite-dimensional Hilbert space setting. These estimators form the conceptual basis for the spherical harmonics constructions discussed later. To review, let (X , µ) be a measured space and let F ⊂ L2 (X , µ) be a finite-dimensional linear subspace of dimension r. Note that every function f ∈ F admits the expansion f=
r X
θℓ := ⟨f, ϕℓ ⟩.
θℓ ϕ ℓ ,
ℓ=1
Projection density estimation (unlabeled data). Let x1 , . . . , xn be i.i.d. samples drawn from an unknown density f ⋆ ∈ L2 (X , µ). The L2 (X )-orthogonal projection of f ⋆ onto F is ΠF f ⋆ := arg min ∥f ⋆ − f ∥2L2 (X ) = f ∈F
r X
θℓ ϕ ℓ ,
θℓ = Ex∼f ⋆ [ϕℓ (x)].
ℓ=1
Since the coefficients θℓ are expectations, they admit unbiased empirical estimators 1 θbℓ := n
n X
ϕℓ (xi ).
i=1
This leads to the projection density estimator fb :=
r X ℓ=1
25
θbℓ ϕℓ .
Projection regression estimation (labeled data). Now consider a supervised setting where (xi , yi )ni=1 are i.i.d. samples from a joint distribution on X × R, where xi ∼ µ is drawn uniformly from X , and yi = f ⋆ (xi ) + εi , E[εi ] = 0, E[ε2i ] = σ 2 , with ε1 , . . . , εn independent of x1 , . . . , xn . The regression function f ⋆ (x) = E[y|x] lies in L2 (X , µ), and its L2 (X )-orthogonal projection onto F is given by r X ΠF f ⋆ := arg min E (f (x) − f ⋆ (x))2 = β ℓ ϕℓ , f ∈F
βℓ = Ex,y [y ϕℓ (x)].
ℓ=1
The coefficients βℓ admit empirical estimators 1 βbℓ := n
n X
yi ϕℓ (xi ),
i=1
leading to the projection regression estimator fb :=
r X
βbℓ ϕℓ .
ℓ=1
Relation to the method of moments. Both the projection density estimator and the projection regression estimator can be interpreted as instances of the method of moments. In the density estimation setting, the population projection coefficients satisfy θℓ = E ϕℓ (x) , ℓ ∈ [r], P and the empirical coefficients θbℓ = n1 ni=1 ϕℓ (xi ) are obtained by matching these moments. The reP sulting estimator fb = rℓ=1 θbℓ ϕℓ is therefore a moment-based approximation of the L2 (X )-projection of f ⋆ onto F. Similarly, in the regression setting, the population projection coefficients satisfy the moment identities βℓ = E y ϕℓ (x) , ℓ ∈ [r], P and are estimated by their empirical counterparts βbℓ = n1 ni=1 yi ϕℓ (xi ). In both cases, the estimators are obtained by matching population moments with empirical moments and substituting the resulting coefficients into the basis expansion.
A.7
Projection Estimators on Sphere
We now specialize the projection estimators to the case where the input space is the unit sphere and the approximation space is chosen according to spherical harmonics. This specialization yields classical spectral estimators and admits efficient kernel representations via zonal harmonics. Spherical harmonics and approximation spaces. Let X = Sd−1 be the unit sphere equipped with the uniform probability measure µ. For each ℓ ≥ 0, let Hℓ be the eigenspace of spherical 2 d−1 ), where N ℓ harmonics with degree ℓ, and let {ϕℓ,m }N ℓ m=1 be an orthonormal basis of Hℓ in L (S is the dimension of this space. 26
For a fixed truncation level k ∈ Z≥0 , we define the finite-dimensional approximation space F :=
k M
Hℓ ,
r := dim(F) =
ℓ=0
k X
Nℓ .
ℓ=0
Note that, in contrast to the general setting of the previous subsection, where basis functions were indexed by a single index ℓ ∈ [r], here each basis function is indexed by a degree ℓ and a multiplicity index m. Projection estimators in spherical harmonics coordinates. Any function f ∈ F admits the expansion Nℓ k X X f (x) = θℓ,m ϕℓ,m (x), θℓ,m = ⟨f, ϕℓ,m ⟩. ℓ=0 m=1
In the density estimation setting, where x1 , . . . , xn are i.i.d. samples from an unknown density f ⋆ on Sd−1 , the population projection coefficients satisfy n 1X b ϕℓ,m (xi ). θℓ,m = Ex∼f ⋆ ϕℓ,m (x) =⇒ θℓ,m = n i=1
The resulting projection estimator is fb(x) =
Nℓ k X X
θbℓ,m ϕℓ,m (x).
ℓ=0 m=1
An analogous expression holds in the regression setting, with coefficients θℓ,m replaced by βℓ,m = E[y ϕℓ,m (x)]. Projection kernels and zonal harmonics. Rather than working explicitly with the basis {ϕℓ,m }, it is often convenient to express the projection estimator using the associated projection kernel Nℓ k X X ′ Π≤k (x, x ) := ϕℓ,m (x) ϕℓ,m (x′ ). ℓ=0 m=1
With this notation, the projection estimator admits the kernel form n
1X Π≤k (x, xi ) (density estimation), fb(x) = n i=1
n
1X fb(x) = yi Π≤k (x, xi ) (regression). n i=1
The kernel Π≤k (x, x′ ) is a zonal kernel, meaning that it depends on x and x′ only through their inner product ⟨x, x′ ⟩. Gegenbauer polynomial representation. By the addition theorem for spherical harmonics (Dai, 2013), the projection kernel admits the explicit representation ′
Πk (x, x ) =
k X ℓ+λ ℓ=0
λ
(λ)
Cℓ (⟨x, x′ ⟩),
27
λ=
d−2 , 2
(λ)
where Cℓ denotes the Gegenbauer polynomial of degree ℓ. As a result, both density and regression projection estimators can be evaluated efficiently using only inner products between data points, without explicitly computing the spherical harmonics basis functions. Indeed, Gegenbauer polynomials admit a three-term recurrence, meaning that each polynomial (λ) (λ) (λ) Cℓ+1 (t) can be computed using only the two preceding values Cℓ (t) and Cℓ−1 (t). Consequently, (λ)
for a fixed t ∈ [−1, 1], the sequence {Cℓ (t)}kℓ=0 can be evaluated iteratively, storing only two intermediate values at any time. This yields an O(k) time complexity and O(1) memory usage for computing all degrees up to k. We conclude with an important implication. Although projection estimators are computationally tractable for polynomial features of moderate degree k growing polynomially with the dimension d, exact symmetry through data augmentation may still require augmentation over the full group. In other words, averaging or data augmentation does not, in general, alleviate the computational cost of projecting onto invariant subspaces, even for moderate-degree polynomial features. The next proposition shows explicitly that the condition in Theorem D.1 is already satisfied when k = O(d2 ). Proposition A.1 (Permutation irreps in low-degree harmonics). Let Sd act on Sd−1 by permuting coordinates. Then every irreducible representation of Sd appears in the restriction of spherical har d 2 monics of degree at most 2 = O(d ). Equivalently, the space of degree-O(d2 ) spherical harmonics already contains all symmetry modes of the permutation action. See (Tahmasebi and Weber, 2026a) for further discussion.
A.8
Approximate Projection via Random Group Averaging
In this subsection, we study approximating the projection onto the invariant subspace F G by averaging over a random subset of group elements, rather than the entire group. This viewpoint is central to understanding why approximate symmetry can be achieved efficiently. Recall that F ⊂ L2 (X , µ) is a finite-dimensional Hilbert space of dimension r, closed under the group action, and that the lifted action induces a unitary representation ρ : G → U (r). The orthogonal projection onto the invariant subspace F G is given by group averaging, ΠG f = Eg [Tg f ]. Let S = {g1 , . . . , gs } be a multiset of elements drawn independently and uniformly from G. We define the empirical averaging operator s
ΠS f :=
1X Tgi f. s i=1
This operator can be viewed as an approximation of ΠG . Decomposition into irreducible components. By finite-group representation theory, there exists an orthonormal change of coordinates under which F decomposes as M M F ∼ Cmλ ⊗ Vλ =⇒ ρ(g) ∼ Imλ ⊗ ρλ (g), g ∈ G. = = b λ∈G
Note that
b λ∈G
X
mλ = r = dim(F).
b λ∈G
Under this decomposition, the exact projection ΠG acts as the identity on the trivial representation and annihilates all nontrivial irreducible components. In contrast, the empirical operator ΠS replaces the group average on each block by a finite sample average. 28
Behavior of random averaging. For the trivial irreducible representation, ρtriv (g) = 1 for all g ∈ G, and therefore ΠS f = f on F G for any S. Thus, invariant components are preserved exactly, regardless of the choice of S. For any nontrivial irreducible representation λ ̸= triv, the group average of the representation matrices vanishes: Eg ρλ (g) = 0. One way to see this is that Aλ := Eg [ρλ (g)] commutes with ρλ (h) for every h ∈ G (by left-invariance of the uniform measure), hence by Schur’s lemma Aλ = c I for some scalar c. Taking traces yields c dλ = tr(Aλ ) = Eg tr(ρλ (g)) , and orthogonality of traces (i.e., characters) of irreducible representations implies Eg [ρλ (g)] = 0 for P every nontrivial λ, hence c = 0 and therefore Aλ = 0. Consequently, the empirical average 1 g∈S ρλ (g) concentrates around 0 as |S| grows, and the contribution of non-invariant components |S| is attenuated by random averaging. Isotypic components. Let Fλ ⊆ F denote the λ-isotypic subspace, i.e., sum of all L the direct m ∼ λ irreducible subrepresentations equivalent to Vλ in the decomposition F = λ∈Gb C ⊗ Vλ . Equivalently, Fλ is the image of the orthogonal projector onto the λ-block. Any f ∈ F decomposes orthogonally as X f = fλ , fλ ∈ Fλ , ⟨fλ , fλ′ ⟩L2 (X ) = 0 (λ ̸= λ′ ). b λ∈G
In particular, the invariant subspace is the trivial isotypic component: F G = Ftriv . Expected approximation error. Let f ∈ F with ∥f ∥L2 (X ) ≤ 1, and let S be a multiset of |S| i.i.d. uniform samples from G. Since ΠG f = ftriv and ΠS acts blockwise, we have X ΠS f − ΠG f = ΠS fλ , λ̸=triv
and by orthogonality of distinct isotypic components (and unitarity of the action), X ∥ΠS fλ ∥2L2 (X ) . ∥ΠS f − ΠG f ∥2L2 (X ) = λ̸=triv
Taking expectation over the randomness of S yields X ES ∥ΠS f − ΠG f ∥2L2 (X ) = ES ∥ΠS fλ ∥2L2 (X ) . λ̸=triv
Moreover, for any fixed component u ∈ Fλ with λ ̸= triv, the random vectors {Tg u}g are mean-zero in Fλ and satisfy ∥Tg u∥L2 (X ) = ∥u∥L2 (X ) . A direct variance computation gives ES ∥ΠS u∥2L2 (X ) =
29
1 ∥u∥2L2 (X ) , |S|
since cross terms vanish by Eg [Tg u] = 0 for λ ̸= triv. Applying this with u = fλ and summing over λ ̸= triv yields ES ∥ΠS f − ΠG f ∥2L2 (X ) =
1 X 1 1 ∥fλ ∥2L2 (X ) ≤ ∥f ∥2L2 (X ) ≤ . |S| |S| |S| λ̸=triv
In particular, the expected approximation error decays exactly as 1/|S|, uniformly over all f ∈ F with ∥f ∥L2 (X ) ≤ 1. Therefore, random averaging over a small number of group elements preserves invariant components exactly, while suppressing non-invariant components in expectation. From a representationtheoretic viewpoint, this corresponds to averaging each nontrivial irreducible block toward zero, with variance decreasing as the number of sampled group elements increases.
A.9
Uniform Bounds for Partial Data Augmentation
In this subsection, we present a result showing that a single instance of partial data augmentation, constructed using a random subset S ⊆ G, can be reused to obtain guarantees that hold uniformly over the entire function space F, with high probability. In contrast to expectation-based bounds that apply to a fixed estimator, the results below control the approximation error of partial augmentation simultaneously for all functions in F, making them suitable for algorithm-agnostic and reusable augmentation schemes. Theorem A.2 (Partial data augmentation uniformly over F (high probability)). Let (X , µ) be a measured space and let F ⊆ L2 (X , µ) be a finite-dimensional subspace with dim(F) = r. Assume a group G acts isometrically on (X , µ) and that F is closed under the induced action. Let Tg : F → F denote the lifted (unitary) operators and let ΠG := Eg∼G [Tg ]
and
ΠS :=
1 X Tg , |S| g∈S
where S = {g1 , . . . , g|S| } is a multiset of |S| i.i.d. uniform samples from G. Then ΠG is the L2 (X )orthogonal projector from F onto the invariant subspace F G := {f ∈ F : Tg f = f ∀g ∈ G}. Fix any δ ∈ (0, 1) and any radius B > 0. With probability at least 1 − δ over the draw of S, the following holds simultaneously for all f ∈ F with ∥f ∥L2 (X ) ≤ B: s ∥ΠS f − ΠG f ∥L2 (X ) ≤ ∥ΠS − ΠG ∥op ∥f ∥L2 (X ) ≤ C B
log min{r, |G|}/δ , |S|
where ∥·∥op denotes the operator norm on F induced by ∥·∥L2 (X ) , and C > 0 is a universal constant. Equivalently, s log min{r, |G|}/δ sup ∥ΠS f − ΠG f ∥L2 (X ) ≤ C B . |S| f ∈F ∥f ∥L2 (X ) ≤B
In particular, if one performs partial data augmentation using the fixed set S and then applies the corresponding augmentation operator ΠS to any predictor f ∈ F , the augmentation error relative to full augmentation (i.e., ΠG ) is uniformly controlled as above.
30
Proof. We work on the Hilbert space (F , ⟨·, ·⟩) with the L2 (X ) inner product. Since the action of G on (X , µ) is isometric and F is closed under the induced action, each lifted map Tg : F → F is unitary: ∥Tg f ∥L2 (X ) = ∥f ∥L2 (X ) for all f ∈ F, g ∈ G. In particular, ∥Tg ∥op = 1 and ∥ΠS ∥op ≤ 1, ∥ΠG ∥op ≤ 1. Step 1: ΠG is the orthogonal projector onto F G . By definition, ΠG = Eg [Tg ] is a bounded linear operator on F. For any h ∈ F G we have Tg h = h for all g, hence ΠG h = h. Conversely, for any f ∈ F and any g0 ∈ G, left-invariance of the Haar/uniform measure implies Tg0 ΠG f = Tg0 Eg [Tg f ] = Eg [Tg0 g f ] = Eg [Tg f ] = ΠG f, so ΠG f ∈ F G . Thus range(ΠG ) = F G and ΠG acts as the identity on F G . Moreover, since each Tg is unitary, ΠG is self-adjoint: ⟨ΠG f, h⟩ = Eg ⟨Tg f, h⟩ = Eg ⟨f, Tg−1 h⟩ = Eg ⟨f, Tg h⟩ = ⟨f, ΠG h⟩, where we used Tg−1 = Tg−1 and invariance of the uniform/Haar measure under inversion. A selfadjoint idempotent operator is an orthogonal projector, hence ΠG is the L2 (X )-orthogonal projector onto F G . Step 2: Uniform control reduces to the operator norm. For any f ∈ F, ∥ΠS f − ΠG f ∥L2 (X ) ≤ ∥ΠS − ΠG ∥op ∥f ∥L2 (X ) . Therefore, it suffices to bound ∥ΠS − ΠG ∥op with high probability. Step 3: Block decomposition and reduction to nontrivial irreducibles. Fix an orthonormal basis of F that block-diagonalizes the unitary representation g 7→ Tg into irreducible components (finite-group harmonic decomposition): M F ∼ Cmλ ⊗ Vλ , = b λ∈G
where Vλ is an irreducible representation of dimension dλ . Under this change of basis, each Tg becomes block-diagonal with blocks Imλ ⊗ ρλ (g). On the trivial block λ = triv, ρtriv (g) = 1 for all g, so ΠS and ΠG coincide (both equal the identity) on F G . Thus ΠS − ΠG =
M
Imλ ⊗
λ̸=triv
1 X |S|
ρλ (g) ,
g∈S
and hence ∥ΠS − ΠG ∥op = max
λ̸=triv
31
1 X ρλ (g) |S| g∈S
. op
Step 4: Matrix concentration for each nontrivial irreducible block. Fix λ ̸= triv and define i.i.d. random matrices Xi := ρλ (gi ) ∈ Cdλ ×dλ for gi ∼ G. Since ρλ is unitary, ∥Xi ∥op = 1. Moreover, E[Xi ] = Eg∼G [ρλ (g)] = 0, because Eg [ρλ (g)] is an intertwiner from ρλ to itself, hence by Schur’s lemma it must be a scalar multiple of the identity; taking traces gives that scalar equals d1λ Eg [χλ (g)], which is 0 for any |S|
nontrivial irreducible representation. Therefore, {Xi }i=1 are independent, mean-zero, and satisfy ∥Xi ∥op ≤ 1. By a standard matrix Bernstein inequality (for sums of independent mean-zero matrices), for any t > 0, |S| X 1 P ≥ t ≤ 2dλ exp − c |S| t2 , Xi |S| i=1
op
for a universal constant c > 0 (using the crude variance bound ∥E[Xi Xi∗ ]∥op ≤ 1 and similarly for Xi∗ Xi ). For more details, see (Tropp, 2012). Step 5: Union bound over irreducible blocks.p Taking a union bound over all λ ̸= triv and P using that λ∈Gb d2λ = |G| (finite groups) and dλ ≤ |G|, we have P(∥ΠS − ΠG ∥op ≥ t) ≤
X
2dλ exp(−c|S|t2 )
λ̸=triv
X ≤ 2 dλ exp(−c|S|t2 ) b λ∈G
≤ 2 min{r, |G|} exp(−c|S|t2 ), P P P where we used λ dλ ≤ λ d2λ = |G| and also λ dλ ≤ r since the total dimension of the representation on F is r. Choosing s log(min{r, |G|}/δ) t=C |S| for a sufficiently large universal constant C > 0 makes the right-hand side at most δ. Thus, with probability at least 1 − δ, s log(min{r, |G|}/δ) ∥ΠS − ΠG ∥op ≤ C . |S| Step 6: Conclude the uniform bound over ∥f ∥ ≤ B. On this event, for every f ∈ F with ∥f ∥L2 (X ) ≤ B, s ∥ΠS f − ΠG f ∥L2 (X ) ≤ ∥ΠS − ΠG ∥op ∥f ∥L2 (X ) ≤ C B which is exactly the desired statement.
32
log(2 min{r, |G|}/δ) , |S|
A.10
Baseline Excess Risk of Projection Estimators (No Augmentation)
Let ΠF denote the L2 (X )-orthogonal projection onto F ⊂ L2 (X , µ). Lemma A.3 (Baseline excess risk: density estimation). Let F ⊂ L2 (X , µ) be r-dimensional with orthonormal basis {ϕℓ }rℓ=1 . Let x1 , . . . , xn be i.i.d. samples drawn from an unknown density f ⋆ with respect to µ, and assume f ⋆ ∈ L2 (X ) ∩ L∞ (µ). Define 1 θbℓ := n
n X
ϕℓ (xi ),
fb :=
i=1
r X
θbℓ ϕℓ .
ℓ=1
Then the expected excess L2 (X ) error over F satisfies ∥f ⋆ ∥∞ r. E ∥fb − ΠF f ⋆ ∥2L2 (X ) ≤ n Proof. Write ΠF f ⋆ =
Pr
ℓ=1 θℓ ϕℓ with θℓ = ⟨f
⋆, ϕ ⟩ = E ℓ x∼f ⋆ [ϕℓ (x)]. By orthonormality,
∥fb − ΠF f ⋆ ∥2L2 (X ) =
r X (θbℓ − θℓ )2 . ℓ=1
Taking expectation gives
r X ⋆ 2 b Var(θbℓ ). E ∥f − ΠF f ∥L2 (X ) = ℓ=1
Since θbℓ is an empirical mean, Var(θbℓ ) = n1 Varx∼f ⋆ (ϕℓ (x)) ≤ n1 Ex∼f ⋆ [ϕℓ (x)2 ]. Moreover, Z Z Ex∼f ⋆ [ϕℓ (x)2 ] = ϕℓ (x)2 f ⋆ (x) dµ(x) ≤ ∥f ⋆ ∥∞ ϕℓ (x)2 dµ(x) = ∥f ⋆ ∥∞ , X
X
and summing over ℓ ∈ [r] yields the claim. Lemma A.4 (Baseline excess risk: regression). Let F ⊂ L2 (X , µ) be r-dimensional with orthonormal basis {ϕℓ }rℓ=1 . Let (xi , yi )ni=1 be i.i.d. samples where xi ∼ µ and yi = f ⋆ (xi ) + εi ,
E[εi ] = 0,
E[ε2i ] = σ 2 ,
with εi independent of xi . Assume f ⋆ ∈ L2 (X ) ∩ L∞ (µ). Define 1 βbℓ := n
n X
yi ϕℓ (xi ),
i=1
fb :=
r X
βbℓ ϕℓ .
ℓ=1
Then the expected excess L2 (X ) error over F satisfies ∥f ⋆ ∥2∞ + σ 2 r. E ∥fb − ΠF f ⋆ ∥2L2 (X ) ≤ n Equivalently, for the squared-loss population risk R(f ) := E[(y − f (x))2 ], ∥f ⋆ ∥2∞ + σ 2 r. E R(fb) − inf R(f ) = E ∥fb − ΠF f ⋆ ∥2L2 (X ) ≤ f ∈F n 33
Proof. Let ΠF f ⋆ =
Pr
ℓ=1 βℓ ϕℓ , where
βℓ = ⟨f ⋆ , ϕℓ ⟩L2 (X ) = Ex∼µ [f ⋆ (x)ϕℓ (x)] = E[y ϕℓ (x)]. As before, ∥fb − ΠF f ⋆ ∥2L2 (X ) =
r X
r X ⋆ 2 b E ∥f − ΠF f ∥L2 (X ) = Var(βbℓ ).
(βbℓ − βℓ )2 ,
ℓ=1
ℓ=1
Since βbℓ is an empirical mean, Var(βbℓ ) = n1 Var(yϕℓ (x)) ≤ n1 E[y 2 ϕℓ (x)2 ]. Moreover, using E[y 2 | x] = f ⋆ (x)2 + σ 2 , E[y 2 ϕℓ (x)2 ] = Ex∼µ [(f ⋆ (x)2 + σ 2 )ϕℓ (x)2 ] ≤ (∥f ⋆ ∥2∞ + σ 2 ) Ex∼µ [ϕℓ (x)2 ] = ∥f ⋆ ∥2∞ + σ 2 , and summing over ℓ ∈ [r] gives the stated bound. Finally, for squared loss R(f ) = E[(y − f (x))2 ] with y = f ⋆ (x) + ε and E[ε | x] = 0, one has the standard identity R(f ) − R(ΠF f ⋆ ) = ∥f − ΠF f ⋆ ∥2L2 (X ) , which yields the excess-risk equality.
B
Proof of Theorem 4.1
Proof. We work with the L2 (X ) inner product. Since F is closed under the group action and the action is isometric, the averaged operator ΠG := Eg [Tg ] is the orthogonal projector onto F G . Let ΠF denote the L2 (X )-orthogonal projection onto F ⊂ L2 (X , µ), and similarly define ΠF G . Hence for any h ∈ F, ΠG h = ΠF G h, and in particular ΠG (ΠF f ⋆ ) = ΠF G f ⋆ . Step 1: Define an intermediate target in F. Let fF := ΠF f ⋆ ∈ F,
finv := ΠF G f ⋆ = ΠG fF ∈ F G .
We will bound the excess risk ∥fbS − finv ∥2L2 (X ) . Step 2: Estimation inside the invariant subspace. Consider the ideal estimator that uses full group averaging (equivalently, projects onto F G with respect to µ). Denote it by fbinv . By Lemma A.3 applied to the rinv -dimensional space F G (with its orthonormal basis), ∥f ⋆ ∥∞ E ∥fbinv − finv ∥2L2 (X ) ≤ rinv n in the density estimation setting. In the regression setting, the analogous bound follows from Lemma A.4: ∥f ⋆ ∥2∞ + σ 2 E ∥fbinv − finv ∥2L2 (X ) ≤ rinv . n
34
1 P Step 3: Replacing full averaging by averaging over S. Let ΠS := |S| g∈S Tg denote the empirical averaging operator. By the construction of the augmented projection estimator and linearity, we may write fbS = ΠS fb, fbinv = ΠG fb,
for the (non-augmented) projection estimator fb ∈ F built from the base samples (density or regression). Conditioning on the base data, we may apply the random-averaging identity from Appendix A.8 to obtain 1 b ES ∥fbS − fbinv ∥2L2 (X ) x1:n = ES ∥(ΠS − ΠG )fb∥2L2 (X ) x1:n = ∥f − ΠG fb∥2L2 (X ) . |S| Taking expectation over the base data and using ΠG = ΠF G on F , we obtain 1 b E ∥fbS − fbinv ∥2L2 (X ) = E ∥f − ΠF G fb∥2L2 (X ) . |S| Since fF ∈ F G , we have (I − ΠF G )fF = 0. Therefore, fb − ΠF G fb = (I − ΠF G )fb = (I − ΠF G )(fb − fF ). Since I − ΠF G is an orthogonal projector, it is non-expansive in L2 (X ). Hence ∥fb − ΠF G fb∥2L2 (X ) ≤ ∥fb − fF ∥2L2 (X ) . Consequently,
1 b E ∥f − fF ∥2L2 (X ) . E ∥fbS − fbinv ∥2L2 (X ) ≤ |S|
By Lemma A.3 in the density-estimation setting, and by Lemma A.4 in the regression setting, r E ∥fb − fF ∥2L2 (X ) ≲ . n Therefore, E ∥fbS − fbinv ∥2L2 (X ) ≲
r . n|S|
Step 4: Combine errors. Finally, by the inequality ∥a + b∥2 ≤ 2∥a∥2 + 2∥b∥2 , E ∥fbS − finv ∥2L2 (X ) ≤ 2 E ∥fbS − fbinv ∥2L2 (X ) + 2 E ∥fbinv − finv ∥2L2 (X ) . Substituting the bounds from Steps 2–3 yields, for density estimation, ∥f ⋆ ∥∞ r E ∥fbS − ΠF G f ⋆ ∥2L2 (X ) ≲ rinv + . n n|S| Similarly, in the regression setting with additive zero-mean noise of variance σ 2 , we obtain ∥f ⋆ ∥2∞ + σ 2 r E ∥fbS − ΠF G f ⋆ ∥2L2 (X ) ≲ rinv + . n n|S| Here we used that finv = ΠF G f ⋆ , since fF ∈ F G under the invariance assumption. This completes the proof. 35
Remark B.1 (Optimality up to constants). The proven upper bound is optimal up to absolute constants for random S. Indeed, the proof is based on an orthogonal decomposition into the invariant component and the residual non-invariant component. By the Pythagorean theorem, these two components contribute additively to the L2 error. The invariant component yields the usual rinv /n term, while random subset averaging reduces the non-invariant contribution by a factor of |S|, yielding the r/(n|S|) term. Thus, in general, neither term can be improved beyond absolute constants.
C
Proof of Theorem 4.3
Proof. We prove the density-estimation case; the regression case is identical, with the baseline projection-estimator bound over F G replaced by the corresponding regression bound. Step 0: Notation. Let fb ∈ F denote the (unaugmented) projection estimator based on the samples x1 , . . . , xn , and let fbS ∈ F denote the projection estimator obtained from the partially augmented samples {g −1 xi : i ∈ [n], g ∈ S}. As shown in the preliminaries (closure of F under the action and the orthonormal-basis identification), partial data augmentation by S corresponds 1 P to applying the averaging operator ΠS := |S| g∈S Tg to the (unaugmented) coefficient vector. Equivalently, at the function level, fbS = ΠS fb, (1) where Tg denotes the lifted unitary action on F . Moreover, the full-group averaging operator ΠG := Eg∼G [Tg ] is the L2 (X )-orthogonal projector onto F G . Step 1: Decompose the excess error. Let finv := ΠF G f ⋆ . Under the invariance assumption, fF := ΠF f ⋆ belongs to F G , and hence finv = fF . Using fbS = ΠS fb from Equation (1) and adding and subtracting ΠG fb, we have fbS − finv = ΠS fb − ΠG fb + ΠG fb − finv . Therefore, by ∥a + b∥2 ≤ 2∥a∥2 + 2∥b∥2 , ∥fbS − finv ∥2L2 (X ) ≤ 2∥(ΠS − ΠG )fb∥2L2 (X ) + 2∥ΠG fb − finv ∥2L2 (X ) .
(2)
Step 2: Control the partial-augmentation error via the operator norm. We first use the invariance of fF to center the partial-augmentation error around the baseline estimation error. Since fF ∈ F G , we have ΠS fF = fF , ΠG fF = fF . Hence (ΠS − ΠG )fF = 0, and therefore (ΠS − ΠG )fb = (ΠS − ΠG )(fb − fF ). Consequently,
∥(ΠS − ΠG )fb∥2L2 (X ) ≤ ∥ΠS − ΠG ∥2op ∥fb − fF ∥2L2 (X ) .
By Theorem A.2, for any δ ∈ (0, 1), with probability at least 1 − δ over the draw of S, log min{r, |G|}/δ 2 ∥ΠS − ΠG ∥op ≤ C0 |S| 36
(3)
(4)
for a universal constant C0 > 0. Combining Equations (3) and (4), on the same event, log min{r, |G|}/δ b 2 b ∥(ΠS − ΠG )f ∥L2 (X ) ≤ C0 ∥f − fF ∥2L2 (X ) . |S|
(5)
Step 3: Baseline estimation inside the invariant subspace. Since ΠG is the orthogonal projector onto F G , and finv = fF ∈ F G , we have ΠG fb − finv = ΠG (fb − fF ). Thus, by non-expansiveness of the orthogonal projector ΠG , ∥ΠG fb − finv ∥2L2 (X ) ≤ ∥fb − fF ∥2L2 (X ) . Moreover, the refined invariant projection-estimator bound from Step 2 of the proof gives, in the density-estimation setting, ∥f ⋆ ∥∞ E ∥ΠG fb − finv ∥2L2 (X ) ≤ C1 rinv . n
(6)
In the regression setting with additive zero-mean noise of variance σ 2 , the same argument gives ∥f ⋆ ∥2∞ + σ 2 E ∥ΠG fb − finv ∥2L2 (X ) ≤ C1 rinv . n Step 4: Take conditional expectation over the data. Taking conditional expectation of (2) given S, and using Equation (5), we obtain, on the event in Equation (4), h i log min{r, |G|}/δ 2 E ∥fbS − finv ∥L2 (X ) S ≤ 2C0 E ∥fb − fF ∥2L2 (X ) |S| + 2 E ∥ΠG fb − finv ∥2 2 . L (X )
By Lemma A.3, the baseline projection estimator satisfies ∥f ⋆ ∥∞ r E ∥fb − fF ∥2L2 (X ) ≤ C2 n in the density-estimation setting. Combining this with Equation (6) gives h i 2 E fbS − ΠF G f ⋆ L2 (X ) S ≤ C∥f ⋆ ∥∞
rinv r log min{r, |G|}/δ + n n|S|
! .
Similarly, in the regression setting with additive zero-mean noise of variance σ 2 , Lemma A.4 yields ∥f ⋆ ∥2∞ + σ 2 r, E ∥fb − fF ∥2L2 (X ) ≤ C2 n and therefore h i 2 E fbS − ΠF G f ⋆ L2 (X ) S ≤ C ∥f ⋆ ∥2∞ + σ 2 This completes the proof. 37
rinv r log min{r, |G|}/δ + n n|S|
! .
D
Proof of Theorem 4.5
We next state the formal version of Theorem 4.5 and provide its proof. Theorem D.1 (Exact invariance forces full augmentation). Let G be a finite group and let F be a finite-dimensional real (or complex) Hilbert space carrying a unitary representation ρ : G → U (F). For a multiset S ⊆ G, define the averaging operator 1 X 1 X ΠS := ρ(g), ΠG := ρ(g). |S| |G| g∈S
g∈G
Assume F is representation-complete in the sense that every irreducible representation of G appears b the multiplicity mλ (F) ≥ 1). as a subrepresentation of F (equivalently, for every λ ∈ G Suppose that partial data augmentation using S yields an estimator that is exactly G-invariant for all inputs, i.e., ρ(h)ΠS = ΠS for all h ∈ G, (7) or equivalently ΠS = ΠG on F. Then S must be uniform over the whole group in the following sense: if we write S as a multiset with multiplicity function mS : G → Z≥0 , then mS (g) is constant over g ∈ G, and in particular S contains each group element equally often. Consequently, if S is a subset (no repetitions), then necessarily S = G. Equivalently, under the representation-completeness assumption, the condition ΠS = ΠG holds if and only if the Fourier coefficients of the uniform measure on S vanish on all nontrivial irreducible representations: 1 X b \ {triv}, ρλ (g) = 0 for all λ ∈ G |S| g∈S
which forces S to be (multi)setwise uniform over G. Proof. Let G be a finite group and let ρ : G → U (F) be a unitary representation on the finitedimensional Hilbert space F . By assumption, F is representation-complete, meaning that every irreducible representation of G appears with positive multiplicity in F. Recall the averaging operators 1 X 1 X ΠS := ρ(g), ΠG := ρ(g), |S| |G| g∈S
g∈G
where S is viewed as a multiset. Irreducible decomposition. By the Peter–Weyl theorem for finite groups, F admits an orthogonal decomposition into irreducible components M F ∼ Cmλ ⊗ Vλ , = b λ∈G
where Vλ is an irreducible representation of dimension dλ and mλ ≥ 1 by representation-completeness. With respect to this decomposition, the representation ρ is block-diagonal: M ρ(g) = Imλ ⊗ ρλ (g), b λ∈G
and hence both ΠS and ΠG are block-diagonal as well. 38
Action of the full group average. For the trivial irreducible representation λ = triv, we have ρtriv (g) = 1 for all g ∈ G, so 1 X (triv) ΠG = 1 = 1. |G| g∈G
For any nontrivial irreducible representation λ ̸= triv, orthogonality of matrix coefficients implies 1 X ρλ (g) = 0. |G| g∈G
Therefore, ΠG acts as the identity on the trivial isotypic component F G and annihilates all nontrivial isotypic components. Consequences of exact invariance. Suppose now that ΠS = ΠG as operators on F. Comparing the action of ΠS and ΠG on each irreducible block, we conclude that for every nontrivial irreducible representation λ ̸= triv, 1 X ρλ (g) = 0. (8) |S| g∈S
Fourier-analytic interpretation. Define the probability measure µS on G by µS (g) :=
mS (g) , |S|
where mS (g) denotes the multiplicity of g in the multiset S. Equation (8) states precisely that the Fourier transform of µS vanishes on all nontrivial irreducible representations: X µ cS (λ) := µS (g)ρλ (g) = 0 for all λ ̸= triv. g∈G
By the Fourier inversion theorem for finite groups, the only probability measure on G whose Fourier coefficients vanish on all nontrivial irreducible representations is the uniform measure. Hence µS (g) = 1/|G| for all g ∈ G. Conclusion. Therefore, the multiplicity function mS (g) is constant over G, meaning that S is uniform over the group. In particular, if S is a subset without repetitions, this forces S = G. This completes the proof.
E
Extensions to Ordinary Least Squares (OLS) and Infinite-Dimensional Hypothesis Classes
While in the main text, we focused on projection estimators, this choice is not essential to data augmentation, and it only makes the statistical and representation-theoretic effects of augmentation especially transparent. In this section, we compare the projection estimator with ordinary least squares (OLS), and then explain how the same finite-dimensional analysis applies to finitedimensional truncations of infinite-dimensional function classes.
39
E.1
Projection Estimators Versus Ordinary Least Squares (OLS)
Let F be an r-dimensional subspace of L2 (X , µ), and let ϕ(x) = ϕ1 (x), . . . , ϕr (x)
⊤
be an orthonormal basis of F. For fβ (x) = ⟨β, ϕ(x)⟩, orthonormality gives ∥fβ ∥2L2 (X ) = ∥β∥22 , Ex∼µ ϕ(x)ϕ(x)⊤ = Ir . Given data (xi , yi )ni=1 , define bb := 1 n
n X
yi ϕ(xi ),
i=1
b := 1 Σ n
n X
ϕ(xi )ϕ(xi )⊤ .
i=1
The projection estimator used throughout the paper is βbproj = bb,
fbproj (x) = ⟨bb, ϕ(x)⟩.
b by its population value Ir . This Thus, the projection estimator replaces the empirical covariance Σ is natural in our setting because the samples are drawn from µ, and the basis is orthonormal with respect to µ. By contrast, ordinary least squares solves the empirical least-squares problem 1 βbols ∈ arg minr β∈R n
n X
2 yi − ⟨β, ϕ(xi )⟩ .
i=1
Equivalently, it satisfies b βbols = bb =⇒ βbols = Σ b †bb, Σ
b †bb, ϕ(x)⟩, fbols (x) = ⟨Σ
b is invertible, this reduces to βbols = Σ b −1bb. where † denotes the Moore–Penrose pseudoinverse; if Σ n×r ⊤ ⊤ Finally, let Φ ∈ R be the feature matrix with rows ϕ(xi ) , and let y = (y1 , . . . , yn ) . Then † 1 ⊤ 1 ⊤ 1 ⊤ b b βols = Φ Φ Φ y = (Φ⊤ Φ)† Φ⊤ y. βproj = Φ y, n n n The difference between the two estimators is therefore exactly the covariance used to map empirical b = (1/n)Φ⊤ Φ, whereas the projection moments to coefficients: OLS uses the empirical covariance Σ estimator uses the population covariance Ir . We next describe how augmentation enters these formulas. Let G act on X , and let ρ : G → Rr×r denote the induced representation on F, defined by (ρ(g)f )(x) = f (g −1 x). Equivalently, for fβ (x) = ⟨β, ϕ(x)⟩, we write ρ(g)fβ = fρ(g)β , which implies ϕ(g −1 x) = ρ(g)⊤ ϕ(x). For an augmentation set S ⊆ G, the augmented empirical moment vector is X bbS := 1 ρ(s)bb. |S| s∈S
40
This is exactly the partial averaging operator applied to the coefficient vector: bbS = ΠSbb. Thus, the augmented projection estimator is βbproj,S = ΠSbb. For ordinary least squares, augmentation also modifies the empirical covariance. The augmented covariance is X ⊤ b b S := 1 ρ(s)Σρ(s) . Σ |S| s∈S
Consequently, the augmented least-squares estimator is b † bbS = βbols,S = Σ S
1 X ⊤ b ρ(s)Σρ(s) |S| s∈S
!†
! 1 X ρ(s)bb . |S| s∈S
This formula shows that OLS has the same first-order averaging structure as the projection estimator, but also contains a second-order averaging operation through the empirical covariance matrix. This distinction explains why projection estimators provide a cleaner object for the theoretical study of data augmentation. For projection estimators, the effect of augmentation is exactly the action of the averaging operator ΠS on F. Hence, the excess risk can be read directly from how well ΠS approximates the full averaging operator ΠG . In OLS, the estimator depends both on the b S . Thus, exact averaging on F averaged moment vector bbS and on the averaged covariance matrix Σ immediately gives exact averaging of the first-order moment term, whereas exact equality of the full OLS estimator with its fully augmented counterpart also involves the covariance term. Note that this second-order term is absent from the projection estimator because the population covariance is already fixed to Ir . Projection estimators also avoid small-sample instability. When n is comparable to, or smaller b may be singular or poorly conditioned. OLS can therefore be than, r, the empirical covariance Σ b unstable unless one adds regularization or assumes enough samples to guarantee concentration of Σ around Ir . By contrast, the projection estimator is well-defined for every sample size and depends linearly on the empirical moments. This isolates the effect of augmentation from the separate issue of empirical covariance inversion. In short, the projection estimator may be viewed as the population-covariance analogue of OLS: βbproj = Ir−1bb,
b †bb. βbols = Σ
Since our goal is to understand how partial augmentation suppresses non-invariant components, projection estimators are a natural theoretical choice: they turn augmentation into an averaging operator on F, give clean rates, and avoid conditioning assumptions that are orthogonal to the main phenomenon.
E.2
Infinite-Dimensional Hypothesis Classes
The main results are stated for finite-dimensional spaces F. This assumption separates the effect of augmentation from the separate issue of approximation error. The same conclusions apply to infinite-dimensional classes after choosing a finite-dimensional truncation.
41
Let F be an infinite-dimensional G-invariant subspace of L2 (X , µ), and let Fr ⊂ F be an r-dimensional G-invariant subspace. For example, Fr may be spanned by the first r basis functions in a spectral, Fourier, or polynomial decomposition, provided the truncation is closed under the action of G. Let rinv (r) := dim(FrG ) denote the dimension of the invariant subspace inside Fr . Applying our finite-dimensional results to Fr gives the same bounds with r replaced by dim(Fr ), and with rinv replaced by rinv (r). In particular, for a fixed truncation Fr , the partial augmentation term scales as r , n|S| while the invariant estimation term scales as rinv (r) . n Thus, for this truncation, the same statistical transition occurs at |S| ≍
r . rinv (r)
For an infinite-dimensional class, one must also account for the approximation error incurred by restricting to Fr . Let fr := ΠFr f ⋆ be the projection of the target onto the truncation. Then the total error decomposes into an estimation part and an approximation part. Schematically, for partial augmentation on Fr , one obtains a bound of the form E ∥fbS,r − f ⋆ ∥2L2 (X ) ≲
rinv (r) r + n n|S| | {z }
estimation and augmentation
+ ∥f ⋆ − fr ∥2L2 (X ) , | {z } approximation
up to the problem-dependent constants appearing in the finite-dimensional results. If the target is invariant and the truncation Fr is G-invariant, then fr is also invariant, so the same invariantsubspace analysis applies inside Fr . The remaining task is to optimize over the truncation level r. This requires balancing the statistical terms r rinv (r) + n n|S| against the approximation error
∥f ⋆ − ΠFr f ⋆ ∥2L2 (X ) .
The optimal truncation is problem-specific. It depends on the smoothness or spectral decay of f ⋆ , on how the group action decomposes across the basis functions, and on how quickly the invariant dimension rinv (r) grows with r. These approximation-theoretic questions are important, but they are separate from the main focus of this paper. Our results characterize the effect of partial augmentation once a finite-dimensional representation has been chosen; optimizing this representation for a particular infinite-dimensional model is left to problem-specific work. 42