PaperlayerView exact revision on arXiv

Source-linked AI summary

Universal approximations of invariant maps by neural networks

Dmitry Yarotsky

arXiv:1804.10306v1cs.NE

TL;DR

The paper asks how neural-network-like models can intrinsically approximate continuous maps while preserving group invariance or equivariance. It constructs complete invariant/equivariant networks and proves universal approximation results, including for charge-conserving convnets under SE(2).

  • Problem

    The paper studies how finite neural-network-like models can intrinsically approximate continuous maps while preserving prescribed invariance or equivariance.

    Source: §1.1 · p. 2, §1.3 · p. 5

  • Method

    It develops complete invariant/equivariant architectures, including polynomial-layer constructions and charge-conserving convnets for two-dimensional rigid-motion equivariance.

    Source: §5 · p. 57

  • Results

    The paper proves universal approximation for norm-continuous SE(2)-equivariant maps and completeness for an explicitly constructed S_N-invariant network.

    Source: §4.3 · p. 48, §5 · p. 57

  • Takeaways & Limitations

    Charge-conserving convnets provide finite universal approximators for continuous SE(2)-equivariant signal transformations, while the S_N construction offers a viable alternative to symmetrization.

    Source: §5 · p. 57

    The charge-conserving model excludes linear equivariant operators such as the Laplacian when they are not defined on the whole L2 signal space.

    Source: §4 · p. 33

Abstract

from arXiv · show

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 finite neural-network-like models that are intrinsically invariant or equivariant and complete for approximating continuous maps under group symmetries. It treats compact groups, translations on continuous signals, and SE(2) transformations through polynomial layers, convolutional networks, and charge-conserving convnets.

1.2 Related work

  • The work extends universal approximation theory for neural networks to group-invariant and group-equivariant maps, alongside prior studies of invariant features, deep-network expressiveness, and applied symmetry architectures.The introduction situates the results relative to classical approximation results and prior work on invariant representations, convolutional networks, scattering operators, and rotation-invariant recognition.Source: §1.2 · pp. 4–5

1.1 Motivation

  • The paper seeks intrinsic models that preserve prescribed symmetries while remaining complete in the universal-approximation sense.The framework assumes group actions are encoded by linear representations on layer spaces, with equivariance maintained across network links.Source: §1.1 · p. 4, §1.3 · p. 5

1.3 Contribution of this paper

  • For compact groups, polynomial invariant theory yields exactly invariant/equivariant shallow networks with an extra polynomial layer, including a complete SN-invariant model.The construction is based on classical results of Hilbert [1890, 1893] and Weyl [1946], with polarization improving the general approach.Source: §1.3 · pp. 5–6, §1.2 · p. 5
  • For translation groups, the paper proves universal-approximation results for convolutional networks acting on continuous signals over R^ν.Without pooling, approximation is characterized by continuity and translational equivariance; with pooling, continuous scalar maps can be approximated.Source: §1.3 · p. 6
  • For SE(2)-equivariant transformations, the charge-conserving convnet is universal by organizing features into isotypic representations of SO(2).Theorem 4.1 characterizes approximability of L2(R^2, R^dV) to L2(R^2, R^dU) transformations by continuity and SE(2)-equivariance.Source: §1.3 · p. 6

2 Compact groups and shallow approximations

This section develops universal invariant and equivariant shallow-network approximations for compact groups and finite-dimensional real representations. It establishes constructions based on group averaging, polynomial generators, polarization, and an explicit efficient ansatz for symmetric-group invariants.

2.1 Approximations based on symmetrization

  • Group averaging yields universal invariant and equivariant shallow-network approximations; finite groups require finite sums, while infinite-group integrals can be approximated by sampling.The construction assumes compact groups, finite-dimensional representations, and uniform approximation on compact sets.Source: §2.1 · pp. 7–9

2.2 Approximations based on polynomial invariants

  • Hilbert’s theorem reduces compact-group invariant approximation to a finite generating set of polynomial invariants, with equivariants represented using finitely many polynomial equivariant generators.The resulting architectures add a polynomial invariant layer before conventional shallow-network layers.Source: §2.2 · pp. 10–11

