Data Augmentation: A Fourier Analysis Perspective

# Data Augmentation: A Fourier Analysis Perspective
Source: [https://arxiv.org/html/2606.24418](https://arxiv.org/html/2606.24418)
Behrooz Tahmasebi111Harvard John A\. Paulson School of Engineering and Applied Sciences, Harvard University, Cambridge, MA 02138, USA\. Emails:\{behrooz\_tahmasebi,mweber\}@seas\.harvard\.eduStefanie Jegelka222Technical University of Munich \(CIT, MCML, MDSI\) and MIT Computer Science and Artificial Intelligence Laboratory \(CSAIL\)\. Email:stefanie\.jegelka@tum\.de

###### 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íazet al\.,[2025](https://arxiv.org/html/2606.24418#bib.bib54)\): 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

###### Contents

1. [1Introduction](https://arxiv.org/html/2606.24418#S1)1. [1\.1Our Contributions](https://arxiv.org/html/2606.24418#S1.SS1)
2. [2Related Work](https://arxiv.org/html/2606.24418#S2)
3. [3Problem Statement](https://arxiv.org/html/2606.24418#S3)1. [3\.1Data Domain, Symmetry Groups, and Actions](https://arxiv.org/html/2606.24418#S3.SS1) 2. [3\.2Function Spaces and Lifted Group Actions](https://arxiv.org/html/2606.24418#S3.SS2) 3. [3\.3Learning Tasks](https://arxiv.org/html/2606.24418#S3.SS3) 4. [3\.4Data Augmentation](https://arxiv.org/html/2606.24418#S3.SS4) 5. [3\.5Objectives and Questions](https://arxiv.org/html/2606.24418#S3.SS5) 6. [3\.6Projection Estimators](https://arxiv.org/html/2606.24418#S3.SS6)
4. [4Main Results](https://arxiv.org/html/2606.24418#S4)
5. [5Interpreting the Regimes of Partial Augmentation](https://arxiv.org/html/2606.24418#S5)1. [5\.1Extension to Binary Classification](https://arxiv.org/html/2606.24418#S5.SS1)
6. [6Projection Estimators on the Sphere](https://arxiv.org/html/2606.24418#S6)
7. [7Conclusion](https://arxiv.org/html/2606.24418#S7)
8. [References](https://arxiv.org/html/2606.24418#bib)
9. [APreliminaries](https://arxiv.org/html/2606.24418#A1)1. [A\.1Spherical Harmonics](https://arxiv.org/html/2606.24418#A1.SS1) 2. [A\.2Gegenbauer Polynomials, Zonal Kernels, and Projection Kernels](https://arxiv.org/html/2606.24418#A1.SS2) 3. [A\.3Groups](https://arxiv.org/html/2606.24418#A1.SS3) 4. [A\.4Group Actions](https://arxiv.org/html/2606.24418#A1.SS4) 5. [A\.5Group Representations](https://arxiv.org/html/2606.24418#A1.SS5) 6. [A\.6Projection Estimators](https://arxiv.org/html/2606.24418#A1.SS6) 7. [A\.7Projection Estimators on Sphere](https://arxiv.org/html/2606.24418#A1.SS7) 8. [A\.8Approximate Projection via Random Group Averaging](https://arxiv.org/html/2606.24418#A1.SS8) 9. [A\.9Uniform Bounds for Partial Data Augmentation](https://arxiv.org/html/2606.24418#A1.SS9) 10. [A\.10Baseline Excess Risk of Projection Estimators \(No Augmentation\)](https://arxiv.org/html/2606.24418#A1.SS10)
10. [BProof of Theorem4\.1](https://arxiv.org/html/2606.24418#A2)
11. [CProof of Theorem4\.3](https://arxiv.org/html/2606.24418#A3)
12. [DProof of Theorem4\.5](https://arxiv.org/html/2606.24418#A4)
13. [EExtensions to Ordinary Least Squares \(OLS\) and Infinite\-Dimensional Hypothesis Classes](https://arxiv.org/html/2606.24418#A5)1. [E\.1Projection Estimators Versus Ordinary Least Squares \(OLS\)](https://arxiv.org/html/2606.24418#A5.SS1) 2. [E\.2Infinite\-Dimensional Hypothesis Classes](https://arxiv.org/html/2606.24418#A5.SS2)

## 1Introduction

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\.1Our Contributions

We summarize the main contributions of this paper\.

#### Statistical optimality of partial data augmentation\.

In Theorem[4\.1](https://arxiv.org/html/2606.24418#S4.Thmtheorem1), we analyze partial data augmentation for projection\-based density and regression estimators\. We prove that partial augmentation using a randomly sampled subsetS⊆GS\\subseteq Gachieves the same minimax\-optimal sample complexity as full group\-sized augmentation, provided that the number of sampled group elements satisfies

\|S\|≳rrinv,\|S\|\\;\\gtrsim\\;\\frac\{r\}\{r\_\{\\mathrm\{inv\}\}\},whererrdenotes the dimension of the full feature space andrinvr\_\{\\mathrm\{inv\}\}is the dimension of the invariant subspace induced by the symmetries\. Indeed, the required size of the augmentation subset depends only on the invariant dimensionrinvr\_\{\\mathrm\{inv\}\}and is independent of the group size\. Consequently, statistically optimal rates can be achieved without averaging over the entire group, which may be large or even infinite\. This sheds light on a question raised in recent work\(Díazet al\.,[2025](https://arxiv.org/html/2606.24418#bib.bib54)\)concerning whether statistical optimality can be reconciled with computational scalability in learning under general symmetry groups\.

#### Uniform and reusable partial data augmentation\.

In Theorem[4\.2](https://arxiv.org/html/2606.24418#S4.Thmtheorem2)and Theorem[4\.3](https://arxiv.org/html/2606.24418#S4.Thmtheorem3), we further study the role of partial data augmentation from a uniform generalization perspective\. Specifically, we ask whether a*single*randomly chosen augmentation setSScan be reused across multiple learning tasks and still achieve minimax\-optimal rates with high probability\.

Our main finding is that enforcing uniformity over the entire function classℱ\\mathcal\{F\}incurs only a mild logarithmic overhead\. Concretely, Theorem[4\.3](https://arxiv.org/html/2606.24418#S4.Thmtheorem3)shows that it suffices to choose

\|S\|≳r​log⁡\(min⁡\{r,\|G\|\}\)rinv,\|S\|\\;\\gtrsim\\;\\frac\{r\\,\\log\\\!\\big\(\\min\\\{r,\|G\|\\\}\\big\)\}\{r\_\{\\mathrm\{inv\}\}\},wherer=dim\(ℱ\)r=\\dim\(\\mathcal\{F\}\)andrinv=dim\(ℱG\)r\_\{\\mathrm\{inv\}\}=\\dim\(\\mathcal\{F\}^\{G\}\)\. Thus, the cost of reusing a single partial augmentation set is only alog⁡\(min⁡\{r,\|G\|\}\)\\log\(\\min\\\{r,\|G\|\\\}\)factor, which remains small even when the function space dimensionrris large or the groupGGis infinite\.

#### Impossibility of exact invariance via partial augmentation\.

Finally, in Theorem[4\.5](https://arxiv.org/html/2606.24418#S4.Thmtheorem5), 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 groupGGis computationally intractable in general\. Specifically, assuming the hypothesis space is sufficiently rich to represent all irreducible symmetry modes, exactGG\-invariance via data augmentation requires averaging over the entire group and thus no strict subsetS⊊GS\\subsetneq Gcan 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\.*

## 2Related 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\(Zhanget al\.,[2025](https://arxiv.org/html/2606.24418#bib.bib3); Batzneret al\.,[2022](https://arxiv.org/html/2606.24418#bib.bib35); Bronsteinet al\.,[2017](https://arxiv.org/html/2606.24418#bib.bib36); Smidt,[2021](https://arxiv.org/html/2606.24418#bib.bib37); Batzneret al\.,[2023](https://arxiv.org/html/2606.24418#bib.bib52); Weber,[2025](https://arxiv.org/html/2606.24418#bib.bib55)\)\. From a theoretical perspective, the statistical benefits of exploiting symmetries have been studied for group averaging\(Tahmasebi and Jegelka,[2023](https://arxiv.org/html/2606.24418#bib.bib4); Tahmasebi and Weber,[2026a](https://arxiv.org/html/2606.24418#bib.bib58)\), as well as for canonicalization\-based approaches\(Tahmasebi and Jegelka,[2025a](https://arxiv.org/html/2606.24418#bib.bib5)\)\. Related work has also examined the role of regularization in symmetric models\(Tahmasebi and Jegelka,[2025b](https://arxiv.org/html/2606.24418#bib.bib22)\)and the problem of testing for and identifying invariances\(Dehmamyet al\.,[2021](https://arxiv.org/html/2606.24418#bib.bib61); Soleymaniet al\.,[2025b](https://arxiv.org/html/2606.24418#bib.bib31); Tahmasebi and Weber,[2026b](https://arxiv.org/html/2606.24418#bib.bib60)\)\. In parallel, recent studies have investigated generalization\(Biettiet al\.,[2021](https://arxiv.org/html/2606.24418#bib.bib59); Meiet al\.,[2021](https://arxiv.org/html/2606.24418#bib.bib13)\)and the computational complexity\(Soleymaniet al\.,[2025c](https://arxiv.org/html/2606.24418#bib.bib32),[a](https://arxiv.org/html/2606.24418#bib.bib30); Kianiet al\.,[2024](https://arxiv.org/html/2606.24418#bib.bib56)\)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](https://arxiv.org/html/2606.24418#bib.bib14); Paciniet al\.,[2025](https://arxiv.org/html/2606.24418#bib.bib57)\)\.

#### 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\(Kabaet al\.,[2023](https://arxiv.org/html/2606.24418#bib.bib1); Maet al\.,[2024](https://arxiv.org/html/2606.24418#bib.bib2); Dymet al\.,[2024](https://arxiv.org/html/2606.24418#bib.bib38); Shumaylovet al\.,[2025](https://arxiv.org/html/2606.24418#bib.bib51)\)aim to map inputs to a canonical representative of their orbit, while frame averaging\(Punyet al\.,[2022](https://arxiv.org/html/2606.24418#bib.bib7)\)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\(Shenet al\.,[2022](https://arxiv.org/html/2606.24418#bib.bib17)\), its role as an implicit form of regularization\(Linet al\.,[2024](https://arxiv.org/html/2606.24418#bib.bib18); Yanget al\.,[2023b](https://arxiv.org/html/2606.24418#bib.bib29)\), and its group\-theoretic foundations\(Chenet al\.,[2020](https://arxiv.org/html/2606.24418#bib.bib19)\)\. Most closely related to our setting,Daoet al\.\([2019](https://arxiv.org/html/2606.24418#bib.bib8)\)developed a kernel\-based analysis of data augmentation, with further refinements and extensions in\(Patil and Du,[2023](https://arxiv.org/html/2606.24418#bib.bib21); Meiet al\.,[2021](https://arxiv.org/html/2606.24418#bib.bib13)\)\. 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\(Zhenget al\.,[2023](https://arxiv.org/html/2606.24418#bib.bib24); Donget al\.,[2023](https://arxiv.org/html/2606.24418#bib.bib25); Chenet al\.,[2024](https://arxiv.org/html/2606.24418#bib.bib26)\)\. 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](https://arxiv.org/html/2606.24418#bib.bib12)\), reinforcement learning\(Maet al\.,[2025](https://arxiv.org/html/2606.24418#bib.bib23)\), and natural language processing\(Liet al\.,[2022](https://arxiv.org/html/2606.24418#bib.bib27); Pelliceret al\.,[2023](https://arxiv.org/html/2606.24418#bib.bib28)\)\. Additional application\-focused studies include image classification\(Mikołajczyk and Grochowski,[2018](https://arxiv.org/html/2606.24418#bib.bib10)\), graph learning\(Zhaoet al\.,[2022](https://arxiv.org/html/2606.24418#bib.bib9)\), and other domains\(Mumuni and Mumuni,[2022](https://arxiv.org/html/2606.24418#bib.bib11)\)\. It is also important to note that data augmentation can sometimes be detrimental, as discussed inKirichenkoet al\.\([2023](https://arxiv.org/html/2606.24418#bib.bib20)\)\. The partial enforcement of symmetry has a long history in applications where symmetry is either intrinsically approximate\(Finziet al\.,[2021](https://arxiv.org/html/2606.24418#bib.bib39); Romero and Lohit,[2022](https://arxiv.org/html/2606.24418#bib.bib40); van der Ouderaaet al\.,[2022](https://arxiv.org/html/2606.24418#bib.bib41); Kimet al\.,[2023](https://arxiv.org/html/2606.24418#bib.bib42); Parket al\.,[2025](https://arxiv.org/html/2606.24418#bib.bib43); Wanget al\.,[2022](https://arxiv.org/html/2606.24418#bib.bib44)\), or unknown and therefore must be discovered from data\(Yanget al\.,[2024](https://arxiv.org/html/2606.24418#bib.bib45),[2023a](https://arxiv.org/html/2606.24418#bib.bib46); van der Ouderaaet al\.,[2023](https://arxiv.org/html/2606.24418#bib.bib47); Huh,[2025](https://arxiv.org/html/2606.24418#bib.bib48); Desaiet al\.,[2022](https://arxiv.org/html/2606.24418#bib.bib49); Dehmamyet al\.,[2021](https://arxiv.org/html/2606.24418#bib.bib61); Shawet al\.,[2024](https://arxiv.org/html/2606.24418#bib.bib50)\)\.

#### Invariant kernels\.

Recent work on invariant kernels\(Díazet al\.,[2025](https://arxiv.org/html/2606.24418#bib.bib54)\)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\.

## 3Problem Statement

We formalize the learning problems considered in this paper and set up the notation used throughout\.

### 3\.1Data Domain, Symmetry Groups, and Actions

Let\(𝒳,μ\)\(\\mathcal\{X\},\\mu\)be a measurable space, whereμ\\mudenotes a reference probability measure on𝒳\\mathcal\{X\}\. We assume that a groupGGacts on𝒳\\mathcal\{X\}via measurable maps

\(g,x\)↦g​x,g∈G,x∈𝒳,\(g,x\)\\;\\mapsto\\;gx,\\qquad g\\in G,\\ x\\in\\mathcal\{X\},satisfyinge​x=xex=xandg​\(h​x\)=\(g​h\)​xg\(hx\)=\(gh\)xfor allg,h∈Gg,h\\in G, whereeedenotes the identity element\. Throughout the paper, we assume that the action ofGGon𝒳\\mathcal\{X\}is*measure\-preserving*, meaning thatμ​\(g​A\)=μ​\(A\)\\mu\(gA\)=\\mu\(A\)for all measurable setsA⊆𝒳A\\subseteq\\mathcal\{X\}and allg∈Gg\\in G\.

This framework captures a wide range of symmetries arising in practice, including permutations, sign flips, rotations, reflections, and combinations thereof\. We allowGGto be finite or infinite \(compact\); when sampling fromGGis required, we assume there is an oracle access to the uniform sampling for the canonical \(Haar\) probability measure on the group\.

### 3\.2Function Spaces and Lifted Group Actions

Letℱ⊂L2​\(𝒳,μ\)\\mathcal\{F\}\\subset L^\{2\}\(\\mathcal\{X\},\\mu\)be a finite\-dimensional linear subspace withdim\(ℱ\)=r\\dim\(\\mathcal\{F\}\)=r\. LetΠℱ\\Pi\_\{\\mathcal\{F\}\}denote theL2​\(𝒳\)L^\{2\}\(\\mathcal\{X\}\)\-orthogonal projection ontoℱ⊂L2​\(𝒳,μ\)\\mathcal\{F\}\\subset L^\{2\}\(\\mathcal\{X\},\\mu\)\. We assume thatℱ\\mathcal\{F\}is*closed under the action ofGG*, meaning that for everyf∈ℱf\\in\\mathcal\{F\}and everyg∈Gg\\in G, the functionx↦f​\(g−1​x\)x\\mapsto f\(g^\{\-1\}x\)also belongs toℱ\\mathcal\{F\}\.

This closure property induces a lifted action ofGGonℱ\\mathcal\{F\}\. Specifically, for eachg∈Gg\\in G, define a linear operatorTg:ℱ→ℱT\_\{g\}:\\mathcal\{F\}\\to\\mathcal\{F\}by\(Tg​f\)​\(x\):=f​\(g−1​x\)\.\(T\_\{g\}f\)\(x\):=f\(g^\{\-1\}x\)\.Under our assumptions, eachTgT\_\{g\}is unitary with respect to theL2​\(𝒳\)L^\{2\}\(\\mathcal\{X\}\)inner product, and the mapg↦Tgg\\mapsto T\_\{g\}defines a finite\-dimensional unitary representation ofGGonℱ\\mathcal\{F\}\(Appendix[A\.5](https://arxiv.org/html/2606.24418#A1.SS5)\)\.

A central object in this paper is the subspace ofGG\-invariant functions, defined as

ℱG:=\{f∈ℱ:Tg​f=f​for all​g∈G\}\.\\mathcal\{F\}^\{G\}\\;:=\\;\\\{f\\in\\mathcal\{F\}:T\_\{g\}f=f\\ \\text\{for all \}g\\in G\\\}\.We denote its dimension byrinv:=dim\(ℱG\)r\_\{\\mathrm\{inv\}\}:=\\dim\(\\mathcal\{F\}^\{G\}\)\. Intuitively,rinvr\_\{\\mathrm\{inv\}\}measures the*effective dimension*of the function class after accounting for the symmetries\.

### 3\.3Learning Tasks

We study two classical statistical learning problems\.

#### Density estimation\.

We observe unlabeled samplesx1,…,xn∈𝒳x\_\{1\},\\dots,x\_\{n\}\\in\\mathcal\{X\}drawn i\.i\.d\. from an unknown densityf⋆f^\{\\star\}with respect toμ\\mu, wheref⋆∈L2​\(𝒳,μ\)∩L∞​\(𝒳,μ\)f^\{\\star\}\\in L^\{2\}\(\\mathcal\{X\},\\mu\)\\cap L^\{\\infty\}\(\\mathcal\{X\},\\mu\)\. The goal is to estimatef⋆f^\{\\star\}in squaredL2​\(𝒳\)L^\{2\}\(\\mathcal\{X\}\)risk\.

#### Supervised regression\.

We observe labeled samples\{\(xi,yi\)\}i=1n\\\{\(x\_\{i\},y\_\{i\}\)\\\}\_\{i=1\}^\{n\}generated according toyi=f⋆​\(xi\)\+εi,y\_\{i\}=f^\{\\star\}\(x\_\{i\}\)\+\\varepsilon\_\{i\},wherexi∼μx\_\{i\}\\sim\\mui\.i\.d\., the noise variablesεi\\varepsilon\_\{i\}are independent, mean\-zero, and satisfy𝔼​\[εi2\]=σ2\\mathbb\{E\}\[\\varepsilon\_\{i\}^\{2\}\]=\\sigma^\{2\}\. The regression functionf⋆f^\{\\star\}is assumed to belong toL2​\(𝒳,μ\)∩L∞​\(𝒳,μ\)L^\{2\}\(\\mathcal\{X\},\\mu\)\\cap L^\{\\infty\}\(\\mathcal\{X\},\\mu\)\. Performance is measured in squaredL2​\(𝒳\)L^\{2\}\(\\mathcal\{X\}\)error\.

For both settings, we focus on*projection estimators*, which estimatef⋆f^\{\\star\}by projecting empirical moments onto the finite\-dimensional spaceℱ\\mathcal\{F\}\. These estimators are classical, minimax\-optimal, and serve as a clean testbed for studying the effect of symmetry and data augmentation\.

### 3\.4Data Augmentation

Given a set of group elementsS⊆GS\\subseteq G, data augmentation proceeds by transforming each observed sample using elements ofSS\. Concretely, the augmented sample is given by

\{g−1​xi:i∈\[n\],g∈S\},\{\(g−1​xi,yi\):i∈\[n\],g∈S\},\\\{g^\{\-1\}x\_\{i\}:i\\in\[n\],\\ g\\in S\\\},\\qquad\\\{\(g^\{\-1\}x\_\{i\},y\_\{i\}\):i\\in\[n\],\\ g\\in S\\\},in the density estimation and regression settings, respectively\. We distinguish two regimes:

- •*Full data augmentation*, whereS=GS=G\.
- •*Partial data augmentation*, whereSSis a \(typically random\) strict subset ofGG\.

Full augmentation can enforce exact invariance but is often computationally infeasible whenGGis large or infinite\. Partial augmentation is computationally efficient and more practical, but its statistical benefits are less well understood\.

### 3\.5Objectives 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 setSSbe reused across tasks or estimators, while still providing uniform generalization guarantees?
- •Exact versus approximate invariance\.Is it possible to enforce exactGG\-invariance via partial data augmentation, or is full group\-sized augmentation fundamentally necessary?

### 3\.6Projection 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](https://arxiv.org/html/2606.24418#A5)\.

#### Density estimation\.

Let\(ϕℓ\)ℓ=1r\(\\phi\_\{\\ell\}\)\_\{\\ell=1\}^\{r\}be a fixedL2​\(𝒳\)L^\{2\}\(\\mathcal\{X\}\)\-orthonormal basis ofℱ\\mathcal\{F\}\. Suppose we observe unlabeled samplesx1,…,xnx\_\{1\},\\dots,x\_\{n\}drawn i\.i\.d\. from an unknown densityf⋆f^\{\\star\}with respect toμ\\mu, wheref⋆∈L2​\(𝒳,μ\)∩L∞​\(𝒳,μ\)f^\{\\star\}\\in L^\{2\}\(\\mathcal\{X\},\\mu\)\\cap L^\{\\infty\}\(\\mathcal\{X\},\\mu\)\. The population projection off⋆f^\{\\star\}ontoℱ\\mathcal\{F\}is

Πℱ​f⋆=∑ℓ=1rθℓ​ϕℓ,θℓ:=𝔼​\[ϕℓ​\(x\)\]\.\\Pi\_\{\\mathcal\{F\}\}f^\{\\star\}=\\sum\_\{\\ell=1\}^\{r\}\\theta\_\{\\ell\}\\,\\phi\_\{\\ell\},\\qquad\\theta\_\{\\ell\}:=\\mathbb\{E\}\[\\phi\_\{\\ell\}\(x\)\]\.The coefficientsθℓ\\theta\_\{\\ell\}can be estimated unbiasedly from data by empirical averages, leading to the projection density estimator

θ^ℓ:=1n​∑i=1nϕℓ​\(xi\)⟹f^:=∑ℓ=1rθ^ℓ​ϕℓ∈ℱ\.\\widehat\{\\theta\}\_\{\\ell\}:=\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\\phi\_\{\\ell\}\(x\_\{i\}\)\\implies\\widehat\{f\}:=\\sum\_\{\\ell=1\}^\{r\}\\widehat\{\\theta\}\_\{\\ell\}\\,\\phi\_\{\\ell\}\\;\\in\\;\\mathcal\{F\}\.

#### Regression\.

In the regression setting, we observe labeled samples\(xi,yi\)i=1n\(x\_\{i\},y\_\{i\}\)\_\{i=1\}^\{n\}with

yi=f⋆​\(xi\)\+εi,𝔼​\[εi\]=0,𝔼​\[εi2\]=σ2\.y\_\{i\}=f^\{\\star\}\(x\_\{i\}\)\+\\varepsilon\_\{i\},\\qquad\\mathbb\{E\}\[\\varepsilon\_\{i\}\]=0,\\quad\\mathbb\{E\}\[\\varepsilon\_\{i\}^\{2\}\]=\\sigma^\{2\}\.The population projection of the regression functionf⋆f^\{\\star\}ontoℱ\\mathcal\{F\}is againΠℱ​f⋆\\Pi\_\{\\mathcal\{F\}\}f^\{\\star\}, with coefficients

βℓ:=𝔼​\[y​ϕℓ​\(x\)\]\.\\beta\_\{\\ell\}:=\\mathbb\{E\}\[y\\,\\phi\_\{\\ell\}\(x\)\]\.Estimating these moments empirically yields the projection regression estimator

f^:=∑ℓ=1rβ^ℓ​ϕℓ,β^ℓ:=1n​∑i=1nyi​ϕℓ​\(xi\)\.\\widehat\{f\}:=\\sum\_\{\\ell=1\}^\{r\}\\widehat\{\\beta\}\_\{\\ell\}\\,\\phi\_\{\\ell\},\\qquad\\widehat\{\\beta\}\_\{\\ell\}:=\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}y\_\{i\}\\,\\phi\_\{\\ell\}\(x\_\{i\}\)\.

#### Statistical properties\.

Projection estimators achieve minimax\-optimal rates overrr\-dimensional classes, with expectedL2​\(𝒳\)L^\{2\}\(\\mathcal\{X\}\)error of orderr/nr/nin 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\.

## 4Main 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 ofSS\.

###### Theorem 4\.1\(Partial data augmentation for projection estimators\)\.

Letℱ⊂L2​\(𝒳,μ\)\\mathcal\{F\}\\subset L^\{2\}\(\\mathcal\{X\},\\mu\)be a finite\-dimensional space of dimensionrr, closed under the action of a groupGG, and letℱG\\mathcal\{F\}^\{G\}denote its invariant subspace with dimensionrinvr\_\{\\mathrm\{inv\}\}\. Assumef⋆∈L2​\(𝒳\)∩L∞​\(𝒳\)f^\{\\star\}\\in L^\{2\}\(\\mathcal\{X\}\)\\cap L^\{\\infty\}\(\\mathcal\{X\}\)\. Letx1,…,xn∼μx\_\{1\},\\dots,x\_\{n\}\\sim\\mube i\.i\.d\., and letS=\{g1,…,g\|S\|\}S=\\\{g\_\{1\},\\dots,g\_\{\|S\|\}\\\}be i\.i\.d\. uniform samples fromGG\. Letf^S\\widehat\{f\}\_\{S\}be the projection estimator obtained by augmenting each samplexix\_\{i\}by\{g​xi:g∈S\}\\\{gx\_\{i\}:g\\in S\\\}\. Then, the expected*excess*L2​\(𝒳\)L^\{2\}\(\\mathcal\{X\}\)error overℱG\\mathcal\{F\}^\{G\}satisfies

𝔼​\[‖f^S−ΠℱG​f⋆‖L2​\(𝒳\)2\]≤C​\(‖f⋆‖∞n​rinv\+rn​\|S\|\),\\mathbb\{E\}\\big\[\\\|\\widehat\{f\}\_\{S\}\-\\Pi\_\{\\mathcal\{F\}^\{G\}\}f^\{\\star\}\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}\\big\]\\leq C\\left\(\\frac\{\\\|f^\{\\star\}\\\|\_\{\\infty\}\}\{n\}\\,r\_\{\\mathrm\{inv\}\}\+\\frac\{r\}\{n\|S\|\}\\right\),for some absolute constantC\>0C\>0\. The same holds for projection regression estimators, with‖f⋆‖∞​rinv/n\\\|f^\{\\star\}\\\|\_\{\\infty\}r\_\{\\mathrm\{inv\}\}/nreplaced by\(‖f⋆‖∞2\+σ2\)​rinv/n\(\\\|f^\{\\star\}\\\|\_\{\\infty\}^\{2\}\+\\sigma^\{2\}\)r\_\{\\mathrm\{inv\}\}/n\. Moreover, this upper bound is tight up to absolute constants\.

The bound in Theorem[4\.1](https://arxiv.org/html/2606.24418#S4.Thmtheorem1)decomposes the excess risk into two terms with clear interpretations\. The first term,rinv/nr\_\{\\mathrm\{inv\}\}/n, corresponds to the estimation error within the invariant subspaceℱG\\mathcal\{F\}^\{G\}and matches the minimax\-optimal rate achieved by full data augmentation\. The second term,r/\(n​\|S\|\)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\|S\|\\gtrsim r/r\_\{\\mathrm\{inv\}\}, 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 groupGG, 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](https://arxiv.org/html/2606.24418#S4.Thmtheorem1)control the performance of partial data augmentation for a fixed estimator, in expectation over the random choice of the augmentation setSS\. 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 ofSS?*

Our next result answers this question in the affirmative\. It shows that a single randomly chosen augmentation setSSsuffices 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](https://arxiv.org/html/2606.24418#A1.Thmtheorem2): uniform partial data augmentation\)\.

With high probability over the choice of a random augmentation setS⊆GS\\subseteq Gof size\|S\|\|S\|, partial data augmentation usingSSprovides a uniform approximation to full data augmentation over the entire hypothesis spaceℱ\\mathcal\{F\}\. Specifically, for all functionsf∈ℱf\\in\\mathcal\{F\}with boundedL2​\(𝒳\)L^\{2\}\(\\mathcal\{X\}\)norm, the output obtained by averagingffusingSSis close to the output obtained by averaging using the full groupGG, with approximation error on the order oflog⁡\(min⁡\{r,\|G\|\}\)\|S\|\\displaystyle\\sqrt\{\\frac\{\\log\(\\min\\\{r,\|G\|\\\}\)\}\{\|S\|\}\}, wherer=dim\(ℱ\)r=\\dim\(\\mathcal\{F\}\)\. As a consequence, a single randomly chosen augmentation setSScan be reused across all learning algorithms whose outputs lie inℱ\\mathcal\{F\}, incurring only a vanishing worst\-case error as\|S\|\|S\|grows\.

Theorem[4\.2](https://arxiv.org/html/2606.24418#S4.Thmtheorem2)shows that partial data augmentation can be made*reusable*: once a random subsetSSof group elements is sampled, it can be applied across all predictors inℱ\\mathcal\{F\}without sacrificing statistical guarantees\. Compared to the expectation\-based bounds of Theorem[4\.1](https://arxiv.org/html/2606.24418#S4.Thmtheorem1), the price of uniformity is only alog⁡\(min⁡\{r,\|G\|\}\)\\log\(\\min\\\{r,\|G\|\\\}\)factor\.

In particular, if\|S\|\|S\|grows slightly faster thanlog\(min\{r,\|G\|\}\\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](https://arxiv.org/html/2606.24418#S4.Thmtheorem2):

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ℱ\\mathcal\{F\}\. Full augmentation removes all nontrivial modes, while partial augmentation only approximately cancels them\. For a random subsetSS, each mode is controlled by a large\-deviation bound, and a union bound over the relevant modes gives the logarithmic factorlog⁡\(min⁡\{r,\|G\|\}\)\\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 augmentation 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 setSScan 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ℱ⊂L2​\(𝒳,μ\)\\mathcal\{F\}\\subset L^\{2\}\(\\mathcal\{X\},\\mu\)be a finite\-dimensional space of dimensionrr, closed under the action of a groupGG, and letℱG\\mathcal\{F\}^\{G\}denote its invariant subspace with dimensionrinvr\_\{\\mathrm\{inv\}\}\. Assumef⋆∈L2​\(𝒳\)∩L∞​\(μ\)f^\{\\star\}\\in L^\{2\}\(\\mathcal\{X\}\)\\cap L^\{\\infty\}\(\\mu\)\. Letx1,…,xn∼μx\_\{1\},\\dots,x\_\{n\}\\sim\\mube i\.i\.d\., and letS=\{g1,…,g\|S\|\}S=\\\{g\_\{1\},\\dots,g\_\{\|S\|\}\\\}be i\.i\.d\. uniform samples fromGG\. Letf^S\\widehat\{f\}\_\{S\}denote the projection estimator obtained via*partial data augmentation*usingSS\.

Then, for anyδ∈\(0,1\)\\delta\\in\(0,1\), with probability at least1−δ1\-\\deltaover the draw ofSS, the following bound holds simultaneously for allf⋆∈ℱGf^\{\\star\}\\in\\mathcal\{F\}^\{G\}with‖f⋆‖∞≤B\\\|f^\{\\star\}\\\|\_\{\\infty\}\\leq B:

𝔼\[∥f^S−ΠℱGf⋆∥L2​\(𝒳\)2\|S\]≤C\(rinvn\+r​log⁡\(min⁡\{r,\|G\|\}/δ\)n​\|S\|\),\\mathbb\{E\}\\\!\\left\[\\big\\\|\\widehat\{f\}\_\{S\}\-\\Pi\_\{\\mathcal\{F\}^\{G\}\}f^\{\\star\}\\big\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}\\;\\middle\|\\;S\\right\]\\leq C\\left\(\\frac\{r\_\{\\mathrm\{inv\}\}\}\{n\}\+\\frac\{r\\log\\\!\\big\(\\min\\\{r,\|G\|\\\}/\\delta\\big\)\}\{n\|S\|\}\\right\),whereC\>0C\>0depends only onBB\. The same bound holds for projection regression estimators under additive zero\-mean noise with varianceσ2\\sigma^\{2\}, withCCalso depending onσ2\\sigma^\{2\}\.

Theorem[4\.3](https://arxiv.org/html/2606.24418#S4.Thmtheorem3)refines Theorem[4\.1](https://arxiv.org/html/2606.24418#S4.Thmtheorem1)by providing a high\-probability, reusable guarantee for partial data augmentation\. In particular, the augmentation setSSis reusable: on the same high\-probability event, the bound holds uniformly even iff⋆∈ℱGf^\{\\star\}\\in\\mathcal\{F\}^\{G\}is chosen adversarially after observingSS\. Compared to the expectation\-based bound, the only additional cost is alog⁡\(min⁡\{r,\|G\|\}\)\\log\(\\min\\\{r,\|G\|\\\}\)factor, which arises from enforcing uniform control over the entire function spaceℱ\\mathcal\{F\}\. Importantly, this logarithmic dependence remains mild even when the groupGGis 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\.

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](https://arxiv.org/html/2606.24418#A4.Thmtheorem1): exact invariance requires full augmentation\)\.

For finite groups, partial data augmentation cannot enforce*exact*GG\-invariance unless the full group is used\. More precisely, if a learning procedure based on averaging over a subsetS⊆GS\\subseteq Gproduces outputs that are exactly invariant under all elements ofGG, and if the hypothesis space is rich enough to represent all irreducible symmetry modes ofGG, thenSSmust 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\.

Theorem[4\.5](https://arxiv.org/html/2606.24418#S4.Thmtheorem5)establishes a sharp separation between approximate and exact symmetry enforcement via data augmentation\. In contrast to the statistical guarantees obtained with partial augmentation, exactGG\-invariance requires full group\-sized augmentation whenever the hypothesis space is sufficiently expressive\.

\|S\|\|S\|Excess riskr/n\\scriptstyle r/nrinv/n\\ \\scriptstyle r\_\{\\mathrm\{inv\}\}/n1\\scriptstyle 1r/rinv\\scriptstyle r/r\_\{\\mathrm\{inv\}\}r​log⁡D/rinv\\scriptstyle r\\log D/r\_\{\\mathrm\{inv\}\}D\+1\\scriptstyle D\+1Phase I:StatisticalinterpolationPhase II:StatisticaloptimalityPhase III:UniformreusabilityPhase IV:Exact invarianceFigure 1:Phase diagram for partial augmentation\. The risk decreases from the ordinary rater/nr/nto the invariant raterinv/nr\_\{\\mathrm\{inv\}\}/n, and saturates once\|S\|≍r/rinv\|S\|\\asymp r/r\_\{\\mathrm\{inv\}\}\. Larger augmentation sets may still be required for stronger guarantees, such as uniform reusability and exact invariance\.

## 5Interpreting 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 setSS, 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 withr=dim\(ℱ\)r=\\dim\(\\mathcal\{F\}\)andrinv=dim\(ℱG\)r\_\{\\mathrm\{inv\}\}=\\dim\(\\mathcal\{F\}^\{G\}\)\. Without augmentation, the estimation error scales asr/nr/n\. Full augmentation reduces the effective dimension torinvr\_\{\\mathrm\{inv\}\}, yielding the invariant raterinv/nr\_\{\\mathrm\{inv\}\}/n\. Partial augmentation interpolates between these two rates\. Indeed, the augmentation error is controlled byrn​\|S\|,\\frac\{r\}\{n\|S\|\},so the total error behaves asrinvn\+rn​\|S\|\.\\frac\{r\_\{\\mathrm\{inv\}\}\}\{n\}\+\\frac\{r\}\{n\|S\|\}\.Thus, when\|S\|\|S\|is small, partial augmentation only partially suppresses the non\-invariant directions, and the risk lies between the ordinary rater/nr/nand the invariant raterinv/nr\_\{\\mathrm\{inv\}\}/n\. The first critical threshold is therefore

\|S\|stat≍rrinv\.\|S\|\_\{\\mathrm\{stat\}\}\\asymp\\frac\{r\}\{r\_\{\\mathrm\{inv\}\}\}\.Once\|S\|≳r/rinv\|S\|\\gtrsim r/r\_\{\\mathrm\{inv\}\}, 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/rinvr/r\_\{\\mathrm\{inv\}\}marks the statistical phase transition, beyond which increasing\|S\|\|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 setSSto work uniformly over all functions inℱ\\mathcal\{F\}\. This requires high\-probability control of the operator norm‖ΠS−ΠG‖op\\\|\\Pi\_\{S\}\-\\Pi\_\{G\}\\\|\_\{\\mathrm\{op\}\}\. Our uniform bound shows that this incurs only a logarithmic overhead:

‖ΠS−ΠG‖op2≲log⁡N\|S\|,N:=min⁡\{r,\|G\|\}\.\\\|\\Pi\_\{S\}\-\\Pi\_\{G\}\\\|\_\{\\mathrm\{op\}\}^\{2\}\\lesssim\\frac\{\\log N\}\{\|S\|\},\\qquad N:=\\min\\\{r,\|G\|\\\}\.More sharply,NNmay be replaced by a representation\-theoretic Fourier complexity

D:=∑λ∈Λdλ2≤min\{r,\|G\|−1\},D:=\\sum\_\{\\lambda\\in\\Lambda\}d\_\{\\lambda\}^\{2\}\\leq\\min\\\{r,\|G\|\-1\\\},whereΛ\\Lambdadenotes the set of nontrivial irreducible representations ofGGthat appear inℱ\\mathcal\{F\}, anddλd\_\{\\lambda\}is the dimension of the irrepλ\\lambda\. For background on group representations, see Appendix[A\.5](https://arxiv.org/html/2606.24418#A1.SS5)\.

Consequently, the reusable\-uniform regime begins once

\|S\|≳rrinv​log⁡\(min⁡\{N,D\}\),\|S\|\\gtrsim\\frac\{r\}\{r\_\{\\mathrm\{inv\}\}\}\\log\(\\min\\\{N,D\\\}\),Equivalently, the transition size satisfies the upper bound

\|S\|unif≲rrinv​log⁡\(min⁡\{N,D\}\)\.\|S\|\_\{\\mathrm\{unif\}\}\\lesssim\\frac\{r\}\{r\_\{\\mathrm\{inv\}\}\}\\log\(\\min\\\{N,D\\\}\)\.
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\\Pi\_\{S\}to approximateΠG\\Pi\_\{G\}, whereas exact invariance requires equality of averaging operators:

ΠS=ΠGon​ℱ\.\\Pi\_\{S\}=\\Pi\_\{G\}\\qquad\\text\{on \}\\mathcal\{F\}\.This can forceS=GS=Gwhenℱ\\mathcal\{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 ofGGonℱ\\mathcal\{F\}decompose as

ℱℂ≅ℱℂG⊕⨁λ∈Λℂmλ⊗Vλ,\\mathcal\{F\}\_\{\\mathbb\{C\}\}\\cong\\mathcal\{F\}^\{G\}\_\{\\mathbb\{C\}\}\\oplus\\bigoplus\_\{\\lambda\\in\\Lambda\}\\mathbb\{C\}^\{m\_\{\\lambda\}\}\\otimes V\_\{\\lambda\},whereΛ\\Lambdacontains only the nontrivial irreducible representations appearing inℱ\\mathcal\{F\}\. A weighted augmentation rule

ν=∑s∈Sws​δs,ws≥0,∑s∈Sws=1,\\nu=\\sum\_\{s\\in S\}w\_\{s\}\\delta\_\{s\},\\qquad w\_\{s\}\\geq 0,\\qquad\\sum\_\{s\\in S\}w\_\{s\}=1,satisfiesΠν=ΠG\\Pi\_\{\\nu\}=\\Pi\_\{G\}onℱ\\mathcal\{F\}if and only if

∑s∈Sws​ρλ​\(s\)=0for every​λ∈Λ\.\\sum\_\{s\\in S\}w\_\{s\}\\rho\_\{\\lambda\}\(s\)=0\\qquad\\text\{for every \}\\lambda\\in\\Lambda\.Equivalently, the origin must be written as a convex combination of the Fourier feature vectors

g⟼\(ρλ​\(g\)\)λ∈Λ\.g\\longmapsto\\big\(\\rho\_\{\\lambda\}\(g\)\\big\)\_\{\\lambda\\in\\Lambda\}\.These vectors lie in a real vector space of dimension at mostD=∑λ∈Λdλ2,D=\\sum\_\{\\lambda\\in\\Lambda\}d\_\{\\lambda\}^\{2\},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\.\|S\|\_\{\\mathrm\{exact\}\}\\leq 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\|\|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\.\|S\|\_\{\\mathrm\{stat\}\}\\;\\lesssim\\;\|S\|\_\{\\mathrm\{unif\}\}\\;\\lesssim\\;\|S\|\_\{\\mathrm\{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:

𝔼​‖f^S−ΠℱG​f⋆‖L2​\(𝒳\)2≍rinvn\.\\mathbb\{E\}\\\|\\widehat\{f\}\_\{S\}\-\\Pi\_\{\\mathcal\{F\}^\{G\}\}f^\{\\star\}\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}\\asymp\\frac\{r\_\{\\mathrm\{inv\}\}\}\{n\}\.The later thresholds provide stronger guarantees, but they do not improve the statistical rate\.

### 5\.1Extension 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\(X,Y\)\\sim P, whereY∈\{±1\}Y\\in\\\{\\pm 1\\\}, and the optimal prediction rule is the Bayes classifier induced by the regression function

f⋆​\(x\):=𝔼​\[Y∣X=x\]\.f^\{\\star\}\(x\):=\\mathbb\{E\}\[Y\\mid X=x\]\.The Bayes classifier is

y⋆​\(x\):=sign⁡\(f⋆​\(x\)\)\.y^\{\\star\}\(x\):=\\operatorname\{sign\}\(f^\{\\star\}\(x\)\)\.Given an estimatorf^\\widehat\{f\}off⋆f^\{\\star\}, we form the plug\-in classifier

y^​\(x\):=sign⁡\(f^​\(x\)\)∈\{±1\}\.\\widehat\{y\}\(x\):=\\operatorname\{sign\}\(\\widehat\{f\}\(x\)\)\\in\\\{\\pm 1\\\}\.Then the excess classification risk is controlled by the regression error:

ℙ​\(y^​\(X\)≠Y\)−ℙ​\(y⋆​\(X\)≠Y\)≤𝔼X​\[\|f^​\(X\)−f⋆​\(X\)\|\]≤‖f^−f⋆‖L2​\(𝒳\)\.\\mathbb\{P\}\(\\widehat\{y\}\(X\)\\neq Y\)\-\\mathbb\{P\}\(y^\{\\star\}\(X\)\\neq Y\)\\leq\\mathbb\{E\}\_\{X\}\\big\[\|\\widehat\{f\}\(X\)\-f^\{\\star\}\(X\)\|\\big\]\\leq\\\|\\widehat\{f\}\-f^\{\\star\}\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}\.Indeed, the excess risk can be written as

𝔼X​\[\|f⋆​\(X\)\|​𝟏​\{y^​\(X\)≠y⋆​\(X\)\}\]\.\\mathbb\{E\}\_\{X\}\\Big\[\|f^\{\\star\}\(X\)\|\\mathbf\{1\}\\\{\\widehat\{y\}\(X\)\\neq y^\{\\star\}\(X\)\\\}\\Big\]\.On the eventy^​\(X\)≠y⋆​\(X\)\\widehat\{y\}\(X\)\\neq y^\{\\star\}\(X\), the signs off^​\(X\)\\widehat\{f\}\(X\)andf⋆​\(X\)f^\{\\star\}\(X\)disagree, and hence

\|f⋆​\(X\)\|≤\|f^​\(X\)−f⋆​\(X\)\|\.\|f^\{\\star\}\(X\)\|\\leq\|\\widehat\{f\}\(X\)\-f^\{\\star\}\(X\)\|\.Thus, the claimed bound follows\. Consequently, the regression guarantees in this paper directly imply classification guarantees for the corresponding plug\-in classifiers\. For example, iff^S\\widehat\{f\}\_\{S\}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

𝔼​\[‖f^S−f⋆‖L2​\(𝒳\)2\]≲rinvn\+rn​\|S\|\\mathbb\{E\}\\big\[\\\|\\widehat\{f\}\_\{S\}\-f^\{\\star\}\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}\\big\]\\lesssim\\frac\{r\_\{\\mathrm\{inv\}\}\}\{n\}\+\\frac\{r\}\{n\|S\|\}which implies

𝔼​\[ℙ​\(y^S​\(X\)≠Y\)−ℙ​\(y⋆​\(X\)≠Y\)\]≲\(rinvn\+rn​\|S\|\)1/2\.\\mathbb\{E\}\\Big\[\\mathbb\{P\}\(\\widehat\{y\}\_\{S\}\(X\)\\neq Y\)\-\\mathbb\{P\}\(y^\{\\star\}\(X\)\\neq Y\)\\Big\]\\lesssim\\left\(\\frac\{r\_\{\\mathrm\{inv\}\}\}\{n\}\+\\frac\{r\}\{n\|S\|\}\\right\)^\{1/2\}\.Thus, the same augmentation regimes appear in binary classification: partial augmentation interpolates between the ordinary and invariant rates, and once\|S\|≳r/rinv\|S\|\\gtrsim r/r\_\{\\mathrm\{inv\}\}, 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 setSScan be reused across classifiers whose underlying regression estimates lie inℱ\\mathcal\{F\}\.

## 6Projection Estimators on the Sphere

We briefly specialize our framework to the unit sphere𝕊d−1\\mathbb\{S\}^\{d\-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 groupG⊆O​\(d\)G\\subseteq\\mathrm\{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](https://arxiv.org/html/2606.24418#A1.SS1),[A\.2](https://arxiv.org/html/2606.24418#A1.SS2), and[A\.7](https://arxiv.org/html/2606.24418#A1.SS7)\.

Let𝒳=𝕊d−1\\mathcal\{X\}=\\mathbb\{S\}^\{d\-1\}withμ\\muthe uniform probability measure\. For each degreeℓ≥0\\ell\\geq 0, letℋℓ\\mathcal\{H\}\_\{\\ell\}denote the space of spherical harmonics of degreeℓ\\ell, with dimensionNℓN\_\{\\ell\}\. For a cutoffk≥0k\\geq 0, define the truncated spaceℱ:=⨁ℓ=0kℋℓ\\mathcal\{F\}:=\\bigoplus\_\{\\ell=0\}^\{k\}\\mathcal\{H\}\_\{\\ell\}withr:=dim\(ℱ\)=∑ℓ=0kNℓr:=\\dim\(\\mathcal\{F\}\)=\\sum\_\{\\ell=0\}^\{k\}N\_\{\\ell\}, and letΠ≤k\\Pi\_\{\\leq k\}denote theL2​\(μ\)L^\{2\}\(\\mu\)\-orthogonal projection ontoℱ\\mathcal\{F\}\. Eachℋℓ\\mathcal\{H\}\_\{\\ell\}is invariant underO​\(d\)\\mathrm\{O\}\(d\), and henceℱ\\mathcal\{F\}is closed under the action of any subgroupG⊆O​\(d\)G\\subseteq\\mathrm\{O\}\(d\), with invariant subspaceℱG\\mathcal\{F\}^\{G\}of dimensionrinvr\_\{\\mathrm\{inv\}\}\.

Projection estimators for density estimation and regression on𝕊d−1\\mathbb\{S\}^\{d\-1\}admit kernel representations\. Define the degree\-ℓ\\ellzonal kernelZℓ​\(x,x′\):=∑j=1Nℓϕℓ,j​\(x\)​ϕℓ,j​\(x′\),Z\_\{\\ell\}\(x,x^\{\\prime\}\):=\\sum\_\{j=1\}^\{N\_\{\\ell\}\}\\phi\_\{\\ell,j\}\(x\)\\phi\_\{\\ell,j\}\(x^\{\\prime\}\),and the truncated kernelΠ≤k​\(x,x′\):=∑ℓ=0kZℓ​\(x,x′\)\.\\Pi\_\{\\leq k\}\(x,x^\{\\prime\}\):=\\sum\_\{\\ell=0\}^\{k\}Z\_\{\\ell\}\(x,x^\{\\prime\}\)\.By the addition theorem for spherical harmonics,Zℓ​\(x,x′\)Z\_\{\\ell\}\(x,x^\{\\prime\}\)depends only on⟨x,x′⟩\\langle x,x^\{\\prime\}\\rangleand has a closed\-form expression in terms of Gegenbauer polynomials\. Consequently,Π≤k\\Pi\_\{\\leq k\}can be evaluated using only inner products, with computational costO​\(k\)O\(k\)per evaluation via standard three\-term recurrences\.

As a result, projection estimators take the form

f^​\(x\)=1n​∑i=1nΠ≤k​\(x,xi\)\(density estimation\),f^​\(x\)=1n​∑i=1nyi​Π≤k​\(x,xi\)\(regression\)\.\\widehat\{f\}\(x\)=\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\\Pi\_\{\\leq k\}\(x,x\_\{i\}\)\\quad\\text\{\(density estimation\)\},\\quad\\widehat\{f\}\(x\)=\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}y\_\{i\}\\,\\Pi\_\{\\leq k\}\(x,x\_\{i\}\)\\quad\\text\{\(regression\)\}\.
For large or continuous groupsG⊆O​\(d\)G\\subseteq\\mathrm\{O\}\(d\), full data augmentation, averaging over all group elements, is computationally infeasible\. In contrast, partial data augmentation using a small random subsetS⊆GS\\subseteq Gis 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 byrinvr\_\{\\mathrm\{inv\}\}rather than the size ofGG\.

## 7Conclusion

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íazet al\.,[2025](https://arxiv.org/html/2606.24418#bib.bib54)\)\.

## 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

- N\. Alon and S\. Lovett \(2013\)Almostkk\-wise vs\.kk\-wise independent permutations, and uniformity for general group actions\.Theory of Computing9\(15\),pp\. 559–577\.Cited by:[Remark 4\.4](https://arxiv.org/html/2606.24418#S4.Thmtheorem4.p1.3)\.
- N\. Alon and Y\. Roichman \(1994\)Random cayley graphs and expanders\.Random Structures & Algorithms5\(2\),pp\. 271–284\.Cited by:[Remark 4\.4](https://arxiv.org/html/2606.24418#S4.Thmtheorem4.p1.3)\.
- S\. Batzner, A\. Musaelian, and B\. Kozinsky \(2023\)Advancing molecular simulation with equivariant interatomic potentials\.Nature Reviews Physics5\(8\),pp\. 437–438\.Cited by:[§2](https://arxiv.org/html/2606.24418#S2.SS0.SSS0.Px1.p1.1)\.
- S\. Batzner, A\. Musaelian, L\. Sun, M\. Geiger, J\. P\. Mailoa, M\. Kornbluth, N\. Molinari, T\. E\. Smidt, and B\. Kozinsky \(2022\)E\(3\)\-equivariant graph neural networks for data\-efficient and accurate interatomic potentials\.Nature communications13\(1\),pp\. 2453\.Cited by:[§2](https://arxiv.org/html/2606.24418#S2.SS0.SSS0.Px1.p1.1)\.
- A\. Bietti, L\. Venturi, and J\. Bruna \(2021\)On the sample complexity of learning under geometric stability\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Cited by:[§2](https://arxiv.org/html/2606.24418#S2.SS0.SSS0.Px1.p1.1)\.
- J\. Bourgain and A\. Gamburd \(2008\)Uniform expansion bounds for cayley graphs ofSL2​\(𝔽p\)\\mathrm\{SL\}\_\{2\}\(\\mathbb\{F\}\_\{p\}\)\.Annals of Mathematics,pp\. 625–642\.Cited by:[Remark 4\.4](https://arxiv.org/html/2606.24418#S4.Thmtheorem4.p1.3)\.
- M\. M\. Bronstein, J\. Bruna, Y\. LeCun, A\. Szlam, and P\. Vandergheynst \(2017\)Geometric deep learning: going beyond euclidean data\.IEEE Signal Processing Magazine34\(4\),pp\. 18–42\.Cited by:[§2](https://arxiv.org/html/2606.24418#S2.SS0.SSS0.Px1.p1.1)\.
- S\. Chen, E\. Dobriban, and J\. H\. Lee \(2020\)A group\-theoretic framework for data augmentation\.Journal of Machine Learning Research21\(245\),pp\. 1–71\.Cited by:[§2](https://arxiv.org/html/2606.24418#S2.SS0.SSS0.Px3.p1.1)\.
- Y\. Chen, Z\. Yan, and Y\. Zhu \(2024\)A comprehensive survey for generative data augmentation\.Neurocomputing600,pp\. 128167\.Cited by:[§2](https://arxiv.org/html/2606.24418#S2.SS0.SSS0.Px4.p1.1)\.
- F\. Dai \(2013\)Approximation theory and harmonic analysis on spheres and balls\.Springer\.Cited by:[§A\.1](https://arxiv.org/html/2606.24418#A1.SS1.p1.7),[§A\.7](https://arxiv.org/html/2606.24418#A1.SS7.SSS0.Px4.p1.3)\.
- T\. Dao, A\. Gu, A\. Ratner, V\. Smith, C\. De Sa, and C\. Ré \(2019\)A kernel theory of modern data augmentation\.InInt\. Conference on Machine Learning \(ICML\),Cited by:[§2](https://arxiv.org/html/2606.24418#S2.SS0.SSS0.Px3.p1.1)\.
- N\. Dehmamy, R\. Walters, Y\. Liu, D\. Wang, and R\. Yu \(2021\)Automatic symmetry discovery with lie algebra convolutional network\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Cited by:[§2](https://arxiv.org/html/2606.24418#S2.SS0.SSS0.Px1.p1.1),[§2](https://arxiv.org/html/2606.24418#S2.SS0.SSS0.Px4.p1.1)\.
- K\. Desai, B\. Nachman, and J\. Thaler \(2022\)Symmetry discovery with deep learning\.Physical Review D105\(9\),pp\. 096031\.Cited by:[§2](https://arxiv.org/html/2606.24418#S2.SS0.SSS0.Px4.p1.1)\.
- M\. Díaz, D\. Drusvyatskiy, J\. Kendrick, and R\. R\. Thomas \(2025\)Invariant kernels: rank stabilization and generalization across dimensions\.arXiv preprint arXiv:2502\.01886\.Cited by:[§1\.1](https://arxiv.org/html/2606.24418#S1.SS1.SSS0.Px1.p1.4),[§2](https://arxiv.org/html/2606.24418#S2.SS0.SSS0.Px5.p1.1),[§7](https://arxiv.org/html/2606.24418#S7.p3.1)\.
- Y\. Dong, Y\. Xie, and R\. Ward \(2023\)Adaptively weighted data augmentation consistency regularization for robust optimization under concept shift\.InInt\. Conference on Machine Learning \(ICML\),Cited by:[§2](https://arxiv.org/html/2606.24418#S2.SS0.SSS0.Px4.p1.1)\.
- N\. Dym, H\. Lawrence, and J\. W\. Siegel \(2024\)Equivariant frames and the impossibility of continuous canonicalization\.InInt\. Conference on Machine Learning \(ICML\),Cited by:[§2](https://arxiv.org/html/2606.24418#S2.SS0.SSS0.Px2.p1.1)\.
- M\. Finzi, G\. Benton, and A\. G\. Wilson \(2021\)Residual pathway priors for soft equivariance constraints\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Cited by:[§2](https://arxiv.org/html/2606.24418#S2.SS0.SSS0.Px4.p1.1)\.
- D\. Huh \(2025\)Discovering group structures via unitary representation learning\.InInt\. Conference on Learning Representations \(ICLR\),Cited by:[§2](https://arxiv.org/html/2606.24418#S2.SS0.SSS0.Px4.p1.1)\.
- S\. Kaba, A\. K\. Mondal, Y\. Zhang, Y\. Bengio, and S\. Ravanbakhsh \(2023\)Equivariance with learned canonicalization functions\.InInt\. Conference on Machine Learning \(ICML\),Cited by:[§2](https://arxiv.org/html/2606.24418#S2.SS0.SSS0.Px2.p1.1)\.
- B\. Kiani, T\. Le, H\. Lawrence, S\. Jegelka, and M\. Weber \(2024\)On the hardness of learning under symmetries\.InInternational Conference on Learning Representations,Vol\.2024,pp\. 25956–26003\.Cited by:[§2](https://arxiv.org/html/2606.24418#S2.SS0.SSS0.Px1.p1.1)\.
- H\. Kim, H\. Lee, H\. Yang, and J\. Lee \(2023\)Regularizing towards soft equivariance under mixed symmetries\.InInt\. Conference on Machine Learning \(ICML\),Cited by:[§2](https://arxiv.org/html/2606.24418#S2.SS0.SSS0.Px4.p1.1)\.
- P\. Kirichenko, M\. Ibrahim, R\. Balestriero, D\. Bouchacourt, S\. R\. Vedantam, H\. Firooz, and A\. G\. Wilson \(2023\)Understanding the detrimental class\-level effects of data augmentation\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Cited by:[§2](https://arxiv.org/html/2606.24418#S2.SS0.SSS0.Px4.p1.1)\.
- B\. Li, Y\. Hou, and W\. Che \(2022\)Data augmentation approaches in natural language processing: a survey\.Ai Open3,pp\. 71–90\.Cited by:[§2](https://arxiv.org/html/2606.24418#S2.SS0.SSS0.Px4.p1.1)\.
- C\. Lin, C\. Kaushik, E\. L\. Dyer, and V\. Muthukumar \(2024\)The good, the bad and the ugly sides of data augmentation: an implicit spectral regularization perspective\.Journal of Machine Learning Research25\(91\),pp\. 1–85\.Cited by:[§2](https://arxiv.org/html/2606.24418#S2.SS0.SSS0.Px3.p1.1)\.
- G\. Ma, Y\. Wang, D\. Lim, S\. Jegelka, and Y\. Wang \(2024\)A canonicalization perspective on invariant and equivariant learning\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Cited by:[§2](https://arxiv.org/html/2606.24418#S2.SS0.SSS0.Px2.p1.1)\.
- G\. Ma, Z\. Wang, Z\. Yuan, X\. Wang, B\. Yuan, and D\. Tao \(2025\)A comprehensive survey of data augmentation in visual reinforcement learning\.International Journal of Computer Vision,pp\. 1–38\.Cited by:[§2](https://arxiv.org/html/2606.24418#S2.SS0.SSS0.Px4.p1.1)\.
- S\. Mei, T\. Misiakiewicz, and A\. Montanari \(2021\)Learning with invariances in random features and kernel models\.InConference on Learning Theory \(COLT\),Cited by:[§2](https://arxiv.org/html/2606.24418#S2.SS0.SSS0.Px1.p1.1),[§2](https://arxiv.org/html/2606.24418#S2.SS0.SSS0.Px3.p1.1)\.
- A\. Mikołajczyk and M\. Grochowski \(2018\)Data augmentation for improving deep learning in image classification problem\.In2018 international interdisciplinary PhD workshop \(IIPhDW\),pp\. 117–122\.Cited by:[§2](https://arxiv.org/html/2606.24418#S2.SS0.SSS0.Px4.p1.1)\.
- A\. Mumuni and F\. Mumuni \(2022\)Data augmentation: a comprehensive survey of modern approaches\.Array16,pp\. 100258\.Cited by:[§2](https://arxiv.org/html/2606.24418#S2.SS0.SSS0.Px4.p1.1)\.
- M\. Pacini, M\. Petrache, B\. Lepri, S\. Trivedi, and R\. Walters \(2025\)On universality of deep equivariant networks\.arXiv preprint arXiv:2510\.15814\.Cited by:[§2](https://arxiv.org/html/2606.24418#S2.SS0.SSS0.Px1.p1.1)\.
- J\. Y\. Park, S\. Bhatt, S\. Zeng, L\. L\.S\. Wong, A\. Koppel, S\. Ganesh, and R\. Walters \(2025\)Approximate equivariance in reinforcement learning\.InInt\. Conference on Artificial Intelligence and Statistics \(AISTATS\),Cited by:[§2](https://arxiv.org/html/2606.24418#S2.SS0.SSS0.Px4.p1.1)\.
- P\. Patil and J\. Du \(2023\)Generalized equivalences between subsampling and ridge regularization\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Cited by:[§2](https://arxiv.org/html/2606.24418#S2.SS0.SSS0.Px3.p1.1)\.
- L\. F\. A\. O\. Pellicer, T\. M\. Ferreira, and A\. H\. R\. Costa \(2023\)Data augmentation techniques in natural language processing\.Applied Soft Computing132,pp\. 109803\.Cited by:[§2](https://arxiv.org/html/2606.24418#S2.SS0.SSS0.Px4.p1.1)\.
- M\. Petrache and S\. Trivedi \(2023\)Approximation\-generalization trade\-offs under \(approximate\) group equivariance\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Cited by:[§2](https://arxiv.org/html/2606.24418#S2.SS0.SSS0.Px1.p1.1)\.
- O\. Puny, M\. Atzmon, H\. Ben\-Hamu, I\. Misra, A\. Grover, E\. J\. Smith, and Y\. Lipman \(2022\)Frame averaging for invariant and equivariant network design\.InInt\. Conference on Learning Representations \(ICLR\),Cited by:[§2](https://arxiv.org/html/2606.24418#S2.SS0.SSS0.Px2.p1.1)\.
- D\. W\. Romero and S\. Lohit \(2022\)Learning partial equivariances from data\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Cited by:[§2](https://arxiv.org/html/2606.24418#S2.SS0.SSS0.Px4.p1.1)\.
- B\. Shaw, A\. Magner, and K\. Moon \(2024\)Symmetry discovery beyond affine transformations\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Cited by:[§2](https://arxiv.org/html/2606.24418#S2.SS0.SSS0.Px4.p1.1)\.
- R\. Shen, S\. Bubeck, and S\. Gunasekar \(2022\)Data augmentation as feature manipulation\.InInt\. Conference on Machine Learning \(ICML\),Cited by:[§2](https://arxiv.org/html/2606.24418#S2.SS0.SSS0.Px3.p1.1)\.
- C\. Shorten and T\. M\. Khoshgoftaar \(2019\)A survey on image data augmentation for deep learning\.Journal of big data6\(1\),pp\. 1–48\.Cited by:[§2](https://arxiv.org/html/2606.24418#S2.SS0.SSS0.Px4.p1.1)\.
- Z\. Shumaylov, P\. Zaika, J\. Rowbottom, F\. Sherry, M\. Weber, and C\. Schönlieb \(2025\)Lie algebra canonicalization: equivariant neural operators under arbitrary lie groups\.InInt\. Conference on Learning Representations \(ICLR\),Cited by:[§2](https://arxiv.org/html/2606.24418#S2.SS0.SSS0.Px2.p1.1)\.
- T\. E\. Smidt \(2021\)Euclidean symmetry and equivariance in machine learning\.Trends in Chemistry3\(2\),pp\. 82–85\.Cited by:[§2](https://arxiv.org/html/2606.24418#S2.SS0.SSS0.Px1.p1.1)\.
- A\. Soleymani, B\. Tahmasebi, P\. Jaillet, and S\. Jegelka \(2025a\)From finite to infinite groups: a polynomial\-time algorithm for learning with exact invariances\.InNeurIPS 2025 Workshop on Symmetry and Geometry in Neural Representations,Cited by:[§2](https://arxiv.org/html/2606.24418#S2.SS0.SSS0.Px1.p1.1)\.
- A\. Soleymani, B\. Tahmasebi, S\. Jegelka, and P\. Jaillet \(2025b\)A robust kernel statistical test of invariance: detecting subtle asymmetries\.InInt\. Conference on Artificial Intelligence and Statistics \(AISTATS\),Cited by:[§2](https://arxiv.org/html/2606.24418#S2.SS0.SSS0.Px1.p1.1)\.
- A\. Soleymani, B\. Tahmasebi, S\. Jegelka, and P\. Jaillet \(2025c\)Learning with exact invariances in polynomial time\.InInt\. Conference on Machine Learning \(ICML\),Cited by:[§2](https://arxiv.org/html/2606.24418#S2.SS0.SSS0.Px1.p1.1),[Remark 3\.2](https://arxiv.org/html/2606.24418#S3.Thmtheorem2.p1.2),[Remark 4\.6](https://arxiv.org/html/2606.24418#S4.Thmtheorem6.p1.1)\.
- B\. Tahmasebi and S\. Jegelka \(2023\)The exact sample complexity gain from invariances for kernel regression\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Cited by:[§2](https://arxiv.org/html/2606.24418#S2.SS0.SSS0.Px1.p1.1)\.
- B\. Tahmasebi and S\. Jegelka \(2025a\)Generalization bounds for canonicalization: a comparative study with group averaging\.InInt\. Conference on Learning Representations \(ICLR\),Cited by:[§2](https://arxiv.org/html/2606.24418#S2.SS0.SSS0.Px1.p1.1)\.
- B\. Tahmasebi and S\. Jegelka \(2025b\)Regularity in canonicalized models: a theoretical perspective\.InInt\. Conference on Artificial Intelligence and Statistics \(AISTATS\),Cited by:[§2](https://arxiv.org/html/2606.24418#S2.SS0.SSS0.Px1.p1.1)\.
- B\. Tahmasebi and M\. Weber \(2026a\)Achieving approximate symmetry is exponentially easier than exact symmetry\.InInt\. Conference on Learning Representations \(ICLR\),Cited by:[Proposition A\.1](https://arxiv.org/html/2606.24418#A1.Thmtheorem1.p1.5.5),[§2](https://arxiv.org/html/2606.24418#S2.SS0.SSS0.Px1.p1.1)\.
- B\. Tahmasebi and M\. Weber \(2026b\)Adaptive symmetry discovery for dynamical system identification\.InInt\. Conference on Machine Learning \(ICML\),Cited by:[§2](https://arxiv.org/html/2606.24418#S2.SS0.SSS0.Px1.p1.1)\.
- J\. A\. Tropp \(2012\)User\-friendly tail bounds for sums of random matrices\.Foundations of computational mathematics12\(4\),pp\. 389–434\.Cited by:[§A\.9](https://arxiv.org/html/2606.24418#A1.SS9.SSS0.Px4.p2.4)\.
- T\. van der Ouderaa, A\. Immer, and M\. van der Wilk \(2023\)Learning layer\-wise equivariances automatically using gradients\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Cited by:[§2](https://arxiv.org/html/2606.24418#S2.SS0.SSS0.Px4.p1.1)\.
- T\. van der Ouderaa, D\. W\. Romero, and M\. van der Wilk \(2022\)Relaxing equivariance constraints with non\-stationary continuous filters\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Cited by:[§2](https://arxiv.org/html/2606.24418#S2.SS0.SSS0.Px4.p1.1)\.
- R\. Wang, R\. Walters, and R\. Yu \(2022\)Approximately equivariant networks for imperfectly symmetric dynamics\.InInt\. Conference on Machine Learning \(ICML\),Cited by:[§2](https://arxiv.org/html/2606.24418#S2.SS0.SSS0.Px4.p1.1)\.
- M\. Weber \(2025\)Geometric machine learning\.AI Magazine46\(1\),pp\. e12210\.Cited by:[§2](https://arxiv.org/html/2606.24418#S2.SS0.SSS0.Px1.p1.1)\.
- J\. Yang, N\. Dehmamy, R\. Walters, and R\. Yu \(2024\)Latent space symmetry discovery\.InInt\. Conference on Machine Learning \(ICML\),Cited by:[§2](https://arxiv.org/html/2606.24418#S2.SS0.SSS0.Px4.p1.1)\.
- J\. Yang, R\. Walters, N\. Dehmamy, and R\. Yu \(2023a\)Generative adversarial symmetry discovery\.InInt\. Conference on Machine Learning \(ICML\),Cited by:[§2](https://arxiv.org/html/2606.24418#S2.SS0.SSS0.Px4.p1.1)\.
- S\. Yang, Y\. Dong, R\. Ward, I\. S\. Dhillon, S\. Sanghavi, and Q\. Lei \(2023b\)Sample efficiency of data augmentation consistency regularization\.InInt\. Conference on Artificial Intelligence and Statistics \(AISTATS\),Cited by:[§2](https://arxiv.org/html/2606.24418#S2.SS0.SSS0.Px3.p1.1)\.
- X\. Zhang, L\. Wang, J\. Helwig, Y\. Luo, C\. Fu, Y\. Xie, M\. Liu, Y\. Lin, Z\. Xu, K\. Yan,et al\.\(2025\)Artificial intelligence for science in quantum, atomistic, and continuum systems\.Foundations and Trends® in Machine Learning18\(4\),pp\. 385–912\.Cited by:[§2](https://arxiv.org/html/2606.24418#S2.SS0.SSS0.Px1.p1.1)\.
- T\. Zhao, W\. Jin, Y\. Liu, Y\. Wang, G\. Liu, S\. Günnemann, N\. Shah, and M\. Jiang \(2022\)Graph data augmentation for graph machine learning: a survey\.arXiv preprint arXiv:2202\.08871\.Cited by:[§2](https://arxiv.org/html/2606.24418#S2.SS0.SSS0.Px4.p1.1)\.
- C\. Zheng, G\. Wu, and C\. Li \(2023\)Toward understanding generative data augmentation\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Cited by:[§2](https://arxiv.org/html/2606.24418#S2.SS0.SSS0.Px4.p1.1)\.

## Appendix APreliminaries

### A\.1Spherical Harmonics

We briefly review basic facts about spherical harmonics on the unit sphere\(Dai,[2013](https://arxiv.org/html/2606.24418#bib.bib53)\)\. Let

𝕊d−1:=\{x∈ℝd:‖x‖2=1\}\\mathbb\{S\}^\{d\-1\}:=\\left\\\{x\\in\\mathbb\{R\}^\{d\}:\\\|x\\\|\_\{2\}=1\\right\\\}be the unit sphere inℝd\\mathbb\{R\}^\{d\}, equipped with the normalized surface measureμ\\mu, so that∫𝕊d−1𝑑μ​\(x\)=1\\int\_\{\\mathbb\{S\}^\{d\-1\}\}d\\mu\(x\)=1\. For functionsf,h:𝕊d−1→ℝf,h:\\mathbb\{S\}^\{d\-1\}\\to\\mathbb\{R\}, we define theL2L^\{2\}inner product

⟨f,h⟩L2​\(𝕊d−1\):=∫𝕊d−1f​\(x\)​h​\(x\)​𝑑μ​\(x\),\\langle f,h\\rangle\_\{L^\{2\}\(\\mathbb\{S\}^\{d\-1\}\)\}:=\\int\_\{\\mathbb\{S\}^\{d\-1\}\}f\(x\)\\,h\(x\)\\,d\\mu\(x\),and denote byL2​\(𝕊d−1\)L^\{2\}\(\\mathbb\{S\}^\{d\-1\}\)the associated Hilbert space\.

The \(Euclidean\) Laplacian onℝd\\mathbb\{R\}^\{d\}is defined by

Δ:=∑i=1d∂2∂xi2\.\\Delta:=\\sum\_\{i=1\}^\{d\}\\frac\{\\partial^\{2\}\}\{\\partial x\_\{i\}^\{2\}\}\.In contrast, the Laplace–Beltrami operatorΔ𝕊d−1\\Delta\_\{\\mathbb\{S\}^\{d\-1\}\}is the intrinsic Laplacian associated with the Riemannian metric on the sphere\. WhileΔ\\Deltaacts on functions defined inℝd\\mathbb\{R\}^\{d\},Δ𝕊d−1\\Delta\_\{\\mathbb\{S\}^\{d\-1\}\}acts on functions defined on𝕊d−1\\mathbb\{S\}^\{d\-1\}and can be viewed as the restriction ofΔ\\Deltato tangential directions along the sphere\.

Let−Δ𝕊d−1\-\\Delta\_\{\\mathbb\{S\}^\{d\-1\}\}denote the \(positive semidefinite\) Laplace–Beltrami operator on𝕊d−1\\mathbb\{S\}^\{d\-1\}\. Its spectrum is discrete and indexed byℓ=0,1,2,…\\ell=0,1,2,\\ldots, with eigenvalues

λℓ:=ℓ​\(ℓ\+d−2\)\.\\lambda\_\{\\ell\}:=\\ell\(\\ell\+d\-2\)\.
#### Spherical harmonics\.

The eigenspace corresponding toλℓ\\lambda\_\{\\ell\}is denoted byℋℓ\\mathcal\{H\}\_\{\\ell\}and consists of the restrictions to𝕊d−1\\mathbb\{S\}^\{d\-1\}of homogeneous harmonic polynomials of degreeℓ\\ellinℝd\\mathbb\{R\}^\{d\}, namely

ℋℓ:=\{p\|𝕊d−1:pis homogeneous of degreeℓandΔp=0inℝd\}\.\\mathcal\{H\}\_\{\\ell\}:=\\Big\\\{p\|\_\{\\mathbb\{S\}^\{d\-1\}\}:p\\text\{ is homogeneous of degree \}\\ell\\text\{ and \}\\Delta p=0\\text\{ in \}\\mathbb\{R\}^\{d\}\\Big\\\}\.The spaces\{ℋℓ\}ℓ≥0\\\{\\mathcal\{H\}\_\{\\ell\}\\\}\_\{\\ell\\geq 0\}are mutually orthogonal inL2​\(𝕊d−1\)L^\{2\}\(\\mathbb\{S\}^\{d\-1\}\)and yield the orthogonal decomposition

L2​\(𝕊d−1\)=⨁ℓ=0∞ℋℓ\.L^\{2\}\(\\mathbb\{S\}^\{d\-1\}\)=\\bigoplus\_\{\\ell=0\}^\{\\infty\}\\mathcal\{H\}\_\{\\ell\}\.Let us denote the multiplicity of the eigenvalueλℓ\\lambda\_\{\\ell\}as

Nℓ:=dim\(ℋℓ\)=\(d\+ℓ−1ℓ\)−\(d\+ℓ−3ℓ−2\)N\_\{\\ell\}:=\\dim\(\\mathcal\{H\}\_\{\\ell\}\)=\\binom\{d\+\\ell\-1\}\{\\ell\}\-\\binom\{d\+\\ell\-3\}\{\\ell\-2\}For eachℓ\\ell, let\{ϕℓ,m\}m=1Nℓ\\\{\\phi\_\{\\ell,m\}\\\}\_\{m=1\}^\{N\_\{\\ell\}\}be an orthonormal basis ofℋℓ\\mathcal\{H\}\_\{\\ell\}\.

#### Asymptotics of the multiplicities\.

For fixed degreeℓ\\elland dimensiond→∞d\\to\\infty, the multiplicityNℓN\_\{\\ell\}satisfies

Nℓ=dℓℓ\!\+Oℓ​\(dℓ−1\)\.N\_\{\\ell\}=\\frac\{d^\{\\ell\}\}\{\\ell\!\}\+O\_\{\\ell\}\\\!\\left\(d^\{\\ell\-1\}\\right\)\.where the implicit constant depends only onℓ\\ell\. In particular,NℓN\_\{\\ell\}grows polynomially inddwith leading orderdℓd^\{\\ell\}\. Moreover, the dimension of the space of spherical harmonics of degree at mostkksatisfies

∑ℓ=0kNℓ=\(d\+k−1k\)\+\(d\+k−2k−1\),\\sum\_\{\\ell=0\}^\{k\}N\_\{\\ell\}=\\binom\{d\+k\-1\}\{k\}\+\\binom\{d\+k\-2\}\{k\-1\},In particular, for fixedkkandd→∞d\\to\\infty,

∑ℓ=0kNℓ=dkk\!\+Ok​\(dk−1\),\\sum\_\{\\ell=0\}^\{k\}N\_\{\\ell\}=\\frac\{d^\{k\}\}\{k\!\}\+O\_\{k\}\\\!\\left\(d^\{k\-1\}\\right\),where the implicit constant depends only onkk\.

#### Harmonic expansion\.

Every functionf∈L2​\(𝕊d−1\)f\\in L^\{2\}\(\\mathbb\{S\}^\{d\-1\}\)admits the convergent expansion

f=∑ℓ=0∞∑m=1Nℓfℓ,m​ϕℓ,m,fℓ,m:=⟨f,ϕℓ,m⟩L2​\(𝕊d−1\)\.f=\\sum\_\{\\ell=0\}^\{\\infty\}\\sum\_\{m=1\}^\{N\_\{\\ell\}\}f\_\{\\ell,m\}\\,\\phi\_\{\\ell,m\},\\qquad f\_\{\\ell,m\}:=\\langle f,\\phi\_\{\\ell,m\}\\rangle\_\{L^\{2\}\(\\mathbb\{S\}^\{d\-1\}\)\}\.Truncating the expansion at degreesℓ≤k\\ell\\leq kyields theL2L^\{2\}\-orthogonal projection offfonto the space of spherical polynomials of degree at mostkk, and provides the bestL2L^\{2\}approximation offfwithin this class\.

### A\.2Gegenbauer Polynomials, Zonal Kernels, and Projection Kernels

A*zonal*functionZ:𝕊d−1×𝕊d−1→ℝZ:\\mathbb\{S\}^\{d\-1\}\\times\\mathbb\{S\}^\{d\-1\}\\to\\mathbb\{R\}is a function that only depends on the inner product, i\.e\.,

Z​\(x,y\)=ζ​\(⟨x,y⟩\),x,y∈𝕊d−1,Z\(x,y\)=\\zeta\(\\langle x,y\\rangle\),\\qquad x,y\\in\\mathbb\{S\}^\{d\-1\},for someζ:\[−1,1\]→ℝ\\zeta:\[\-1,1\]\\to\\mathbb\{R\}\.

#### Gegenbauer polynomials\.

Letλ:=d−22\\lambda:=\\frac\{d\-2\}\{2\}\. The Gegenbauer polynomials\{Cℓ\(λ\)\}ℓ≥0\\\{C\_\{\\ell\}^\{\(\\lambda\)\}\\\}\_\{\\ell\\geq 0\}form an orthogonal family on\[−1,1\]\[\-1,1\]with respect to the weight\(1−t2\)λ−12\(1\-t^\{2\}\)^\{\\lambda\-\\frac\{1\}\{2\}\}\.

#### Zonal harmonics \(reproducing kernels\)\.

For eachℓ≥0\\ell\\geq 0, letℋℓ\\mathcal\{H\}\_\{\\ell\}be the eigenspace of the Laplace–Beltrami operator−Δ𝕊d−1\-\\Delta\_\{\\mathbb\{S\}^\{d\-1\}\}with eigenvalueλℓ=ℓ​\(ℓ\+d−2\)\\lambda\_\{\\ell\}=\\ell\(\\ell\+d\-2\), and let\{ϕℓ,m\}m=1Nℓ\\\{\\phi\_\{\\ell,m\}\\\}\_\{m=1\}^\{N\_\{\\ell\}\}be an orthonormal basis ofℋℓ\\mathcal\{H\}\_\{\\ell\}inL2​\(𝕊d−1\)L^\{2\}\(\\mathbb\{S\}^\{d\-1\}\)\. Define the*zonal harmonic*\(also called the reproducing kernel ofℋℓ\\mathcal\{H\}\_\{\\ell\}\) by

Zℓ​\(x,y\):=∑m=1Nℓϕℓ,m​\(x\)​ϕℓ,m​\(y\)\.Z\_\{\\ell\}\(x,y\):=\\sum\_\{m=1\}^\{N\_\{\\ell\}\}\\phi\_\{\\ell,m\}\(x\)\\phi\_\{\\ell,m\}\(y\)\.Note thatZℓ​\(x,y\)Z\_\{\\ell\}\(x,y\)is a function of⟨x,y⟩\\langle x,y\\rangleand can be written explicitly as

Zℓ​\(x,y\)=ℓ\+λλ​Cℓ\(λ\)​\(⟨x,y⟩\),λ=d−22\.Z\_\{\\ell\}\(x,y\)=\\frac\{\\ell\+\\lambda\}\{\\lambda\}\\,C\_\{\\ell\}^\{\(\\lambda\)\}\(\\langle x,y\\rangle\),\\qquad\\lambda=\\frac\{d\-2\}\{2\}\.In particular,Zℓ​\(x,x\)=NℓZ\_\{\\ell\}\(x,x\)=N\_\{\\ell\}is constant inxx\.

#### Projection kernel to degree≤k\\leq k\.

LetΠ≤k\\Pi\_\{\\leq k\}denote theL2​\(𝕊d−1\)L^\{2\}\(\\mathbb\{S\}^\{d\-1\}\)\-orthogonal projector onto the space⨁ℓ=0kℋℓ\\bigoplus\_\{\\ell=0\}^\{k\}\\mathcal\{H\}\_\{\\ell\}of spherical polynomials of degree at mostkk\. ThenΠ≤k\\Pi\_\{\\leq k\}is an integral operator with kernel

Π≤k​\(x,y\):=∑ℓ=0kZℓ​\(x,y\)=∑ℓ=0kℓ\+λλ​Cℓ\(λ\)​\(⟨x,y⟩\),\\Pi\_\{\\leq k\}\(x,y\):=\\sum\_\{\\ell=0\}^\{k\}Z\_\{\\ell\}\(x,y\)=\\sum\_\{\\ell=0\}^\{k\}\\frac\{\\ell\+\\lambda\}\{\\lambda\}\\,C\_\{\\ell\}^\{\(\\lambda\)\}\(\\langle x,y\\rangle\),so that

\(Π≤k​f\)​\(x\)=∫𝕊d−1Π≤k​\(x,y\)​f​\(y\)​𝑑σ​\(y\)\.\(\\Pi\_\{\\leq k\}f\)\(x\)=\\int\_\{\\mathbb\{S\}^\{d\-1\}\}\\Pi\_\{\\leq k\}\(x,y\)\\,f\(y\)\\,d\\sigma\(y\)\.Hence, the projection depends only on inner products and can be evaluated efficiently: for fixedxx, computingΠ≤k​\(x,y\)\\Pi\_\{\\leq k\}\(x,y\)reduces to evaluatingCℓ\(λ\)​\(t\)C\_\{\\ell\}^\{\(\\lambda\)\}\(t\)fort=⟨x,y⟩t=\\langle x,y\\rangleandℓ=0,…,k\\ell=0,\\dots,k, which can be done inO​\(k\)O\(k\)time using Gegenbauer polynomials\.

### A\.3Groups

A*group*is a pair\(G,⋅\)\(G,\\cdot\)whereGGis a set and⋅:G×G→G\\cdot:G\\times G\\to Gis a binary operation \(often written as multiplication\) such that:

- •\(Associativity\)\(g⋅h\)⋅k=g⋅\(h⋅k\)\(g\\cdot h\)\\cdot k=g\\cdot\(h\\cdot k\)for allg,h,k∈Gg,h,k\\in G\.
- •\(Identity\)There exists an elemente∈Ge\\in Gsuch thate⋅g=g⋅e=ge\\cdot g=g\\cdot e=gfor allg∈Gg\\in G\.
- •\(Inverse\)For everyg∈Gg\\in Gthere existsg−1∈Gg^\{\-1\}\\in Gsuch thatg⋅g−1=g−1⋅g=eg\\cdot g^\{\-1\}=g^\{\-1\}\\cdot g=e\.

Throughout the paper, we omit the “⋅\\cdot” notation and writeg​hghfor the group product for allg,h∈Gg,h\\in G\.

Here we list a number of example groups\.

- •Permutation group\.The symmetric groupSdS\_\{d\}is the set of all bijectionsπ:\{1,…,d\}→\{1,…,d\}\\pi:\\\{1,\\dots,d\\\}\\to\\\{1,\\dots,d\\\}with group operation given by composition\. Equivalently, eachπ∈Sd\\pi\\in S\_\{d\}is a permutation of the indices\{1,…,d\}\\\{1,\\dots,d\\\}\.
- •Sign\-flipping group\.The sign\-flipping group consists of all vectorsε=\(ε1,…,εd\)\\varepsilon=\(\\varepsilon\_\{1\},\\dots,\\varepsilon\_\{d\}\)withεi∈\{\+1,−1\}\\varepsilon\_\{i\}\\in\\\{\+1,\-1\\\}, equipped with componentwise multiplication\.
- •Hyperoctahedral group \(signed permutations\)\.The hyperoctahedral groupBdB\_\{d\}is the group of all*signed permutation matrices*inℝd×d\\mathbb\{R\}^\{d\\times d\}, i\.e\., matricesQQsuch that each row and each column contains exactly one nonzero entry, and every nonzero entry equals\+1\+1or−1\-1\. Equivalently, each element ofBdB\_\{d\}can be specified by a pair\(π,ε\)\(\\pi,\\varepsilon\)whereπ∈Sd\\pi\\in S\_\{d\}andε∈\{±1\}d\\varepsilon\\in\\\{\\pm 1\\\}^\{d\}\. This group models invariance under the reordering of coordinates, together with independent sign flips\.
- •Cyclic group\.The cyclic group of orderdd, denotedCdC\_\{d\}, is generated by a single elementrrwith relationrd=er^\{d\}=e: Cd:=\{e,r,r2,…,rd−1\},ra​rb=ra\+b​\(mod​d\)\.C\_\{d\}:=\\\{e,r,r^\{2\},\\dots,r^\{d\-1\}\\\},\\qquad r^\{a\}r^\{b\}=r^\{a\+b\\ \(\\mathrm\{mod\}\\ d\)\}\.A canonical example is the group of circular shifts onddcoordinates\.
- •Dihedral group\.The dihedral group of order2​d2d, denotedDdD\_\{d\}, is the symmetry group of a regulardd\-gon\. It containsddrotations andddreflections, and can be presented by generatorsrr\(a rotation by2​π/d2\\pi/d\) andss\(a reflection\) satisfying rd=e,s2=e,s​r​s=r−1\.r^\{d\}=e,\\qquad s^\{2\}=e,\\qquad srs=r^\{\-1\}\.Each element ofDdD\_\{d\}can be written uniquely as eitherrkr^\{k\}ors​rksr^\{k\}for somek∈\{0,1,…,d−1\}k\\in\\\{0,1,\\dots,d\-1\\\}\. In applications ondd\-tuples, one may realizerras a cyclic shift andssas reversal \(a “flip”\), generating both shifts and flip\-symmetries\.

We also frequently encounter infinite groups:

- •Orthogonal group\.The orthogonal groupO​\(d\)\\mathrm\{O\}\(d\)is O​\(d\):=\{Q∈ℝd×d:Q⊤​Q=Id\},\\mathrm\{O\}\(d\):=\\\{Q\\in\\mathbb\{R\}^\{d\\times d\}:Q^\{\\top\}Q=I\_\{d\}\\\},i\.e\., the set of linear maps ofℝd\\mathbb\{R\}^\{d\}that preserve Euclidean inner products \(and hence distances\)\. These include rotations and reflections\.
- •Special orthogonal group\.The special orthogonal groupSO​\(d\)\\mathrm\{SO\}\(d\)is the subgroup SO​\(d\):=\{Q∈O​\(d\):det\(Q\)=1\},\\mathrm\{SO\}\(d\):=\\\{Q\\in O\(d\):\\det\(Q\)=1\\\},consisting of proper rotations \(orientation\-preserving orthogonal transformations\)\.
- •Unitary group\.The unitary groupU​\(d\)\\mathrm\{U\}\(d\)is U​\(d\):=\{U∈ℂd×d:U∗​U=Id\},\\mathrm\{U\}\(d\):=\\\{U\\in\\mathbb\{C\}^\{d\\times d\}:U^\{\*\}U=I\_\{d\}\\\},whereU∗U^\{\*\}denotes the conjugate transpose ofUU\. Equivalently,U​\(d\)\\mathrm\{U\}\(d\)consists of all linear maps ofℂd\\mathbb\{C\}^\{d\}that preserve the complex inner product\.
- •Translation group\.The translation group\(ℝd,\+\)\(\\mathbb\{R\}^\{d\},\+\)acts onℝd\\mathbb\{R\}^\{d\}byt⋅x=x\+tt\\cdot x=x\+t\. This models translation invariance in Euclidean spaces\.

For compact groupsGG, there exists a unique probability measure onGG, called the*Haar measure*, which is invariant under left group translations\. Samplingg∈Gg\\in Gtherefore corresponds to sampling a group element uniformly at random throughout the paper\. We write𝔼g​\[⋅\]\\mathbb\{E\}\_\{g\}\[\\cdot\]to denote expectation with respect to uniform sampling from the group\.

### A\.4Group Actions

Let\(𝒳,μ\)\(\\mathcal\{X\},\\mu\)be a measured space\. A \(left\)*group action*of a groupGGon𝒳\\mathcal\{X\}is a map\(g,x\)↦g​x\(g,x\)\\mapsto gxsatisfying

e​x=xand\(g1​g2\)​x=g1​\(g2​x\),∀g1,g2∈G,∀x∈𝒳\.ex=x\\quad\\text\{and\}\\quad\(g\_\{1\}g\_\{2\}\)x=g\_\{1\}\(g\_\{2\}x\),\\qquad\\forall g\_\{1\},g\_\{2\}\\in G,\\ \\forall x\\in\\mathcal\{X\}\.We assume that the action is*isometric*, i\.e\.,μ​\(g​A\)=μ​\(A\)\\mu\(gA\)=\\mu\(A\)for all measurableA⊆𝒳A\\subseteq\\mathcal\{X\}andg∈Gg\\in G\.

#### Lifted action on function spaces\.

Letℱ⊂L2​\(𝒳,μ\)\\mathcal\{F\}\\subset L^\{2\}\(\\mathcal\{X\},\\mu\)be a finite\-dimensional vector space of continuous functions\. Let\{ϕℓ\}ℓ=1r\\\{\\phi\_\{\\ell\}\\\}\_\{\\ell=1\}^\{r\}be a fixed orthonormal basis ofℱ\\mathcal\{F\}, wherer≔dim\(ℱ\)r\\coloneqq\\dim\(\\mathcal\{F\}\)\. Therefore, we may identifyℱ\\mathcal\{F\}withℝr\\mathbb\{R\}^\{r\}\. With a slight abuse of notation, each functionf∈ℱf\\in\\mathcal\{F\}is identified with a vectorf∈ℝrf\\in\\mathbb\{R\}^\{r\}\.

We say thatℱ\\mathcal\{F\}is*closed*under the group action if, for anyf∈ℱf\\in\\mathcal\{F\}, we havex↦f​\(g​x\)∈ℱx\\mapsto f\(gx\)\\in\\mathcal\{F\}for allg∈Gg\\in G\. Throughout, we assume thatℱ\\mathcal\{F\}is closed under the group action\.

The action ofGGon𝒳\\mathcal\{X\}induces a natural action onℱ\\mathcal\{F\}defined by

\(Tg​f\)​\(x\):=f​\(g−1​x\),∀g∈G,\(T\_\{g\}f\)\(x\):=f\(g^\{\-1\}x\),\\qquad\\forall g\\in G,whereTg:ℱ→ℱT\_\{g\}:\\mathcal\{F\}\\to\\mathcal\{F\}are unitary operators \(matrices\), due to the isometry assumption\. Whenℱ\\mathcal\{F\}is finite\-dimensional, we can identify eachTgT\_\{g\}with a matrix of dimensiondim\(ℱ\)\\dim\(\\mathcal\{F\}\), and thusTg∈ℝr×rT\_\{g\}\\in\\mathbb\{R\}^\{r\\times r\}for allg∈Gg\\in G, wherer≔dim\(ℱ\)r\\coloneqq\\dim\(\\mathcal\{F\}\)\. In particular,Te=IrT\_\{e\}=I\_\{r\}, wheree∈Ge\\in Gdenotes the identity element andIr∈ℝr×rI\_\{r\}\\in\\mathbb\{R\}^\{r\\times r\}is the identity matrix, and we haveTg​Th=Tg​hT\_\{g\}T\_\{h\}=T\_\{gh\}for allg,h∈Gg,h\\in G\.

#### Invariant functions and projection\.

TheGG\-invariant subspace ofℱ\\mathcal\{F\}is

ℱG:=\{f∈ℱ:Tg​f=f​∀g∈G\}=⋂g∈Gker⁡\(Tg−I\)\.\\mathcal\{F\}^\{G\}:=\\\{f\\in\\mathcal\{F\}:T\_\{g\}f=f\\;\\;\\forall g\\in G\\\}=\\bigcap\_\{g\\in G\}\\ker\(T\_\{g\}\-I\)\.We identifyℱG⊆ℱ\\mathcal\{F\}^\{G\}\\subseteq\\mathcal\{F\}with a finite\-dimensional vector subspace ofℝr\\mathbb\{R\}^\{r\}, whererinv≔dim\(ℱG\)r\_\{\\operatorname\{inv\}\}\\coloneqq\\dim\(\\mathcal\{F\}^\{G\}\)\. For compact groupsGG, the orthogonal projection onto the invariant subspaceℱG\\mathcal\{F\}^\{G\}is given by

ΠG​f≔𝔼g​\[Tg​f\]\.\\Pi\_\{G\}f\\;\\coloneqq\\;\\mathbb\{E\}\_\{g\}\\\!\\left\[\\,T\_\{g\}f\\,\\right\]\.

### A\.5Group Representations

A \(unitary\) representation of a groupGGon a finite\-dimensional Hilbert spaceℋ\\mathcal\{H\}is a map

ρ:G→𝒰​\(ℋ\),\\rho:G\\to\\mathcal\{U\}\(\\mathcal\{H\}\),fromGGto the group of unitary operators onℋ\\mathcal\{H\}, such that

ρ​\(e\)=Iℋandρ​\(g​h\)=ρ​\(g\)​ρ​\(h\)for all​g,h∈G\.\\rho\(e\)=I\_\{\\mathcal\{H\}\}\\qquad\\text\{and\}\\qquad\\rho\(gh\)=\\rho\(g\)\\rho\(h\)\\quad\\text\{for all \}g,h\\in G\.Indeed, the group multiplication inGGis represented by the composition of unitary operators onℋ\\mathcal\{H\}\.

A subspaceW⊆ℋW\\subseteq\\mathcal\{H\}is said to be*GG\-invariant*if

ρ​\(g\)​w∈Wfor all​w∈W​and all​g∈G,\\rho\(g\)w\\in W\\quad\\text\{for all \}w\\in W\\text\{ and all \}g\\in G,that is, the action of the group does not move vectors inWWoutside ofWW\.

A representationρ\\rhois called*irreducible*if the only closedGG\-invariant subspaces ofℋ\\mathcal\{H\}are the trivial ones, namely\{0\}\\\{0\\\}andℋ\\mathcal\{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:

ℋ≅⨁λ∈G^ℂmλ⊗Vλ,\\mathcal\{H\}\\;\\cong\\;\\bigoplus\_\{\\lambda\\in\\widehat\{G\}\}\\mathbb\{C\}^\{m\_\{\\lambda\}\}\\otimes V\_\{\\lambda\},whereG^\\widehat\{G\}denotes the set of inequivalent irreducible representations,VλV\_\{\\lambda\}is an irreducible representation of dimensiondλ∈ℕd\_\{\\lambda\}\\in\\mathbb\{N\}, andmλ∈ℤ≥0m\_\{\\lambda\}\\in\\mathbb\{Z\}\_\{\\geq 0\}is its multiplicity\. The number of irreducible representations equals the number of conjugacy classes ofGG, and their dimensions satisfy

∑λ∈G^dλ2=\|G\|\.\\sum\_\{\\lambda\\in\\widehat\{G\}\}d\_\{\\lambda\}^\{2\}=\|G\|\.In particular,\|G^\|≤\|G\|\|\\widehat\{G\}\|\\leq\|G\|for all finite groupsGG\.

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ℱ\\mathcal\{F\}into*isotypic components*\.

#### Matrix structure under a change of coordinates\.

Letρ:G→𝒰​\(ℋ\)\\rho:G\\to\\mathcal\{U\}\(\\mathcal\{H\}\)be a finite\-dimensional unitary representation\. There exists an orthonormal basis ofℋ\\mathcal\{H\}under which each operatorρ​\(g\)\\rho\(g\)takes a block\-diagonal form consistent with the above decomposition:

ρ​\(g\)≅⨁λ∈G^Imλ⊗ρλ​\(g\),g∈G,\\rho\(g\)\\;\\cong\\;\\bigoplus\_\{\\lambda\\in\\widehat\{G\}\}I\_\{m\_\{\\lambda\}\}\\otimes\\rho\_\{\\lambda\}\(g\),\\qquad g\\in G,whereρλ:G→𝒰​\(Vλ\)\\rho\_\{\\lambda\}:G\\to\\mathcal\{U\}\(V\_\{\\lambda\}\)denotes an irreducible representation of dimensiondλd\_\{\\lambda\}, andImλI\_\{m\_\{\\lambda\}\}is the identity operator on the multiplicity spaceℂmλ\\mathbb\{C\}^\{m\_\{\\lambda\}\}\.

In this basis, each irreducible representation appearsmλm\_\{\\lambda\}times, and the action ofGGis 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ℋ=ℱ\\mathcal\{H\}=\\mathcal\{F\}, we note that each operatorTgT\_\{g\}is unitary onℱ\\mathcal\{F\}, and the mapg↦Tgg\\mapsto T\_\{g\}defines a finite\-dimensional unitary representationρ:G→U​\(r\)\\rho:G\\to U\(r\)onℱ\\mathcal\{F\}\(or, equivalently, onℝr\\mathbb\{R\}^\{r\}\)\.

The*trivial irreducible representation*ofGGis the one\-dimensional representation in which every group element acts as the identity, i\.e\.,ρtriv​\(g\)=1∈ℝ\\rho\_\{\\mathrm\{triv\}\}\(g\)=1\\in\\mathbb\{R\}for allg∈Gg\\in G\. Functions lying in the trivial isotypic component are exactly those that are fixed by the action ofGG, and therefore correspond precisely toGG\-invariant functionsℱG\\mathcal\{F\}^\{G\}, and can be obtained via orthogonal projection\.

### A\.6Projection 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\(𝒳,μ\)\(\\mathcal\{X\},\\mu\)be a measured space and letℱ⊂L2​\(𝒳,μ\)\\mathcal\{F\}\\subset L^\{2\}\(\\mathcal\{X\},\\mu\)be a finite\-dimensional linear subspace of dimensionrr\. Note that every functionf∈ℱf\\in\\mathcal\{F\}admits the expansion

f=∑ℓ=1rθℓ​ϕℓ,θℓ≔⟨f,ϕℓ⟩\.f=\\sum\_\{\\ell=1\}^\{r\}\\theta\_\{\\ell\}\\phi\_\{\\ell\},\\qquad\\theta\_\{\\ell\}\\coloneqq\\langle f,\\phi\_\{\\ell\}\\rangle\.
#### Projection density estimation \(unlabeled data\)\.

Letx1,…,xnx\_\{1\},\\dots,x\_\{n\}be i\.i\.d\. samples drawn from an unknown densityf⋆∈L2​\(𝒳,μ\)f^\{\\star\}\\in L^\{2\}\(\\mathcal\{X\},\\mu\)\. TheL2​\(𝒳\)L^\{2\}\(\\mathcal\{X\}\)\-orthogonal projection off⋆f^\{\\star\}ontoℱ\\mathcal\{F\}is

Πℱ​f⋆:=arg⁡minf∈ℱ⁡‖f⋆−f‖L2​\(𝒳\)2=∑ℓ=1rθℓ​ϕℓ,θℓ=𝔼x∼f⋆​\[ϕℓ​\(x\)\]\.\\Pi\_\{\\mathcal\{F\}\}f^\{\\star\}:=\\arg\\min\_\{f\\in\\mathcal\{F\}\}\\\|f^\{\\star\}\-f\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}=\\sum\_\{\\ell=1\}^\{r\}\\theta\_\{\\ell\}\\phi\_\{\\ell\},\\qquad\\theta\_\{\\ell\}=\\mathbb\{E\}\_\{x\\sim f^\{\\star\}\}\[\\phi\_\{\\ell\}\(x\)\]\.Since the coefficientsθℓ\\theta\_\{\\ell\}are expectations, they admit unbiased empirical estimators

θ^ℓ:=1n​∑i=1nϕℓ​\(xi\)\.\\widehat\{\\theta\}\_\{\\ell\}:=\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\\phi\_\{\\ell\}\(x\_\{i\}\)\.This leads to the*projection density estimator*

f^:=∑ℓ=1rθ^ℓ​ϕℓ\.\\widehat\{f\}:=\\sum\_\{\\ell=1\}^\{r\}\\widehat\{\\theta\}\_\{\\ell\}\\phi\_\{\\ell\}\.

#### Projection regression estimation \(labeled data\)\.

Now consider a supervised setting where\(xi,yi\)i=1n\(x\_\{i\},y\_\{i\}\)\_\{i=1\}^\{n\}are i\.i\.d\. samples from a joint distribution on𝒳×ℝ\\mathcal\{X\}\\times\\mathbb\{R\}, wherexi∼μx\_\{i\}\\sim\\muis drawn uniformly from𝒳\\mathcal\{X\}, and

yi=f⋆​\(xi\)\+εi,𝔼​\[εi\]=0,𝔼​\[εi2\]=σ2,y\_\{i\}=f^\{\\star\}\(x\_\{i\}\)\+\\varepsilon\_\{i\},\\qquad\\mathbb\{E\}\[\\varepsilon\_\{i\}\]=0,\\qquad\\mathbb\{E\}\[\\varepsilon\_\{i\}^\{2\}\]=\\sigma^\{2\},withε1,…,εn\\varepsilon\_\{1\},\\dots,\\varepsilon\_\{n\}independent ofx1,…,xnx\_\{1\},\\dots,x\_\{n\}\.

The regression functionf⋆​\(x\)=𝔼​\[y\|x\]f^\{\\star\}\(x\)=\\mathbb\{E\}\[y\|x\]lies inL2​\(𝒳,μ\)L^\{2\}\(\\mathcal\{X\},\\mu\), and itsL2​\(𝒳\)L^\{2\}\(\\mathcal\{X\}\)\-orthogonal projection ontoℱ\\mathcal\{F\}is given by

Πℱf⋆:=argminf∈ℱ𝔼\[\(f\(x\)−f⋆\(x\)\)2\]=∑ℓ=1rβℓϕℓ,βℓ=𝔼x,y\[yϕℓ\(x\)\]\.\\Pi\_\{\\mathcal\{F\}\}f^\{\\star\}:=\\arg\\min\_\{f\\in\\mathcal\{F\}\}\\mathbb\{E\}\\big\[\(f\(x\)\-f^\{\\star\}\(x\)\)^\{2\}\\big\]=\\sum\_\{\\ell=1\}^\{r\}\\beta\_\{\\ell\}\\phi\_\{\\ell\},\\qquad\\beta\_\{\\ell\}=\\mathbb\{E\}\_\{x,y\}\[y\\,\\phi\_\{\\ell\}\(x\)\]\.The coefficientsβℓ\\beta\_\{\\ell\}admit empirical estimators

β^ℓ:=1n​∑i=1nyi​ϕℓ​\(xi\),\\widehat\{\\beta\}\_\{\\ell\}:=\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}y\_\{i\}\\,\\phi\_\{\\ell\}\(x\_\{i\}\),leading to the*projection regression estimator*

f^:=∑ℓ=1rβ^ℓ​ϕℓ\.\\widehat\{f\}:=\\sum\_\{\\ell=1\}^\{r\}\\widehat\{\\beta\}\_\{\\ell\}\\phi\_\{\\ell\}\.

#### 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

θℓ=𝔼​\[ϕℓ​\(x\)\],ℓ∈\[r\],\\theta\_\{\\ell\}\\;=\\;\\mathbb\{E\}\\big\[\\phi\_\{\\ell\}\(x\)\\big\],\\qquad\\ell\\in\[r\],and the empirical coefficientsθ^ℓ=1n​∑i=1nϕℓ​\(xi\)\\widehat\{\\theta\}\_\{\\ell\}=\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\\phi\_\{\\ell\}\(x\_\{i\}\)are obtained by matching these moments\. The resulting estimatorf^=∑ℓ=1rθ^ℓ​ϕℓ\\widehat\{f\}=\\sum\_\{\\ell=1\}^\{r\}\\widehat\{\\theta\}\_\{\\ell\}\\phi\_\{\\ell\}is therefore a moment\-based approximation of theL2​\(𝒳\)L^\{2\}\(\\mathcal\{X\}\)\-projection off⋆f^\{\\star\}ontoℱ\\mathcal\{F\}\.

Similarly, in the regression setting, the population projection coefficients satisfy the moment identities

βℓ=𝔼​\[y​ϕℓ​\(x\)\],ℓ∈\[r\],\\beta\_\{\\ell\}\\;=\\;\\mathbb\{E\}\\big\[y\\,\\phi\_\{\\ell\}\(x\)\\big\],\\qquad\\ell\\in\[r\],and are estimated by their empirical counterpartsβ^ℓ=1n​∑i=1nyi​ϕℓ​\(xi\)\\widehat\{\\beta\}\_\{\\ell\}=\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}y\_\{i\}\\,\\phi\_\{\\ell\}\(x\_\{i\}\)\. In both cases, the estimators are obtained by matching population moments with empirical moments and substituting the resulting coefficients into the basis expansion\.

### A\.7Projection 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𝒳=𝕊d−1\\mathcal\{X\}=\\mathbb\{S\}^\{d\-1\}be the unit sphere equipped with the uniform probability measureμ\\mu\. For eachℓ≥0\\ell\\geq 0, letℋℓ\\mathcal\{H\}\_\{\\ell\}be the eigenspace of spherical harmonics with degreeℓ\\ell, and let\{ϕℓ,m\}m=1Nℓ\\\{\\phi\_\{\\ell,m\}\\\}\_\{m=1\}^\{N\_\{\\ell\}\}be an orthonormal basis ofℋℓ\\mathcal\{H\}\_\{\\ell\}inL2​\(𝕊d−1\)L^\{2\}\(\\mathbb\{S\}^\{d\-1\}\), whereNℓN\_\{\\ell\}is the dimension of this space\.

For a fixed truncation levelk∈ℤ≥0k\\in\\mathbb\{Z\}\_\{\\geq 0\}, we define the finite\-dimensional approximation space

ℱ:=⨁ℓ=0kℋℓ,r≔dim\(ℱ\)=∑ℓ=0kNℓ\.\\mathcal\{F\}\\;:=\\;\\bigoplus\_\{\\ell=0\}^\{k\}\\mathcal\{H\}\_\{\\ell\},\\qquad r\\coloneqq\\dim\(\\mathcal\{F\}\)=\\;\\sum\_\{\\ell=0\}^\{k\}N\_\{\\ell\}\.Note that, in contrast to the general setting of the previous subsection, where basis functions were indexed by a single indexℓ∈\[r\]\\ell\\in\[r\], here each basis function is indexed by a degreeℓ\\elland a multiplicity indexmm\.

#### Projection estimators in spherical harmonics coordinates\.

Any functionf∈ℱf\\in\\mathcal\{F\}admits the expansion

f​\(x\)=∑ℓ=0k∑m=1Nℓθℓ,m​ϕℓ,m​\(x\),θℓ,m=⟨f,ϕℓ,m⟩\.f\(x\)\\;=\\;\\sum\_\{\\ell=0\}^\{k\}\\sum\_\{m=1\}^\{N\_\{\\ell\}\}\\theta\_\{\\ell,m\}\\,\\phi\_\{\\ell,m\}\(x\),\\qquad\\theta\_\{\\ell,m\}=\\langle f,\\phi\_\{\\ell,m\}\\rangle\.In the density estimation setting, wherex1,…,xnx\_\{1\},\\dots,x\_\{n\}are i\.i\.d\. samples from an unknown densityf⋆f^\{\\star\}on𝕊d−1\\mathbb\{S\}^\{d\-1\}, the population projection coefficients satisfy

θℓ,m=𝔼x∼f⋆​\[ϕℓ,m​\(x\)\]⟹θ^ℓ,m=1n​∑i=1nϕℓ,m​\(xi\)\.\\theta\_\{\\ell,m\}\\;=\\;\\mathbb\{E\}\_\{x\\sim f^\{\\star\}\}\\big\[\\phi\_\{\\ell,m\}\(x\)\\big\]\\implies\\widehat\{\\theta\}\_\{\\ell,m\}\\;=\\;\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\\phi\_\{\\ell,m\}\(x\_\{i\}\)\.The resulting projection estimator is

f^​\(x\)=∑ℓ=0k∑m=1Nℓθ^ℓ,m​ϕℓ,m​\(x\)\.\\widehat\{f\}\(x\)\\;=\\;\\sum\_\{\\ell=0\}^\{k\}\\sum\_\{m=1\}^\{N\_\{\\ell\}\}\\widehat\{\\theta\}\_\{\\ell,m\}\\,\\phi\_\{\\ell,m\}\(x\)\.
An analogous expression holds in the regression setting, with coefficientsθℓ,m\\theta\_\{\\ell,m\}replaced byβℓ,m=𝔼​\[y​ϕℓ,m​\(x\)\]\\beta\_\{\\ell,m\}=\\mathbb\{E\}\[y\\,\\phi\_\{\\ell,m\}\(x\)\]\.

#### Projection kernels and zonal harmonics\.

Rather than working explicitly with the basis\{ϕℓ,m\}\\\{\\phi\_\{\\ell,m\}\\\}, it is often convenient to express the projection estimator using the associated*projection kernel*

Π≤k​\(x,x′\):=∑ℓ=0k∑m=1Nℓϕℓ,m​\(x\)​ϕℓ,m​\(x′\)\.\\Pi\_\{\\leq k\}\(x,x^\{\\prime\}\)\\;:=\\;\\sum\_\{\\ell=0\}^\{k\}\\sum\_\{m=1\}^\{N\_\{\\ell\}\}\\phi\_\{\\ell,m\}\(x\)\\,\\phi\_\{\\ell,m\}\(x^\{\\prime\}\)\.With this notation, the projection estimator admits the kernel form

f^​\(x\)=1n​∑i=1nΠ≤k​\(x,xi\)\(density estimation\),f^​\(x\)=1n​∑i=1nyi​Π≤k​\(x,xi\)\(regression\)\.\\widehat\{f\}\(x\)\\;=\\;\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\\Pi\_\{\\leq k\}\(x,x\_\{i\}\)\\quad\\text\{\(density estimation\)\},\\quad\\widehat\{f\}\(x\)\\;=\\;\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}y\_\{i\}\\,\\Pi\_\{\\leq k\}\(x,x\_\{i\}\)\\quad\\text\{\(regression\)\}\.
The kernelΠ≤k​\(x,x′\)\\Pi\_\{\\leq k\}\(x,x^\{\\prime\}\)is a*zonal kernel*, meaning that it depends onxxandx′x^\{\\prime\}only through their inner product⟨x,x′⟩\\langle x,x^\{\\prime\}\\rangle\.

#### Gegenbauer polynomial representation\.

By the addition theorem for spherical harmonics\(Dai,[2013](https://arxiv.org/html/2606.24418#bib.bib53)\), the projection kernel admits the explicit representation

Πk​\(x,x′\)=∑ℓ=0kℓ\+λλ​Cℓ\(λ\)​\(⟨x,x′⟩\),λ=d−22,\\Pi\_\{k\}\(x,x^\{\\prime\}\)\\;=\\;\\sum\_\{\\ell=0\}^\{k\}\\frac\{\\ell\+\\lambda\}\{\\lambda\}\\,C\_\{\\ell\}^\{\(\\lambda\)\}\(\\langle x,x^\{\\prime\}\\rangle\),\\qquad\\lambda=\\frac\{d\-2\}\{2\},whereCℓ\(λ\)C\_\{\\ell\}^\{\(\\lambda\)\}denotes the Gegenbauer polynomial of degreeℓ\\ell\. 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 polynomialCℓ\+1\(λ\)​\(t\)C\_\{\\ell\+1\}^\{\(\\lambda\)\}\(t\)can be computed using only the two preceding valuesCℓ\(λ\)​\(t\)C\_\{\\ell\}^\{\(\\lambda\)\}\(t\)andCℓ−1\(λ\)​\(t\)C\_\{\\ell\-1\}^\{\(\\lambda\)\}\(t\)\. Consequently, for a fixedt∈\[−1,1\]t\\in\[\-1,1\], the sequence\{Cℓ\(λ\)​\(t\)\}ℓ=0k\\\{C\_\{\\ell\}^\{\(\\lambda\)\}\(t\)\\\}\_\{\\ell=0\}^\{k\}can be evaluated iteratively, storing only two intermediate values at any time\. This yields anO​\(k\)O\(k\)time complexity andO​\(1\)O\(1\)memory usage for computing all degrees up tokk\.

We conclude with an important implication\. Although projection estimators are computationally tractable for polynomial features of moderate degreekkgrowing polynomially with the dimensiondd, 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](https://arxiv.org/html/2606.24418#A4.Thmtheorem1)is already satisfied whenk=O​\(d2\)k=O\(d^\{2\}\)\.

###### Proposition A\.1\(Permutation irreps in low\-degree harmonics\)\.

LetSdS\_\{d\}act on𝕊d−1\\mathbb\{S\}^\{d\-1\}by permuting coordinates\. Then every irreducible representation ofSdS\_\{d\}appears in the restriction of spherical harmonics of degree at most\(d2\)=O​\(d2\)\\binom\{d\}\{2\}=O\(d^\{2\}\)\. Equivalently, the space of degree\-O​\(d2\)O\(d^\{2\}\)spherical harmonics already contains all symmetry modes of the permutation action\. See\(Tahmasebi and Weber,[2026a](https://arxiv.org/html/2606.24418#bib.bib58)\)for further discussion\.

### A\.8Approximate Projection via Random Group Averaging

In this subsection, we study approximating the projection onto the invariant subspaceℱG\\mathcal\{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ℱ⊂L2​\(𝒳,μ\)\\mathcal\{F\}\\subset L^\{2\}\(\\mathcal\{X\},\\mu\)is a finite\-dimensional Hilbert space of dimensionrr, closed under the group action, and that the lifted action induces a unitary representationρ:G→U​\(r\)\\rho:G\\to U\(r\)\. The orthogonal projection onto the invariant subspaceℱG\\mathcal\{F\}^\{G\}is given by group averaging,ΠG​f=𝔼g​\[Tg​f\]\.\\Pi\_\{G\}f\\;=\\;\\mathbb\{E\}\_\{g\}\[T\_\{g\}f\]\.

LetS=\{g1,…,gs\}S=\\\{g\_\{1\},\\dots,g\_\{s\}\\\}be a multiset of elements drawn independently and uniformly fromGG\. We define the empirical averaging operator

ΠS​f≔1s​∑i=1sTgi​f\.\\Pi\_\{S\}f\\;\\coloneqq\\;\\frac\{1\}\{s\}\\sum\_\{i=1\}^\{s\}T\_\{g\_\{i\}\}f\.This operator can be viewed as an approximation ofΠG\\Pi\_\{G\}\.

#### Decomposition into irreducible components\.

By finite\-group representation theory, there exists an orthonormal change of coordinates under whichℱ\\mathcal\{F\}decomposes as

ℱ≅⨁λ∈G^ℂmλ⊗Vλ⟹ρ​\(g\)≅⨁λ∈G^Imλ⊗ρλ​\(g\),g∈G\.\\mathcal\{F\}\\;\\cong\\;\\bigoplus\_\{\\lambda\\in\\widehat\{G\}\}\\mathbb\{C\}^\{m\_\{\\lambda\}\}\\otimes V\_\{\\lambda\}\\implies\\rho\(g\)\\;\\cong\\;\\bigoplus\_\{\\lambda\\in\\widehat\{G\}\}I\_\{m\_\{\\lambda\}\}\\otimes\\rho\_\{\\lambda\}\(g\),\\qquad g\\in G\.Note that

∑λ∈G^mλ=r=dim\(ℱ\)\.\\sum\_\{\\lambda\\in\\widehat\{G\}\}m\_\{\\lambda\}=r=\\dim\(\\mathcal\{F\}\)\.Under this decomposition, the exact projectionΠG\\Pi\_\{G\}acts as the identity on the trivial representation and annihilates all nontrivial irreducible components\. In contrast, the empirical operatorΠS\\Pi\_\{S\}replaces the group average on each block by a finite sample average\.

#### Behavior of random averaging\.

For the trivial irreducible representation,ρtriv​\(g\)=1\\rho\_\{\\mathrm\{triv\}\}\(g\)=1for allg∈Gg\\in G, and therefore

ΠS​f=fonℱGfor any​S\.\\Pi\_\{S\}f=f\\quad\\text\{on\}\\quad\\mathcal\{F\}^\{G\}\\quad\\text\{for any \}S\.Thus, invariant components are preserved exactly, regardless of the choice ofSS\.

For any nontrivial irreducible representationλ≠triv\\lambda\\neq\\mathrm\{triv\}, the group average of the representation matrices vanishes:

𝔼g​\[ρλ​\(g\)\]=0\.\\mathbb\{E\}\_\{g\}\\big\[\\rho\_\{\\lambda\}\(g\)\\big\]\\;=\\;0\.One way to see this is thatAλ:=𝔼g​\[ρλ​\(g\)\]A\_\{\\lambda\}:=\\mathbb\{E\}\_\{g\}\[\\rho\_\{\\lambda\}\(g\)\]commutes withρλ​\(h\)\\rho\_\{\\lambda\}\(h\)for everyh∈Gh\\in G\(by left\-invariance of the uniform measure\), hence by Schur’s lemmaAλ=c​IA\_\{\\lambda\}=c\\,Ifor some scalarcc\. Taking traces yields

c​dλ=tr​\(Aλ\)=𝔼g​\[tr​\(ρλ​\(g\)\)\],c\\,d\_\{\\lambda\}\\;=\\;\\mathrm\{tr\}\(A\_\{\\lambda\}\)\\;=\\;\\mathbb\{E\}\_\{g\}\\big\[\\mathrm\{tr\}\(\\rho\_\{\\lambda\}\(g\)\)\\big\],and orthogonality of traces \(i\.e\., characters\) of irreducible representations implies𝔼g​\[ρλ​\(g\)\]=0\\mathbb\{E\}\_\{g\}\[\\rho\_\{\\lambda\}\(g\)\]=0for every nontrivialλ\\lambda, hencec=0c=0and thereforeAλ=0A\_\{\\lambda\}=0\. Consequently, the empirical average1\|S\|​∑g∈Sρλ​\(g\)\\frac\{1\}\{\|S\|\}\\sum\_\{g\\in S\}\\rho\_\{\\lambda\}\(g\)concentrates around0as\|S\|\|S\|grows, and the contribution of non\-invariant components is attenuated by random averaging\.

#### Isotypic components\.

Letℱλ⊆ℱ\\mathcal\{F\}\_\{\\lambda\}\\subseteq\\mathcal\{F\}denote theλ\\lambda\-isotypic subspace, i\.e\., the direct sum of all irreducible subrepresentations equivalent toVλV\_\{\\lambda\}in the decompositionℱ≅⨁λ∈G^ℂmλ⊗Vλ\\mathcal\{F\}\\cong\\bigoplus\_\{\\lambda\\in\\widehat\{G\}\}\\mathbb\{C\}^\{m\_\{\\lambda\}\}\\otimes V\_\{\\lambda\}\. Equivalently,ℱλ\\mathcal\{F\}\_\{\\lambda\}is the image of the orthogonal projector onto theλ\\lambda\-block\. Anyf∈ℱf\\in\\mathcal\{F\}decomposes orthogonally as

f=∑λ∈G^fλ,fλ∈ℱλ,⟨fλ,fλ′⟩L2​\(𝒳\)=0​\(λ≠λ′\)\.f\\;=\\;\\sum\_\{\\lambda\\in\\widehat\{G\}\}f\_\{\\lambda\},\\qquad f\_\{\\lambda\}\\in\\mathcal\{F\}\_\{\\lambda\},\\qquad\\langle f\_\{\\lambda\},f\_\{\\lambda^\{\\prime\}\}\\rangle\_\{L^\{2\}\(\\mathcal\{X\}\)\}=0\\;\\;\(\\lambda\\neq\\lambda^\{\\prime\}\)\.In particular, the invariant subspace is the trivial isotypic component:ℱG=ℱtriv\\mathcal\{F\}^\{G\}=\\mathcal\{F\}\_\{\\mathrm\{triv\}\}\.

#### Expected approximation error\.

Letf∈ℱf\\in\\mathcal\{F\}with‖f‖L2​\(𝒳\)≤1\\\|f\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}\\leq 1, and letSSbe a multiset of\|S\|\|S\|i\.i\.d\. uniform samples fromGG\. SinceΠG​f=ftriv\\Pi\_\{G\}f=f\_\{\\mathrm\{triv\}\}andΠS\\Pi\_\{S\}acts blockwise, we have

ΠS​f−ΠG​f=∑λ≠trivΠS​fλ,\\Pi\_\{S\}f\-\\Pi\_\{G\}f\\;=\\;\\sum\_\{\\lambda\\neq\\mathrm\{triv\}\}\\Pi\_\{S\}f\_\{\\lambda\},and by orthogonality of distinct isotypic components \(and unitarity of the action\),

‖ΠS​f−ΠG​f‖L2​\(𝒳\)2=∑λ≠triv‖ΠS​fλ‖L2​\(𝒳\)2\.\\\|\\Pi\_\{S\}f\-\\Pi\_\{G\}f\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}\\;=\\;\\sum\_\{\\lambda\\neq\\mathrm\{triv\}\}\\\|\\Pi\_\{S\}f\_\{\\lambda\}\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}\.Taking expectation over the randomness ofSSyields

𝔼S​\[‖ΠS​f−ΠG​f‖L2​\(𝒳\)2\]=∑λ≠triv𝔼S​\[‖ΠS​fλ‖L2​\(𝒳\)2\]\.\\mathbb\{E\}\_\{S\}\\big\[\\\|\\Pi\_\{S\}f\-\\Pi\_\{G\}f\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}\\big\]\\;=\\;\\sum\_\{\\lambda\\neq\\mathrm\{triv\}\}\\mathbb\{E\}\_\{S\}\\big\[\\\|\\Pi\_\{S\}f\_\{\\lambda\}\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}\\big\]\.
Moreover, for any fixed componentu∈ℱλu\\in\\mathcal\{F\}\_\{\\lambda\}withλ≠triv\\lambda\\neq\\mathrm\{triv\}, the random vectors\{Tg​u\}g\\\{T\_\{g\}u\\\}\_\{g\}are mean\-zero inℱλ\\mathcal\{F\}\_\{\\lambda\}and satisfy‖Tg​u‖L2​\(𝒳\)=‖u‖L2​\(𝒳\)\\\|T\_\{g\}u\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}=\\\|u\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}\. A direct variance computation gives

𝔼S​\[‖ΠS​u‖L2​\(𝒳\)2\]=1\|S\|​‖u‖L2​\(𝒳\)2,\\mathbb\{E\}\_\{S\}\\big\[\\\|\\Pi\_\{S\}u\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}\\big\]\\;=\\;\\frac\{1\}\{\|S\|\}\\,\\\|u\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\},since cross terms vanish by𝔼g​\[Tg​u\]=0\\mathbb\{E\}\_\{g\}\[T\_\{g\}u\]=0forλ≠triv\\lambda\\neq\\mathrm\{triv\}\. Applying this withu=fλu=f\_\{\\lambda\}and summing overλ≠triv\\lambda\\neq\\mathrm\{triv\}yields

𝔼S​\[‖ΠS​f−ΠG​f‖L2​\(𝒳\)2\]=1\|S\|​∑λ≠triv‖fλ‖L2​\(𝒳\)2≤1\|S\|​‖f‖L2​\(𝒳\)2≤1\|S\|\.\\mathbb\{E\}\_\{S\}\\big\[\\\|\\Pi\_\{S\}f\-\\Pi\_\{G\}f\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}\\big\]\\;=\\;\\frac\{1\}\{\|S\|\}\\sum\_\{\\lambda\\neq\\mathrm\{triv\}\}\\\|f\_\{\\lambda\}\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}\\;\\leq\\;\\frac\{1\}\{\|S\|\}\\,\\\|f\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}\\;\\leq\\;\\frac\{1\}\{\|S\|\}\.In particular, the expected approximation error decays exactly as1/\|S\|1/\|S\|, uniformly over allf∈ℱf\\in\\mathcal\{F\}with‖f‖L2​\(𝒳\)≤1\\\|f\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}\\leq 1\.

Therefore, random averaging over a small number of group elements preserves invariant components exactly, while suppressing non\-invariant components in expectation\. From a representation\-theoretic viewpoint, this corresponds to averaging each nontrivial irreducible block toward zero, with variance decreasing as the number of sampled group elements increases\.

### A\.9Uniform 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 subsetS⊆GS\\subseteq G, can be reused to obtain guarantees that hold uniformly over the entire function spaceℱ\\mathcal\{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ℱ\\mathcal\{F\}, making them suitable for algorithm\-agnostic and reusable augmentation schemes\.

###### Theorem A\.2\(Partial data augmentation uniformly overℱ\\mathcal\{F\}\(high probability\)\)\.

Let\(𝒳,μ\)\(\\mathcal\{X\},\\mu\)be a measured space and letℱ⊆L2​\(𝒳,μ\)\\mathcal\{F\}\\subseteq L^\{2\}\(\\mathcal\{X\},\\mu\)be a finite\-dimensional subspace withdim\(ℱ\)=r\\dim\(\\mathcal\{F\}\)=r\. Assume a groupGGacts isometrically on\(𝒳,μ\)\(\\mathcal\{X\},\\mu\)and thatℱ\\mathcal\{F\}is closed under the induced action\. LetTg:ℱ→ℱT\_\{g\}:\\mathcal\{F\}\\to\\mathcal\{F\}denote the lifted \(unitary\) operators and let

ΠG:=𝔼g∼G​\[Tg\]andΠS:=1\|S\|​∑g∈STg,\\Pi\_\{G\}\\;:=\\;\\mathbb\{E\}\_\{g\\sim G\}\[T\_\{g\}\]\\qquad\\text\{and\}\\qquad\\Pi\_\{S\}\\;:=\\;\\frac\{1\}\{\|S\|\}\\sum\_\{g\\in S\}T\_\{g\},whereS=\{g1,…,g\|S\|\}S=\\\{g\_\{1\},\\dots,g\_\{\|S\|\}\\\}is a multiset of\|S\|\|S\|i\.i\.d\. uniform samples fromGG\. ThenΠG\\Pi\_\{G\}is theL2​\(𝒳\)L^\{2\}\(\\mathcal\{X\}\)\-orthogonal projector fromℱ\\mathcal\{F\}onto the invariant subspaceℱG:=\{f∈ℱ:Tg​f=f​∀g∈G\}\\mathcal\{F\}^\{G\}:=\\\{f\\in\\mathcal\{F\}:T\_\{g\}f=f\\ \\forall g\\in G\\\}\.

Fix anyδ∈\(0,1\)\\delta\\in\(0,1\)and any radiusB\>0B\>0\. With probability at least1−δ1\-\\deltaover the draw ofSS, the following holds*simultaneously for all*f∈ℱf\\in\\mathcal\{F\}with‖f‖L2​\(𝒳\)≤B\\\|f\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}\\leq B:

‖ΠS​f−ΠG​f‖L2​\(𝒳\)≤‖ΠS−ΠG‖op​‖f‖L2​\(𝒳\)≤C​B​log⁡\(min⁡\{r,\|G\|\}/δ\)\|S\|,\\\|\\Pi\_\{S\}f\-\\Pi\_\{G\}f\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}\\;\\leq\\;\\\|\\Pi\_\{S\}\-\\Pi\_\{G\}\\\|\_\{\\mathrm\{op\}\}\\;\\\|f\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}\\;\\leq\\;C\\,B\\,\\sqrt\{\\frac\{\\log\\\!\\big\(\\min\\\{r,\|G\|\\\}/\\delta\\big\)\}\{\|S\|\}\},where∥⋅∥op\\\|\\cdot\\\|\_\{\\mathrm\{op\}\}denotes the operator norm onℱ\\mathcal\{F\}induced by∥⋅∥L2​\(𝒳\)\\\|\\cdot\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}, andC\>0C\>0is a universal constant\. Equivalently,

supf∈ℱ‖f‖L2​\(𝒳\)≤B‖ΠS​f−ΠG​f‖L2​\(𝒳\)≤C​B​log⁡\(min⁡\{r,\|G\|\}/δ\)\|S\|\.\\sup\_\{\\begin\{subarray\}\{c\}f\\in\\mathcal\{F\}\\\\ \\\|f\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}\\leq B\\end\{subarray\}\}\\\|\\Pi\_\{S\}f\-\\Pi\_\{G\}f\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}\\;\\leq\\;C\\,B\\,\\sqrt\{\\frac\{\\log\\\!\\big\(\\min\\\{r,\|G\|\\\}/\\delta\\big\)\}\{\|S\|\}\}\.
In particular, if one performs*partial data augmentation*using the fixed setSSand then applies the corresponding augmentation operatorΠS\\Pi\_\{S\}to any predictorf∈ℱf\\in\\mathcal\{F\}, the augmentation error relative to full augmentation \(i\.e\.,ΠG\\Pi\_\{G\}\) is uniformly controlled as above\.

###### Proof\.

We work on the Hilbert space\(ℱ,⟨⋅,⋅⟩\)\(\\mathcal\{F\},\\langle\\cdot,\\cdot\\rangle\)with theL2​\(𝒳\)L^\{2\}\(\\mathcal\{X\}\)inner product\. Since the action ofGGon\(𝒳,μ\)\(\\mathcal\{X\},\\mu\)is isometric andℱ\\mathcal\{F\}is closed under the induced action, each lifted mapTg:ℱ→ℱT\_\{g\}:\\mathcal\{F\}\\to\\mathcal\{F\}is unitary:

‖Tg​f‖L2​\(𝒳\)=‖f‖L2​\(𝒳\)for all​f∈ℱ,g∈G\.\\\|T\_\{g\}f\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}=\\\|f\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}\\qquad\\text\{for all \}f\\in\\mathcal\{F\},\\ g\\in G\.In particular,‖Tg‖op=1\\\|T\_\{g\}\\\|\_\{\\mathrm\{op\}\}=1and‖ΠS‖op≤1\\\|\\Pi\_\{S\}\\\|\_\{\\mathrm\{op\}\}\\leq 1,‖ΠG‖op≤1\\\|\\Pi\_\{G\}\\\|\_\{\\mathrm\{op\}\}\\leq 1\.

#### Step 1:ΠG\\Pi\_\{G\}is the orthogonal projector ontoℱG\\mathcal\{F\}^\{G\}\.

By definition,ΠG=𝔼g​\[Tg\]\\Pi\_\{G\}=\\mathbb\{E\}\_\{g\}\[T\_\{g\}\]is a bounded linear operator onℱ\\mathcal\{F\}\. For anyh∈ℱGh\\in\\mathcal\{F\}^\{G\}we haveTg​h=hT\_\{g\}h=hfor allgg, henceΠG​h=h\\Pi\_\{G\}h=h\. Conversely, for anyf∈ℱf\\in\\mathcal\{F\}and anyg0∈Gg\_\{0\}\\in G, left\-invariance of the Haar/uniform measure implies

Tg0​ΠG​f=Tg0​𝔼g​\[Tg​f\]=𝔼g​\[Tg0​g​f\]=𝔼g​\[Tg​f\]=ΠG​f,T\_\{g\_\{0\}\}\\Pi\_\{G\}f\\;=\\;T\_\{g\_\{0\}\}\\,\\mathbb\{E\}\_\{g\}\[T\_\{g\}f\]\\;=\\;\\mathbb\{E\}\_\{g\}\[T\_\{g\_\{0\}g\}f\]\\;=\\;\\mathbb\{E\}\_\{g\}\[T\_\{g\}f\]\\;=\\;\\Pi\_\{G\}f,soΠG​f∈ℱG\\Pi\_\{G\}f\\in\\mathcal\{F\}^\{G\}\. Thusrange​\(ΠG\)=ℱG\\mathrm\{range\}\(\\Pi\_\{G\}\)=\\mathcal\{F\}^\{G\}andΠG\\Pi\_\{G\}acts as the identity onℱG\\mathcal\{F\}^\{G\}\. Moreover, since eachTgT\_\{g\}is unitary,ΠG\\Pi\_\{G\}is self\-adjoint:

⟨ΠG​f,h⟩=𝔼g​⟨Tg​f,h⟩=𝔼g​⟨f,Tg−1​h⟩=𝔼g​⟨f,Tg​h⟩=⟨f,ΠG​h⟩,\\langle\\Pi\_\{G\}f,h\\rangle=\\mathbb\{E\}\_\{g\}\\langle T\_\{g\}f,h\\rangle=\\mathbb\{E\}\_\{g\}\\langle f,T\_\{g\}^\{\-1\}h\\rangle=\\mathbb\{E\}\_\{g\}\\langle f,T\_\{g\}h\\rangle=\\langle f,\\Pi\_\{G\}h\\rangle,where we usedTg−1=Tg−1T\_\{g\}^\{\-1\}=T\_\{g^\{\-1\}\}and invariance of the uniform/Haar measure under inversion\. A self\-adjoint idempotent operator is an orthogonal projector, henceΠG\\Pi\_\{G\}is theL2​\(𝒳\)L^\{2\}\(\\mathcal\{X\}\)\-orthogonal projector ontoℱG\\mathcal\{F\}^\{G\}\.

#### Step 2: Uniform control reduces to the operator norm\.

For anyf∈ℱf\\in\\mathcal\{F\},

‖ΠS​f−ΠG​f‖L2​\(𝒳\)≤‖ΠS−ΠG‖op​‖f‖L2​\(𝒳\)\.\\\|\\Pi\_\{S\}f\-\\Pi\_\{G\}f\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}\\;\\leq\\;\\\|\\Pi\_\{S\}\-\\Pi\_\{G\}\\\|\_\{\\mathrm\{op\}\}\\;\\\|f\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}\.Therefore, it suffices to bound‖ΠS−ΠG‖op\\\|\\Pi\_\{S\}\-\\Pi\_\{G\}\\\|\_\{\\mathrm\{op\}\}with high probability\.

#### Step 3: Block decomposition and reduction to nontrivial irreducibles\.

Fix an orthonormal basis ofℱ\\mathcal\{F\}that block\-diagonalizes the unitary representationg↦Tgg\\mapsto T\_\{g\}into irreducible components \(finite\-group harmonic decomposition\):

ℱ≅⨁λ∈G^ℂmλ⊗Vλ,\\mathcal\{F\}\\;\\cong\\;\\bigoplus\_\{\\lambda\\in\\widehat\{G\}\}\\mathbb\{C\}^\{m\_\{\\lambda\}\}\\otimes V\_\{\\lambda\},whereVλV\_\{\\lambda\}is an irreducible representation of dimensiondλd\_\{\\lambda\}\. Under this change of basis, eachTgT\_\{g\}becomes block\-diagonal with blocksImλ⊗ρλ​\(g\)I\_\{m\_\{\\lambda\}\}\\otimes\\rho\_\{\\lambda\}\(g\)\. On the trivial blockλ=triv\\lambda=\\mathrm\{triv\},ρtriv​\(g\)=1\\rho\_\{\\mathrm\{triv\}\}\(g\)=1for allgg, soΠS\\Pi\_\{S\}andΠG\\Pi\_\{G\}coincide \(both equal the identity\) onℱG\\mathcal\{F\}^\{G\}\. Thus

ΠS−ΠG=⨁λ≠triv\(Imλ⊗\(1\|S\|​∑g∈Sρλ​\(g\)\)\),\\Pi\_\{S\}\-\\Pi\_\{G\}\\;=\\;\\bigoplus\_\{\\lambda\\neq\\mathrm\{triv\}\}\\Big\(I\_\{m\_\{\\lambda\}\}\\otimes\\Big\(\\frac\{1\}\{\|S\|\}\\sum\_\{g\\in S\}\\rho\_\{\\lambda\}\(g\)\\Big\)\\Big\),and hence

‖ΠS−ΠG‖op=maxλ≠triv⁡‖1\|S\|​∑g∈Sρλ​\(g\)‖op\.\\\|\\Pi\_\{S\}\-\\Pi\_\{G\}\\\|\_\{\\mathrm\{op\}\}=\\max\_\{\\lambda\\neq\\mathrm\{triv\}\}\\left\\\|\\frac\{1\}\{\|S\|\}\\sum\_\{g\\in S\}\\rho\_\{\\lambda\}\(g\)\\right\\\|\_\{\\mathrm\{op\}\}\.

#### Step 4: Matrix concentration for each nontrivial irreducible block\.

Fixλ≠triv\\lambda\\neq\\mathrm\{triv\}and define i\.i\.d\. random matricesXi:=ρλ​\(gi\)∈ℂdλ×dλX\_\{i\}:=\\rho\_\{\\lambda\}\(g\_\{i\}\)\\in\\mathbb\{C\}^\{d\_\{\\lambda\}\\times d\_\{\\lambda\}\}forgi∼Gg\_\{i\}\\sim G\. Sinceρλ\\rho\_\{\\lambda\}is unitary,‖Xi‖op=1\\\|X\_\{i\}\\\|\_\{\\mathrm\{op\}\}=1\. Moreover,

𝔼​\[Xi\]=𝔼g∼G​\[ρλ​\(g\)\]=0,\\mathbb\{E\}\[X\_\{i\}\]=\\mathbb\{E\}\_\{g\\sim G\}\[\\rho\_\{\\lambda\}\(g\)\]=0,because𝔼g​\[ρλ​\(g\)\]\\mathbb\{E\}\_\{g\}\[\\rho\_\{\\lambda\}\(g\)\]is an intertwiner fromρλ\\rho\_\{\\lambda\}to itself, hence by Schur’s lemma it must be a scalar multiple of the identity; taking traces gives that scalar equals1dλ​𝔼g​\[χλ​\(g\)\]\\frac\{1\}\{d\_\{\\lambda\}\}\\mathbb\{E\}\_\{g\}\[\\chi\_\{\\lambda\}\(g\)\], which is0for any nontrivial irreducible representation\. Therefore,\{Xi\}i=1\|S\|\\\{X\_\{i\}\\\}\_\{i=1\}^\{\|S\|\}are independent, mean\-zero, and satisfy‖Xi‖op≤1\\\|X\_\{i\}\\\|\_\{\\mathrm\{op\}\}\\leq 1\.

By a standard matrix Bernstein inequality \(for sums of independent mean\-zero matrices\), for anyt\>0t\>0,

ℙ​\(‖1\|S\|​∑i=1\|S\|Xi‖op≥t\)≤2​dλ​exp⁡\(−c​\|S\|​t2\),\\mathbb\{P\}\\\!\\left\(\\left\\\|\\frac\{1\}\{\|S\|\}\\sum\_\{i=1\}^\{\|S\|\}X\_\{i\}\\right\\\|\_\{\\mathrm\{op\}\}\\geq t\\right\)\\;\\leq\\;2d\_\{\\lambda\}\\exp\\\!\\Big\(\-c\\,\|S\|\\,t^\{2\}\\Big\),for a universal constantc\>0c\>0\(using the crude variance bound‖𝔼​\[Xi​Xi∗\]‖op≤1\\\|\\mathbb\{E\}\[X\_\{i\}X\_\{i\}^\{\\ast\}\]\\\|\_\{\\mathrm\{op\}\}\\leq 1and similarly forXi∗​XiX\_\{i\}^\{\\ast\}X\_\{i\}\)\. For more details, see\(Tropp,[2012](https://arxiv.org/html/2606.24418#bib.bib33)\)\.

#### Step 5: Union bound over irreducible blocks\.

Taking a union bound over allλ≠triv\\lambda\\neq\\mathrm\{triv\}and using that∑λ∈G^dλ2=\|G\|\\sum\_\{\\lambda\\in\\widehat\{G\}\}d\_\{\\lambda\}^\{2\}=\|G\|\(finite groups\) anddλ≤\|G\|d\_\{\\lambda\}\\leq\\sqrt\{\|G\|\}, we have

ℙ​\(‖ΠS−ΠG‖op≥t\)\\displaystyle\\mathbb\{P\}\\\!\\left\(\\\|\\Pi\_\{S\}\-\\Pi\_\{G\}\\\|\_\{\\mathrm\{op\}\}\\geq t\\right\)≤∑λ≠triv2​dλ​exp⁡\(−c​\|S\|​t2\)\\displaystyle\\leq\\sum\_\{\\lambda\\neq\\mathrm\{triv\}\}2d\_\{\\lambda\}\\exp\(\-c\|S\|t^\{2\}\)\\;≤2​\(∑λ∈G^dλ\)​exp⁡\(−c​\|S\|​t2\)\\displaystyle\\leq\\;2\\Big\(\\sum\_\{\\lambda\\in\\widehat\{G\}\}d\_\{\\lambda\}\\Big\)\\exp\(\-c\|S\|t^\{2\}\)\\;≤2​min⁡\{r,\|G\|\}​exp⁡\(−c​\|S\|​t2\),\\displaystyle\\leq\\;2\\,\\min\\\{r,\|G\|\\\}\\,\\exp\(\-c\|S\|t^\{2\}\),where we used∑λdλ≤∑λdλ2=\|G\|\\sum\_\{\\lambda\}d\_\{\\lambda\}\\leq\\sum\_\{\\lambda\}d\_\{\\lambda\}^\{2\}=\|G\|and also∑λdλ≤r\\sum\_\{\\lambda\}d\_\{\\lambda\}\\leq rsince the total dimension of the representation onℱ\\mathcal\{F\}isrr\.

Choosing

t=C​log⁡\(min⁡\{r,\|G\|\}/δ\)\|S\|t=C\\sqrt\{\\frac\{\\log\(\\min\\\{r,\|G\|\\\}/\\delta\)\}\{\|S\|\}\}for a sufficiently large universal constantC\>0C\>0makes the right\-hand side at mostδ\\delta\. Thus, with probability at least1−δ1\-\\delta,

‖ΠS−ΠG‖op≤C​log⁡\(min⁡\{r,\|G\|\}/δ\)\|S\|\.\\\|\\Pi\_\{S\}\-\\Pi\_\{G\}\\\|\_\{\\mathrm\{op\}\}\\;\\leq\\;C\\sqrt\{\\frac\{\\log\(\\min\\\{r,\|G\|\\\}/\\delta\)\}\{\|S\|\}\}\.

#### Step 6: Conclude the uniform bound over‖f‖≤B\\\|f\\\|\\leq B\.

On this event, for everyf∈ℱf\\in\\mathcal\{F\}with‖f‖L2​\(𝒳\)≤B\\\|f\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}\\leq B,

‖ΠS​f−ΠG​f‖L2​\(𝒳\)≤‖ΠS−ΠG‖op​‖f‖L2​\(𝒳\)≤C​B​log⁡\(2​min⁡\{r,\|G\|\}/δ\)\|S\|,\\\|\\Pi\_\{S\}f\-\\Pi\_\{G\}f\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}\\;\\leq\\;\\\|\\Pi\_\{S\}\-\\Pi\_\{G\}\\\|\_\{\\mathrm\{op\}\}\\,\\\|f\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}\\;\\leq\\;C\\,B\\,\\sqrt\{\\frac\{\\log\(2\\min\\\{r,\|G\|\\\}/\\delta\)\}\{\|S\|\}\},which is exactly the desired statement\. ∎

### A\.10Baseline Excess Risk of Projection Estimators \(No Augmentation\)

LetΠℱ\\Pi\_\{\\mathcal\{F\}\}denote theL2​\(𝒳\)L^\{2\}\(\\mathcal\{X\}\)\-orthogonal projection ontoℱ⊂L2​\(𝒳,μ\)\\mathcal\{F\}\\subset L^\{2\}\(\\mathcal\{X\},\\mu\)\.

###### Lemma A\.3\(Baseline excess risk: density estimation\)\.

Letℱ⊂L2​\(𝒳,μ\)\\mathcal\{F\}\\subset L^\{2\}\(\\mathcal\{X\},\\mu\)berr\-dimensional with orthonormal basis\{ϕℓ\}ℓ=1r\\\{\\phi\_\{\\ell\}\\\}\_\{\\ell=1\}^\{r\}\. Letx1,…,xnx\_\{1\},\\dots,x\_\{n\}be i\.i\.d\. samples drawn from an unknown densityf⋆f^\{\\star\}with respect toμ\\mu, and assumef⋆∈L2​\(𝒳\)∩L∞​\(μ\)f^\{\\star\}\\in L^\{2\}\(\\mathcal\{X\}\)\\cap L^\{\\infty\}\(\\mu\)\. Define

θ^ℓ:=1n​∑i=1nϕℓ​\(xi\),f^:=∑ℓ=1rθ^ℓ​ϕℓ\.\\widehat\{\\theta\}\_\{\\ell\}:=\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\\phi\_\{\\ell\}\(x\_\{i\}\),\\qquad\\widehat\{f\}:=\\sum\_\{\\ell=1\}^\{r\}\\widehat\{\\theta\}\_\{\\ell\}\\,\\phi\_\{\\ell\}\.Then the expected*excess*L2​\(𝒳\)L^\{2\}\(\\mathcal\{X\}\)error overℱ\\mathcal\{F\}satisfies

𝔼​\[‖f^−Πℱ​f⋆‖L2​\(𝒳\)2\]≤‖f⋆‖∞n​r\.\\mathbb\{E\}\\big\[\\\|\\widehat\{f\}\-\\Pi\_\{\\mathcal\{F\}\}f^\{\\star\}\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}\\big\]\\;\\leq\\;\\frac\{\\\|f^\{\\star\}\\\|\_\{\\infty\}\}\{n\}\\,r\.

###### Proof\.

WriteΠℱ​f⋆=∑ℓ=1rθℓ​ϕℓ\\Pi\_\{\\mathcal\{F\}\}f^\{\\star\}=\\sum\_\{\\ell=1\}^\{r\}\\theta\_\{\\ell\}\\phi\_\{\\ell\}withθℓ=⟨f⋆,ϕℓ⟩=𝔼x∼f⋆​\[ϕℓ​\(x\)\]\\theta\_\{\\ell\}=\\langle f^\{\\star\},\\phi\_\{\\ell\}\\rangle=\\mathbb\{E\}\_\{x\\sim f^\{\\star\}\}\[\\phi\_\{\\ell\}\(x\)\]\. By orthonormality,

‖f^−Πℱ​f⋆‖L2​\(𝒳\)2=∑ℓ=1r\(θ^ℓ−θℓ\)2\.\\\|\\widehat\{f\}\-\\Pi\_\{\\mathcal\{F\}\}f^\{\\star\}\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}=\\sum\_\{\\ell=1\}^\{r\}\(\\widehat\{\\theta\}\_\{\\ell\}\-\\theta\_\{\\ell\}\)^\{2\}\.Taking expectation gives

𝔼​\[‖f^−Πℱ​f⋆‖L2​\(𝒳\)2\]=∑ℓ=1rVar​\(θ^ℓ\)\.\\mathbb\{E\}\\big\[\\\|\\widehat\{f\}\-\\Pi\_\{\\mathcal\{F\}\}f^\{\\star\}\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}\\big\]=\\sum\_\{\\ell=1\}^\{r\}\\mathrm\{Var\}\(\\widehat\{\\theta\}\_\{\\ell\}\)\.Sinceθ^ℓ\\widehat\{\\theta\}\_\{\\ell\}is an empirical mean,Var​\(θ^ℓ\)=1n​Varx∼f⋆​\(ϕℓ​\(x\)\)≤1n​𝔼x∼f⋆​\[ϕℓ​\(x\)2\]\\mathrm\{Var\}\(\\widehat\{\\theta\}\_\{\\ell\}\)=\\frac\{1\}\{n\}\\mathrm\{Var\}\_\{x\\sim f^\{\\star\}\}\(\\phi\_\{\\ell\}\(x\)\)\\leq\\frac\{1\}\{n\}\\mathbb\{E\}\_\{x\\sim f^\{\\star\}\}\[\\phi\_\{\\ell\}\(x\)^\{2\}\]\. Moreover,

𝔼x∼f⋆​\[ϕℓ​\(x\)2\]=∫𝒳ϕℓ​\(x\)2​f⋆​\(x\)​𝑑μ​\(x\)≤‖f⋆‖∞​∫𝒳ϕℓ​\(x\)2​𝑑μ​\(x\)=‖f⋆‖∞,\\mathbb\{E\}\_\{x\\sim f^\{\\star\}\}\[\\phi\_\{\\ell\}\(x\)^\{2\}\]=\\int\_\{\\mathcal\{X\}\}\\phi\_\{\\ell\}\(x\)^\{2\}f^\{\\star\}\(x\)\\,d\\mu\(x\)\\leq\\\|f^\{\\star\}\\\|\_\{\\infty\}\\int\_\{\\mathcal\{X\}\}\\phi\_\{\\ell\}\(x\)^\{2\}\\,d\\mu\(x\)=\\\|f^\{\\star\}\\\|\_\{\\infty\},and summing overℓ∈\[r\]\\ell\\in\[r\]yields the claim\. ∎

###### Lemma A\.4\(Baseline excess risk: regression\)\.

Letℱ⊂L2​\(𝒳,μ\)\\mathcal\{F\}\\subset L^\{2\}\(\\mathcal\{X\},\\mu\)berr\-dimensional with orthonormal basis\{ϕℓ\}ℓ=1r\\\{\\phi\_\{\\ell\}\\\}\_\{\\ell=1\}^\{r\}\. Let\(xi,yi\)i=1n\(x\_\{i\},y\_\{i\}\)\_\{i=1\}^\{n\}be i\.i\.d\. samples wherexi∼μx\_\{i\}\\sim\\muand

yi=f⋆​\(xi\)\+εi,𝔼​\[εi\]=0,𝔼​\[εi2\]=σ2,y\_\{i\}=f^\{\\star\}\(x\_\{i\}\)\+\\varepsilon\_\{i\},\\qquad\\mathbb\{E\}\[\\varepsilon\_\{i\}\]=0,\\qquad\\mathbb\{E\}\[\\varepsilon\_\{i\}^\{2\}\]=\\sigma^\{2\},withεi\\varepsilon\_\{i\}independent ofxix\_\{i\}\. Assumef⋆∈L2​\(𝒳\)∩L∞​\(μ\)f^\{\\star\}\\in L^\{2\}\(\\mathcal\{X\}\)\\cap L^\{\\infty\}\(\\mu\)\. Define

β^ℓ:=1n​∑i=1nyi​ϕℓ​\(xi\),f^:=∑ℓ=1rβ^ℓ​ϕℓ\.\\widehat\{\\beta\}\_\{\\ell\}:=\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}y\_\{i\}\\,\\phi\_\{\\ell\}\(x\_\{i\}\),\\qquad\\widehat\{f\}:=\\sum\_\{\\ell=1\}^\{r\}\\widehat\{\\beta\}\_\{\\ell\}\\,\\phi\_\{\\ell\}\.Then the expected*excess*L2​\(𝒳\)L^\{2\}\(\\mathcal\{X\}\)error overℱ\\mathcal\{F\}satisfies

𝔼​\[‖f^−Πℱ​f⋆‖L2​\(𝒳\)2\]≤‖f⋆‖∞2\+σ2n​r\.\\mathbb\{E\}\\big\[\\\|\\widehat\{f\}\-\\Pi\_\{\\mathcal\{F\}\}f^\{\\star\}\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}\\big\]\\;\\leq\\;\\frac\{\\\|f^\{\\star\}\\\|\_\{\\infty\}^\{2\}\+\\sigma^\{2\}\}\{n\}\\,r\.Equivalently, for the squared\-loss population riskR​\(f\):=𝔼​\[\(y−f​\(x\)\)2\]R\(f\):=\\mathbb\{E\}\[\(y\-f\(x\)\)^\{2\}\],

𝔼​\[R​\(f^\)−inff∈ℱR​\(f\)\]=𝔼​\[‖f^−Πℱ​f⋆‖L2​\(𝒳\)2\]≤‖f⋆‖∞2\+σ2n​r\.\\mathbb\{E\}\\big\[R\(\\widehat\{f\}\)\-\\inf\_\{f\\in\\mathcal\{F\}\}R\(f\)\\big\]\\;=\\;\\mathbb\{E\}\\big\[\\\|\\widehat\{f\}\-\\Pi\_\{\\mathcal\{F\}\}f^\{\\star\}\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}\\big\]\\;\\leq\\;\\frac\{\\\|f^\{\\star\}\\\|\_\{\\infty\}^\{2\}\+\\sigma^\{2\}\}\{n\}\\,r\.

###### Proof\.

LetΠℱ​f⋆=∑ℓ=1rβℓ​ϕℓ\\Pi\_\{\\mathcal\{F\}\}f^\{\\star\}=\\sum\_\{\\ell=1\}^\{r\}\\beta\_\{\\ell\}\\phi\_\{\\ell\}, where

βℓ=⟨f⋆,ϕℓ⟩L2​\(𝒳\)=𝔼x∼μ​\[f⋆​\(x\)​ϕℓ​\(x\)\]=𝔼​\[y​ϕℓ​\(x\)\]\.\\beta\_\{\\ell\}=\\langle f^\{\\star\},\\phi\_\{\\ell\}\\rangle\_\{L^\{2\}\(\\mathcal\{X\}\)\}=\\mathbb\{E\}\_\{x\\sim\\mu\}\[f^\{\\star\}\(x\)\\phi\_\{\\ell\}\(x\)\]=\\mathbb\{E\}\[y\\,\\phi\_\{\\ell\}\(x\)\]\.As before,

‖f^−Πℱ​f⋆‖L2​\(𝒳\)2=∑ℓ=1r\(β^ℓ−βℓ\)2,𝔼​\[‖f^−Πℱ​f⋆‖L2​\(𝒳\)2\]=∑ℓ=1rVar​\(β^ℓ\)\.\\\|\\widehat\{f\}\-\\Pi\_\{\\mathcal\{F\}\}f^\{\\star\}\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}=\\sum\_\{\\ell=1\}^\{r\}\(\\widehat\{\\beta\}\_\{\\ell\}\-\\beta\_\{\\ell\}\)^\{2\},\\qquad\\mathbb\{E\}\\big\[\\\|\\widehat\{f\}\-\\Pi\_\{\\mathcal\{F\}\}f^\{\\star\}\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}\\big\]=\\sum\_\{\\ell=1\}^\{r\}\\mathrm\{Var\}\(\\widehat\{\\beta\}\_\{\\ell\}\)\.Sinceβ^ℓ\\widehat\{\\beta\}\_\{\\ell\}is an empirical mean,Var​\(β^ℓ\)=1n​Var​\(y​ϕℓ​\(x\)\)≤1n​𝔼​\[y2​ϕℓ​\(x\)2\]\\mathrm\{Var\}\(\\widehat\{\\beta\}\_\{\\ell\}\)=\\frac\{1\}\{n\}\\mathrm\{Var\}\(y\\phi\_\{\\ell\}\(x\)\)\\leq\\frac\{1\}\{n\}\\mathbb\{E\}\[y^\{2\}\\phi\_\{\\ell\}\(x\)^\{2\}\]\. Moreover, using𝔼​\[y2∣x\]=f⋆​\(x\)2\+σ2\\mathbb\{E\}\[y^\{2\}\\mid x\]=f^\{\\star\}\(x\)^\{2\}\+\\sigma^\{2\},

𝔼​\[y2​ϕℓ​\(x\)2\]=𝔼x∼μ​\[\(f⋆​\(x\)2\+σ2\)​ϕℓ​\(x\)2\]≤\(‖f⋆‖∞2\+σ2\)​𝔼x∼μ​\[ϕℓ​\(x\)2\]=‖f⋆‖∞2\+σ2,\\mathbb\{E\}\[y^\{2\}\\phi\_\{\\ell\}\(x\)^\{2\}\]=\\mathbb\{E\}\_\{x\\sim\\mu\}\[\(f^\{\\star\}\(x\)^\{2\}\+\\sigma^\{2\}\)\\phi\_\{\\ell\}\(x\)^\{2\}\]\\leq\(\\\|f^\{\\star\}\\\|\_\{\\infty\}^\{2\}\+\\sigma^\{2\}\)\\,\\mathbb\{E\}\_\{x\\sim\\mu\}\[\\phi\_\{\\ell\}\(x\)^\{2\}\]=\\\|f^\{\\star\}\\\|\_\{\\infty\}^\{2\}\+\\sigma^\{2\},and summing overℓ∈\[r\]\\ell\\in\[r\]gives the stated bound\.

Finally, for squared lossR​\(f\)=𝔼​\[\(y−f​\(x\)\)2\]R\(f\)=\\mathbb\{E\}\[\(y\-f\(x\)\)^\{2\}\]withy=f⋆​\(x\)\+εy=f^\{\\star\}\(x\)\+\\varepsilonand𝔼​\[ε∣x\]=0\\mathbb\{E\}\[\\varepsilon\\mid x\]=0, one has the standard identity

R​\(f\)−R​\(Πℱ​f⋆\)=‖f−Πℱ​f⋆‖L2​\(𝒳\)2,R\(f\)\-R\(\\Pi\_\{\\mathcal\{F\}\}f^\{\\star\}\)=\\\|f\-\\Pi\_\{\\mathcal\{F\}\}f^\{\\star\}\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\},which yields the excess\-risk equality\. ∎

## Appendix BProof of Theorem[4\.1](https://arxiv.org/html/2606.24418#S4.Thmtheorem1)

###### Proof\.

We work with theL2​\(𝒳\)L^\{2\}\(\\mathcal\{X\}\)inner product\. Sinceℱ\\mathcal\{F\}is closed under the group action and the action is isometric, the averaged operatorΠG:=𝔼g​\[Tg\]\\Pi\_\{G\}:=\\mathbb\{E\}\_\{g\}\[T\_\{g\}\]is the orthogonal projector ontoℱG\\mathcal\{F\}^\{G\}\. LetΠℱ\\Pi\_\{\\mathcal\{F\}\}denote theL2​\(𝒳\)L^\{2\}\(\\mathcal\{X\}\)\-orthogonal projection ontoℱ⊂L2​\(𝒳,μ\)\\mathcal\{F\}\\subset L^\{2\}\(\\mathcal\{X\},\\mu\), and similarly defineΠℱG\\Pi\_\{\\mathcal\{F\}^\{G\}\}\. Hence for anyh∈ℱh\\in\\mathcal\{F\},ΠG​h=ΠℱG​h\\Pi\_\{G\}h=\\Pi\_\{\\mathcal\{F\}^\{G\}\}h, and in particularΠG​\(Πℱ​f⋆\)=ΠℱG​f⋆\\Pi\_\{G\}\(\\Pi\_\{\\mathcal\{F\}\}f^\{\\star\}\)=\\Pi\_\{\\mathcal\{F\}^\{G\}\}f^\{\\star\}\.

#### Step 1: Define an intermediate target inℱ\\mathcal\{F\}\.

Let

fℱ:=Πℱ​f⋆∈ℱ,finv:=ΠℱG​f⋆=ΠG​fℱ∈ℱG\.f\_\{\\mathcal\{F\}\}\\;:=\\;\\Pi\_\{\\mathcal\{F\}\}f^\{\\star\}\\in\\mathcal\{F\},\\qquad f\_\{\\mathrm\{inv\}\}\\;:=\\;\\Pi\_\{\\mathcal\{F\}^\{G\}\}f^\{\\star\}=\\Pi\_\{G\}f\_\{\\mathcal\{F\}\}\\in\\mathcal\{F\}^\{G\}\.We will bound the excess risk‖f^S−finv‖L2​\(𝒳\)2\\\|\\widehat\{f\}\_\{S\}\-f\_\{\\mathrm\{inv\}\}\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}\.

#### Step 2: Estimation inside the invariant subspace\.

Consider the ideal estimator that uses*full*group averaging \(equivalently, projects ontoℱG\\mathcal\{F\}^\{G\}with respect toμ\\mu\)\. Denote it byf^inv\\widehat\{f\}\_\{\\mathrm\{inv\}\}\. By Lemma[A\.3](https://arxiv.org/html/2606.24418#A1.Thmtheorem3)applied to therinvr\_\{\\mathrm\{inv\}\}\-dimensional spaceℱG\\mathcal\{F\}^\{G\}\(with its orthonormal basis\),

𝔼​\[‖f^inv−finv‖L2​\(𝒳\)2\]≤‖f⋆‖∞n​rinv\\mathbb\{E\}\\big\[\\\|\\widehat\{f\}\_\{\\mathrm\{inv\}\}\-f\_\{\\mathrm\{inv\}\}\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}\\big\]\\;\\leq\\;\\frac\{\\\|f^\{\\star\}\\\|\_\{\\infty\}\}\{n\}\\,r\_\{\\mathrm\{inv\}\}in the density estimation setting\. In the regression setting, the analogous bound follows from Lemma[A\.4](https://arxiv.org/html/2606.24418#A1.Thmtheorem4):

𝔼​\[‖f^inv−finv‖L2​\(𝒳\)2\]≤‖f⋆‖∞2\+σ2n​rinv\.\\mathbb\{E\}\\big\[\\\|\\widehat\{f\}\_\{\\mathrm\{inv\}\}\-f\_\{\\mathrm\{inv\}\}\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}\\big\]\\;\\leq\\;\\frac\{\\\|f^\{\\star\}\\\|\_\{\\infty\}^\{2\}\+\\sigma^\{2\}\}\{n\}\\,r\_\{\\mathrm\{inv\}\}\.

#### Step 3: Replacing full averaging by averaging overSS\.

LetΠS:=1\|S\|​∑g∈STg\\Pi\_\{S\}:=\\frac\{1\}\{\|S\|\}\\sum\_\{g\\in S\}T\_\{g\}denote the empirical averaging operator\. By the construction of the augmented projection estimator and linearity, we may write

f^S=ΠS​f^,f^inv=ΠG​f^,\\widehat\{f\}\_\{S\}\\;=\\;\\Pi\_\{S\}\\widehat\{f\},\\qquad\\widehat\{f\}\_\{\\mathrm\{inv\}\}\\;=\\;\\Pi\_\{G\}\\widehat\{f\},for the \(non\-augmented\) projection estimatorf^∈ℱ\\widehat\{f\}\\in\\mathcal\{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](https://arxiv.org/html/2606.24418#A1.SS8)to obtain

𝔼S​\[‖f^S−f^inv‖L2​\(𝒳\)2\|x1:n\]=𝔼S​\[‖\(ΠS−ΠG\)​f^‖L2​\(𝒳\)2\|x1:n\]=1\|S\|​‖f^−ΠG​f^‖L2​\(𝒳\)2\.\\mathbb\{E\}\_\{S\}\\big\[\\\|\\widehat\{f\}\_\{S\}\-\\widehat\{f\}\_\{\\mathrm\{inv\}\}\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}\\,\\big\|\\,x\_\{1:n\}\\big\]=\\mathbb\{E\}\_\{S\}\\big\[\\\|\(\\Pi\_\{S\}\-\\Pi\_\{G\}\)\\widehat\{f\}\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}\\,\\big\|\\,x\_\{1:n\}\\big\]=\\frac\{1\}\{\|S\|\}\\,\\\|\\widehat\{f\}\-\\Pi\_\{G\}\\widehat\{f\}\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}\.Taking expectation over the base data and usingΠG=ΠℱG\\Pi\_\{G\}=\\Pi\_\{\\mathcal\{F\}^\{G\}\}onℱ\\mathcal\{F\}, we obtain

𝔼​\[‖f^S−f^inv‖L2​\(𝒳\)2\]=1\|S\|​𝔼​\[‖f^−ΠℱG​f^‖L2​\(𝒳\)2\]\.\\mathbb\{E\}\\big\[\\\|\\widehat\{f\}\_\{S\}\-\\widehat\{f\}\_\{\\mathrm\{inv\}\}\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}\\big\]=\\frac\{1\}\{\|S\|\}\\mathbb\{E\}\\big\[\\\|\\widehat\{f\}\-\\Pi\_\{\\mathcal\{F\}^\{G\}\}\\widehat\{f\}\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}\\big\]\.Sincefℱ∈ℱGf\_\{\\mathcal\{F\}\}\\in\\mathcal\{F\}^\{G\}, we have

\(I−ΠℱG\)​fℱ=0\.\(I\-\\Pi\_\{\\mathcal\{F\}^\{G\}\}\)f\_\{\\mathcal\{F\}\}=0\.Therefore,

f^−ΠℱG​f^=\(I−ΠℱG\)​f^=\(I−ΠℱG\)​\(f^−fℱ\)\.\\widehat\{f\}\-\\Pi\_\{\\mathcal\{F\}^\{G\}\}\\widehat\{f\}=\(I\-\\Pi\_\{\\mathcal\{F\}^\{G\}\}\)\\widehat\{f\}=\(I\-\\Pi\_\{\\mathcal\{F\}^\{G\}\}\)\(\\widehat\{f\}\-f\_\{\\mathcal\{F\}\}\)\.SinceI−ΠℱGI\-\\Pi\_\{\\mathcal\{F\}^\{G\}\}is an orthogonal projector, it is non\-expansive inL2​\(𝒳\)L^\{2\}\(\\mathcal\{X\}\)\. Hence

‖f^−ΠℱG​f^‖L2​\(𝒳\)2≤‖f^−fℱ‖L2​\(𝒳\)2\.\\\|\\widehat\{f\}\-\\Pi\_\{\\mathcal\{F\}^\{G\}\}\\widehat\{f\}\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}\\leq\\\|\\widehat\{f\}\-f\_\{\\mathcal\{F\}\}\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}\.Consequently,

𝔼​\[‖f^S−f^inv‖L2​\(𝒳\)2\]≤1\|S\|​𝔼​\[‖f^−fℱ‖L2​\(𝒳\)2\]\.\\mathbb\{E\}\\big\[\\\|\\widehat\{f\}\_\{S\}\-\\widehat\{f\}\_\{\\mathrm\{inv\}\}\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}\\big\]\\leq\\frac\{1\}\{\|S\|\}\\mathbb\{E\}\\big\[\\\|\\widehat\{f\}\-f\_\{\\mathcal\{F\}\}\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}\\big\]\.By Lemma[A\.3](https://arxiv.org/html/2606.24418#A1.Thmtheorem3)in the density\-estimation setting, and by Lemma[A\.4](https://arxiv.org/html/2606.24418#A1.Thmtheorem4)in the regression setting,

𝔼​\[‖f^−fℱ‖L2​\(𝒳\)2\]≲rn\.\\mathbb\{E\}\\big\[\\\|\\widehat\{f\}\-f\_\{\\mathcal\{F\}\}\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}\\big\]\\lesssim\\frac\{r\}\{n\}\.Therefore,

𝔼​\[‖f^S−f^inv‖L2​\(𝒳\)2\]≲rn​\|S\|\.\\mathbb\{E\}\\big\[\\\|\\widehat\{f\}\_\{S\}\-\\widehat\{f\}\_\{\\mathrm\{inv\}\}\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}\\big\]\\lesssim\\frac\{r\}\{n\|S\|\}\.

#### Step 4: Combine errors\.

Finally, by the inequality‖a\+b‖2≤2​‖a‖2\+2​‖b‖2\\\|a\+b\\\|^\{2\}\\leq 2\\\|a\\\|^\{2\}\+2\\\|b\\\|^\{2\},

𝔼​\[‖f^S−finv‖L2​\(𝒳\)2\]≤2​𝔼​\[‖f^S−f^inv‖L2​\(𝒳\)2\]\+2​𝔼​\[‖f^inv−finv‖L2​\(𝒳\)2\]\.\\mathbb\{E\}\\big\[\\\|\\widehat\{f\}\_\{S\}\-f\_\{\\mathrm\{inv\}\}\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}\\big\]\\leq 2\\,\\mathbb\{E\}\\big\[\\\|\\widehat\{f\}\_\{S\}\-\\widehat\{f\}\_\{\\mathrm\{inv\}\}\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}\\big\]\+2\\,\\mathbb\{E\}\\big\[\\\|\\widehat\{f\}\_\{\\mathrm\{inv\}\}\-f\_\{\\mathrm\{inv\}\}\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}\\big\]\.Substituting the bounds from Steps 2–3 yields, for density estimation,

𝔼​\[‖f^S−ΠℱG​f⋆‖L2​\(𝒳\)2\]≲‖f⋆‖∞n​rinv\+rn​\|S\|\.\\mathbb\{E\}\\big\[\\\|\\widehat\{f\}\_\{S\}\-\\Pi\_\{\\mathcal\{F\}^\{G\}\}f^\{\\star\}\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}\\big\]\\lesssim\\frac\{\\\|f^\{\\star\}\\\|\_\{\\infty\}\}\{n\}\\,r\_\{\\mathrm\{inv\}\}\+\\frac\{r\}\{n\|S\|\}\.Similarly, in the regression setting with additive zero\-mean noise of varianceσ2\\sigma^\{2\}, we obtain

𝔼​\[‖f^S−ΠℱG​f⋆‖L2​\(𝒳\)2\]≲‖f⋆‖∞2\+σ2n​rinv\+rn​\|S\|\.\\mathbb\{E\}\\big\[\\\|\\widehat\{f\}\_\{S\}\-\\Pi\_\{\\mathcal\{F\}^\{G\}\}f^\{\\star\}\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}\\big\]\\lesssim\\frac\{\\\|f^\{\\star\}\\\|\_\{\\infty\}^\{2\}\+\\sigma^\{2\}\}\{n\}\\,r\_\{\\mathrm\{inv\}\}\+\\frac\{r\}\{n\|S\|\}\.Here we used thatfinv=ΠℱG​f⋆f\_\{\\mathrm\{inv\}\}=\\Pi\_\{\\mathcal\{F\}^\{G\}\}f^\{\\star\}, sincefℱ∈ℱGf\_\{\\mathcal\{F\}\}\\in\\mathcal\{F\}^\{G\}under the invariance assumption\. This completes the proof\. ∎

## Appendix CProof of Theorem[4\.3](https://arxiv.org/html/2606.24418#S4.Thmtheorem3)

###### Proof\.

We prove the density\-estimation case; the regression case is identical, with the baseline projection\-estimator bound overℱG\\mathcal\{F\}^\{G\}replaced by the corresponding regression bound\.

#### Step 0: Notation\.

Letf^∈ℱ\\widehat\{f\}\\in\\mathcal\{F\}denote the \(unaugmented\) projection estimator based on the samplesx1,…,xnx\_\{1\},\\dots,x\_\{n\}, and letf^S∈ℱ\\widehat\{f\}\_\{S\}\\in\\mathcal\{F\}denote the projection estimator obtained from the*partially augmented*samples\{g−1​xi:i∈\[n\],g∈S\}\\\{g^\{\-1\}x\_\{i\}:i\\in\[n\],\\,g\\in S\\\}\. As shown in the preliminaries \(closure ofℱ\\mathcal\{F\}under the action and the orthonormal\-basis identification\), partial data augmentation bySScorresponds to applying the averaging operatorΠS:=1\|S\|​∑g∈STg\\Pi\_\{S\}:=\\frac\{1\}\{\|S\|\}\\sum\_\{g\\in S\}T\_\{g\}to the \(unaugmented\) coefficient vector\. Equivalently, at the function level,

f^S=ΠS​f^,\\widehat\{f\}\_\{S\}\\;=\\;\\Pi\_\{S\}\\widehat\{f\},\(1\)whereTgT\_\{g\}denotes the lifted unitary action onℱ\\mathcal\{F\}\. Moreover, the full\-group averaging operatorΠG:=𝔼g∼G​\[Tg\]\\Pi\_\{G\}:=\\mathbb\{E\}\_\{g\\sim G\}\[T\_\{g\}\]is theL2​\(𝒳\)L^\{2\}\(\\mathcal\{X\}\)\-orthogonal projector ontoℱG\\mathcal\{F\}^\{G\}\.

#### Step 1: Decompose the excess error\.

Letfinv:=ΠℱG​f⋆f\_\{\\mathrm\{inv\}\}:=\\Pi\_\{\\mathcal\{F\}^\{G\}\}f^\{\\star\}\. Under the invariance assumption,fℱ:=Πℱ​f⋆f\_\{\\mathcal\{F\}\}:=\\Pi\_\{\\mathcal\{F\}\}f^\{\\star\}belongs toℱG\\mathcal\{F\}^\{G\}, and hencefinv=fℱf\_\{\\mathrm\{inv\}\}=f\_\{\\mathcal\{F\}\}\. Usingf^S=ΠS​f^\\widehat\{f\}\_\{S\}=\\Pi\_\{S\}\\widehat\{f\}from Equation \([1](https://arxiv.org/html/2606.24418#A3.E1)\) and adding and subtractingΠG​f^\\Pi\_\{G\}\\widehat\{f\}, we have

f^S−finv=\(ΠS​f^−ΠG​f^\)\+\(ΠG​f^−finv\)\.\\widehat\{f\}\_\{S\}\-f\_\{\\mathrm\{inv\}\}=\\big\(\\Pi\_\{S\}\\widehat\{f\}\-\\Pi\_\{G\}\\widehat\{f\}\\big\)\+\\big\(\\Pi\_\{G\}\\widehat\{f\}\-f\_\{\\mathrm\{inv\}\}\\big\)\.Therefore, by‖a\+b‖2≤2​‖a‖2\+2​‖b‖2\\\|a\+b\\\|^\{2\}\\leq 2\\\|a\\\|^\{2\}\+2\\\|b\\\|^\{2\},

‖f^S−finv‖L2​\(𝒳\)2≤2​‖\(ΠS−ΠG\)​f^‖L2​\(𝒳\)2\+2​‖ΠG​f^−finv‖L2​\(𝒳\)2\.\\\|\\widehat\{f\}\_\{S\}\-f\_\{\\mathrm\{inv\}\}\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}\\leq 2\\\|\(\\Pi\_\{S\}\-\\Pi\_\{G\}\)\\widehat\{f\}\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}\+2\\\|\\Pi\_\{G\}\\widehat\{f\}\-f\_\{\\mathrm\{inv\}\}\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}\.\(2\)

#### Step 2: Control the partial\-augmentation error via the operator norm\.

We first use the invariance offℱf\_\{\\mathcal\{F\}\}to center the partial\-augmentation error around the baseline estimation error\. Sincefℱ∈ℱGf\_\{\\mathcal\{F\}\}\\in\\mathcal\{F\}^\{G\}, we have

ΠS​fℱ=fℱ,ΠG​fℱ=fℱ\.\\Pi\_\{S\}f\_\{\\mathcal\{F\}\}=f\_\{\\mathcal\{F\}\},\\qquad\\Pi\_\{G\}f\_\{\\mathcal\{F\}\}=f\_\{\\mathcal\{F\}\}\.Hence

\(ΠS−ΠG\)​fℱ=0,\(\\Pi\_\{S\}\-\\Pi\_\{G\}\)f\_\{\\mathcal\{F\}\}=0,and therefore

\(ΠS−ΠG\)​f^=\(ΠS−ΠG\)​\(f^−fℱ\)\.\(\\Pi\_\{S\}\-\\Pi\_\{G\}\)\\widehat\{f\}=\(\\Pi\_\{S\}\-\\Pi\_\{G\}\)\(\\widehat\{f\}\-f\_\{\\mathcal\{F\}\}\)\.Consequently,

‖\(ΠS−ΠG\)​f^‖L2​\(𝒳\)2≤‖ΠS−ΠG‖op2​‖f^−fℱ‖L2​\(𝒳\)2\.\\\|\(\\Pi\_\{S\}\-\\Pi\_\{G\}\)\\widehat\{f\}\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}\\leq\\\|\\Pi\_\{S\}\-\\Pi\_\{G\}\\\|\_\{\\mathrm\{op\}\}^\{2\}\\\|\\widehat\{f\}\-f\_\{\\mathcal\{F\}\}\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}\.\(3\)
By Theorem[A\.2](https://arxiv.org/html/2606.24418#A1.Thmtheorem2), for anyδ∈\(0,1\)\\delta\\in\(0,1\), with probability at least1−δ1\-\\deltaover the draw ofSS,

‖ΠS−ΠG‖op2≤C0​log⁡\(min⁡\{r,\|G\|\}/δ\)\|S\|\\\|\\Pi\_\{S\}\-\\Pi\_\{G\}\\\|\_\{\\mathrm\{op\}\}^\{2\}\\leq C\_\{0\}\\,\\frac\{\\log\\\!\\big\(\\min\\\{r,\|G\|\\\}/\\delta\\big\)\}\{\|S\|\}\(4\)for a universal constantC0\>0C\_\{0\}\>0\. Combining Equations \([3](https://arxiv.org/html/2606.24418#A3.E3)\) and \([4](https://arxiv.org/html/2606.24418#A3.E4)\), on the same event,

‖\(ΠS−ΠG\)​f^‖L2​\(𝒳\)2≤C0​log⁡\(min⁡\{r,\|G\|\}/δ\)\|S\|​‖f^−fℱ‖L2​\(𝒳\)2\.\\\|\(\\Pi\_\{S\}\-\\Pi\_\{G\}\)\\widehat\{f\}\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}\\leq C\_\{0\}\\,\\frac\{\\log\\\!\\big\(\\min\\\{r,\|G\|\\\}/\\delta\\big\)\}\{\|S\|\}\\\|\\widehat\{f\}\-f\_\{\\mathcal\{F\}\}\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}\.\(5\)

#### Step 3: Baseline estimation inside the invariant subspace\.

SinceΠG\\Pi\_\{G\}is the orthogonal projector ontoℱG\\mathcal\{F\}^\{G\}, andfinv=fℱ∈ℱGf\_\{\\mathrm\{inv\}\}=f\_\{\\mathcal\{F\}\}\\in\\mathcal\{F\}^\{G\}, we have

ΠG​f^−finv=ΠG​\(f^−fℱ\)\.\\Pi\_\{G\}\\widehat\{f\}\-f\_\{\\mathrm\{inv\}\}=\\Pi\_\{G\}\(\\widehat\{f\}\-f\_\{\\mathcal\{F\}\}\)\.Thus, by non\-expansiveness of the orthogonal projectorΠG\\Pi\_\{G\},

‖ΠG​f^−finv‖L2​\(𝒳\)2≤‖f^−fℱ‖L2​\(𝒳\)2\.\\\|\\Pi\_\{G\}\\widehat\{f\}\-f\_\{\\mathrm\{inv\}\}\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}\\leq\\\|\\widehat\{f\}\-f\_\{\\mathcal\{F\}\}\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}\.Moreover, the refined invariant projection\-estimator bound from Step 2 of the proof gives, in the density\-estimation setting,

𝔼​\[‖ΠG​f^−finv‖L2​\(𝒳\)2\]≤C1​‖f⋆‖∞n​rinv\.\\mathbb\{E\}\\big\[\\\|\\Pi\_\{G\}\\widehat\{f\}\-f\_\{\\mathrm\{inv\}\}\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}\\big\]\\leq C\_\{1\}\\,\\frac\{\\\|f^\{\\star\}\\\|\_\{\\infty\}\}\{n\}\\,r\_\{\\mathrm\{inv\}\}\.\(6\)In the regression setting with additive zero\-mean noise of varianceσ2\\sigma^\{2\}, the same argument gives

𝔼​\[‖ΠG​f^−finv‖L2​\(𝒳\)2\]≤C1​‖f⋆‖∞2\+σ2n​rinv\.\\mathbb\{E\}\\big\[\\\|\\Pi\_\{G\}\\widehat\{f\}\-f\_\{\\mathrm\{inv\}\}\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}\\big\]\\leq C\_\{1\}\\,\\frac\{\\\|f^\{\\star\}\\\|\_\{\\infty\}^\{2\}\+\\sigma^\{2\}\}\{n\}\\,r\_\{\\mathrm\{inv\}\}\.

#### Step 4: Take conditional expectation over the data\.

Taking conditional expectation of \([2](https://arxiv.org/html/2606.24418#A3.E2)\) givenSS, and using Equation \([5](https://arxiv.org/html/2606.24418#A3.E5)\), we obtain, on the event in Equation \([4](https://arxiv.org/html/2606.24418#A3.E4)\),

𝔼​\[‖f^S−finv‖L2​\(𝒳\)2\|S\]\\displaystyle\\mathbb\{E\}\\Big\[\\\|\\widehat\{f\}\_\{S\}\-f\_\{\\mathrm\{inv\}\}\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}\\,\\Big\|\\,S\\Big\]≤2​C0​log⁡\(min⁡\{r,\|G\|\}/δ\)\|S\|​𝔼​\[‖f^−fℱ‖L2​\(𝒳\)2\]\\displaystyle\\leq 2C\_\{0\}\\,\\frac\{\\log\\\!\\big\(\\min\\\{r,\|G\|\\\}/\\delta\\big\)\}\{\|S\|\}\\mathbb\{E\}\\big\[\\\|\\widehat\{f\}\-f\_\{\\mathcal\{F\}\}\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}\\big\]\+2​𝔼​\[‖ΠG​f^−finv‖L2​\(𝒳\)2\]\.\\displaystyle\\qquad\+2\\,\\mathbb\{E\}\\big\[\\\|\\Pi\_\{G\}\\widehat\{f\}\-f\_\{\\mathrm\{inv\}\}\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}\\big\]\.By Lemma[A\.3](https://arxiv.org/html/2606.24418#A1.Thmtheorem3), the baseline projection estimator satisfies

𝔼​\[‖f^−fℱ‖L2​\(𝒳\)2\]≤C2​‖f⋆‖∞n​r\\mathbb\{E\}\\big\[\\\|\\widehat\{f\}\-f\_\{\\mathcal\{F\}\}\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}\\big\]\\leq C\_\{2\}\\,\\frac\{\\\|f^\{\\star\}\\\|\_\{\\infty\}\}\{n\}\\,rin the density\-estimation setting\. Combining this with Equation \([6](https://arxiv.org/html/2606.24418#A3.E6)\) gives

𝔼\[∥f^S−ΠℱGf⋆∥L2​\(𝒳\)2\|S\]≤C∥f⋆∥∞\(rinvn\+r​log⁡\(min⁡\{r,\|G\|\}/δ\)n​\|S\|\)\.\\mathbb\{E\}\\\!\\left\[\\big\\\|\\widehat\{f\}\_\{S\}\-\\Pi\_\{\\mathcal\{F\}^\{G\}\}f^\{\\star\}\\big\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}\\;\\middle\|\\;S\\right\]\\leq C\\\|f^\{\\star\}\\\|\_\{\\infty\}\\left\(\\frac\{r\_\{\\mathrm\{inv\}\}\}\{n\}\+\\frac\{r\\,\\log\\\!\\big\(\\min\\\{r,\|G\|\\\}/\\delta\\big\)\}\{n\|S\|\}\\right\)\.Similarly, in the regression setting with additive zero\-mean noise of varianceσ2\\sigma^\{2\}, Lemma[A\.4](https://arxiv.org/html/2606.24418#A1.Thmtheorem4)yields

𝔼​\[‖f^−fℱ‖L2​\(𝒳\)2\]≤C2​‖f⋆‖∞2\+σ2n​r,\\mathbb\{E\}\\big\[\\\|\\widehat\{f\}\-f\_\{\\mathcal\{F\}\}\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}\\big\]\\leq C\_\{2\}\\,\\frac\{\\\|f^\{\\star\}\\\|\_\{\\infty\}^\{2\}\+\\sigma^\{2\}\}\{n\}\\,r,and therefore

𝔼\[∥f^S−ΠℱGf⋆∥L2​\(𝒳\)2\|S\]≤C\(∥f⋆∥∞2\+σ2\)\(rinvn\+r​log⁡\(min⁡\{r,\|G\|\}/δ\)n​\|S\|\)\.\\mathbb\{E\}\\\!\\left\[\\big\\\|\\widehat\{f\}\_\{S\}\-\\Pi\_\{\\mathcal\{F\}^\{G\}\}f^\{\\star\}\\big\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}\\;\\middle\|\\;S\\right\]\\leq C\\big\(\\\|f^\{\\star\}\\\|\_\{\\infty\}^\{2\}\+\\sigma^\{2\}\\big\)\\left\(\\frac\{r\_\{\\mathrm\{inv\}\}\}\{n\}\+\\frac\{r\\,\\log\\\!\\big\(\\min\\\{r,\|G\|\\\}/\\delta\\big\)\}\{n\|S\|\}\\right\)\.This completes the proof\. ∎

## Appendix DProof of Theorem[4\.5](https://arxiv.org/html/2606.24418#S4.Thmtheorem5)

We next state the formal version of Theorem[4\.5](https://arxiv.org/html/2606.24418#S4.Thmtheorem5)and provide its proof\.

###### Theorem D\.1\(Exact invariance forces full augmentation\)\.

LetGGbe a finite group and letℱ\\mathcal\{F\}be a finite\-dimensional real \(or complex\) Hilbert space carrying a unitary representationρ:G→U​\(ℱ\)\\rho:G\\to U\(\\mathcal\{F\}\)\. For a multisetS⊆GS\\subseteq G, define the averaging operator

ΠS:=1\|S\|​∑g∈Sρ​\(g\),ΠG:=1\|G\|​∑g∈Gρ​\(g\)\.\\Pi\_\{S\}\\;:=\\;\\frac\{1\}\{\|S\|\}\\sum\_\{g\\in S\}\\rho\(g\),\\qquad\\Pi\_\{G\}\\;:=\\;\\frac\{1\}\{\|G\|\}\\sum\_\{g\\in G\}\\rho\(g\)\.Assumeℱ\\mathcal\{F\}is*representation\-complete*in the sense that every irreducible representation ofGGappears as a subrepresentation ofℱ\\mathcal\{F\}\(equivalently, for everyλ∈G^\\lambda\\in\\widehat\{G\}the multiplicitymλ​\(ℱ\)≥1m\_\{\\lambda\}\(\\mathcal\{F\}\)\\geq 1\)\.

Suppose that partial data augmentation usingSSyields an estimator that is*exactlyGG\-invariant for all inputs*, i\.e\.,

ρ​\(h\)​ΠS=ΠSfor all​h∈G,\\rho\(h\)\\Pi\_\{S\}\\;=\\;\\Pi\_\{S\}\\qquad\\text\{for all \}h\\in G,\(7\)or equivalentlyΠS=ΠG\\Pi\_\{S\}=\\Pi\_\{G\}onℱ\\mathcal\{F\}\.

ThenSSmust be uniform over the whole group in the following sense: if we writeSSas a multiset with multiplicity functionmS:G→ℤ≥0m\_\{S\}:G\\to\\mathbb\{Z\}\_\{\\geq 0\}, then

mS​\(g\)​is constant over​g∈G,m\_\{S\}\(g\)\\ \\text\{is constant over \}g\\in G,and in particularSScontains each group element equally often\. Consequently, ifSSis a*subset*\(no repetitions\), then necessarilyS=GS=G\.

Equivalently, under the representation\-completeness assumption, the conditionΠS=ΠG\\Pi\_\{S\}=\\Pi\_\{G\}holds if and only if the Fourier coefficients of the uniform measure onSSvanish on all nontrivial irreducible representations:

1\|S\|​∑g∈Sρλ​\(g\)=0for all​λ∈G^∖\{triv\},\\frac\{1\}\{\|S\|\}\\sum\_\{g\\in S\}\\rho\_\{\\lambda\}\(g\)=0\\qquad\\text\{for all \}\\lambda\\in\\widehat\{G\}\\setminus\\\{\\mathrm\{triv\}\\\},which forcesSSto be \(multi\)setwise uniform overGG\.

###### Proof\.

LetGGbe a finite group and letρ:G→U​\(ℱ\)\\rho:G\\to U\(\\mathcal\{F\}\)be a unitary representation on the finite\-dimensional Hilbert spaceℱ\\mathcal\{F\}\. By assumption,ℱ\\mathcal\{F\}is representation\-complete, meaning that every irreducible representation ofGGappears with positive multiplicity inℱ\\mathcal\{F\}\.

Recall the averaging operators

ΠS:=1\|S\|​∑g∈Sρ​\(g\),ΠG:=1\|G\|​∑g∈Gρ​\(g\),\\Pi\_\{S\}:=\\frac\{1\}\{\|S\|\}\\sum\_\{g\\in S\}\\rho\(g\),\\qquad\\Pi\_\{G\}:=\\frac\{1\}\{\|G\|\}\\sum\_\{g\\in G\}\\rho\(g\),whereSSis viewed as a multiset\.

#### Irreducible decomposition\.

By the Peter–Weyl theorem for finite groups,ℱ\\mathcal\{F\}admits an orthogonal decomposition into irreducible components

ℱ≅⨁λ∈G^ℂmλ⊗Vλ,\\mathcal\{F\}\\;\\cong\\;\\bigoplus\_\{\\lambda\\in\\widehat\{G\}\}\\mathbb\{C\}^\{m\_\{\\lambda\}\}\\otimes V\_\{\\lambda\},whereVλV\_\{\\lambda\}is an irreducible representation of dimensiondλd\_\{\\lambda\}andmλ≥1m\_\{\\lambda\}\\geq 1by representation\-completeness\. With respect to this decomposition, the representationρ\\rhois block\-diagonal:

ρ​\(g\)=⨁λ∈G^Imλ⊗ρλ​\(g\),\\rho\(g\)\\;=\\;\\bigoplus\_\{\\lambda\\in\\widehat\{G\}\}I\_\{m\_\{\\lambda\}\}\\otimes\\rho\_\{\\lambda\}\(g\),and hence bothΠS\\Pi\_\{S\}andΠG\\Pi\_\{G\}are block\-diagonal as well\.

#### Action of the full group average\.

For the trivial irreducible representationλ=triv\\lambda=\\mathrm\{triv\}, we haveρtriv​\(g\)=1\\rho\_\{\\mathrm\{triv\}\}\(g\)=1for allg∈Gg\\in G, so

ΠG\(triv\)=1\|G\|​∑g∈G1=1\.\\Pi\_\{G\}^\{\(\\mathrm\{triv\}\)\}=\\frac\{1\}\{\|G\|\}\\sum\_\{g\\in G\}1=1\.For any nontrivial irreducible representationλ≠triv\\lambda\\neq\\mathrm\{triv\}, orthogonality of matrix coefficients implies

1\|G\|​∑g∈Gρλ​\(g\)=0\.\\frac\{1\}\{\|G\|\}\\sum\_\{g\\in G\}\\rho\_\{\\lambda\}\(g\)=0\.Therefore,ΠG\\Pi\_\{G\}acts as the identity on the trivial isotypic componentℱG\\mathcal\{F\}^\{G\}and annihilates all nontrivial isotypic components\.

#### Consequences of exact invariance\.

Suppose now thatΠS=ΠG\\Pi\_\{S\}=\\Pi\_\{G\}as operators onℱ\\mathcal\{F\}\. Comparing the action ofΠS\\Pi\_\{S\}andΠG\\Pi\_\{G\}on each irreducible block, we conclude that for every nontrivial irreducible representationλ≠triv\\lambda\\neq\\mathrm\{triv\},

1\|S\|​∑g∈Sρλ​\(g\)=0\.\\frac\{1\}\{\|S\|\}\\sum\_\{g\\in S\}\\rho\_\{\\lambda\}\(g\)=0\.\(8\)

#### Fourier\-analytic interpretation\.

Define the probability measureμS\\mu\_\{S\}onGGby

μS​\(g\):=mS​\(g\)\|S\|,\\mu\_\{S\}\(g\):=\\frac\{m\_\{S\}\(g\)\}\{\|S\|\},wheremS​\(g\)m\_\{S\}\(g\)denotes the multiplicity ofggin the multisetSS\. Equation \([8](https://arxiv.org/html/2606.24418#A4.E8)\) states precisely that the Fourier transform ofμS\\mu\_\{S\}vanishes on all nontrivial irreducible representations:

μS^​\(λ\):=∑g∈GμS​\(g\)​ρλ​\(g\)=0for all​λ≠triv\.\\widehat\{\\mu\_\{S\}\}\(\\lambda\):=\\sum\_\{g\\in G\}\\mu\_\{S\}\(g\)\\rho\_\{\\lambda\}\(g\)=0\\qquad\\text\{for all \}\\lambda\\neq\\mathrm\{triv\}\.
By the Fourier inversion theorem for finite groups, the only probability measure onGGwhose Fourier coefficients vanish on all nontrivial irreducible representations is the uniform measure\. HenceμS​\(g\)=1/\|G\|\\mu\_\{S\}\(g\)=1/\|G\|for allg∈Gg\\in G\.

#### Conclusion\.

Therefore, the multiplicity functionmS​\(g\)m\_\{S\}\(g\)is constant overGG, meaning thatSSis uniform over the group\. In particular, ifSSis a subset without repetitions, this forcesS=GS=G\. This completes the proof\. ∎

## Appendix EExtensions 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 finite\-dimensional truncations of infinite\-dimensional function classes\.

### E\.1Projection Estimators Versus Ordinary Least Squares \(OLS\)

Letℱ\\mathcal\{F\}be anrr\-dimensional subspace ofL2​\(𝒳,μ\)L^\{2\}\(\\mathcal\{X\},\\mu\), and let

ϕ​\(x\)=\(ϕ1​\(x\),…,ϕr​\(x\)\)⊤\\phi\(x\)=\\big\(\\phi\_\{1\}\(x\),\\ldots,\\phi\_\{r\}\(x\)\\big\)^\{\\top\}be an orthonormal basis ofℱ\\mathcal\{F\}\. Forfβ​\(x\)=⟨β,ϕ​\(x\)⟩f\_\{\\beta\}\(x\)=\\langle\\beta,\\phi\(x\)\\rangle, orthonormality gives

‖fβ‖L2​\(𝒳\)2=‖β‖22,𝔼x∼μ​\[ϕ​\(x\)​ϕ​\(x\)⊤\]=Ir\.\\\|f\_\{\\beta\}\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}=\\\|\\beta\\\|\_\{2\}^\{2\},\\qquad\\mathbb\{E\}\_\{x\\sim\\mu\}\\big\[\\phi\(x\)\\phi\(x\)^\{\\top\}\\big\]=I\_\{r\}\.Given data\(xi,yi\)i=1n\(x\_\{i\},y\_\{i\}\)\_\{i=1\}^\{n\}, define

b^:=1n​∑i=1nyi​ϕ​\(xi\),Σ^:=1n​∑i=1nϕ​\(xi\)​ϕ​\(xi\)⊤\.\\widehat\{b\}:=\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}y\_\{i\}\\phi\(x\_\{i\}\),\\qquad\\widehat\{\\Sigma\}:=\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\\phi\(x\_\{i\}\)\\phi\(x\_\{i\}\)^\{\\top\}\.The projection estimator used throughout the paper is

β^proj=b^,f^proj​\(x\)=⟨b^,ϕ​\(x\)⟩\.\\widehat\{\\beta\}\_\{\\mathrm\{proj\}\}=\\widehat\{b\},\\qquad\\widehat\{f\}\_\{\\mathrm\{proj\}\}\(x\)=\\langle\\widehat\{b\},\\phi\(x\)\\rangle\.Thus, the projection estimator replaces the empirical covarianceΣ^\\widehat\{\\Sigma\}by its population valueIrI\_\{r\}\. This is natural in our setting because the samples are drawn fromμ\\mu, and the basis is orthonormal with respect toμ\\mu\.

By contrast, ordinary least squares solves the empirical least\-squares problem

β^ols∈arg⁡minβ∈ℝr⁡1n​∑i=1n\(yi−⟨β,ϕ​\(xi\)⟩\)2\.\\widehat\{\\beta\}\_\{\\mathrm\{ols\}\}\\in\\operatorname\{arg\}\\min\_\{\\beta\\in\\mathbb\{R\}^\{r\}\}\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\\big\(y\_\{i\}\-\\langle\\beta,\\phi\(x\_\{i\}\)\\rangle\\big\)^\{2\}\.Equivalently, it satisfies

Σ^​β^ols=b^⟹β^ols=Σ^†​b^,f^ols​\(x\)=⟨Σ^†​b^,ϕ​\(x\)⟩,\\widehat\{\\Sigma\}\\,\\widehat\{\\beta\}\_\{\\mathrm\{ols\}\}=\\widehat\{b\}\\implies\\widehat\{\\beta\}\_\{\\mathrm\{ols\}\}=\\widehat\{\\Sigma\}^\{\\dagger\}\\widehat\{b\},\\qquad\\widehat\{f\}\_\{\\mathrm\{ols\}\}\(x\)=\\langle\\widehat\{\\Sigma\}^\{\\dagger\}\\widehat\{b\},\\phi\(x\)\\rangle,where†\\daggerdenotes the Moore–Penrose pseudoinverse; ifΣ^\\widehat\{\\Sigma\}is invertible, this reduces toβ^ols=Σ^−1​b^\\widehat\{\\beta\}\_\{\\mathrm\{ols\}\}=\\widehat\{\\Sigma\}^\{\-1\}\\widehat\{b\}\. Finally, letΦ∈ℝn×r\\Phi\\in\\mathbb\{R\}^\{n\\times r\}be the feature matrix with rowsϕ​\(xi\)⊤\\phi\(x\_\{i\}\)^\{\\top\}, and lety=\(y1,…,yn\)⊤y=\(y\_\{1\},\\ldots,y\_\{n\}\)^\{\\top\}\. Then

β^proj=1n​Φ⊤​y,β^ols=\(1n​Φ⊤​Φ\)†​1n​Φ⊤​y=\(Φ⊤​Φ\)†​Φ⊤​y\.\\widehat\{\\beta\}\_\{\\mathrm\{proj\}\}=\\frac\{1\}\{n\}\\Phi^\{\\top\}y,\\qquad\\widehat\{\\beta\}\_\{\\mathrm\{ols\}\}=\\left\(\\frac\{1\}\{n\}\\Phi^\{\\top\}\\Phi\\right\)^\{\\dagger\}\\frac\{1\}\{n\}\\Phi^\{\\top\}y=\(\\Phi^\{\\top\}\\Phi\)^\{\\dagger\}\\Phi^\{\\top\}y\.The difference between the two estimators is therefore exactly the covariance used to map empirical moments to coefficients: OLS uses the empirical covarianceΣ^=\(1/n\)​Φ⊤​Φ\\widehat\{\\Sigma\}=\(1/n\)\\Phi^\{\\top\}\\Phi, whereas the projection estimator uses the population covarianceIrI\_\{r\}\.

We next describe how augmentation enters these formulas\. LetGGact on𝒳\\mathcal\{X\}, and letρ:G→ℝr×r\\rho:G\\to\\mathbb\{R\}^\{r\\times r\}denote the induced representation onℱ\\mathcal\{F\}, defined by

\(ρ​\(g\)​f\)​\(x\)=f​\(g−1​x\)\.\(\\rho\(g\)f\)\(x\)=f\(g^\{\-1\}x\)\.Equivalently, forfβ​\(x\)=⟨β,ϕ​\(x\)⟩f\_\{\\beta\}\(x\)=\\langle\\beta,\\phi\(x\)\\rangle, we writeρ​\(g\)​fβ=fρ​\(g\)​β\\rho\(g\)f\_\{\\beta\}=f\_\{\\rho\(g\)\\beta\}, which implies

ϕ​\(g−1​x\)=ρ​\(g\)⊤​ϕ​\(x\)\.\\phi\(g^\{\-1\}x\)=\\rho\(g\)^\{\\top\}\\phi\(x\)\.For an augmentation setS⊆GS\\subseteq G, the augmented empirical moment vector is

b^S:=1\|S\|​∑s∈Sρ​\(s\)​b^\.\\widehat\{b\}\_\{S\}:=\\frac\{1\}\{\|S\|\}\\sum\_\{s\\in S\}\\rho\(s\)\\widehat\{b\}\.This is exactly the partial averaging operator applied to the coefficient vector:

b^S=ΠS​b^\.\\widehat\{b\}\_\{S\}=\\Pi\_\{S\}\\widehat\{b\}\.Thus, the augmented projection estimator is

β^proj,S=ΠS​b^\.\\widehat\{\\beta\}\_\{\\mathrm\{proj\},S\}=\\Pi\_\{S\}\\widehat\{b\}\.
For ordinary least squares, augmentation also modifies the empirical covariance\. The augmented covariance is

Σ^S:=1\|S\|​∑s∈Sρ​\(s\)​Σ^​ρ​\(s\)⊤\.\\widehat\{\\Sigma\}\_\{S\}:=\\frac\{1\}\{\|S\|\}\\sum\_\{s\\in S\}\\rho\(s\)\\widehat\{\\Sigma\}\\rho\(s\)^\{\\top\}\.Consequently, the augmented least\-squares estimator is

β^ols,S=Σ^S†​b^S=\(1\|S\|​∑s∈Sρ​\(s\)​Σ^​ρ​\(s\)⊤\)†​\(1\|S\|​∑s∈Sρ​\(s\)​b^\)\.\\widehat\{\\beta\}\_\{\\mathrm\{ols\},S\}=\\widehat\{\\Sigma\}\_\{S\}^\{\\dagger\}\\widehat\{b\}\_\{S\}=\\left\(\\frac\{1\}\{\|S\|\}\\sum\_\{s\\in S\}\\rho\(s\)\\widehat\{\\Sigma\}\\rho\(s\)^\{\\top\}\\right\)^\{\\dagger\}\\left\(\\frac\{1\}\{\|S\|\}\\sum\_\{s\\in S\}\\rho\(s\)\\widehat\{b\}\\right\)\.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\\Pi\_\{S\}onℱ\\mathcal\{F\}\. Hence, the excess risk can be read directly from how wellΠS\\Pi\_\{S\}approximates the full averaging operatorΠG\\Pi\_\{G\}\. In OLS, the estimator depends both on the averaged moment vectorb^S\\widehat\{b\}\_\{S\}and on the averaged covariance matrixΣ^S\\widehat\{\\Sigma\}\_\{S\}\. Thus, exact averaging onℱ\\mathcal\{F\}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 toIrI\_\{r\}\.

Projection estimators also avoid small\-sample instability\. Whennnis comparable to, or smaller than,rr, the empirical covarianceΣ^\\widehat\{\\Sigma\}may be singular or poorly conditioned\. OLS can therefore be unstable unless one adds regularization or assumes enough samples to guarantee concentration ofΣ^\\widehat\{\\Sigma\}aroundIrI\_\{r\}\. 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:

β^proj=Ir−1​b^,β^ols=Σ^†​b^\.\\widehat\{\\beta\}\_\{\\mathrm\{proj\}\}=I\_\{r\}^\{\-1\}\\widehat\{b\},\\qquad\\widehat\{\\beta\}\_\{\\mathrm\{ols\}\}=\\widehat\{\\Sigma\}^\{\\dagger\}\\widehat\{b\}\.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ℱ\\mathcal\{F\}, give clean rates, and avoid conditioning assumptions that are orthogonal to the main phenomenon\.

### E\.2Infinite\-Dimensional Hypothesis Classes

The main results are stated for finite\-dimensional spacesℱ\\mathcal\{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\.

Letℱ\\mathcal\{F\}be an infinite\-dimensionalGG\-invariant subspace ofL2​\(𝒳,μ\)L^\{2\}\(\\mathcal\{X\},\\mu\), and let

ℱr⊂ℱ\\mathcal\{F\}\_\{r\}\\subset\\mathcal\{F\}be anrr\-dimensionalGG\-invariant subspace\. For example,ℱr\\mathcal\{F\}\_\{r\}may be spanned by the firstrrbasis functions in a spectral, Fourier, or polynomial decomposition, provided the truncation is closed under the action ofGG\. Let

rinv​\(r\):=dim\(ℱrG\)r\_\{\\mathrm\{inv\}\}\(r\):=\\dim\(\\mathcal\{F\}\_\{r\}^\{G\}\)denote the dimension of the invariant subspace insideℱr\\mathcal\{F\}\_\{r\}\. Applying our finite\-dimensional results toℱr\\mathcal\{F\}\_\{r\}gives the same bounds withrrreplaced bydim\(ℱr\)\\dim\(\\mathcal\{F\}\_\{r\}\), and withrinvr\_\{\\mathrm\{inv\}\}replaced byrinv​\(r\)r\_\{\\mathrm\{inv\}\}\(r\)\. In particular, for a fixed truncationℱr\\mathcal\{F\}\_\{r\}, the partial augmentation term scales as

while the invariant estimation term scales as

rinv​\(r\)n\.\\frac\{r\_\{\\mathrm\{inv\}\}\(r\)\}\{n\}\.Thus, for this truncation, the same statistical transition occurs at

\|S\|≍rrinv​\(r\)\.\|S\|\\asymp\\frac\{r\}\{r\_\{\\mathrm\{inv\}\}\(r\)\}\.
For an infinite\-dimensional class, one must also account for the approximation error incurred by restricting toℱr\\mathcal\{F\}\_\{r\}\. Let

fr:=Πℱr​f⋆f\_\{r\}:=\\Pi\_\{\\mathcal\{F\}\_\{r\}\}f^\{\\star\}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ℱr\\mathcal\{F\}\_\{r\}, one obtains a bound of the form

𝔼​\[‖f^S,r−f⋆‖L2​\(𝒳\)2\]≲rinv​\(r\)n\+rn​\|S\|⏟estimation and augmentation\+‖f⋆−fr‖L2​\(𝒳\)2⏟approximation,\\mathbb\{E\}\\big\[\\\|\\widehat\{f\}\_\{S,r\}\-f^\{\\star\}\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}\\big\]\\lesssim\\underbrace\{\\frac\{r\_\{\\mathrm\{inv\}\}\(r\)\}\{n\}\+\\frac\{r\}\{n\|S\|\}\}\_\{\\text\{estimation and augmentation\}\}\+\\underbrace\{\\\|f^\{\\star\}\-f\_\{r\}\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}\}\_\{\\text\{approximation\}\},up to the problem\-dependent constants appearing in the finite\-dimensional results\. If the target is invariant and the truncationℱr\\mathcal\{F\}\_\{r\}isGG\-invariant, thenfrf\_\{r\}is also invariant, so the same invariant\-subspace analysis applies insideℱr\\mathcal\{F\}\_\{r\}\.

The remaining task is to optimize over the truncation levelrr\. This requires balancing the statistical terms

rinv​\(r\)n\+rn​\|S\|\\frac\{r\_\{\\mathrm\{inv\}\}\(r\)\}\{n\}\+\\frac\{r\}\{n\|S\|\}against the approximation error

‖f⋆−Πℱr​f⋆‖L2​\(𝒳\)2\.\\\|f^\{\\star\}\-\\Pi\_\{\\mathcal\{F\}\_\{r\}\}f^\{\\star\}\\\|\_\{L^\{2\}\(\\mathcal\{X\}\)\}^\{2\}\.The optimal truncation is problem\-specific\. It depends on the smoothness or spectral decay off⋆f^\{\\star\}, on how the group action decomposes across the basis functions, and on how quickly the invariant dimensionrinv​\(r\)r\_\{\\mathrm\{inv\}\}\(r\)grows withrr\. 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\.