Universal Approximations of Invariant Maps by Neural Networks

By Dmitry Yarotsky. 2018

249 citations recorded by the source corpus.

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.

Subfields: Computational Theory and Mathematics, Radiology, Nuclear Medicine and Imaging, Statistical and Nonlinear Physics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Radiology, Nuclear Medicine and Imaging

In Statistical and Nonlinear Physics

Citations in the corpus

Set2Graph: Learning Graphs From Sets (2020, neutral): “We denote for an arbitrary tensor A ∈ R a × b ×···× c its inﬁnity norm by For an arbitrary (cid:15) > 0 , there exists an equivariant polynomial This is a standard lemma, similar to (Yarotsky, 2018; Maron et al., 2019c; Segol & Lipman, 2020); for completeness we provide a proof in the supplementary.”
On the Universality of Invariant Networks (2019, methodology): “Universality of ﬁrst order networks is also known when G = S n (Zaheer et al., 2017; Qi et al., 2017; Yarotsky, 2018) in the context of invariant networks that operate on sets or point clouds.”
Universal approximations of permutation invariant/equivariant functions by deep neural networks (2019, background): “Although invariant versions are proved by [22] and [27], the equivariant version of universal approximation theorem for Sn is first in the literature.”
On Learning Sets of Symmetric Elements (2020, background): “…papers studied the properties of equivariant layers (Ravanbakhsh et al., 2017; Kondor & Trivedi, 2018; Cohen et al., 2019a) and characterized the expressive power of models that use such layers (Yarotsky, 2018; Maron et al., 2019c; Keriven & Peyr´e, 2019; Maehara & NT, 2019; Segol & Lipman, 2019).”
Universal Equivariant Multilayer Perceptrons (2020, background): “The first step follows the symmetrisization argument [43], which in its general form is widely used in invariant theory [38].”
HARK Side of Deep Learning - From Grad Student Descent to Automated Machine Learning (2019, background): “…networks, i.e., a single hidden layer network containing a ﬁnite number of neurons can approximate continuous functions with arbitrary precision [37, 38] (ii) the complexity of the computed function by a neural network grows exponentially with its depth, i.e., for every additional hidden layer,…”
Invariant and Equivariant Graph Networks (2018, background): “Yarotsky (2018) suggested certain group invariant/equivariant models and proved their universality.”
Probabilistic Symmetries and Invariant Neural Networks (2020, background): “…distributions, and in that sense they are related to the recent literature on universal approximations (as in Cybenko, 1989; Hornik, 1991) of invariant and equivariant functions (e.g., Yarotsky, 2018; Maron et al., 2019; Keriven and Peyré, 2019; Segol and Lipman, 2020; Ravanbakhsh, 2020).”
Universal Invariant and Equivariant Graph Neural Networks (2019, background): “For regular-grid graphs, they match classical convolutional networks (LeCun et al., 1989) which by design can only approximate translation-invariant or equivariant functions (Yarotsky, 2018).”
On Universal Equivariant Set Networks (2019, background): “Yarotsky (2018) proves that neural networks constructed using a ﬁnite set of invariant and equivariant polynomial layers are also equivariant universal, however his network is not explicit (i.e., the polynomials are not characterized for the equivariant case) and also of less practical interest due…”
On the equivalence between graph isomorphism testing and function approximation with GNNs (2019, background): “[31] proposes a neural network architecture with polynomial layers that is able to achieve universal approximation of invariant or equivariant functions.”