2.3 Polarization and multiplicity reduction

  • These polynomial-generator constructions are universal but generally non-constructive, and their generator counts can grow rapidly with the dimensions of the input and output spaces.Polarization and Weyl’s theorem are introduced to ameliorate this limitation by exploiting isotypic decompositions and multiplicities.Source: §2.3 · p. 12
  • Polarization transfers polynomial invariants between isotypic modules with different multiplicities because maps acting on multiplicity factors commute with the group action.If f is invariant on the target module, composing it with such an intertwining map produces an invariant on the source module.Source: §2.3 · pp. 12–13
  • Weyl’s theorem shows that invariants on representations with arbitrary multiplicities are linearly spanned by transformed invariants from multiplicity dim V_α, enabling multiplicity reduction.The construction uses polarization operators and iterates across isotypic components.Source: §2.3 · p. 13
  • Any continuous invariant map can be approximated using the reduced invariant ansatz with an additional linear layer of matrices A_α; for finite groups, it uses at most C^T dim V scalar weights.The ansatz requires an isotypic decomposition and a generating set of invariants, and the extra layer performs multiplication by A_t.Source: §2.3 · p. 14
  • The equivariant analogue likewise approximates every continuous equivariant map with arbitrary multiplicities, reducing construction to particular multiplicities through an extra equivariant linear layer.Polynomial equivariants are handled as invariants in an extended polynomial algebra, and the same polarization argument applies.Source: §2.3 · pp. 15–16

2.4 The symmetric group S_N

  • For V = R^N ⊗ R^M under S_N, the explicit ansatz is complete and exactly invariant, requiring only O(T_1N(M + T_2)) arithmetic operations and activation evaluations.It is constructed by polarizing the first N coordinate power sums and avoids the N! terms required by direct symmetrization.Source: §2.4 · pp. 16–17

3 Translations and deep convolutional networks

This section develops universal-approximation results for translation-equivariant convolutional networks across finite grids and continuum signals. It treats basic and locally stacked architectures, downsampling and pooling, and bounded-domain information flow.

3 Translations and deep convolutional networks

  • Pooling reduces translation equivariance from a grid-translation group to a coarser subgroup, so full R^d-equivariance is treated only for convnets without pooling.A stride-m pooling layer changes equivariance from (λZ)^2 to (mλZ)^2 in the stated example.Source: §3 · p. 18

3.1 Finite abelian groups and single convolutional layers

  • Proposition 3.1 gives a complete Γ-equivariant approximation ansatz for continuous maps on finite abelian groups, using a single non-local convolutional layer on periodic discrete grids.The ansatz is expressible as a linear combination of scalar filters formed from linear convolutions and pointwise nonlinear activations; non-local weights are necessary for single-layer completeness.Source: §3 · p. 19, §3.1 · p. 20

3 Translations and deep convolutional networks

  • Theorem 3.2 covers practical spatially bounded convnets with pooling, without requiring the target map to be translation-invariant.This setting differs from the continuum theorem by allowing bounded domains and pooling rather than full translation equivariance.Source: §3 · p. 19

3.2 Continuum signals and deep convnets

  • The continuum construction extends the finite-grid result to infinitely extended and detailed R^ν signals, while retaining finite computation through discretization, spatial cutoff, and fixed finite receptive fields.The model uses local convolutional layers with nonlinear activations followed by a final pointwise linear layer; increasing detail and range defines the approximation limit.Source: §3.2 · pp. 21–22
  • Theorem 3.1 characterizes exactly the limit points of basic local convnets as the continuous R^ν-equivariant maps under uniform convergence on compact sets.Basic convnets discretize and spatially truncate L2 signals, then apply finitely many stacked local convolutional layers while grid spacing vanishes and range grows.Source: §3.2 · pp. 23–24
  • For fixed λ and T with degenerate output range Λ = 0, basic convnets of spacing λ and depth T approximate any continuous map f : Vλ,(T−1)λLrf → Uλ,0.The approximation uses sufficiently large feature dimensions and suitable weights in the intermediate layers.Source: §3.2 · p. 26
  • The basic-convnet construction uses early layers to approximately copy spatially distributed inputs into a localized representation, followed by two layers that approximate the target map.Nonlinear activations prevent exact copying, so successive layers approximate the required copy operations; additional linear transformations can be incorporated into later layers.Source: §3.2 · pp. 26, 28
  • For continuous translation-equivariant maps on continuum signals, the framework approximates the target on compact sets by choosing sufficiently fine spacing, sufficiently large range, and sufficient depth.The construction combines finite-dimensional approximation at Λ = 0 with truncation and projection limits, and the authors present it as a rigorous framework for continual and infinitely extended signals.Source: §3.2 · pp. 28–29

3.3 Convnets with pooling

  • Pooling erodes translation equivariance, so the downsampling result instead targets real-valued maps f: V → R without assuming translational invariance.The model uses decimation pooling with a fixed stride s, and requires the stride not exceed the receptive-field size so every input node can connect to the next layer.Source: §3.3 · p. 30
  • A map f: V → R is a limit point of convnets with downsampling if and only if it is continuous in the norm topology.The result applies to fixed stride and receptive field satisfying the connectivity constraint, while grid spacing decreases and the spatial range grows.Source: §3.3 · pp. 30–32

