Achieving Approximate Symmetry Is Exponentially Easier than Exact Symmetry
Authors: Behrooz Tahmasebi
Melanie Weber
Venue: ICLR 2026 Poster (2026)
Keywords: symmetry
invariance
relaxed equivariance
complexity
theory
Primary area: learning theory
TL;DR: We prove that approximate symmetry is exponentially easier to enforce than exact symmetry via averaging

Abstract: Enforcing exact symmetry in machine learning models often yields significant gains in scientific applications, serving as a powerful inductive bias. However, recent work suggests that relying on approximate symmetry can offer greater flexibility and robustness. Despite promising empirical evidence, there has been little theoretical understanding, and in particular, a direct comparison between exact and approximate symmetry is missing from the literature. In this paper, we initiate this study by asking:
What is the cost of enforcing exact versus approximate symmetry?
To address this question, we introduce averaging complexity, a framework
for quantifying the cost of enforcing symmetry via averaging. Our main result is an exponential separation: under standard conditions, achieving exact symmetry requires linear averaging complexity, whereas approximate symmetry can be attained with only logarithmic averaging complexity.
To the best of our knowledge, this provides the first theoretical separation of these two cases, formally justifying why approximate symmetry may be preferable in practice. Beyond this, our tools and techniques may be of independent interest for the broader study of symmetries in machine learning.

Published as a conference paper at ICLR 2026
ACHIEVING APPROXIMATE SYMMETRY IS EXPONEN- TIALLY EASIER THAN EXACT SYMMETRY
Behrooz Tahmasebi & Melanie Weber Harvard John A. Paulson School of Engineering and Applied Sciences (SEAS)
Harvard University, Cambridge, MA 02138, USA [behrooz,tahmasebb mweber seass harvard.edu
ABSTRACT
Enforcing exact symmetry in machine learning models often yields significant gains in scientific applications, serving as a powerful inductive bias. However, recent work suggests that relying on approximate symmetry can offer greater flex- ibility and robustness. Despite promising empirical evidence, there has been lit- tle theoretical understanding, and in particular, direct comparison between exact and approximate symmetry is missing from the literature. this paper, we initiate this study by asking: What is the cost of enforcing exact versus approximate sym- metry? To address this question, we introduce averaging complexity, a framework for quantifying the cost of enforcing symmetry via averaging. Our main result is an exponential separation: under standard conditions, achieving exact symmetry requires linear averaging complexity, whereas approximate symmetry can be at- tained with only logarithmic averaging complexity. To the best of our knowledge, this provides the first theoretical separation of these two cases, formally justifying why approximate symmetry may be preferable in practice. Beyond this, our tools and techniques may of independent interest for the broader study of symmetries in machine learning.
INTRODUCTION
The field of geometric machine learning aims to incorporate structures observed in scientific data into abstract machine learning models, with the goal of leveraging these strong inductive biases to make learning more robust, efficient, and interpretable (Bronstein et al., 2021; Weber, 2025). Promi- nent examples include permutation symmetries in point clouds for vision tasks, sign-flip symmetries in spectral graph methods, rotational symmetry in robotic tasks, and other structures in molecular and atomistic data with applications from physics to drug discovery (Bogatskiy et al., 2020; Wang et al., 2022a; Nguyen et al., 2024; Kufel et al., 2025).
A natural approach to handling symmetries is to encode them exactly into the model through dif- ferent mechanisms. This ensures that the invariance hypothesis is exploited its full extent. The literature offers a variety of such methods, including model-agnostic approaches such as group av- eraging, data augmentation (Dao al., 2019; Chen et al., 2020; Patil & Du, 2023; Tahmasebi al., 2025), canonicalization, and frame averaging (Puny et al., 2022: Lin et al., 2024; Atzmon et al., 2022; Kaba et al., 2023; Ma et al., 2024; Tahmasebi & Jegelka, 2025a:b; Dym al., 2024; Shu- maylov et al., 2025), as well as model-dependent approaches such as convolutional neural networks as well as neural networks with equivariant weights (Cohen & Welling, 2016; 2017; Krizhevsky et al., 2012; Satorras et al., 2021; Maron et al., 2019; Liao & Smidt, 2023; Zaheer et al., 2017). Both categories have been shown to be effective in practice, and detailed theoretical studies have further analyzed their benefits.
However, introducing exact symmetries also comes with a number caveats. In many applications, invariance is only partial, and targets may respect symmetry only approximately (Finzi et al., 2021; Romero & Lohit, 2022; van der Ouderaa et al., 2022; Kim et al., 2023; Park et al., 2025; Wang et al., 2022b). For example, in medical imaging, expected reflectional symmetries and results are often mildly sensitive to such transformations. Another case arises when only partial knowledge of the underlying symmetries is available, and symmetry discovery is performed (Yang
not perfect,

---

Published as a conference paper at ICLR 2026
Original fury))
Averaged, [5|
Averaged, [5] - 100
2-
2.75
2.50
2.25
0
2,00
1.75
22
-1
01
2
-2
Figure I: Approximate and exact symmetry enforcement via averaging for the 100-element group of 2D rotations. Left: original anisotropic function f(r,y). Middle: average over |S| s log(100) random rotations (approximate symmetry). Right: average over [S] = 100 rotations (exact symmetry). Approximate symmetry already high quality when [S] = log [G].
et al., 2023; van der Ouderaa et al., 2023; Desai et al., 2022; Dehmamy et al., 2021; Shaw et al., 2024: Yang al., 2024; Huh, 2025). In this setting, enforcing exact invariance introduces funda- mental limitations on universality and expressive power, making flexibility essential. Indeed, from distributional shift, robustness, and optimization perspective, it is often argued that allowing the model to violate symmetry to certain degree can improve performance while still exploiting the strong inductive biases present in the data. Motivated by these considerations, researchers have proposed using approximate symmetry instead of exact symmetry, which enables models to be more flexible, to achieve more robust performance, and to exploit symmetry in a semi- cuni-sueereiee fashion, particularly in the context of symmetry discovery.
Despite these practical successes, theoretical gaps remain. Since approximate symmetry can be viewed as relaxed form of invariance compared to hard-coded constraints, one might expect it easier to achieve data. theoretical analysis of the complexity of this emergence would provide several benefits. First, explains why approximate symmetries are ubiquitous in data, where exact equivariance rarely holds. Second, it shows why models exploit them more easily: lower enforcement complexity can yield better sample computational efficiency, well robustness to noise and distributional shifts.
Motivated by these considerations, in this paper, study the following question: Is it easier, from complexity perspective, to enforce approximate symmetry compared to exact symmetry? A key chal- lenge lies in defining what is meant by the "complexity" of achieving approximate symmetry and in formalizing the associated "budget" in this setting. While there is no unified notion of such com- plexity the literature, we introduce natural measure for comparing the two regimes: averaging complexity.
To define averaging complexity, we assume access a black-box model, and learner that is only allowed to post-pa post-process this model linearly via a number of action queries (AQ). The number of such queries required in averaging scheme is defined as the averaging complexity of the scheme. The learner's goal is to accomplish her task using as few queries as possible, which we interpret as the learner's budget.
Within this formal framework, we pose the following quantitative question: Given model, what the averaging complexity of enforcing approximate versus exact symmetry? Is there a separa- tion between their complexities? Specifically, is achieving approximate symmetry easier than exact symmetry, as suggested by practical evidence?
Our main contribution is summarized in the following statement (informal; under mild conditions):
The averaging complexity of achieving exact symmetry scales linearly with the group size, while approximate symmetry requires only logarithmic complexity in the group size.
2

---

Published as a conference paper at ICLR 2026
This result provides a foundation for understanding why approximate symmetry is often preferred in practice: an abstract model, is exponentially easier to achieve. The central message of this paper is the exponential separation, demonstrating that for given budget, approximate symmetry is more capable of achieving stronger results in semi-supervised learning (for example, in sym- metry discovery). Beyond this, our abstract framework and complexity notion, together with the prresentaaiinntthoreeee tools developed in this work, can also be applied to the broader study of geometric machine learning, independent of the specific results presented here.
In short, this paper makes the following contributions:
We advance the theoretical understanding of approximate versus exact symmetries in ma- chine learning models, and we prove that approximate symmetry is exponentially easier enforce in an abstract setting. To the best of our knowledge, this is the first theoretical separation between these two widely used approaches.
The abstract formulation of averaging complexity, together with the theoretical tools de- veloped this work, may be of independent interest for future studies in the theory of geometric machine learning. We believe that the results presented here represent just one instance of their broader applicability.
2
RELATED WORK
Symmetries appear in many scientific datasets, and equivariant machine learning has proven power- ful across applications in particle physics (Bogatskiy et al., 2020), robotics (Wang et al., 2022a), and quantum physics, in both exact (Nguyen al., 2024) and approximate forms (Kufel et al., 2025). Incorporating symmetry has been shown to improve sample complexity and generalization (Wang al., 2021: Tahmasebi & Jegelka, 2023; Elesedy, 2021), estimation (Chen al., 2023; Tahmasebi & Jegelka, 2024), and learning complexity (Kiani et al., 2024; Soleymani et al., 2025c;a). Gen- eralization benefits have been observed even when only approximate symmetry holds (Petrache & Trivedi, 2023).
Many architectures have been proposed for incorporating symmetries in neural networks, including group-equivariant CNNs (Cohen & Welling, 2016) and steerable CNNs (Cohen & Welling, 2017), both built on top of standard convolutional networks (Krizhevsky et al., 2012). Equivariant graph neural networks (Satorras et al., 2021; Maron et al., 2019) and transformers (Liao & Smidt, 2023)
have also been proposed and used in practice. canonical example for permutation symmetry is Deep Sets (Zaheer et al., 2017).
Beyond exact methods, many approaches for introducing relaxed invariance have been proposed in the literature, including modified filters (van der Ouderaa et al., 2022), soft equivariance (Kim et al., 2023; Finzi et al., 2021), I). partial equivariance (Romero & Lohit, 2022), and Lie-algebraic parameterizations (McNeela, 2023). Approximate symmetry has proved effective in reinforcement learning (Park et al., 2025) via approximately equivariant Markov decision processes (MDPs). Other examples include the use of structured matrices (Samudre et al., 2025) and relaxed constraints (Per- tigkiozoglou et al., 2024): see also (Wang et al., 2022b; Wu et al., 2025). For neural processes, Ashman et al. (2024) propose approximately equivariant schemes with promising benefits. This line of work extends to approximately equivariant graph networks (Huang et al., 2023) and symmetry breaking for relaxed equivariance (Wang al., 2024; 2023). The role and benefits of approximate cquivariance in the neural-netwon optimization landscape have also been studied (Xie & Smidt, 2025). In the context of symmetry discovery, many results use semi- supervisd methods to learn the underlying symmetry (Yang al., 2023; van der Ouderaa et al., 2023; Desai et al., 2022; Dehmamy et al., ; Shaw et al., 2024; Yang et al., 2024; Huh, 2025).
For modell-ggosste methods for equivariant learning, frame averaging (Puny al., 2022; Lin et al., 2024; Atzmon et al., 2022) and canonicalization (Kaba et al., 2023; Ma et al., 2024; Tahmasebi & Jegelka, 2025a;b; Dym al., 2024; Shumaylov al., 2025) as two widely applicable paradigms.
3

---

