Source-linked AI summary
Universal approximations of invariant maps by neural networks
Dmitry Yarotsky
TL;DR
The paper seeks finite neural-network-like models that intrinsically approximate invariant or equivariant maps while preserving symmetries and completeness. It develops complete constructions for compact groups, translations, and SE(2), including charge-conserving convnets whose limits exactly characterize continuous SE(2)-equivariant maps.
Problem
The paper asks how finite neural-network-like models can intrinsically approximate ground-truth invariant or equivariant maps while remaining symmetry-respecting and provably complete.
Method
The paper constructs symmetry-aware approximators using complete invariant/equivariant architectures, finite-model approximation frameworks, and charge-conserving convnets for SE(2)-equivariant signal maps.
Results
The main results establish universal approximation properties for standard convnets and show that charge-conserving convnets approximate exactly the norm-continuous SE(2)-equivariant maps.
Takeaways & Limitations
The constructions provide complete symmetry-preserving alternatives, including an explicitly complete SN-invariant network modification that avoids symmetrization over SN.
Takeaways & Limitations
The stated SE(2) characterization excludes linear differential operators such as the Laplacian unless they are smoothed to become well-defined and norm-continuous on L2.
Abstract
from arXiv · showhide
We describe generalizations of the universal approximation theorem for neural networks to maps invariant or equivariant with respect to linear representations of groups. Our goal is to establish network-like computational models that are both invariant/equivariant and provably complete in the sense of their ability to approximate any continuous invariant/equivariant map. Our contribution is three-fold. First, in the general case of compact groups we propose a construction of a complete invariant/equivariant network using an intermediate polynomial layer. We invoke classical theorems of Hilbert and Weyl to justify and simplify this construction; in particular, we describe an explicit complete ansatz for approximation of permutation-invariant maps. Second, we consider groups of translations and prove several versions of the universal approximation theorem for convolutional networks in the limit of continuous signals on euclidean spaces. Finally, we consider 2D signal transformations equivariant with respect to the group SE(2) of rigid euclidean motions. In this case we introduce the "charge--conserving convnet" -- a convnet-like computational model based on the decomposition of the feature space into isotypic representations of SO(2). We prove this model to be a universal approximator for continuous SE(2)--equivariant signal transformations.
1 Introduction
The paper develops neural-network-like models that intrinsically preserve group symmetries while remaining complete for approximating invariant or equivariant maps. It applies this framework to compact groups, translations, and two-dimensional rigid motions.
- Symmetry in predictive models: Invariant models satisfy f(Aγx) = f(x), whereas equivariant models satisfy f(Aγx) = Aγf(x) when transformations act on inputs and outputs.Convolutional layers provide a familiar equivariant example for grid translations.
- Research goal: The paper seeks finite neural-network-like models that preserve invariance or equivariance and are complete for approximating continuous symmetric maps.The usual shallow perceptron can break symmetry, motivating architectural modifications.
- Compact groups: For compact groups, an intermediate polynomial layer yields shallow networks that are exactly invariant or equivariant and complete; polarization and Weyl’s theorem simplify the construction.For the symmetric group S_N, the paper gives an explicit complete invariant model without symmetrizing over S_N.
- Translations: For translations, the paper proves universal approximation results for convolutional networks on infinite-dimensional spaces of signals, including pooled and unpooled variants.One result characterizes approximability of signal transformations by continuity and translational equivariance; another concerns scalar maps with pooling.
- SE(2) equivariance: The charge-conserving convnet is a convnet-like universal approximator for signal transformations equivariant under SE(2), using a feature-space decomposition into SO(2) representations.Its construction is motivated by conservation of total angular momentum.
2 Compact groups and shallow approximations
For compact groups and finite-dimensional representations, the paper constructs shallow neural approximators that are exactly invariant or equivariant and complete. Polynomial invariants and equivariants, together with polarization and Weyl’s theorem, yield more constructive forms, including an explicit permutation-invariant ansatz.
- Motivation and setup: The standard shallow neural-network ansatz can break symmetry, motivating models that preserve invariance or equivariance while remaining universal.The paper uses continuous, non-polynomial activations and uniform approximation on compact sets as its approximation framework.
- Symmetrization-based approximations: Propositions 2.1 and 2.2 obtain universal invariant and equivariant approximations by averaging shallow-network expressions over the group.For finite groups, averaging becomes a finite sum; for infinite groups, the integrals can be approximated by sampling.
- Polynomial invariant theory: Hilbert’s theorem supplies finite generating sets of polynomial invariants, enabling continuous invariant maps to be approximated through an intermediate polynomial layer.The analogous equivariant construction uses finite generating sets of polynomial equivariants.
- Polarization and multiplicity reduction: Polarization and Weyl’s theorem reduce dependence on arbitrary isotypic multiplicities, producing more constructive invariant and equivariant approximating ansätze.The equivariant improvement adds an extra equivariant linear layer to handle arbitrary multiplicities.
- Polarization and multiplicity reduction: For finite groups, the polarization-based universal ansatz uses no more than C_T dim V scalar weights, with C depending only on the group.This bound applies because finite groups have finitely many non-isomorphic irreducible modules.
- The symmetric group S_N: For permutation-invariant maps on V = R^N ⊗ R^M, the paper gives an explicit complete S_N-invariant ansatz requiring O(T_1N(M + T_2)) operations.Direct symmetrization can require N! terms and becomes impractical at large N without subsampling that breaks exact invariance.
3 Translations and deep convolutional networks
The paper develops universal approximation results for convolutional networks under translation symmetry, addressing finite-model limitations, pooling, and continuum signals. It proves completeness results for non-local, local deep, and downsampling convnets under distinct settings.
- Motivation: Finite convnets lack full translational symmetry on discretized, bounded domains, motivating results in the limits of infinitesimal grid spacing and infinite domain size.Discretization partially preserves grid translations, but noncompact translation groups cannot generally be represented by finite fully equivariant models.
- Pooling and symmetry: Pooling with stride m reduces equivariance from the grid group (λZ)^2 to its subgroup (mλZ)^2.Accordingly, the paper treats convnets with and without pooling separately.
- Finite grids: Proposition 3.1 shows that continuous equivariant maps on finite discrete grids with periodic boundaries can be approximated by equivariant maps of the stated convolutional form.The result follows by applying the general compact-group proposition to finite abelian groups.
- Continuum signals: Theorem 3.1 characterizes limit points of basic local convnets as exactly the continuous R^ν-equivariant maps between L2 signal spaces.The theorem concerns stacked convolutional layers without pooling and uses increasing range and finer grid spacing in the limit.
- Downsampling: Theorem 3.2 states that limit points of spatially bounded convnets with downsampling are precisely continuous maps, without requiring translation invariance of the approximated map.This model includes pooling and is intended to capture convnets commonly used in practice.
4 Charge-conserving convnets
The paper constructs charge-conserving convnets for continuous SE(ν)-equivariant maps on L2 signal spaces, encoding rotational symmetry intrinsically through SO(2) charge decompositions. It proves these convnets are universal approximators in the norm topology.
- The target is approximating continuous SE(ν)-equivariant maps f: V → U on V = L2(Rν, RdV ) and U = L2(Rν, RdU).
- Unlike explicit SO(ν) symmetrization, the proposed construction is intrinsically SE(ν)-equivariant and does not use rotated grids.
- Theorem 4.1 states that the limit points of charge-conserving convnets are exactly the continuous SE(2)-equivariant maps in the norm topology.
- The approximation proof reduces the problem through finite-dimensional SO(2)-modules and invariant polynomial approximation, then controls discretization and cutoff limits uniformly on compact sets.
5 Discussion
The discussion reviews complete invariant/equivariant approximation constructions across finite-dimensional, translation-equivariant, and SE(2)-equivariant settings, while identifying practical and theoretical limitations.
- Finite-dimensional approximation: Finite-dimensional invariant/equivariant extensions add a special polynomial layer to shallow neural networks, providing universal and exact symmetry properties.The construction requires suitable generating polynomial invariants or equivariants, which can be difficult to identify in practice.
- Finite-dimensional approximation: For the symmetric group S_N, an explicit complete invariant modification avoids symmetrization and offers relatively small computational complexity.The paper presents this as a viable alternative to symmetrization-based constructions.
- SE(2) approximation: Finite charge-conserving convnets approximate norm-continuous SE(2)-equivariant maps in the small-scale limit, and only such maps are approximable under the theorem's conditions.The result applies to maps between L2 spaces of two-dimensional signals.
- SE(2) approximation: Charge-conserving convnets split feature spaces into SO(2) isotypic components and constrain information flow through charge conservation.The model is essentially polynomial, using elementary arithmetic operations arranged to preserve the constraints while retaining full expressivity.
- Limitations: Pooling destroys intrinsic translation invariance for scalar-valued maps in the continuum limit, leaving this construction as an open issue.The discussion notes that further exploration is needed.
- Limitations: The SE(2) universality proof depends on a specialized architecture with commuting linear layers and no arbitrary nonlinearities, motivating extensions to more general models.This structure was essential for proving both equivariance and completeness.
A Proof of Lemma 4.1
The proof establishes convergence of discretized Fourier-based operators by combining uniform norm bounds, Fourier analysis, and convergence arguments on compact subsets.
- Fourier representation: The proof uses a discretized Fourier transform to analyze the relevant operators and their convergence as the grid scale tends to zero.The discretized transform is treated as a unitary isomorphism, and its composition with the discretization projector strongly converges to the standard Fourier transform.
- Fourier representation: Fourier transform represents the discrete differential operators as multiplication operators, enabling spectral analysis of the discretized construction.The operators are expressed through their Fourier-domain multiplier functions.
- Norm bounds: Uniform finite bounds on the discretized kernel norms are obtained, with analogous bounds for the limiting kernels.These bounds support the convergence estimates used later in the proof.
- Convergence: Strong convergence follows from Fourier-domain convergence, dominated convergence, and the unitarity and norm-preserving properties of the translation representation.The proof explicitly invokes dominated convergence after establishing an integrable uniform bound.
- Convergence: Convergence is upgraded to uniform convergence on compact subsets by approximating the compact set with finitely many representative signals.Uniform boundedness controls the error between each signal and its representative.