4 Charge-conserving convnets

This section develops charge-conserving convnets for continuous SE(2)-equivariant maps through local SO(2)-invariant processing, equivariant feature extraction, and charge-conserving polynomial operations. It establishes their continuity and equivariance in the scaling limit and proves that they can uniformly approximate every continuous SE(2)-equivariant map on compact sets.

4 Charge-conserving convnets

  • The goal is a complete convnet-like model universally approximating continuous SE(ν)-equivariant maps, specialized to ν=2 without explicit SO(2) symmetrization or rotated grids.The construction targets L2(Rν, RdU)-valued equivariant maps and relies on SO(ν) representation theory, which is simplest here because SO(2) is abelian.Source: §4 · pp. 32–34

4.1.1 Pointwise characterization of SE(ν)–equivariant maps

  • Under an additional regularity condition, an SE(ν)-equivariant map is equivalent to an SO(ν)-invariant map obtained by evaluating its output at a fixed point.For Rν-equivariant f, SE(ν)-equivariance holds exactly when f(R(0,θ)Φ)(0)=f(Φ)(0) for every rotation θ and signal Φ.Source: §4.1.1 · pp. 35–36

4.1.2 Equivariant differentiation

  • Equivariant differentiation extracts local features while switching global representations, with ladder operators changing global and local charges oppositely so total charge µ+η is conserved.This motivates decomposing equivariant maps into equivariant differentiations followed by an SO(2)-invariant pointwise map, later approximated by multiplication layers.Source: §4.1.2 · pp. 37–39
  • The differentiation-based Taylor argument requires smoothing for generic L2 signals, and invariant polynomials can be generated efficiently through multiplication subject to charge conservation.The resulting architecture first computes equivariant derivatives and then applies invariant processing independently at each spatial point.Source: §4.1.2 · pp. 38–39

4.1.3 Discretized differential operators

  • Discrete smoothing and differential operators provide a finite implementation whose operators L(a,b)_λ converge strongly, uniformly on compact sets, to their continuum counterparts as λ→0.The number of smoothing layers scales as ⌈4/λ^2⌉, and the target-space choice L∞ supports subsequent pointwise polynomial layers.Source: §4.1.3 · pp. 40–41

4.1.4 Polynomial approximations on SO(2)-modules

  • Every continuous SO(2)-invariant map on a finite-dimensional SO(2)-module can be approximated by polynomial invariants.For real modules, invariant polynomials are generated by complex extension, charge-conserving multiplication, and taking real parts.Source: §4.1.4 · pp. 41, 43

4.2 Charge-conserving convnet

  • The charge-conserving convnet combines smoothing, differentiation, and pointwise multiplication layers, with multiplication transitions constrained by global-charge conservation.Smoothing and differentiation are linear and local, while multiplication layers implement charge-conserving products and linear combinations; the final output has charge zero.Source: §4.2 · pp. 44, 46, 47, Figure 3 · p. 45

4.3 The main result

  • A map f: V → U is a limit point of charge-conserving convnets if and only if it is continuous and SE(2)-equivariant in the norm topology.The limit uses multi-resolution convnets with arbitrarily large output cutoff and sufficiently small grid spacing, uniformly on compact input sets.Source: §4.3 · p. 48
  • The necessity proof shows that every limit point f is continuous and SE(2)-equivariant, with spatial and rotational equivariance combined to establish full SE(2)-equivariance and complete the proof.The rotational step uses a construction that computes a function invariant with respect to SO(2).Source: §4.3 · pp. 50–52
  • Every continuous SE(2)-equivariant map f can be approximated within ε uniformly on compact K by a multi-resolution charge-conserving convnet with sufficiently small λ and Λ > Λ0.The construction establishes sup_{Φ∈K} ∥b f_λ(Φ) − f(Φ)∥ ≤ ε for all sufficiently small λ.Source: §4.3 · pp. 52, 56
  • The approximation first smooths f while preserving continuity and SE(2)-equivariance, then uses a sufficiently large spatial cutoff to approximate outputs on [−Λ, Λ]2.Compactness of the smoothed image and strong convergence of the cutoff projections justify choosing Λ sufficiently large.Source: §4.3 · pp. 52–53
  • The nested finite-dimensional SO(2)-modules Vζ have projections PVζ that converge strongly to the identity, and approximating f reduces to approximating the map efϵ1,ζ for a fixed finite ζ.Source: §4.3 · pp. 53–54
  • Charge-conserving convolution and multiplication layers realize the invariant polynomial in the scaling limit, while uniform compact-set convergence of λ > 0 networks transfers the approximation to actual convnets.The layer construction groups variables by isotypic components and charge, and the convergence is uniform on compact K.Source: §4.3 · pp. 54–56