Published as a conference paper at ICLR 2026
3 PROBLEM STATEMENT
This section formulates the problem and introduces the function spaces and notation used through- out the paper. The main results appear in the next section, with detailed background provided in Appendix A.
3.1 PRELIMINARIES, NOTATION, AND BACKGROUND
Given a E N, we write [n] := (1,2, n.. Let X' be a topological space (the data domain), and let G' be finite group. Let (2') denote the space of square-integrable functions on X, assuming X' equipped with a canonical Borel measure ns.
A (left) group action of G on X' is a map 0 G x X' - X' such that 00. x)) for all g. and x E X, and the identity element of acts trivially (via the identity map x + x)) on We write gr == ((g, z); for each y. the map - gar is a homeomorphism of X. Indeed, without loss of generality, we assume that the canonical measure js on X' is invariant under the action of G.
dineesdimeniooall real vector space of continuous functions on X, and let GL(F) denote the group of invertible linear mappings from to itself (under composition). Assume that for every y G and f E F, the function + [ggx also belongs to F. Define G G GL(FF as the canonical group action on FF by leveraging the action on the domain:
Let F = (2*) be
(p())(()) = (x), EF Vx E X.
Indeed, p is (linear) group representation of G on F, meaning that p(gh) = p(g) under the composition of linear maps.
Remark While the results in this paper are mainly framed achieving invariance via averaging. they all follow using the same procedure to achieve equivariance via averaging. Using a natural algebraic correspondence, one can find a bijection between such equivariant functions and invariant functions on a new appropriate space. We detail this construction in Appendix A.4.
Remark 2. The results of this paper extend verbatim to dinte-dimesiioal complex subspaces of (X),,, without requiring veal-valuedness or continuity. We restrict attention to real-valued contin- uous functions for notational and conceptual simplicity.
3.2 AVERAGING SCHEMES
In this part, we formalize averaging schemes as abstract mechanisms for enforcing desired functional properties (e.g., symmetry) in function classes.
Consider an abstract setting where a learner aims to post-process the function class F to enforce condition (e.g., symmetry). The learner informed that an arbitrary function E F has been chosen by an oracle and that remains unchanged throughout post-processing. The learner then issues functional queries the oracle follows. Given f F and group element g G. the oracle returns the transformed function æ + f(gr) E F. Because each query evaluates f on gæ E X, we call it an action query (AQ).
After issuing number of action queries, the learner forms a linear combination of the oracle re- sponses obtain a prot-psreessed function. The learner has a limited budget and seeks to minimize the number of action queries. This motivates the following definition.
Definition (Averaging Scheme). An averaging scheme a fanction w G on the finite group G such that [W]),,()) Eyec w(g) = 1. For a function class F, the averaging operator induced by denoted E.,,, IF F. is defined by
(E~()))
VEE
gEG
The size of an averaging scheme is the number of nonzero weights:
size(w) = # #[g e G wlg) + 0}.
Intuitively, an averaging scheme specifies weights used to linearly combine the transformed func- tions (g- (1)) to produce the final output. Crucially, averaging schemes do not depend
4

---

Published as a conference paper at ICLR 2026
the domain point z X;; otherwise, they become instances of (weighted) frame averaging, and the notion averaging complexity becomes ill-defined. We therefore focus on universal linear combinations outputs of averaging operators.
Remark 4. One may allow to take complex values without affecting the results. For simplicity, however, we restrict attention to real-valued averaging schemes w.
3.3 AVERAGING COMPLEXITY
In this paper, we consider the abstract setting where the learner aims to obtain either exactly symmetric function or an approximately symmetric one. To define averaging complexity, we first introduce a few definitions, starting with exact symmetry.
Definition 5 (Exact Symmetry), A function F is exactly symmetric if. for all g G and all E X. one has f(gz) = f(r).
To define approximate symmetry, one must fix notion of distance from symmetry and allow relaxation within prescribed precision. A natural choice is to shrink the "non-symmetry" com- ponents of functions (in (x)) by small factor > 0. When O, the definition reduces to exact symmetry. The L (2'")noom is a canonical way to define distances in function space, and this particular choice for defining different notions of approximate symmetry enables our application to the generalization theory of approximately symmetric regression; see Appendix A.8. For further discussion going beyond the (2)(X')-nor,, please see Appendix F.
In this paper, we use two types of approximate symmetry: weak and strong.
Definition 6 (Weak Approximate Symmetry Enforcement). An averaging scheme G - TR. enforces weak approximate symmetry with respect to a parameter 0 if and only if. for every function f E F, we have
Eg [
(EL)))) du(x) s E,E, eLo - f(g=))
f(gz)))
where g E G is chosen uniformly at random and is the canonical Borel measure on X. Definition 7 (Strong Approximate Symmetry Enforcement). An averaging scheme w G + R enforces strong approximate symmetry with respect to a parameter c > if and only if. for every function f F, we have
((E))))))) (Ew (f))))) dp(x) S &EEE, (Is0) f(x)) du(o))
Vg G,
where g E G is chosen uniformly at random and is the canonical Borel measure on X.
In the weak notion, [/] is multiplicatively e-closer (in (2)) to being symmetric on average over group elements g E G. In the strong notion, the same closeness must hold for every g E G.
We are now ready to define the concept of averaging complexity.
Definition 8 (Averaging Complexity). The averaging complexity of enforcing exact, weak approx- imate, or strong approximate symmetry, denoted (F)x AC*K(F.E), and (C E), respec- tively, is the minimal size of an averaging scheme that a learner can construct such that the result- ing post-processed function is exactly, weakly approximately, strongly approximately symmetric, respectively. Formally.
(F) = -min size(w)
s.t. (Ewlfl)oz) = (EW(f)))x)
FfEF.gEG,zEE
AC (F = min size(w)
s.t. [[(_(())))) (ELII)) (Ba()]
s &E - [(00)1 VFEF
AC*((FE) = min sizo(w)
s.t. [[(=))))()) - (EL
< <EI,[11(()> [EE, f(o))) VfEF.gEG.
Example 9. Consider the set of constant functions on the domain. This function class clearly satis- fies all notions of symmetry for any group action, and thus AC (F)((F) AC**(F,E. = AC (F,E) 1, for all 0, the learner needs just one (trivial) query to achieve any of these symmetries.
5

---

Published as a conference paper at ICLR 2026
3.4 PROPERTIES OF AVERAGING COMPLEXITY
Before presenting the main result of the paper, we first review basic properties of averaging com- plexity in the following proposition.
Proposition 10 (Properties Averaging Complexity). The following properties hold for the differ- ent notions of averaging complexity:
The functions AC (F,s) and (F,s) .) are non-increasing in E.
For all e 0, AC
(F,E) S (F,E) (C) |G|.
For all 0, AC (F, 4e) S (F, (2) S (F,))
If.Fi S F2, then AC*((F)) & (F2). The same holds for AC and AC
The proof of Proposition 10 is deferred to Appendix B. The first two properties follow directly from the definition of averaging complexity and obtained via the trivial averaging scheme (i.e., query- ing all E G). Intuitively, the last inequality illustrates that enforcing exact symmetry becomes more difficult as the class grows.
The proof of the third property is more challenging: it relates the strong and weak notions of ap- proximate symmetry when the precision relaxed by constant factor. This observation allows us to focus, for simplicity, only on the notion of weak approximate symmetry.
MAIN RESULTS
The main purpose of this paper is to study how various notions of averaging complexity relate to properties of the group action and the function class, and whether there is a fundamental separa- tion between exact and approximate symmetry. Such a separation would show that approximate symmetry is, in abstract setting, fundamentally easier to achieve.
4.1 ASSUMPTIONS AND DEFINITIONS
We note that any form of averaging complexity can always be upper bounded linearly by the group size via the trivial averaging scheme that queries all group elements E G. This motivates the question of when sublinear averaging complexity is achievable.
To this end, the role of the function class is crucial: trivial classes, such as the set of constant functions, always have trivial averaging complexity. To avoid pathological cases, we assume the following condition for the domain, group action, and function class:
Assumption 11 (Faithful Group Action). For every non-identity element E G, there exist f E F and x X' such that fgx) * (2))
This assumption excludes degenerate cases while remaining sufficiently general. We next define (symmetric) tensor powers of a function class, which we use later in our results.
Definition 12 (Symmetric Tensor Powers of Function Spaces). Let F be finite-dimensional vector space of functions on domain X and let N. Define
Sym @kFF) = span II f((x: ft E FF [A]] 1=1
Sym @k (F)
Sym of (F),
=
t=
where Sym @0 (F) is the one-dimensional space of constant functions on X.
@k The construction above uses the base function class form the enlarged class Sym (F), which consists of linear combinations of pointwise products of up to k functions from F. In particular, Sym 69 (F) = F. while higher orders E correspond to degree-k homogeneous polynomial features constructed from elements of F.

---

Published as a conference paper at ICLR 2026
@k A canonical example is X' = Rd with F the set of linear functions on R In this case, Sym (F) exactly the space of polynomials in z of total degree at most Another example arises in kernel methods: starting from base kernel (and its feature map), one may form polynomial feature expan- sions, which correspond to tensor powers of the base feature space and yield increased expressivity.
In this paper, symmetric tensor powers serve tool for proving lower bounds on the averaging complexity of enforcing exact symmetry. Our goal is to show that there exists relatively small degree & (i.c., low-order polynomial features) for which the required averaging complexity scales linearly in [G].
4.2 AN EXPONENTIAL SEPARATION
The main result of this paper is summarized in the following series of theorems.
Theorem 13 (Averaging Complexity of Exact Symmetry Enforcement). Under the above assump- tions, for any function class F there exists an integer K. for which we provide an explicit closed-form expression, such that the averaging complexity of exact symmetry enforcement is
AC
Sym
@k
(F))
[G].
Yk K.
(4.1)
The proof of Theorem 13 is given in Appendix C. By definition of tensor powers, one has Sym @k (F) C Sym @k' (F) for any k' 2 k. Since averaging complexity is monotone with respect to inclusion of function classes (Proposition 10), the quantity AC Sym &h (F)) is nondecreasing in k E N; intuitively, enforcing exact symmetry becomes harder as the class grows. At the same time, (F)) - |G] for all & E N. Therefore, to prove Theorem 13, it suffices to show that (Sym k (F)) = |G| for k = K.
(Sym 0b
AC
AC
Theorem asserts that exact symmetry requires linear averaging complexity once polynomial fea- tures of degree k = K are included. A natural question is how to bound K. To answer this question, we establish an explicit upper bound on K, building on recent advances in algebra. In particular, letting p denote the representation of G on F, we show that K admits the upper bound
K S min GG],
Σ Mr -
(4.2)
AEA
where U
cigenvaluss of p( SEG
Mx max
multiplicity of X as eigenvalue of p(g) } gEG
Example 14. Let X = Rd and let G Sd act by permuting the coordinates of x E Rd Let F be the class of all linear functions on R.d. In this setting, for each g E G, the matrix p(g) E Rdxd is the permutation matrix associated with g. If y has cycle decomposition in S. with cycle lengths (l1, .2....,e,) E,) satisfying Ei= = d, then the eigenvalues of p(g) are
exp
2nip
p= 0,0,,.....
j= l=
Moreover, if X is an eigenvalue of some p(g). g E G. with order q (i.e., minimum g N such that A = 1), then we have MM | A counting argument shows that K = O(P). Therefore, polynomial features of degree = ( already suffice to yield linear averaging complexity for enforcing exact symmetry.
Next, we derive upper bounds on the averaging complexity of approximate symmetry, to compare with the exact case, which we already proved requires linear averaging complexity.
Theorem 15 (Averaging Complexity of Approximate Symmetry Enforcement). For any function class and any E > 0, the averaging complexities of weak and strong approximate symmetry enforcement satisfy
(F,)) = @ log G
AC = o log [ogg|G]
where the big-O notation hides universal constants.
7

---

Published as a conference paper at ICLR 2026
Note: The hidden constant in the big-O notation is most 3 2.67 or 32 10.67 for weak or strong symmetry enforcement, respectively. The proof of Theorem 15 is given in Appendix D.
These bounds hold uniformly for all function classes and do not rely Assumption 11 or the use of tensor powers; they apply even beyond the tensor-power setting. Thus, the upper bounds for approximate symmetry enforcement ered in Theorem 13, for which exact symmetry requires linear averaging complexity. Therefore, approximate symmetry enforcement needs only logarithmic averaging complexity (in (G), yielding an exponential separation between the approximate and exact regimes.
universal. In particular, they apply to the classes consid-
The averaging complexity of approximate symmetry enforcement (in the weak strong sense) is O₂ (log [G]), whereas exact symmetry requires complexity [G]. This yields an exponential separation between the two regimes, showing approximate symmetry is much casier to achieve in the abstract model of averaging complexity.
Remark 16. In our proofs also show that the bounds in Theorem 15 are tight (up to constants). In other words, there exist instances that require at least Q2 ( log Gl) action queries (AQs) to achieve approximate symmetry. Details are provided in Appendix E.
5 PROOF SKETCH
We sketch the proofs of our main results. For Theorem 13, we show that averaging over the entire group is necessary to guarantee exact invariance. For Theorem 15, we outline how approximate symmetry yields universal logarithmic averaging complexity. For background representation theory, see (Fulton Harris, 2013).
5.1 PROOF SKETCH FOR THEOREM 13
We first note that, by complete reducibility, any group representation, be decomposed into direct sum of (complex) irreducible representations (irreps) as follows:
p
M&NS
Vi: my Zzo.
(5.1)
where & denotes the set of distinct irreps (equivalently, one per conjugacy class of the group). and Ta i = 1,2,.... G). enumerate these irreps. Applying this to the representation induced on the function class yields nonnegative integer coefficients m, for i.
@K (F) for some What happens to this decomposition when we extend to tensor powers Sym N 1? Let Sym &* (p) denote the induced representation on Sym @* (F) for e [K]. In this case, for each & [K].
Sym 8k (p)
m
Vi: m (k) Ezo
(5.2)
i=1
What happens we have an averaging scheme w(g) and apply it on a space with representation Sym ooke (p)? To analyze this, view w : G + as a group signal (a function on the group), and consider its Fourier transform @ defined by
( Σ ((g)
YT G
(5.3)
SEG
where denotes the conjugate transpose (adjoint) complex- matrix.
Using standard facts from representation theory, one concludes that averaging for Sym $k (kFF) k K, yields exactly symmetric functions if and only if
Vi:
3k
|K| m (k) 40- (w(T))) 0 n, is trivial).
(5.4)
8

---

