Why Symmetry Changes Approximation
Many prediction tasks do not depend on the order in which certain inputs are listed. A function of a set of measurements, for example, should give the same output after the measurements are reordered. Such a target has a symmetry that an arbitrary neural network need not respect. A network may approximate the target well but give slightly different predictions on two inputs that differ only by a permitted permutation.
For a finite collection of symmetries, averaging a network over the group gives a direct remedy: the averaged function is exactly invariant, and its approximation error can be bounded by the error of the original network. The construction is conceptually simple, but its computational cost depends on how many group elements are averaged.
The group may be a subgroup of coordinate permutations, or a finite group represented by transformations that permute coordinates. We assume throughout that every transformation maps \(K\) onto itself. This ensures that evaluating the original approximant at \(\rho(h)x\) stays within its domain.
Two Guarantees from Group Averaging
The first guarantee is algebraic: averaging makes a function invariant, even if the original function \(g\) is not. The second is an approximation guarantee: if \(g\) is close to an invariant target everywhere on \(K\), then the average remains just as close. Both rely on averaging over the whole group with equal weights.
Proof. For any \(k\in G\), the group law gives $$ (\mathcal{S}_Gg)(\rho(k)x) =\frac{1}{|G|}\sum_{h\in G}g(\rho(hk)x). $$ As \(h\) runs through \(G\), \(hk\) also runs through every group element exactly once. Reindexing the sum therefore gives \((\mathcal{S}_Gg)(\rho(k)x)=(\mathcal{S}_Gg)(x)\), proving invariance. For the error, use the invariance of \(f\), the triangle inequality, and the fact that \(\rho(h)x\in K\): $$ \begin{aligned} |(\mathcal{S}_Gg)(x)-f(x)| &=\left|\frac{1}{|G|}\sum_{h\in G}\bigl(g(\rho(h)x)-f(\rho(h)x)\bigr)\right|\\ &\leq \frac{1}{|G|}\sum_{h\in G}|g(\rho(h)x)-f(\rho(h)x)|\\ &\leq \varepsilon. \end{aligned} $$ Taking the supremum over \(x\in K\) proves the result. \(\square\)
There is also a useful mean-square version. It needs a condition on the measure: invariance of the target alone does not make an arbitrary measure unchanged by coordinate transformations.
Proof. The inequality \(\left|\frac{1}{m}\sum_{j=1}^m a_j\right|^2\leq\frac{1}{m}\sum_{j=1}^m|a_j|^2\), where \(m=|G|\), follows from convexity of the squared absolute value. Applying it pointwise and integrating gives $$ \int_K|\mathcal{S}_Gg(x)|^2\,d\mu(x) \leq \frac{1}{m}\sum_{h\in G}\int_K|g(\rho(h)x)|^2\,d\mu(x). $$ Measure invariance implies that each integral on the right equals \(\int_K|g(x)|^2\,d\mu(x)\); hence the first inequality follows. For the second, \(f(\rho(h)x)=f(x)\) gives \(\mathcal{S}_Gg-f=\mathcal{S}_G(g-f)\). Apply the first inequality to \(g-f\). The integrability assumptions ensure these integrals are defined. \(\square\)
What the Construction Costs for a Neural Network
Suppose \(G\) acts by coordinate permutations and \(g\) is represented by a feedforward ReLU network with a scalar affine output. For each \(h\in G\), the function \(x\mapsto g(\rho(h)x)\) is represented by the same network with its input coordinates permuted. Put \(|G|\) copies in parallel and average their scalar outputs in the final affine layer. This gives a network for \(\mathcal{S}_Gg\).
If \(g\) has \(W\) nonzero weights and biases, copying the network \(|G|\) times uses at most \(|G|W\) such parameters. The final averaging can be incorporated by multiplying each copy’s output weights and output bias by \(1/|G|\), so it requires no additional hidden layer. Coordinate permutations are wiring changes, not additional learned parameters. Thus the depth can be retained, while the direct construction’s parameter count grows at most linearly in \(|G|\).
Combining this construction with the uniform-error theorem gives a practical implication: whenever an invariant target has an \(\varepsilon\)-accurate network with \(W\) parameters on \(K\), direct symmetrization gives an exactly invariant network with error at most \(\varepsilon\), depth no greater than the original network’s depth, and at most \(|G|W\) parameters. This is an upper bound for this construction, not a claim that every invariant approximation must pay that cost.
Worked Example: Averaging Over a Coordinate Swap
Take \(K=[0,1]^2\) and let \(G\) contain the identity and the swap \((x_1,x_2)\mapsto(x_2,x_1)\). Start with the one-unit ReLU network \(g(x)=\max(0,x_1-x_2)\). Its group average is $$ (\mathcal{S}_Gg)(x_1,x_2) =\frac{1}{2}\left\{\max(0,x_1-x_2)+\max(0,x_2-x_1)\right\}. $$
If \(x_1\geq x_2\), the two ReLU terms are \(x_1-x_2\) and \(0\), so the average is \((x_1-x_2)/2\). If \(x_2>x_1\), they are \(0\) and \(x_2-x_1\), so the average is \((x_2-x_1)/2\). In either case the result is \(|x_1-x_2|/2\), which is unchanged by swapping the coordinates. For example, at \((0.8,0.3)\) the output is \(0.25\), and at \((0.3,0.8)\) it is also \(0.25\). The symmetrized network uses two copies of \(g\); here averaging removes dependence on the input order exactly.
Worked Example: A Cyclic Group of Three Permutations
Let \(G\) consist of the identity and the two cyclic rotations of three coordinates, acting on \(K=[0,1]^3\). Let \(g(x)=x_1\). The group average is $$ (\mathcal{S}_Gg)(x_1,x_2,x_3)=\frac{x_1+x_2+x_3}{3}. $$
A cyclic rotation merely reorders these three summands, so the output is invariant under every element of this group. At \(x=(1,2/5,1/5)\), the output is \((1+2/5+1/5)/3=(8/5)/3=8/15\). Each of the three networks reads one of the three coordinates, and their outputs receive weight \(1/3\). The target symmetry here is only cyclic invariance; the group does not include every possible permutation, even though this particular average happens also to be invariant under all permutations.
Worked Example: Approximating a Symmetric Sum of Squares
On \(K=[0,1]^3\), consider the target \(f(x)=(x_1^2+x_2^2+x_3^2)/3\), invariant under the full permutation group \(S_3\), which has \(3!=6\) elements. Suppose a univariate ReLU network \(q\) satisfies \(\sup_{t\in[0,1]}|q(t)-t^2|\leq 0.02\). Use \(g(x)=q(x_1)\) as the initial network. Averaging over \(S_3\) yields $$ (\mathcal{S}_{S_3}g)(x)=\frac{q(x_1)+q(x_2)+q(x_3)}{3}, $$ because each coordinate occurs in the first position in exactly two of the six permutations.
For every \(x\in K\), subtract the target and bound each of the three terms: $$ \left|(\mathcal{S}_{S_3}g)(x)-f(x)\right| =\left|\frac{1}{3}\sum_{i=1}^3(q(x_i)-x_i^2)\right| \leq\frac{1}{3}\sum_{i=1}^3 0.02=0.02. $$ The averaged network is exactly permutation-invariant and retains the initial uniform error bound. The direct construction uses six copies of the network for \(g\), although repeated transformed copies give the same three evaluations in this particular example. That distinction illustrates that the general group-size bound is a safe construction bound, not always the smallest implementation.
When Group Size Matters
For the full permutation group on \(d\) coordinates, the direct average has \(d!\) terms. The uniform approximation theorem does not deteriorate with \(d!\), but the straightforward network construction may become very large. For a small subgroup, such as cyclic shifts, the number of copies can be much smaller. The relevant complexity for this method is therefore the size of the group actually used to express the target’s invariance.
A large group can make direct symmetrization unattractive even when the target is simple. The bound says that averaging is a reliable way to enforce symmetry; it does not say that enumerating every group element is computationally efficient, nor that the resulting parameter count is necessary. When group elements produce repeated computations, as in the sum-of-squares example, or when a specialized architecture can reuse computations, the direct count can be loose. Those are opportunities for a more economical representation, not exceptions to the averaging guarantee.
Common Pitfall
Averaging over a group does not guarantee that an arbitrary target will be approximated well. The error bound depends on the target being invariant: in the proof, we used \(f(\rho(h)x)=f(x)\) to compare each transformed network output with the same target value. If that equality fails, the average may instead approximate the target averaged over its orbit. Also, an \(L^2\) error bound under a data distribution requires that distribution to be invariant under the group; the uniform bound has no such measure requirement.
In practice, first identify which transformations truly leave the target unchanged. Averaging over a larger group than the problem supports imposes extra invariance and can alter the function being approximated. For a correctly specified finite group, symmetrization gives a precise guarantee: exact invariance, no increase in uniform error, and a direct network-size cost proportional to the group size.
Check Your Understanding
Use the definitions and bounds above to check your understanding of finite-group symmetrization.
- Why must each group transformation map \(K\) onto itself for the stated uniform approximation result?
- If \(g\) has uniform error at most \(\varepsilon\) for an invariant target, what error bound does the group average satisfy, and which inequality gives it?
- What additional condition on a probability measure is needed for the stated \(L^2\) contraction?
- For the full permutation group on four coordinates, how many copies appear in the direct averaging construction?
- Why can averaging over an inappropriate larger group fail to approximate the intended target well?