5 Discussion

The discussion consolidates the paper’s invariant/equivariant approximation results, highlighting explicit permutation-invariant constructions, continuum convnet universality, and the SE(2)-equivariant charge-conserving model. It also identifies practical limitations involving invariant generators, approximation on compact sets, pooling, and restricted architectures.

Finite-dimensional approximation

  • For general compact-group representations, polynomial layers yield universal and exactly invariant/equivariant extensions, but require difficult-to-identify generating polynomial invariants or equivariants.Polarization can reduce this difficulty when modules contain multiple copies of a few basic modules, though the construction may remain impractical.Source: §5 · p. 56
  • For the symmetric group S_N, the complete exactly invariant shallow-network modification avoids symmetrization and has relatively small computational complexity.The construction is presented as a viable alternative to symmetrization-based approaches.Source: §5 · p. 57

Translation-equivariant approximation

  • For L2(R^ν,R^dV) signals, convnets without pooling approximate exactly the norm-continuous R^ν-equivariant maps, while downsampling convnets approximate exactly the norm-continuous scalar maps.These approximation statements use weak comparison on compact subsets because the signal space is infinite-dimensional.Source: §5 · p. 57
  • Compact or precompact input subsets provide a reasonable abstraction for applications, but relating their structure quantitatively to approximation accuracy remains an open direction.Such subsets may arise from finite-parameter continuous generative processes, finite unions, or finite ε-ball coverings.Source: §5 · p. 57

SE(2)-equivariant approximation

  • Finite charge-conserving convnets approximate exactly the norm-continuous SE(2)-equivariant maps from L2(R2,R^dV) to L2(R2,R^dU) in the small-scale limit.The model extends the topological framework used for continuum approximation and equivariance.Source: §5 · p. 57
  • Charge-conserving convnets split features into SO(2) isotypic components and enforce charge-conserving information flow using constrained arithmetic operations (+, −, ∗).Despite their essentially polynomial structure and lack of arbitrary nonlinearities, these operations achieve full expressivity under the imposed constraints.Source: §5 · p. 58

Open limitations

  • The paper does not construct intrinsically R^ν-invariant approximators for scalar maps because adding pooling destroys R^ν-invariance in the continuum limit.The discussion identifies further exploration of this issue as an open problem.Source: §5 · p. 58
  • The charge-conserving architecture’s special three-group layer structure was essential for proving SE(2)-equivariance and completeness, motivating extensions to more general approximation models.Unlike conventional convolutional networks, it uses commuting linear layers and no arbitrary nonlinearities.Source: §5 · p. 58

A Proof of Lemma 4.1

The lemma is proved by adapting the Fourier-transform proof of the central limit theorem to discretized signals, establishing boundedness and convergence of the associated operators as the grid spacing vanishes.

Fourier representation

  • The proof uses the discretized Fourier transform, which is unitary under the grid-scaled inner product and converges strongly to the standard Fourier transform as λ → 0.The discretization projector is composed with the Fourier transform to connect grid signals with the continuum Fourier representation.Source: A Proof of Lemma 4.1 · p. 61

Spectral analysis

  • Fourier transformation represents the discrete differential operators as multiplication operators, enabling explicit analysis of L(a,b)_λ through its spectral form.The argument also rewrites the operator using translations and the discretized kernel Ψ^(λ)_a,b.Source: A Proof of Lemma 4.1 · pp. 62–63

Uniform bounds

  • Expression (A.6) gives a finite bound uniform in λ for ||Ψ^(λ)_a,b||², and the same bound holds for ||Ψ_a,b||².These bounds, together with Cauchy–Schwarz and norm preservation of translations, establish the first lemma statement.Source: A Proof of Lemma 4.1 · p. 63

Strong convergence

  • Dominated convergence proves the required strong convergence by combining uniform integrable bounds on the Fourier multipliers with translation continuity in L2.The proof uses the unitarity of translations and the convergence of the grid displacement δx to zero.Source: A Proof of Lemma 4.1 · p. 64

Uniform convergence on compact sets

  • Convergence of L(a,b)_λΦ to L(a,b)_0Φ is uniform for Φ in compact subsets K ⊂ V, by finite ε-nets and the uniform operator bound.The argument reduces uniform convergence on K to convergence on finitely many approximating signals.Source: A Proof of Lemma 4.1 · p. 64

Related papers

Loading 1804.10306v1…