Published as a conference paper at ICLR 2026
Therefore, the function @ G + C must have sparse support whenever many inreps appear in the direct-sum decomposition of Sym @* (p), k K. We claim that for K given in Equation 4.2, every nontrivial irrep appears in some Sym s* (p) with k E K. If this claim holds, then
w m.)
for all i with т, nontrivial.
But this means the Fourier transform of w vanishes everywhere except at the point corresponding to the trivial irrep. By Fourier inversion, w must be the uniform measure G; since it sums to one,
w()) c for all G. Thus, any averaging scheme achieving exact symmetry requires access |G] action queries, as claimed.
5.2 PROOF SKETCH FOR THEOREM 15
We adopt the same Fourier-analytie viewpoint in the previous subsection, To establish that averaging complexity O
log GG is achievable under approximate symmetry, it suffices to construct
w : G R such that
size(w) = O ( log G|
V x nontrivial
[0(()))lpp S
(5.5)
We use a probabilistic construction. Sample group elements independently and uniformly at random, and let 5i be their empirical distribution (we use capital letter to emphasize that it is chosen at random). Form the block -diaonnalaa matrix
+ nantrivial ((T)). Then E[=] = and, for every nontrivial x, [(2(T))lop I || Thus, it is enough to control the operator norm of a zero- mean random matrix. Standard large deviation bounds imply that, with high probability, || S provided n 2 log dii for universal constant c. From representation theory, dim(E) s |G] which yields the claimed O log bound.
CONCLUSION AND FUTURE DIRECTIONS
We presented a theoretical study of learning with symmetries, focusing on why approximate sym- metry is both more convenient in practice and more reasonable for natural data. We introduced an abstract framework that defines the averaging complexity of enforcing exact or approximate symme- try as the minimum number of interactions with an oracle via action queries (AQs). Our main result shows an exponential separation: enforcing symmetry exactly can require linear complexity in [G], whereas relaxing approximate symmetry reduces the complexity to logarithmic in [G), providing theoretical evidence for sharp gap between the two regimes.
Several directions remain open. First, while this work focuses on finite groups, extending the frame- work and bounds to infinite groups is both natural and challenging, likely requiring ideas beyond those used here. Second, would be valuable to leverage our abstract formulation, together with pppresentation-therreehe methods, to analyze other theoretical problems in machine learning under symmetry, such as data augmentation. We leave these questions to future work.
ACKNOWLEDGMENTS
BT and MW were supported by NSF awards CBET-21 12085 and DMS MMS-2400905. MW also ac- knowledges support from Alfred P. Sloan Fellowship in Mathematics and an Aramont Fellowship for Emerging Science Research.
REFERENCES
Noga Alon and Shachar Lovett. Almost k-wise vs. k--isee independent permutations, and uniformity for general group actions. Theory of Computing, 9(15):559-55 2013. 29
Noga Alon and Yuval Roichman. Random cayley graphs and expanders. Random Structures &
Algorithms, 5(2):271 1-24, 1994. 29

---

Published as a conference paper at ICLR 2026
Matthew Ashman, Cristiana Diaconu, Adrian Weller, Wessel Bruinsma, and Richard Turner. Ap- proximately equivariant neural processes. In Advances in Neural Information Processing Systems (NeurIPS), 2024. 3,30
Matan Atzmon, Koki Nagano, Sanja Fidler, Sameh Khamis, and Yaron Lipman. Frame averag- ing for equivariant shape space learning. In IEEE Conference Computer Vision and Pattern Recognition (CVPR), 2022. 1,3
Georgia Benkart, Persi Diaconis, Martin W Liebeck, and Pham Huu Tiep. Tensor product markov chains. Journal of Algebru, 561:17-83, 2020. 29
Alexander Bogatskiy, Brandon Anderson, Jan Offermann, Marwah Roussi, David Miller, and Risi Kondor. Lorentz group equivariant neural network for particle physics. Int. Conference on Machine Learning (ICMI.), 2020. 1,3
Jean Bourgain and Alex Gamburd. Uniform expansion bounds for cayley graphs of SL2(F Annals of Mathematics, pp.
2008. 29
Richard Brauer. A note theorems of Burnside and Blichfeldt. Proceedings of the American Mathematical Society, 15(1):31-34, 1964. 29
Michael M Bronstein, Joan Bruna, Taco Cohen, and Petar Veličkovié. Geometric deep learning: Grids, groups, graphs, geodesics, and gauges. arXiv preprint arXiv:2104.13475 2021.
William Burnside. Theory of groups of finite order. Cambridge university press, 2012. 29
Shuxiao Chen, Edgar Dobriban, and Jane H Lee. A group-theoretic framework for data augmenta- tion. Journal of Machine Learning Research, 21(245):1-71, 2020. 1
Ziyu Chen, Markos Katsoulakis, Luc Rey-Bellet, and Wei Zhu. Sample complexity of probability divergences under group symmetry. In Int. Conference on Machine Learning (ICML), 2023. 3
Taco Cohen and Max Welling. Group equivariant convolutional networks. Int. Conference on Machine Learning (ICML), 2016. 3,
Taco S Cohen and Max Welling. Steerable CNNs. In Int. Conference Learning Representations (ICLR), 2017. 3,3
Christoph Dankert, Richard Cleve, Joseph Emerson, and Etera Livine. Exact and approximate uni- tary 2-designs and their application to fidelity estimation. Physical Review AAtomic, Molecular, and Optical Physics, 80(1)40, 2009, 29
Tri Dao, Albert Gu, Alexander Ratner, Virginia Smith, Chris De Sa, and Christopher Ré. A kernel theory of modern data augmentation. In Int. Conference Machine Learning (ICML), 2019. 1
Nima Dehmamy, Robin Walters, Yanchen Liu, Dashun Wang, and Rose Yu. Automatic symmetry discovery with Lie algebra convolutional network. In Advances in Neural Information Processing Systems (NeurIPS), 2021. 3,
Krish Desai, Benjamin Nachman, and Jesse Thaler. Symmetry discovery with deep learning. Phys- ical Review D, 105(9)009031, 2022. 2.
Nadav Dym, Hannah Lawrence, and Jonathan W Siegel. Equivariant frames and the impossibility of continuous canonicalization, 2024. 1,3
Bryn Elesedy. Provably strict generalisation benefit for invariance in kernel methods. In Advances in Neural Information Processing Systems (NeurIPS), 2021. 3
Mare Finzi, Gregory Benton, and Andrew G Wilson. Residual pathway priors for soft equivariance constraints. In Advances Neural Information Processing Systems (NeurIPS), 2021. 1,
William Fulton and Joe Harris. Representation theory: a first course, volume 129. Springer Science & Business Media, 2013. 8, 14, 15
10

---

Published as a conference paper at ICLR 2026
Yanjun Han, Jiantao Jiao, and Tsachy Weissman. Minimax estimation of discrete distributions under l loss. IEEE Transactions on Information Theory, 61(11):6343-633 2015. 31
Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their applications. Bulletin of the American Mathematical Sociery, 43(4):439- 561, 2006. 29
Ningyuan Huang, Ron Levie, and Soledad Villar. Approximately equivariant graph networks. In Advances in Neural Information Processing Systems (NeurIPS), 2023. 3
Dongsung Huh. Discovering group structures via unitary representation learning. In Int. Conference Learning Representations (ICLR), 2025. 2,
I Martin Isaacs. Character theory of finite groups, volume 69. Courier Corporation, 1994. 14
Sékou-Oumar Kaba, Arnab Kumar Mondal, Yan Zhang, Yoshua Bengio, and Siamak Ravanbakhsh. Equivariance with learned canonicalization functions. In Int. Conference on Machine Learning (ICML), 2023. 1,3
Bobak Kiani, Thien Le, Hannah Lawrence. Stefanie Jegelka, and Melanie Weber. On the hardness of learning under symmetries. In Int. Conference on Learning Representations (ICLR), 2024.
Hyunsu Kim, Hyungi Lee, Hongseok Yang, and Juho Lee. Regularizing towards soft equivariance under mixed symmetries. In Int. Conference on Machine Learning (ICML), 2023. 1, 3, 30
János Kollár and Pham Huu Tiep. Simple modules as submodules and quotients of symmetric powers. Journal of Algebra, 657:286-291, 2024. 24
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. ImageNet classification with deep con- volutional neural networks. Advances in Neural Information Processing Systems (NeurIPS), 2012. 3,3
Dominik S Kufel, Jack Kemp, DinhDuy Vu, Simon M Linsel, Chris R Laumann, and Norman Y Yao. Approximately symmetric neural networks for quantum spin liquids. Physical Review Letters, 135 (5):056702, 2025. 3,3
Yi-Lun Liao and Tess Smidt. Equiformer: Equivariant graph attention transformer for 3D atomistic graphs. In Int. Conference on Learning Representations (ICLR), 2023. 1,3
Yuchao Lin, Jacob Helwig, Shurui Gui, and Shuiwang Ji. Equivariance via minimal frame averaging for more symmetries and efficiency. In Int. Conference on Machine Learning (ICML), 2024. 1,
George Ma, Yifei Wang, Derek Lim, Stefanie Jegelka, and Yisen Wang. A canonicalization perspec- tive on invariant and equivariant learning. In Advances in Neural Information Processing Systems (NeurIPS), 2024. 1,
Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. In Int. Conference on Learning Representations (ICLR), 2019. 1,3
Daniel McNeela. Almost equivariance via Lie algebra convolutions. In Symmetry and Geometry in Neural Representations (NeurReps) Workshop, 2023. 3
Quynh T Nguyen, Louis Schatzki, Paolo Braccia, Michael Ragone, Patrick J Coles, Frederic Sauvage, Martin Larocca, and Marco Cerezo. Theory for equivariant quantum neural networks. PRX Quantum, 5(2):020328, 2024. 1,3
Jung Yeon Park, Sujay Bhatt, Sihan Zeng, Lawson L.S. Wong, Alec Koppel, Sumitra Ganesh, and Robin Walters. Approximate equivariance in reinforcement learning. In Int. Conference Arti- ficial Intelligence and Statistics (AISTATS), 2025. 3,3
Pratik Patil and iin-ong Du Generalized equivalences between subsampling and ridge regulariza- tion. In Advances in Neural Information Processing Systems (NeurIPS), 2023.
Stefanos Pertigkiozoglou, Evangelos Chatzipantazis, Shubhendu Trivedi, and Kostas Daniilidis, Im- proving equivariant model training via constraint relaxation. In Advances in Neural Information Processing Systems (NeurIPS). 2024.
11

---

Published as a conference paper at ICLR 2026
Mircea Petrache and Shubhendu Trivedi. ciniiiatioon-ennralizaaaii trade-offs under (approx- imate) group equivariance. In Advances in Neural Information Processing Systems (NeurIPS), 2023. 3
Omri Puny, Matan Atzmon, Edward Smith, Ishan Misra, Aditya Grover, Heli Ben-Hamu, and Yaron Lipman. Frame averaging for invariant and equivariant network design. In Inl. Conference on Learning Representations (ICLR), 2022. 1.3
David W Romero and Suhas Lohit. Learning partial equivariances from data. In Advances in Neural Information Processing Systems (NeurIPS), 2022. 1,
Aidan Roy and Andrew J Scott. Unitary designs and codes. Designs, codes and cryptography, 53 (1):13-31, 2009. 29
Ashwin Samudre, Mircea Petrache, Brian Nord, and Shubhendu Trivedi. Symmetry-basse struc- tured matrices for efficient approximately equivariant networks. In The 28th International Con- ference on Artificial Intelligence and Statistics, 2025. 3
Victor Garcia Satorras, Emiel Hoogeboom, and Max Welling. E(n) equivariant graph neural net- works. In Int. Conference on Machine Learning (ICML), 2021. 1,3
Jean-Pierre Serre. Linear representations of finite groups, volume 42. Springer, 1977. 14
Ben Shaw, Abram Magner, and Kevin Moon. Symmetry discovery beyond affine transformations.
In Advances in Neural Information Processing Systems (NeurIPS), 2024. 2,
Zakhar Shumaylov, Peter Zaika, James Rowbottom, Ferdia Sherry, Melanie Weber, and Carola- Bibiane Schönlieb. Lie algebra canonicalization: Equivariant neural operators under arbitrary Lie groups. In Int. Conference on Learning Representations (ICLR), 2025. 1,
Ashkan Soleymani, Behrooz Tahmasebi, Patrick Jaillet, and Stefanie Jegelka. From finite to infi- nite groups: A polynomial-time algorithm for learning with exact invariances. In NeurlPS 2025 Workshop on Symmetry and Geometry in Neural Representations, 2025a.
Ashkan Soleymani, Behrooz Tahmasebi, Stefanic Jegelka, and Patrick Jaillet. A robust kernel statis- tical test invariance; Detecting subtle asymmetries. Int. Conference on Artificial Intelligence and Statistics (AISTATS), 2025b. 23
Ashkan Soleymani, Behrooz Tahmasebi, Stefanie Jegelka, and Patrick Jaillet. Learning with exact invariances in polynomial time. In Int. Conference on Machine Learning (ICML), 2025c. 20255.. 3
Benjamin Steinberg. On the 2014. 24
theorem. arXiv preprint arXiv:1409.7632,
Robert Steinberg. Complete sets of representations of algebras. Proceedings of the American Math- ematical Society, 13(5)7746-747, 1962. 29
Behrooz Tahmascbi and Stefanie Jegelka. The exact sample complexity gain from invariances for kernel regression. In Advances Neural Information Processing Systems (NeurIPS), 2023.
Behrooz Tahmasebi and Stefanie Jegelka. Sample complexity bounds for estimating probability divergences under invariances. Int. Conference on Machine Learning (ICMI.), 2024.
Behrooz Tahmasebi and Stefanie Jegelka. Regularity in canonicalized models: A theoretical per- spective. In Int. Conference on Artificial Intelligence and Statistics (AISTATS), 2025a. 1.3
Behrooz Tahmasebi and Stefanie Jegelka. Generalization bounds for canonicalization: A compara- tive study with group averaging. In Int. Conference Learning Representations (ICLR), 2025b. 3.3
Behrooz Tahmasebi, Melanie Weber, and Stefanie Jegelka. Data augmentation: A Fourier analysis perspective. In NewrIPS 2025 Workshop on Symmetry and Geometry in Neural Representations, 2025. 1
12

---

Published as a conference paper at ICLR 2026
Joel A Tropp. User-friendly tail bounds for sums of random matrices. Foundations of computational mathematics, 12(4):389 2012. 28
Tycho van der Ouderaa, David W Romero, and Mark van der Wilk. Relaxing equivariance con- straints with non-stationary continuous filters. In Advances in Neural Information Processing Systems (NeurIPS), 2022. 3,
Tycho van der Ouderaa, Alexander Immer, and Mark van der Wilk. Learning layer-wise equiv- ariances automatically using gradients. Advances Neural Information Processing Systems (NeurIPS), 2023. 3
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018. 21
Dian Wang, Robin Walters, and Robert Platt. -equiiaraa reinforcement learning. In Int. Conference on Learning Representations (ICLR), 2022a. 3,
Rui Wang, Robin Walters, and Rose Yu. Incorporating symmetry into deep dynamics models for improved generalization. In Ini. Conference on Learning Representations (ICLR), 2021. 3
Rui Wang, Robin Walters, and Rose Yu. Approximately equivariant networks for imperfectly sym- metric dynamics. In Int. Conference on Machine Learning (ICML), 2022b. 1,3
Rui Wang, Robin Walters, and Tess Smidt. Relaxed octahedral group convolution for learning symmetry breaking 3D physical systems. In NeurlPS Al for Science Workshop, 2023. 3
Rui Wang, Elyssa Hofgard, Han Gao, Robin Walters, and Tess Smidt. Discovering symmetry break- ing in physical systems with relaxed group convolution. In Int. Conference on Machine Learning (ICML), 2024.
Melanie Weber. Geometric machine learning. Wiley Online Library, 2025.
Zhiqiang Wu, Yingjie Liu, Licheng Sun, Jian Yang. Hanlin Dong, Shing-Ho Lin, Xuan Tang, Jinpeng Mi, Bo Jin, and Xian Wei. Relaxed rotational equivariance via G-biases in vision. In Proc. AAAI Conference on Artificial Intelligence (AAAI), 2025. 3
YuQing Xie and Tess Smidt. A tale of two symmetries: Exploring the loss landscape of equivariant models. In Advances in Neural Information Processing Systems (NeurIPS), 2025.
Jianke Yang, Robin Walters, Nima Dehmamy, and Rose Yu. Generative adversarial symmetry dis- covery. In Int. Conference Machine Learning (ICML), 2023. 1,3
Jianke Yang, Nima Dehmamy, Robin Walters, and Rose Yu. Latent space symmetry discovery. In Int. Conference on Machine Learning (ICML), 2024. 2,
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh. Barnabas Poczos, Russ R Salakhutdinov, and A Alexander Smola. Deep sets. In Advances in Neural Information Processing Systems (NeurIPS), 2017. 3,
13

---

Published as a conference paper at ICLR 2026
A BACKGROUND FOR PROOFS
This appendix collects the background used in our proofs. We briefly review finite groups, group actions, group representations, character theory, and Fourier analysis on finite groups (Serre, 1977; Isaacs, 1994; Fulton & Harris, 2013).
A.1
GROUP THEORY
A finite group is a finite set G equipped with binary operation :: G G -+ G satisfying:
(Associativity) For all h, k E G, (g. h) - k (h-k).
(Identity) There exists an element e E G such that e = e. for all G. (Inverses) For each E G, there exists g G with g. g-
g
Given a finite group G, we denote its identity element by e. For brevity, we omit the operation symbol and write gh for g-
The order of G is the number of its elements, denoted |G]. For every integer 2 1, there exists group of order n: the cyclic group 2/nž {0, 1, , 1} under addition modulo n.
A canonical example of finite group is the symmetric group Sa, the group of all permutations of d elements:
Sa { [4] - [d] is bijective }.
with composition as the group operation. Here, we use the notation [d] = (1,2,..., dd for d E N.
G by 9 = 3s G h sgs- This is equivalence relation G. The conjugacy class partition of G. Let r denote the number of conjugacy classes of G. If [g] conjugacy classes, then
Define relation
is [g] = [sgs- s e G}. The conjugacy classes {[g] : g E G} form
[9,] [9.]....,,,,. the distinct
G [g...
Trivially, r < |G). For commutative groups (i.e., gh = hg for all h E G), this bound is tight: r = rI since every conjugacy class a singleton.
In contrast, for many noncommutative groups one has << |G|. A canonical example is the sym- metric group Sa. where conjugacy classes correspond to cycle type; hence r p(d), the par- tition number, which far smaller than [Sa] d!. Asymptotically, log = @(vd) while log [Sa] log(d!) Od d). Thus, in this case have < |Sa). Another canonical example the dihedral group D2n. the symmetries of a regular n-gon, which has 2n elements (rotations and reflections). It has u+3 conjugacy classes when is odd and 22 when n is even; in particular, r D2.1 2n.
A.2 GROUP ACTIONS AND FUNCTION SPACES
Let X' be a topological space and G a finite group. A (left) group action of G on X' is a map 0: G X' X' such that 0(gh, 0(g. 0h,,))) for all g, h E G and x X, and the identity element of G acts trivially (via the identity map x + x) on X. For notational convenience, we write gar 0(g, .)). We consider only continuous actions: for each y E G, the map I gr is homeomorphism of X' onto itself.
Let X' be topological space and let B(X') denote its Borel olaleerra, making (X, B(X) mea- surable space. Fix a reference measure μ X; all function spaces below are defined with respect to μ. Without loss of generality, we assume the action G preserves the reference measure μ. i.e. u(gA) = (A) for all measurable A C X and E G (equivalently, dj(gz) = dp(z) for all E G). For finite groups, this can always be arranged by averaging any reference measure Pref over G:
Σ BEG
Mref (g- AA)
G
14

---

Published as a conference paper at ICLR 2026
which is G-invariant. In many settings, there is also canonical "uniform" choice (e.g., counting measure on finite sets or Haar/surface/LLeessque measure on standard spaces) under which the usual actions are measure- pressevii......ing....
The space of square-integrable functions
(x) = { :f:2e x + R measurable : |I (1 = J [F(x) < cc..
Let F (2)) be a finite-dimensional subspace of continuous real-valued functions that is stable under G, i..., f (gz) E F for all E F and E G. The action of G on X' induces a (left) action on F by:
(ff(()) f FF, Gg
Recall that an action of on (either X' or F) faithful and only if
Vu E U1 gu =u = is the identity element of G.
In this paper, we always assume that the function class F satisfies Assumption 11: the action of G on F is faithful. That is, for every non-identity group element g E G, there exists a function f E and point x E X' such that f(gx) # f(x)). Note that Assumption 11 implies that the action of G on X' is also faithful: if non-identity g fixed every x X, then we would have f(gx) = f() for all f E F,, contradicting Assumption 11.
A.3 GROUP REPRESENTATION THEORY
We use several notions from representation theory to establish our main results. This appendix reviews group representation theory in detail, with particular focus on finite groups. For compre- hensive reference, see (Fulton & Harris, 2013).
Let G be finite group and let V be finite- diiteeddimiiinall (real or complex) inner-produs space. Let GL(V) denote the group of invertible linear maps & V + V (under composition). A (linear) group representation is group homomorphism p: G - GL(V), meaning p(gh) p()) for all h E G. After fixing basis for V, each p(g) can be viewed as matrix in Ri V Vxdim V (or Odim Vxdim V). In other words. a representation "encodes" group elements by matrices so that group multiplication corresponds to matrix multiplication. For example, the trivial representation is defined as p(g) 1 E IR for all g E G.
In this paper, we assume representations are orthogonal (or unitary in the complex case): p(g) p(g) = (respectively, (L))rp(g) = /) for all E G. Equivalently, (p(g)u, p(g)ovv = (u, u)v for all u, E V. This assumption holds without loss of generality in our setting: when V F C T,2(2)) with the (22 inner product and the action is Seeasure-presevingg (i.e., du(gr)= du(z)), the induced action is orthogonal. Indeed, for any f. f F and g G,
f f du((x)
/ f(x) ("(x))((o)) x
[ [(x) (c))
dp(a) (()
(J, L
Two representations p and p' of on V are equivalent if there exists an orthogonal (unitary) matrix U E Rdim dxmi (resp. Ciim Vxdim V) such that Up(g) p for all g E G. A representation is reducible if it is equivalent to nontrivial block-diagonal representation (simultaneously for all g E G); otherwise, p is irreducible (abbreviated "irrep," which we use throughout, consistent with standard representation-theon -therrr terminology).
Irreps are fundamental building blocks of representations. The main important result in representa- tion theory of finite group is that any representation can be decomposed into irreps.
Theorem 17 (Maschke's 's Theorem). Let be a finite group. Over R or C, every finite miitte-dimensioal representation of G decomposes direct sum of irreducible representations.
15

---

Published as a conference paper at ICLR 2026
In partieular, finite group G has only finitely many irreducible representations (up equivalence), which we index as т, for i E [r], where r their number. Any representation p of G on a finite- dimensional space V decomposes
my Th
Zz0.
EE|r]
Here "@" means that, after change of basis (equivalence of representations), all matrices p(g) become block diagonal simultancously, with my blocks each equivalent πτ The nonnegative integers m, are the multipliciries of the irreps
Example 18. Let be the natural permutation representation of the symmetric group Sa on IRd, acting by coordinate permutation:
p(o)æ P. E Sa.
where Pa is the permutation matrix of a. This representation is reducible: the subspace span(1) (with 1 = (I...., ..,,,,)) 1)) is Sa-invariant (the trivial representation IT), and its orthogonal complement {o E Rd Ei= Iz = 0} is also Sæ-invariant (the standard representation π²) of dimension d - 1. In fact, p 11 T2, and both are irreducible.
What do know about irreps of finite group G? If we index them by क., E [r], then equals the number of conjugacy classes of G. We write
G { is irrep of G), r= G the number of conjugacy classes of G.
In particular, G < |G|: for commutative groups this tight, G = |G], while for noncommutative
groups one has |G| < [G], and in many cases even | << |G] (e.g.. for the symmetric group Sa, as we discussed before).
We now focus on complex irreducible representations of a finite group G. For irrep let its dimension d, E N; thus (g)) e Cd xd, for all E G. For commutative groups, all irreps are one-dimensional: dz = 1 for every π G. In contrast, noncommutative groups admit higher- dimensional irreps.
For the complex irreps of finite group, we have the identity:
G| = Σ de
Example 19. For the symmetric group Sa, we have |Sal d! cxp (og d)), while [Sal p(d) exp (o(v)). where p(d) is the number of integer partitions of d. In this case,
d! Σ d2
1)
+ other terms.
S
trivial irrep
standard irrop
Thus, many irreps exist beyond those appearing in the natural permutation representation (trivial and standard), even though the natural permutation representation faithful. In other words, faithfulness does not imply that a representation contains all irreps. In this case, several irreps have dimensions growing superpolynomially in d. A complete classification of Sa is given by the partitions of d.
A.4 EQUIVALENCE BETWEEN INVARIANCE AND EQUIVARIANCE
Adopting the previous definitions and notations, let V denote a cromplex-valueee finiteddimensional representation of G and us consider the space F(V) = span(uf u E V, f = J V. In other words, for any function f X C and any vector natural way. Moreover, the group G acts on F(V) = F & V naturally via the tensor product of the two diagonal representations.
V, one define of X V in
Now consider equivariant functions within F(V), which we denote via F(V) (as functions from X' V). Such functions defined yp E F(V) such that s(gx)) gy((2)) for all x, g. In other
16

---

Published as a conference paper at ICLR 2026
words, must have that gup (0)
(x(x) for all r. This means that yp F(V) is equivariant and only if it an invariant element of F & V.
In other words, if we consider the space of linear functions on X = F & V, then equivariant functions from X' to V are precisely invariant functions from X' to C. This completes the proof of correspondence.
As a result, all the claims and proofs in the paper will apply to the equivariant function classes after applying appropriate changes. In particular, the exponential separation will again apply such cases, with no further assumptions.
A.5 FOURIER ANALYSIS ON FINITE GROUPS
The theory of Fourier analysis on finite groups is essential for the results in this paper. built on group representation theory and has numerous applications, including signal processing groups. Definition 20 (Fourier Transform on Finite Groups), Let G be a finite group and let w : G be (complex-valuer) signal on G. The Fourier transform is the collection of matrices indexed by irreps G.
(xx) Σ (())) m(g),, TEG, DEG
(A.1)
where" denotes the conjugate transpose. This means that while the signal is supported on the group G. its Fourier transform is supported on (one matrix per irrep).
Many natural properties of fourier transform on Cd also hold for finite groups For instance, we have Fourier inversion formuu::
w(g) = |G|
Σ d (()))) FEG
(A.2)
Moreover, for any w G C,
Σ ((g)
Σ dz (r(
(A.3)
G
DEG
EEG
we set 17 = w, we obtain Plancherel formmullllfommukrr
EPOPP
Σ dx (O))
(A.4)
G
9EG
where || ||r denotes the Frobenius norm of matrices.
Example 21. Consider group signal w G + C with the property
(T)) = 0, for all nontrivial π E G.
What does this sparsity of the Fourier transform imply? By the inversion formula,
w(g)
de Tr(((=)=(g))
(A.5)
Tr (D(Tri))))) Tene (0)
(A.6)
G
(muwv)
(A.7)
G
for all g E G. where Tiriv is the mne-dimnnsionll trivial irrep. Hence w must be constant on If, in addition, ([lle,()) = Egee w(g) 1, then necessarily
((g) |G
for all E G.
(A.8)
ie., w is the uniform distribution on G. We will use this fact later to obtaín our main result on the linearity of averaging complexity for exact symmetry enforcement.
17

---

Published as a conference paper at ICLR 2026
A.6 INVARIANT SUBSPACES AND FOURIER ANALYSIS (EXACT SYMMETRY)
In this subsection, we review core properties of group actions on function spaces and how they relate the subspace of exactly symmetric functions. These tools are essential in our proofs.
Consider a finite-dimeniionll vector space F of complex- complex-valued valued functions on the domain A' as before. Not all functions in F are exactly symmetric; the invariant subspace
Fa {s E F: oو - EgE
(A.9)
Let denote the representation of the finite group G induced on F. We write its decomposition as is, in nontrivial cases, proper subset of F.
my niy
my E Z2o-
(A.10)
EE|r]
How can one relate the invariant subspace Fo the decomposition of p into the irreps of G? To this end, consider the uniform signal w(g) c
for all E G, and compute its Fourier transform:
(
Σ w(g)) =())" SEG
क [())
[,(T(g))), VTEG.
(A.11)
G
9EG
However, using the Fourier inversion formula, we have shown in the previous section that for the uniform signal, ((x) 0 for any nontrivial G. Therefore, conclude that
[0 E Rd xd, if I is nontrivial, Ey [g(-())] E IR, if I is trivial.
(A.12)
Note that after change of coordinates (i.e., choosing appropriate basis of F), write the group representation p in block-diagonal form:
p(g)
+ @ T((g)) ddim(F)xdim(F)
VgEG,
(A.13)
ve(rl
where L,; E Rm xmy denotes the identity matrix for each i [r]. Therefore,
[g(o) = +
[m, @ Egg (TA(ai)) = Imais
+
+
(A.14)
kE (r)
where we have indexed the trivial irrep by i Note that, according to the above derivation, we also obtain
Mariv Tr (p(o)) Ey [Tr (p(g)))
(A.15)
where the quantities Tr (p(g)), for g E G, are commonly referred to as the characters of the group representation p.
Define = [g()( For the basis F above that block-diagonan diagonalizes p (the "appropriate" basis), identify each f E F with its coefficient vector f e (d)m(F) Then,
GgEG: gf + p(g) f.
(A.16)
Then
F - Vg gf =
(A.17)
VgEG G: plg) f f
(A.18)
G Σ p f
(A.19)
DEG
- II f f
(A.20)
(ferivs 0, O....) (i.e., all nontrivial blocks are zero).
(A.21)
18

---

Published as a conference paper at ICLR 2026
In particular, II2 II and II" II, so II is the orthogonal projector onto its image, which is Fa,
and thus
dim(Fc) = rank (II) = Mariv = Eg [Tr (p(o))]
(A.22)
Note that we used the fact that
Gg p(g) f f =
Σ p(g) =
(A.23)
G
gEG
summing the equalities yields This is proved as follows. p(gS = f for all E G.
Egec p(g) f f. Conversely, suppose |6| Egea p(g) f = f. Then for any g G,
p(g) f - p(g)
1
Σ
plo't = 1
Σ
p(O))(O')
(A.24)
G
G
D'EG
D'EG
plgg')
1
Σ
plg") f f,
(A.25)
GG
D'EG
E'EG
which completes the proof.
A.7 INVARIANT SUBSPACES AND FOURIER ANALYSIS (APPROXIMATE SYMMETRY)
We now relate weak approximate symmetry of a function f E FF to its coefficient vector f E R with = (F). We have already shown that if f exactly symmetric, then its coefficient vector has the form f (fariv; 0, 0, ..... IR In general, we have f (firiv, Snnn) I where F Fo @ F& and meriv dim (Fa) and Muon == dim(FF).
For weakly symmetric function f E F with parameter e > 0, we have
Eg J (EL())=) (BLLI)))))-CL//))/00f/(dd du(xs) EE, [/x [(xx)( ((xr) du(x))
(A.26)
x
Note that, using measure preservation of the group action on X' and the definition of
1g [/ (5(() f(gz)) du(())
15 l [5())1 du(x) + / (((=)))dd(()))
(A.27)
/ f(x) f(x)
2 x
(A.28)
= 22 / f(x) Ez) du(x))
(A.29)
x
= 2 2f 2 (f, IIf)
(A.30)
= 2 2 2 [triv/ 122,
(A.31)
= 2 If fuoull?
(A.32)
Therefore, we conclude that
[o] is e-weakly approx. symm. +
(Bw))) non 112 S
VfEF (A.33)
A.8 A NOTE ON THE RELATIONSHIP WITH SAMPLE COMPLEXITY UNDER SYMMETRIES
In this subsection, briefly review how the results derived in this paper relate to the sample com- plexity of learning under symmetrics. Let C L²(X') be a finite-dimensional vector space of functions on X. Draw samples z; E X, i [n],, i..d. from reference probability measure μ X. Let f E F be a target function and observe labels
[
yi = f +6
(A.34)
where the noise terms é; independent and identically distributed with law A0, o2).
19

---

Published as a conference paper at ICLR 2026
The empirical risk minimizer (ERM) is
FRRM = arg min feF
Σ
(s(x)) Ua)
(A.35)
2n
The excess population risk (generalization error) of an estimator f
R(f) E[II (12
(A.36)
where the expectation over the sample (and label) randomness.
When learning under (exact) symmetries, we assume that f* is symmetric: gf* = f for all E G. It is then desirable encode the known symmetry f in the ERM output via exact or approximate symmetrization. Motivated by this, define the exactly symmetrized and weakly symmetrized ERM estimators by
Pox (x) =
Σ
FeRM ''a),
(A.37)
G
9EG
(E)M(Z) = (Ew (Ew()ERM)) (x)
Σw(g) FERM(G-'a))
(A.38)
gEG
where G -> R is averaging scheme chosen ensure e-weak approximate symmetry.
Let (0 (z), for j = 1,2,... dim(F), be an ( basis for F, and let ((x) = (P)) (z),... (Pimm()) denote the corresponding feature vector. For any f E F with coefficient vector f E ]dim()), we have f(x) (f, (z))).
Given samples Zı, In, let X E (nxdim(FF be the design matrix with Xi₃ = (z;()) for each i, i. Let y (y:) = X + TR. Then, the ERM problem can be written as
1 2n
fERM = arg
min fERdim())
X
FERM = Xx y. (A.39)
assuming X has full column rank.
The excess population risk of ERM (with no symmetry enforcement) can be written
R(FERM) Elll.ERM f [1:1(2)] E ElllFERM f 12
(A.40)
x (XS' + -
(A.41)
ElI((XTXX -
(A.42)
[|eTx((Tx))>xx x)
(A.43)
0² (XEXT((((XXxx=2222
(A.44)
o² T x) x)-1)]
(A.45)
0²
1 - x x -1)
Tr
E
(A.46)
n
71
(00i)((2))) )
Tr
E
Σ
(A.47)
n
where we used the cyclic property of the trace and the fact that o2 Now, let study the excess population risk of exact symmetry enforcement via group averaging. Let denote the projection operator, before. Note that II = f and IT TT. Moreover, rank(IT) Mariv-
20

---

Published as a conference paper at ICLR 2026
Then
R. ((ERRM)
= E [[IJERM - 8 [12(0] = [[| -
(A.48)
E [| x)-1x (Xf + - 111
(A.49)
E [ x)-1xxex Te1
(A.50)
E(E ( XI-xXXX x) x
(A.51)
o² A (X(X II(X x) x
(A.52)
= I (II(X' x) ")
(A.53)
0² TF
IE
(A.54)
n
)7)
d²
Tr
IT
Σ
(m)))(())))
(A.55)
n
72
Using standard concentration inequalities (Vershynin, 2018), and assuming supwex we have
[ ll co.
- + (()))
C1 mm I E
3 Ims
Vn 2 C3 m,
(A.56)
for some absolute constants 01, C22 03 (depending only on co). Therefore,
a m
R(EERM) θ e 0 (o'maiv
R(SERM) θ
(A.57)
n
where dim(F) and Miriv dim(Fe).
Finally, to study (f note that a given averaging scheme w G IR induces linear operator E. F - F; with slight abuse of notation, we use the same symbol for its action on coefficient vectors.
Note that
Pukk R
(ERM)
= E I1lE f [1))
E||l JERM 1
(A.58)
= E || E. FERM f
(A.59)
< 2 [[I E.. fERM II [2
2 2.
IIRMMM - f
(A.60)
a
2 TE JERM 1I fT
(A.61)
n
where we used the previous derivation of the excess population risk under exact symmetry enforce- ment. To upper bound the first term, note that the invariant subspace Fg is fixed by the linear operator E.:
VSE
R
(A.62)
since gf f for all g G and |Wller()) Therefore,
fERM (FERM, triv, FERM. IlJERM (FERM, triv: 0),
(A.63)
and, morcover,
FERM = (feRM, triv, fERM mon)
E. FERERM = (FERM, triv: E' FERM, non):
(A.64)
where E', denotes the linear operator induced by E.,, on Ft. From the previous section, since E,, is c-weakly approximately symmetric, we have
fEnx S fERM, non
(A.65)
21

---

Published as a conference paper at ICLR 2026
Therefore,
[ non [1]] + @ @ oo-merv
R fank
S c
(A.66)
Assuming || (1), obtain
E FRMM non [2] S 2115" + 2 2R (FFRM) O(1).
(A.67)
Hence the excess population risk under approximate symmetry enforcement satisfies 0 oemuiv
R
pwk JERM
O
O
(A.68)
Remark 22. The three excess population risks derived in this subsection are
σ o2m m
R(FERM
θ
(A.69)
n
o o
R (JJRRM
+
(A.70)
n
Puk R
[EEM
Marii
+ O(e),
(A.71)
n
where = dim(F) and Mariv dim(Fe). Therefore, using Theorem 15, one can achieve the full generalization benefits of symmetry with an appropriate averaging scheme of size only O log without requiring GG averaging. Here e can be chosen as the target generalization error. In particular, taking
e g'muix makes the weakly symmetric estimator's generalization bound match (up to constants) the bound for exact symmetry enforcement (which is superior in this simple linear regression setting). The size of the averaging scheme then only O [o [G] which can be much smaller than G
o
B PROOF OF PROPOSITION 10
Proof. Note that the first two properties, as well the last, follow directly from the definitions of averaging complexity for weak and strong approximate symmetry enforcement. In the second inequality, the universal upper bound |G| on the averaging complexity follows from the uniform averaging scheme defined by
w(g) = G VgEG.
(B.1)
For this scheme, size(w) [G], and for any f E F we
have
1 ((g
(Ew())(
Fa.
(B.2)
G
gEG
which is exactly (and therefore also weakly and strongly approximately) symmetric, since the output of group averaging.
Moreover, we always have
AC (F, s (F,e),
again by definition (similarly for other averaging complexitie)). Therefore, to complete the proof of Proposition 10, it suffices to establish the remaining inequality: for all > O,
AC < AC** (F,e).
(B.3)
To begin the proof, fix E > and wet G + R be an averaging scheme that attains AC ACW((F,E)
E).
By definition, for all F,
E,(l((E.(()()))) - (B= s sE, [I[((>) - l(gx) (B2(0]
22

---

Published as a conference paper at ICLR 2026
We show that the same scheme achieves strong approximate symmetry with precision 4s.
Fix any g' E G. By the triangle inequality and introducing the group-averaging operator By (uniform over G). we have
(()())))))) (B)0 - ( (((E - (g) (x)r))
+
Since the group action on the domain preserves the measure (du(gz) du(x)). we have
| = ( [Bwll (Ew (B.4) (B.5)
Therefore, we have
((EW)))))) - (BLL/)/))///)/ & (f(((())(())) E, ([(((,l))()))]llxxx
By Jensen's inequality,
(z)) [e - (Bx (E. (E.1f)
-Vgl (E, (f)
and therefore
E [f(]))))(=) (L.1f) s 2VE - flax))l
Squaring both sides yields
Ag EG: [(E]()))))) - (BLIf) = 4: (B, -
- ff f(0))1l)())
(B.6)
S E [1]((=) - f(gr)1
(B.7)
where we used the Cauchy-Schwarz inequality in the last step. Thus, the same averaging scheme (with the same size) achieves strong approximate symmetry with precision 4c, which completes the proof in the sense of the definition of the averaging complexity of the strong approximate symmetry enforcement.
Remark 23. Proposition 10 allows us to focus on weak approximate symmetry enforcement: the strong notion follows with only constant-factor loss in precision: for all 0, AC (F,4s) 4s) s AC (F, e). Consequently, the upper bound we prove, O log [G|/e). holds up constants for both notions. From theoretical perspective, this is significant because it lets one upgrade average-cass етror over the group a uniform (worst-case) guarantee over all g E G within a constant factor.
Finally, we note that an analogous constant-facto relationship between uniform and average-cass emrors has recently been observed in the problem of testing symmetries in data; see (Soleymani al., 2025b) for details.
C PROOF OF THEOREM 13
Proof. We begin by recalling why suffices to prove the bound on the averaging complexity for &b
= min ExEA MA-1] 1} By the definition of tensor powers, the space Sym
(F) =
+i_ Sym ((F) is the direct sum of tensor product spaces of degrees & 0, 0.,....,kk Conse-
k
quently, for any k' 2 k we have
Sym (F) θ Sym
Sym o6 (
Sym
Sym o6 (F) Sym 80
(F),
(C.1)
t=0
t=0
where the inclusion follows from the monotonicity of direct sums of vector spaces.
According to Proposition 10, the averaging complexity of exact symmetry enforcement is monotone
with respect to inclusion of vector spaces: Fi C F2, then (Fi) S AC*((F), Specializing
this inequality to Fi = Sym (F) and F2 = Sym 6ok (F) for 2 K, we obtain
60
CC (Sym 6K (F))
AC (Sym 00k (F)),
4A K.
(C.2)
23

---

Published as a conference paper at ICLR 2026
A Moreover, Proposition 10 also implies that AC (Sym @k (F)) z G for all & N. Therefore, to prove Theorem 13, suffices to establish that
AC* @K (F)) = [G],
k= min GG), Σ M -1 )
where
AEA
We complete the proof of Theorem 13 through the following two claims, whose proofs are deferred to the end of this section. For background material required in these arguments, we refer the reader Appendix A.
Claim 24 (Steinberg (2014); Kollár & Tiep (2024)). Let nu i i r [ denote all the irre- ducible representations of a finite group G. Consider the decomposition of the action of G on the function space F (which we have already assumed to be faithful):
m, TE,
my E Zzo-
(C.3)
aEIr]
Define K = min {IG), ExEr M, 1} sentation of G on the tensor power
Moreover, for each ls E [K], decompose the induced repre-
Sym (p)
m (k)
m,
(k)
E Zzo
(C.4)
Then, we have
Vi E [r]. 3E [K] such that m (k) 1.
(C.5)
Claim 24 shows that by taking tensor powers up to order K = min {IGI MA }}, we "observe" every irreducible representation at least once among the decompositions of the tensor powers. Indeed, we have
K
Sym (F) - +
Sym @k (F)
Sym
SK (p)
Sym 8k (p)
m
n
k=
0
i=1
21 by Claim 24
@K
@K(p) is the direct sum
In other words, the induced group action on Sym (F), denoted by Sym of the representations all tensor powers up order K. Furthermore, in the decomposition of
Sym @K (p), every irreducible representation appears at least once. We will use this fact to establish
lower bounds on averaging complexity via Fourier analysis on finite groups
Let us now present the final claim needed to complete the proof.
Claim 25. Consider an averaging scheme G + R that achieves exact symmelry on the func- tion space F with induced representation p. Assume that the decomposition of p into irreducible representations of the finite group G satisfies
P
m4 niy
m4 Z21-
(C.6)
sE|r]
Then, have
Σ (())<())'' = 0 Rd,, DEG
(C.7)
for all nontrivial irreducible representations क E G, where & denotes the set of all irreducible representations of G.
24

---

Published as a conference paper at ICLR 2026
By Claim 25, the Fourier transform of the group signal w G + R is sparse, in the sense that
(T) = Σ
[(())((9) (g)) =0 0 Ra.xd,
(C.8)
SEG
for every non-trivial irrep E G.
Moreover, the conditions of Claim 25 are already satisfied by the representation Sym &K (p) induced on Sym @K (F), thanks to Claim 24. Therefore, combining the two claims and applying the Fourier
inversion formula for the group signal w, we conclude that if w achieves exact symmetry for the function class, then necessarily
(T) = 0 Vx non-trivial
((g)
E
size(w) |G]. (C.9)
G
Here we used the fact that a group signal with Fourier support only on the trivial irrep must be constant, along with the assumption that ( Egec ((g) For further details on Fourier analysis finite groups, Appendix A.5.
This completes the proof of Theorem 13. In the remainder of this section, we provide the proofs of the claim stated above.
C.1 PROOF OF CLAIM 25
Proof. Throughout the proof, we adopt the notation and definitions from Appendix A, in particular those introduced in Appendix A.6. Let G - I denote averaging scheme, and let be the representation induced on the function class F, decomposed into irreps as
p
m Te.
my Zz1.
(C.10)
AE|r]
where : |G| denotes the number of distinct irreps.
Our goal is to show that, under condition m, 2 for i, and assuming that w is an exactly symmetric averaging scheme, the nontrivial components of the Fourier transform of w vanish:
Σ w(g) (g)) = 0 E Rd+xd=
(C.11)
BEG
for all nontrivial irreducible representations E G, where & denotes the set of irreducible represen- tations of G.
Note that, after change of coordinates (i.e., choosing appropriate basis), we write the group representation p in block-diagonal form:
p(g) + (m, 8 n<(g)) Rm æE|r]
E
(C.12)
where I,, E I2 xm denotes the identity matrix for each i [r], and
dim(F)
midmy
with d,, dim(
Therefore, there exist projection matrices II, E Cm one for each i E [r], corresponding to the subspaces spanned by the (possibly multiple) copies of n. the chosen coordinates, each projection takes the form
II
0 (
① 0 ( I Im,da, + 00 00
Vi E [r].
(C.13)
25

---

Published as a conference paper at ICLR 2026
In the orthonormal basis of the function space F, any function f FF can be identified with its coefficient vector f E C We decompose this vector as
(fi, f2. f.),
where each block f: corresponds to the component associated with Wi.
By definition the trivial representation (assumed here to be indexed by i = 1), we have
E Fc
f - (fi, 0, O, ..., 0) E Cm
(C.14)
that 1 is precisely the projection onto the subspace of exactly symmetric functions, i.e. Fg C F.
Note that a given averaging scheme w : G + IR induces a linear operator IE,, : F - F. With slight abuse of notation, we use the same symbol for its action on coefficient vectors, that we may also regard E. C + C
Since enforces exact symmetry, we must have
Euf = ( 1 0, 0.... E C
Vf E C
(C.15)
In other words, because the output of the averaging operator is exactly symmetric, all components corresponding to nontrivial irreps must vanish in the coefficient vector.
Now for arbitrary f E Cmm, we have
E.f
Σ (() 0,.... Cm gEG
(C.16)
Therefore, for any 2 2 (indices corresponding to nontrivial inreps), applying the projection matrix II, to the above identity yields
II,
Sw(g) p(g)f Σ ( ll,(g)f
(C.17)
9EG
DEG
Σ 9EG
w(g) (1(
em: fz
(C.18)
Bm,
Σ ( [T(
f
(C.19)
DEG
0 C
(C.20)
This identity must hold for all f: E Cms, and since m. 2 1 by assumption, we conclude that
Σ ((g)) (g) = 0 e Cd,, xdma
Vi 2.
(C.21)
gEG
Taking the conjugate transpose of the above identity completes the proof.
D PROOF OF THEOREM 15
Proof. Throughout the proof, we rely on the tools and ideas developed Appendix A, as well as those used in the proof of Theorem 13. We briefly review them here.
Let F denote an arbitrary function class, and let p be the representation induced by the action of the finite group G on F, which decomposes into irreducibles as
m, Tr.
m, E Zzo,
(D.1)
iEIr]
where := G is the number of distinct irreps. Note that my may be zero for some indices i.
26

---

Published as a conference paper at ICLR 2026
Under a change of coordinates (i.e., after choosing appropriate basis for F), the group represen- tation can be expressed in block-diagonal form:
p(g)
- (Im. @ (g))
R=xm
gEG, G.
(D.2)
ve(rl
where Imm E Rm denotes the identity matrix for each i E [r]. Here
m dim(FF
Σ m. dx
dx, - dim(a,).
Therefore, there exist projection matrices 11, E Cm one for each E [r]. corresponding to the subspaces spanned by the (possibly multiple, or zero) copies of nı. In the chosen coordinates, each projection has the form
r
0
+ mmdd, 0
e 0,
i E [r],
(D.3)
where the identity block appears in the position associated with π..
In the orthonormal basis of the function space F, any function f F can be identified with its coefficient vector f E CCm We decompose this vector as
(fi, ... fr),
where each block fi E Cmmdd,, corresponds to the isotypic component associated with m.
By convention, assume the trivial representation is indexed by 1. Then
f F
f = (fi, 0, 0, 0) C
(D.4)
so that II, exactly the projection onto the subspace of symmetric functions, i.e., Fo S.F.
Note that, according to Proposition 10, it suffices to prove Theorem 15 for weak approximate sym- metry. Indeed, once the claim established in the weak case, we have
o log IG|
AC (F,s) < AC**(FF
(D.5)
Therefore, throughout this section we focus only weak approximate symmetry enforcement.
R that induces linear operator E, F - F. With slight abuse of notation, we use the same symbol for its action on coefficient vectors, so that we may also regard E. m Cmm Assume that Bay enforces e-weak approximate symmetry for fixed parameter 0.
Consider an averaging scheme
As noted at the end Appendix A.7, this condition can be written as
[ is e-weakly symmetric
T&E f
S
11 1-2
VEEF.
(D.6)
1=2
Equivalently,
Eal is e-weakly symmetric
VFFF.
(D.7)
A necessary and sufficient condition for the above inequality is to require that
Vi > 2:
|1I, < || VfEF.
(D.8)
Using the decomposition of the representation into irreps, this condition reduces to
Ai 2:
Σ [((g) 0m. IL,
eIILf VfEF.
(D.9)
BEG
27

---

Published as a conference paper at ICLR 2026
A necessary and sufficient condition for this to hold is
sup
Σ (() DEG
ni (g)
S
(D.10)
$22
op
Let us now use a probabilistic construction for w - R. Draw n i.dd samples uniformly from G, and let S2 denote the empirical measure induced by these samples. We the capital letter Ω instead of w to emphasize that it is constructed randomly.
Since each is nontrivial irrep, have
yg (T) = 0 E Cd xdai,
2
(D.11)
Moreover, since all representations considered in this paper are unitary, it follows that
sup sup (e)o)lop S 1.
(D.12)
(22 gEG
Now we apply the matrix Bernstein tail bound from Tropp (2012, Theorem 1.6). In their notation, have R == 1, 0² n, and t = n²e. Then, for any 1, obtain
Pn
Σ (g))(()))
>
<
2d exp(- 3x0)
Vi 2.
(D.13)
gEC
Applying a union bound then gives
Pn
sup
Σ (g)
> e
S 2
dx, exp(-
3ne
(D.14)
122
SEG
122
< G exp - 3ne
(D.15)
8
where in the last step used the fact that
Σ 12
dr.
5
Σ 122
dh
|G| - 1.
(D.16)
Thus, to ensure that the probability of failure of a random averaging scheme to satisfy the weak approximate symmetry condition is at most 8 < 1, it suffices take
2.67 x log G + log 1 + 0.7
(D.17)
samples. At the same time, the size of such random averaging scheme is
size(S2) = o log Gl + log 1
(D.18)
which completes the proof.
Remark 26. In the proof, the decomposition into irreps and the removal of redundancies (i.e., cases with m, > 2) are essential for obtaining the log |G] term. A naive application of matrix concentra- tion inequalities to the entire space F would yield only a bound depending on log dim(F), which can be suboptimal when the function space F is large. By contrast, through pnaressenaaton-thhoreete arguments we derive a bound log [G), which holds uniformly for any smite-dimeensionl function space F.
28

---

Published as a conference paper at ICLR 2026
The proofs of main results exactly symmetric functions closely related to classical work in representation theory, including the results of Burnside (Burnside, 2012), Steinberg (Steinberg, 1962), and Brauer (Brauer, 1964).
Remark 27.
The theory of designing averaging schemes is also closely connected to the study of unitary designs and unitary codes, which have been investigated in the literature (Roy & Scott, 2009; Dankert al., 2009). The notion of almost independent permutations is also closely related to our setting, in the specific case of the symmetric group and low-degree polynomials (Alon & Lovett, 2013). Moreover, the fact that under a random averaging scheme logarithmically sized subsets of group elements suffice to ensure that all nontrivial irreps average close to zero has been used in different context in the study of random walks on groups (see the Alon- Roichman theorem (Alon & Roichman, 1994)). This line of work is further related to the theory of Cayley graphs and expander graphs (Bourgain & Gamburd, 2008), as well as tensor product Markov chains (Benkart et al., 2020), both of which have numerous applications (Hoory et al., 2006).
E PROOF OF THE CLAIM IN REMARK 16
Proof. In order to show that at least Og [lo |Gi) action queries (AQs) are required to achieve ap- proximate symmetry, construct particular instance of the problem.
Assume that < 1, and let us consider the group G {0, 1]d under addition modulo two, where d N. Note that log G ((d). Let Tr i E [r]] denote the distinct irreps of G, which are all onc-dimensional since is a commutative group. This means that r = [G]. Consider an arbitrary averaging scheme G - R that achieves weak approximate symmetry (Definition 6).
Using the same line of argument as appeared in the proof of Theorem 15 (Equation D.10), we have
(
(w(g)
S C,
vi:12
(E.1)
gEG
where i = 1 is used above to denote the trivial irrep.
We claim that this means that the support of i is a generating set of the group. other words, letting S = {g G w(g) * 0) we claim that S generates the group. This means that there exists finite & N such that St G, where define A EEj az as A, [ for any set C G.
First, let us show that the above claim completes the proof. Note that G a d-dimensional vector space, and thus if S has fewer than d elements then it is impossible have UkE[n) G, via elementary linear algebra arguments (i.e., span of less than d vectors cannot become d-dimensional vector space). Indeed, in such cases have , Ç G. This means that [S] > d (log (G]). However, the size of the averaging scheme w is size(w) = ||| (logg [G]). Since this bound holds for all 1, the proof complete.
Now let us focus proving that such subset S generates the group. For any two functions w1, w2 G IR, define their convolution, denoted by wi * w2 G - TR, such that
(w) we (g) = wi (h)wa (h (g) Vg G.
(E.2)
BEG
A clear property of the convolution operator is that
supp(wi w2) S supp(w1) supp(w2), for all W1,
(E.3)
In particular, this shows that for the averaging scheme G + R and its ê-fold convolution
W
VEEN.
(E.4)
we have
supp(w"t) C (supp(w))),
AE e N.
(E.5)
29

---

Published as a conference paper at ICLR 2026
This means that
U
supp (w*))
= U (supp(w))), vk
(E.6)
[E(A]
EE(A]
Therefore, to complete the proof, it sufficient show that
U [E(A]
supp (w**) G,
(F.7)
for some finite & E N.
Note that, according to the properties of the Fourier transform groups, we have
W T.)) S (T()))
S Se',
Vi 2
(E.8)
In particular, since 6 < 1, we have that limg-soc
W (T:)
uniformly over 2 2. This
means that wf converges in (G) to the uniform distribution over G. Recall that w is an averaging scheme, thus its average convergence are essentially equivalent here, since G finite.
the group is one. Moreover, convergence in (G) and pointwise
Therefore, since the support of the uniform distribution is the whole group, conclude that for some finite E N, we have that supp(w**) = G. and this completes the proof.
Remark 28. The above lower bound indeed holds for all finite groups, if we replace S with the minimum generating set of the group G. More precisely, the number of required action queries (AQs) is at least P2 ([S),, where S here is the minimum-sized generating set of the group G. For the particular case with G = (0, 1]d, we showed that any generating set has size at least log [G], thus proving the claim.
F BEYOND (x()):: ON APPROXIMATE SYMMETRY IN OTHER METRICS
In this section, we discuss how choosing metrics other than the Here, X is equipped with a Borel measure μl, and (²(X) is defined with respect to j..
can affect our results.
Assume that G + R achieves weak (or strong) approximate symmetry with respect to given parameter e. Let f E C (2) be an arbitrary function. According to Definition 6, and using the characterization of weak approximate symmetry in Equation A.33, we have
|[ll EyAfIllAAN) S e (g)lf(()) f(gx))l
(F.1)
< [l
(F2)
In the above, the operator [.] is defined according to the averaging scheme, and E.g-) [-] is the (full)
group averaging operator corresponding to the uniform averaging scheme over the whole group.
The above inequality tells us that we have a weak (or strong) averaging scheme, then the resulting averaged functions are e-close to their full group-averaged versions in the (. This holds for all intterrie functions f F. Moreover, the size of the averaging scheme only log GG) according to our main result in the paper.
size(w) O
What happens if want go beyond the (2 and provide approximations of group averaging using sparse sets? Let us discuss what happens we want to achieve this for the supremum norm over and J via random averaging scheme G R derived by sampling uniformly from the group. This is motivated by number of previous studies on approximate symmetry (Ashman al., 2024; Kim et al., 2023).
For fixed function f E F and fixed X, note that according to classical concentration inequalities (c.g.. Hoeffding's inequality) we have
(E.))))( (E,If)(>) so [Iifllex(x) log())
( size(w)
with probability 1
(F.3
30

---

Published as a conference paper at ICLR 2026
This bound, while even independent of the group size, is less interesting since it only holds for one particular pair (z, f). To make more general, one may want to take supremum (over a and/or f) of the left-hand side of the above inequality and hope that modified upper bound holds.
To take the supremum over æ E X. we need to use the so-called covering arguments, which are standard in classical statistics. Let (1g,V(s, 2) denote the metrie entropy of X' scale K, that is, the logarithm of the minimum number of points required to cover the whole domain X' with balls of radius at most K, where we equip the domain with given metric. Assume that f E (2) is 1-Lipschitz with respect to the given metric.
Assume x² and
size(w) [1 log(t) + 11/2000 log ln,, (k,
)
(F.4)
Then we have
sup Tx
(B,l)))))-(( O(),, with probability -
(F.5)
Usually, the metric entropy depends linearly on the intrinsic dimension of the domain X, and also heavily affected by the volume of the domain. The above bound, while being nice and independent of the group. still depends on potentially complicated constants determined by the geometry of the imput domain X.
There is one more issue here. The bound above holds only for a fixed function f E F. To obtain uniform bound holding for all f E F, one needs study covering numbers of the function space F, which can be difficult to handle for general spaces.
obtain uniform bound over functions f E F to how complicated this task can become. Consider fixed æ E , and let Muu and Mg denote the probability measures corresponding to the law of the point x transformed either according to the distribution w uniformly over the domain. Note that
Let
( (f)()) - (E)())(())) S Lip(J) WPu,PPg)
(F6)
for all F. where ((.)) denotes the (Wasserstein-l) optimal transport distance between mea- sures on X. This bound is indeed optimal whenever F contains all Lipschitz functions over X. Let Frip denote the set of all T--Lipschitz functions over X' for some fixed T. R.. Assume that this the case, and plug in the empirical measure t4w convergence rate in Wasserstein distance to Ag to obtain
sup ((=) (E,L))))) S SEFLip
L LW
B[ (Mw
(F.7)
size(w)
where the latter expectation is over the randomness of choosing w, and d is the intrinsic dimension of the domain X. Moreover, this upper bound is minimax optimal for general finite groups and data domains; see, for instance, (Han et al., 2015).
Note that there is a curse of dimensionality here: to ensure a bounded error, one needs averaging schemes of size least size(w) = O(GG)) which is often exp(O(d)). This is in contrast to the logarithmic bound in the group size for the (2((")-distana" sionality. As final remark, note that all the analysis above holds only for fixed z X, and obtaining a uniform bound over & E X' introduces another layer of complexity.
which holds with no curse of dimen-
To conclude, obtaining the same type of result uniformly over x E X' and f E impossible in full generality, even for Lipschitz function classes, which are substantially smaller subclass of square-integrable functions. Moreover, since generalization analyses machine learning and statistics are almost always governed by the theoretical motivation: see Appendix A.8. Still, the problem of finding better bounds beyond the L (X)) regime for specific function classes F is open direction that leave for future work.
J
going beyond this regime has less
G EXPERIMENTS
In this section, we present a simple proof-of- of-occet- experiment that validates the theoretical find- ings of this paper. We consider Plrain 5x 1 training and nhes 5x 10 test samples in dimension
31

---

Published as a conference paper at ICLR 2026
d = 20. Each data point x IR is drawn i..d. from Gaussian distribution with zero mean and identity covariance, and is labeled according to the target regression function:
f' (z) (wi abs(x));
where abs(x)) E Rd denotes the element-wise absolute value of æ, and wt Rd is an unknown weight vector sampled from a zero-mean Gaussian with identity covariance.
To learn f*, train three-layer ReLU network with two hidden layers of widths hı 128 and h2 = 64. The network is trained using SGD with learning rate 10 and batch size 256 for 500 epochs, using the squared loss.
By construction, this task is invariant under coordinate-wise sign flips, meaning that for any g E == (+1] have I* (gæ) (xx). The group G therefore has cardinality |G| = 24, which is prohibitively large for exact group averaging in practice. To approximate group averaging, we instead sample a random subset S G of size [S] 2 for k {0. L. 10}. At evaluation time, the prediction on an input z is obtained by averaging the network outputs over all transformations in S, and the test loss computed via the squared loss. Crucially, the subset S is fixed throughout training and is used only at evaluation time, and the training procedure itself does not depend S.
results of this experiment. The left plot shows the final test loss as function of the subset size |S]. As |S] increases, the test loss decreases, reflecting the benefit of averaging over more group elements. Interestingly, most of the improvement is already achieved around |S| 32, and larger subsets yield only marginal gains. This behavior is in strong agreement with our theory, which predicts that logarithmic-sized subsets already capture essentially the full benefit of group averaging.
Figure 2 summarizes
The right plot in Figure 2 illustrates how averaging with a subset of size ||| = 32 affects the test loss the course of training. We observe uniform improvement in test loss across epochs when averaging is applied. This consistent with our theoretical guarantees, which show that logarithmic-sized subsets approximate full group averaging with uniform for all integrabe functions, and hence is reflected uniformly over training as the learned function evolves.
bound that holds
Final Test Loss after Sign-Flip Averading
Efrect of Sign-Flip Averaging over Training
266 X10
24
0.6
22x19
0.5
Text Loos
2x10
0.4
0.3
10x
14
0.1
100
200
300
400
500
Number of Random Sign Files [S]
Spoch
Figure 2: Left: Final test loss when averaging over random subsets S C G of increasing size |S].
Most of the benefit is achieved already at [S] = 32, with only marginal gains beyond that. Right: Test loss over training epochs, with and without averaging using subset of size |SS| 32. The improvement from averaging is observed uniformly over training.
32


Reviews:
[{"review_id": "1g9wMr6Qbp", "reviewer": "Reviewer_MdPu", "summary": "This paper examines the question of the efficiency of enforcing exact equivariant compared to approximate invariance from a theoretical point of view. A framework is developed to precisely characterize the notions of efficiency and approximate invariance in this context. The authors show that, under general assumptions, enforcing exact invariance is exponentially harder than enforcing approximate invariance.", "questions": "- I feel like an additional step that could make the story more complete is a discussion of the potential generalization benefits of approximate invariance. I don't know if such results already exist, maybe a connection to Elesedy and Zaidi 2021 could be drawn.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The paper tackles important and timely questions in geometric deep learning, namely what are the benefits and cost of exact equivariance vs approximate equivariance.\n- The results provided are nontrivial and sound as far as I could check. The formalism could probe useful to prove other results.\n- The paper is well written and clear", "weaknesses": "- The assumption of the function class being a finite-dimensional vector space seems quite strong and potentially restrictive. Can the authors comment on that in the paper?\n- Consider including experimental verification of the claim of logarithmic scaling of averaging complexity for approximate invariance (could be in the appendix)\n- The definition of symmetry for a function coincidences with what is more commonly referred to as invariance, I suggest using that term instead for clarity\n- It seems like the analysis is restricted to invariance and not equivariance. However, this is not clear from the start of the paper. Could the authors clarify that?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "AGGFJhvvLm", "reviewer": "Reviewer_hsGK", "summary": "This paper presents the first formal theory comparing the enforcement difficulty of exact and approximate symmetry in machine learning models. By introducing the notion of averaging complexity, the authors prove an exponential separation: exact symmetry requires linear complexity in the group size, while approximate symmetry needs only logarithmic complexity. Using representation theory and Fourier analysis, the work explains why approximate equivariance is both more flexible and computationally efficient, offering a principled foundation for its empirical success in geometric deep learning.", "questions": "1. The paper focuses on finite groups throughout the analysis. How challenging would it be to extend the notion of averaging complexity to continuous groups, such as $\\mathrm{SO}(3)$ or $\\mathrm{SE}(3)$? Do the authors expect a similar exponential separation between exact and approximate symmetry to hold in that case, or are there fundamental obstacles?\n\n2. The exponential separation result relies on representation-theoretic properties and tensor-power constructions. Could the authors provide additional intuition about the role of the number of distinct character values $K = \\\\{\\mathrm{Tr}(\\rho(g)) : g \\in G\\\\}$? In particular, how should we interpret this parameter in concrete machine learning models?\n\n3. How does averaging complexity relate to empirical training complexity in neural networks that are approximately equivariant? For example, can this framework provide any guidance on the number of samples or architectural constraints required to achieve a desired level of approximate symmetry in practice?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper’s main theorem establishes an exponential separation between exact and approximate symmetry, supported by rigorous analysis using representation theory, Fourier analysis, and probabilistic tools. The writing is clear and well-structured, effectively connecting the theoretical insights to practical implications for generalization and robustness in symmetry-based learning.", "weaknesses": "1. The paper lacks empirical or numerical evidence to support its theoretical claims. Including simple synthetic experiments, such as verifying the predicted scaling laws of averaging complexity in finite groups, would make the results more concrete and help readers connect the abstract theory to observed model behavior.\n2. While the proofs are rigorous, the intuition behind key representation-theoretic arguments, such as the role of tensor powers and character separability in explaining the linear versus logarithmic complexity gap, could be better articulated. Providing illustrative examples of other groups, such as cyclic or dihedral groups, would further improve clarity and highlight the generality of the framework.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Xo8I1aVi6x", "reviewer": "Reviewer_SnX1", "summary": "This paper investigates the theoretical complexity of enforcing exact versus approximate symmetry in machine learning models. The authors introduce a novel framework called \"averaging complexity\" to quantify the cost of symmetry enforcement through action queries. Their main contribution is proving an exponential separation: exact symmetry requires linear averaging complexity in the group size, while approximate symmetry needs only logarithmic complexity. The paper uses representation theory tools to establish these bounds, providing the first theoretical justification for why approximate symmetry is often preferred in practice.", "questions": "Can the authors provide any insight into whether similar results might hold for compact Lie groups? What are the fundamental technical barriers? Would one need to replace action queries with a different notion of complexity?\n\nHow should practitioners use these results? Does the logarithmic bound for approximate symmetry suggest specific algorithmic approaches? Can the probabilistic construction in Theorem 13 be turned into a practical sampling strategy?\n\nThe authors mention constants differ by at most a factor of four between weak and strong approximate symmetry. What are the actual constants? Are they small enough that the logarithmic bound is meaningful for realistic group sizes?\n\nAre the bounds tight? Is there a matching lower bound showing that logarithmic complexity is necessary for approximate symmetry? Can the authors provide examples where the trivial K ≤ |G| bound is achieved versus cases where K is much smaller?\n\nCan the authors provide concrete examples of important function classes or group actions where Assumptions 8 and 9 fail? What happens to the results in these cases?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Originality and Theoretical Contribution\n\nThe paper addresses a significant gap in the literature by providing the first direct theoretical comparison between exact and approximate symmetry enforcement. The exponential separation result (linear versus logarithmic complexity) is novel and formally justifies intuitions from empirical work. The averaging complexity framework itself is a creative abstraction that could enable future theoretical analyses in geometric machine learning.\n\nMathematical Rigor and Technical Quality\n\nThe proofs leverage sophisticated representation theory, including character theory, Fourier analysis on groups, and tensor product decompositions. The constructive proof of Theorem 11 provides explicit bounds on the threshold K where exact symmetry requires full group averaging. The probabilistic construction in Theorem 13 using matrix concentration inequalities is elegant and yields tight logarithmic bounds.\n\nPractical Relevance\n\nThe work connects to important practical considerations in geometric machine learning, including symmetry discovery, robustness to distributional shift, and semi-supervised learning. The theoretical insights help explain why approximate symmetry methods have been successful across various applications from medical imaging to molecular modeling.", "weaknesses": "Limited Scope to Finite Groups\n\nThe entire framework is restricted to finite groups, which significantly limits applicability. Many important symmetries in machine learning involve continuous groups like SO(3) for rotations or SE(3) for molecular systems. The authors acknowledge this limitation but provide no path forward. The technical machinery (character theory, Fourier analysis on finite groups) does not obviously extend to compact Lie groups.\n\nWhile averaging complexity is mathematically elegant, its relationship to practical computational cost or sample complexity is unclear. Action queries are a theoretical construct, but real systems face different bottlenecks (gradient computation, memory, data requirements). The paper would benefit from discussing how averaging complexity relates to these practical concerns.\n\nThe paper is purely theoretical with no experiments whatsoever. Even simple synthetic experiments demonstrating the exponential separation on toy problems would strengthen the work. Without empirical validation, it is difficult to assess whether the constants hidden in the big-O notation matter in practice, or whether the assumptions (faithful action, orbit separability) hold for realistic function classes.\n\nAssumptions 8 and 9 (faithful group action and orbit separability) are needed for Theorem 11 but not for Theorem 13. The paper does not thoroughly discuss when these assumptions hold in practice or provide counterexamples when they fail. For tensor powers reaching degree K, the dimension of the function class grows exponentially, which may be impractical for large groups.\n\nThe paper does not compare averaging complexity to other complexity measures in learning theory such as VC dimension, Rademacher complexity, or sample complexity. Understanding these relationships would better situate the contribution within the broader theoretical landscape.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Dm0fGZcDfk", "reviewer": "Reviewer_gGF9", "summary": "The authors study group averaging procedures for achieving group equivariance. Given a finite group G, a group averaging scheme is a function $\\omega: G\\to \\R$. The group averaging scheme induces a linear averaging operator $[\\mathbb{E}_\\omega(f)](x) = \\sum_{g\\in G}\\omega(g) f(g^{-1}x)$. The 'trivial choice' of $\\omega(g)=1/\\abs{G}$ for all $g\\in G$ yields an operator for which $\\mathbb{E}_\\omega f$ always is invariant to the group action. \n\nThe authors define the size of $\\omega$ as the number of non-zero function values $\\omega(g)$. They then pose the question: How large must $\\omega$ be in order to achieve perfect symmetrization for a given function class $\\mathcal{F}$, and how does this compare to approximate symmetry? By approximate symmetrization, they thereby mean schemes that reduce the equivariance error by a factor $\\varepsilon$, as measured in $L^2$-norm.\n\nThe main results are twofold: First, they show that as long as the function class $\\mathcal{F}$ as a representation of the group contains every irrep of the group, the only scheme that achieves perfect symmetry is the trivial choice -- in particular, the size of $\\omega$ necessarily is equal to $\\vert{G}\\vert$. As a contrast, one can use random constructions to construct $\\omega$ of size $\\log (\\vert G \\vert)/\\varepsilon$", "questions": "1. Can the authors provide some more arguments why $\\mathrm{AC^{ex}}$, $\\mathrm{AC^{wk}}$ and $\\mathrm{AC^{st}}$ is a good way of measuring the hardness of enforcing symmetries? \n\n2. Is there a specific reason why the authors do not just assume that the action of $G$ on $\\mathcal{F}$ is faithful directly?\n\n3. Can the apparent problem that the definition of the tensor product doesn't seem to be correct be fixed?\n\n4. Is the result that $\\mathrm{K}$ can be chosen as $\\vert \\lbrace \\ \\mathrm{Tr}(\\rho(g)) \\ \\vert \\ g \\in G \\rbrace \\vert$ known or new?\n\n5. In the proof of Theorem 13, can the authors point to the concrete matrix concentration inequality they apply in row 1453?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The results of the paper are (mostly, see below for details) correct. The connections between Fourier analysis for finite groups and sampling complexity for achieving invariance through averaging that the authors have discovered are interesting, and they do potentially open up for more research.", "weaknesses": "1. The authors make quite far-reaching claims about their results: They state that their results explain why data rarely is exactly equivariant, and why models exploit approximate symmetries more easily. One has to ask if this is really what they show? What they say is that the only way to achieve exact symmetry through averaging, which is by far not the only way of doing so, is to take an uniform average over the whole group, and that this will need many samples given the function class is, from a representation theory perspective, is complicated enough. The existence of steerable neural networks shows that enforcing symmetry is very possible, and implementing them is arguably not fundamentally harder than implementing any other neural network.\n\n2. Assumption 9 is a lot stronger than the authors make it out to be. For one, it implies assumption 8: If there is a non-trivial group element $g$ for which $gx=x$ for all $x$, there surely cannot exist a function $f$ (in or not in $\\mathcal{F}$) with $f(gx)\\neq f(x)$. In fact, by essentially the same argument, it implies that each element $x$ in the domain has a non-trivial stabiliser $\\{ h \\, \\vert \\, hx=x\\}$. This rules out e.g. the canonical action of the permutation group on $\\mathbb{R}^d$. Since the authors ultimately only need that the action of the group on $\\mathcal{F}$ is faithful, I am unsure why they make this assumption.\n\n3. Definition 10 is as far as I am concerned not the standard definition of a tensor power of function spaces: The elements of the $\\mathcal{F} \\otimes \\mathcal{F}$, for instance, are rather functions on the space $\\mathcal{X}\\times \\mathcal{X}$, with $(f\\otimes g)(x,y) = f(x)g(y)$. I think that this is not just a question of conventions -- note that in order for the representation theoretic machinery to work (in particular that the characters of representation on $\\mathcal{F}^{\\otimes k}$ become $k$:th powers of the characters of the representation on $\\mathcal{F}$), the canonical inner product $\\langle x \\otimes y, z \\otimes w\\rangle = \\langle x,z \\rangle \\langle y,w \\rangle$ needs to be used. This is not what happens when we're forming polynomials from function -- the scalar product is still the $L^2(\\mathcal{X})$-scalar product! \n\n4. There are some mistakes in the reference list. The title of [Bourgain, Gamburd] is missing an $\\mathrm{SL}_2(\\mathbb{F}_p)$,  [Huang, Levie,Villar] and [Tahmasebi,Jegelka;2023] do not have journals. Furthermore, I can't find the paper \"A differentiable metric for discovering groups and unitary representations\" by Dongsung Huh, ICLR 2025. Has the paper changed name at some point?\n\n5. Some parts of the text in the appendix do not flow very well. There are e.g. parts of the texts that are repeated verbatim in several proofs.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "G6R7RCeFcm", "reviewer": "Reviewer_9twD", "summary": "Summary\n\nThis paper investigates the theoretical trade-off between enforcing exact versus approximate symmetry in machine learning models. While exact symmetry is known to act as a strong inductive bias and often improves performance in scientific domains, recent empirical evidence suggests that approximate symmetry can yield greater flexibility and robustness. However, a formal understanding of the cost difference between these two paradigms has been missing.\nTo address this gap, the authors introduce “averaging complexity,” a new framework that quantifies the computational cost of imposing symmetry through averaging operations. Their main theoretical result establishes an exponential separation: under standard conditions, exact symmetry requires linear averaging complexity, while approximate symmetry can be achieved with only logarithmic complexity.\nThis finding provides the first formal justification for the practical advantages of approximate symmetry, showing that small relaxations of exact invariance can substantially reduce computational cost without sacrificing desirable structural properties. Beyond this specific result, the proposed analytical tools and complexity framework are likely to be of independent theoretical interest for the broader study of symmetries and inductive biases in machine learning.", "questions": "1.\tLower Bounds and Tightness: The paper establishes an upper bound of  O(\\log |G| / \\varepsilon)  for approximate symmetry.\nCan the authors characterize whether this rate is tight? In particular, are there matching lower bounds on averaging complexity that depend on the function class F?\n2.\tExtension to Continuous or Lie Groups: The current framework assumes finite groups. How would the results change for compact or continuous groups (e.g., SO(3), SE(3)) where integration replaces summation? Would the averaging complexity still exhibit a logarithmic versus linear separation under appropriate discretization or measure-theoretic assumptions?\n3.\tGeneralization and Robustness: Since approximate symmetry is shown to be easier to enforce, can this framework be extended to analyze generalization error or robustness to distributional shifts?\nFor instance, can one derive bounds on sample complexity or Rademacher complexity as a function of the averaging complexity or \\varepsilon?\n4.\tPractical Implications for Optimization: In practice, symmetry enforcement interacts with gradient-based optimization.\nHow does probabilistic averaging (with only a few sampled group elements) affect gradient variance, bias, and convergence stability during training?\n5.\tFunction Space Dependence: The analysis is primarily framed for continuous functions in L^2(X). Could the authors extend their results to other function spaces—such as Sobolev, Barron, or RKHS spaces—and derive approximation rates depending on smoothness or polynomial degree?\n6.\tAlternative Norms and Metrics: The results rely on L^2-based definitions of approximate symmetry.\nWould the same scaling laws hold under supremum norms or other distances relevant to robust learning or adversarial settings?\n7.\tAdaptive or Data-Dependent Averaging: If the averaging scheme were made adaptive or data-dependent (e.g., learned during training), could one further reduce the \\log |G| scaling? Are there theoretical barriers preventing such improvements?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The paper’s core strength is its clean, theory-driven comparison of exact vs. approximate symmetry, a question that is both timely and genuinely interesting given how often practitioners trade strict equivariance for flexibility. The authors introduce a model-agnostic notion of “averaging complexity” that crisply quantifies the cost of enforcing symmetry via action queries, and they prove a striking exponential separation: exact symmetry needs linear complexity in |G|, whereas approximate symmetry can be achieved with logarithmic complexity. This result not only formalizes widespread empirical intuition—that approximate symmetry is easier and often more robust in practice—but also provides actionable design insight for symmetry-aware learning (e.g., symmetry discovery or semi-supervised settings where small violations are acceptable). Technically, the framework is conceptually simple yet broadly applicable, with proofs that leverage representation theory in a transparent way and yield constructive bounds (e.g., the degree K controlling when exact symmetry becomes linearly expensive). The work thus bridges a real gap between practice and theory, offering a principled rationale for when and why approximate symmetry should be preferred, and supplying tools likely useful beyond the specific results (e.g., for analyzing other symmetry-enforcing pipelines such as group averaging, canonicalization, or data augmentation).", "weaknesses": "The paper tackles an interesting and timely question—contrasting exact vs. approximate symmetry—but its technical development feels overly elementary relative to the ambition of the claim. Most arguments rely on standard representation-theoretic decompositions, Fourier analysis on finite groups, and matrix concentration, yielding a clean but fairly direct O(log |G| / ε) upper bound and a linear lower bound via a Vandermonde-style character argument. As a result, the “exponential separation’’—while appealing—rests on a simplified averaging model (x-independent linear post-processing with action queries) and finite groups, leaving unclear how far the conclusions extend to practically important settings (compact Lie groups such as SO(3)/E(3), continuous domains, learned filters, or non pointwise mechanisms). The lower bound for exact symmetry hinges on tensor-power feature lifts and a bound on K via the number of distinct character values; this can be loose, and the paper does not establish matching lower bounds for approximate symmetry or tight constants (or necessity) in the O(\\log |G|/\\varepsilon) rate. Moreover, the framework abstracts away data- or state-dependent averaging (e.g., frame averaging with x-dependent weights), model-dependent implementations (equivariant layers, steerable kernels), and optimization constraints, so the gap between complexity-in-principle and trainable procedures remains wide. From a learning-theoretic perspective, the results are existential and asymptotic: there are no generalization/error-rate guarantees, no minimax or sample-complexity characterizations tied to the symmetry deficit, and no robustness analysis to noise or misspecification. In short, while the problem is compelling, the paper would benefit from strengthening the main theorems (e.g., tighter—ideally optimal—bounds and explicit constants, extensions beyond finite groups, lower bounds for approximate symmetry, or constructive/algorithmic realizations), thereby elevating the contribution beyond what can be achieved with relatively standard tools.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)