# A Functional Perspective on Learning Symmetric Functions with Neural
Networks

Aaron Zweig  Courant Institute of Mathematical Sciences, New York University,
New York  Joan Bruna This work is partially supported by the Alfred P. Sloan
Foundation, NSF RI-1816753, NSF CAREER CIF 1845360, and the Institute for
Advanced Study. Courant Institute of Mathematical Sciences, New York
University, New York  Center for Data Science, New York University

###### Abstract

Symmetric functions, which take as input an unordered, fixed-size set, are
known to be universally representable by neural networks that enforce
permutation invariance. These architectures only give guarantees for fixed
input sizes, yet in many practical applications, including point clouds and
particle physics, a relevant notion of generalization should include varying
the input size. In this work we treat symmetric functions (of any size) as
functions over probability measures, and study the learning and representation
of neural networks defined on measures. By focusing on shallow architectures,
we establish approximation and generalization bounds under different choices
of regularization (such as RKHS and variation norms), that capture a hierarchy
of functional spaces with increasing degree of non-linear learning. The
resulting models can be learned efficiently and enjoy generalization
guarantees that extend across input sizes, as we verify empirically.

##  1 Introduction

Deep learning becomes far more efficient with prior knowledge of function
invariants. This knowledge underlies architectural choices that enforce the
invariance or equivariance in the network, including Convolutional Neural
Networks [LeC+98] which encode translation symmetries, and Graph Neural
Networks [Sca+08] which encode conjugate permutation symmetries. For functions
with invariance to permutation of the input elements, several universal
architectures encode this invariance by treating the input as a set [Zah+17,
Qi+17]. However, these formulations assume a constant input size, which
precludes learning an entire family of symmetric functions.

Such symmetric functions appear naturally across several domains, including
particle physics, computer graphics, population statistics and cosmology. Yet,
in most of these applications, the input size corresponds to a sampling
parameter that is independent of the underlying symmetric function of
interest. As a motivating example, consider the function family induced by the
max function, where for varying $N$, $f_{N}(\\{x_{1}\dots
x_{N}\\})=\max_{i\leq N}x_{i}$. It is natural to ask if a network can
simultaneously learn all these functions.

In this work, we interpret input sets as an empirical measure defined over the
base space $\mathbb{I}$, and develop families of neural networks defined over
the space of probability measures _probability measures of $\mathbb{I}$_, as
initially suggested in [PK19, DPC19]. We identify functional spaces
characterized by neural architectures and provide generalization bounds that
showcase a natural hierarchy among spaces of symmetric functions. In
particular, our framework allows us to understand the question of generalizing
across input sizes as a corollary. Our constructions rely on the theory of
infinitely wide neural networks [Ben+06, Ros+07, Bac17], and provide a novel
instance of _depth separation_ leveraging the symmetric structure of the
input.

##### Summary of Contributions:

We consider the infinite-width limit of neural networks taking as domain the
space of probability measures in order to formalize learning of symmetric
function families. We prove a necessary and sufficient condition for which
symmetric functions can be learned. By controlling the amount of non-linear
learning, we partition the space of networks on measures into several function
classes, proving a separation result among the classes as well as proving a
generalization result and empirically studying the performance of these
classes to learn symmetric functions on synthetic and real-world data.

##### Related Work

Several works consider representing symmetric functions of fixed input size
with invariant neural networks, and in particular there are two main universal
architectures, DeepSets [Zah+17] and PointNet [Qi+17]. An alternative
generalization of DeepSets is given in [Mar+19], which proves the universality
of tensor networks invariant to any subgroup of the symmetric group. Regarding
variable input size, the work from [Wag+19] proves lower bounds on
representation of the max function in the DeepSets architecture with a
dependency on input size.

Separately, there is a wide literature considering neural networks that act on
elements on functional data. These results mainly consider universal
approximation [SX96, Sti99, RC05]. The work [MH97] bears some similarity to
the present work, as they prove a quantitative separation between the class of
neural networks and the class of functionals with bounded norm, while our main
result shows separations among several neural network classes.

The work most similar to ours are [PK19, DPC19], which also normalize the
DeepSets architecture to define a function on measures. However, they only
prove the universality of this model, while we justify the model by
classifying symmetric families that are representable and recovering
generalization results. We also build on the framework given by [Bac17], which
introduces function classes to characterize neural networks in the wide limit,
and proves statistical generalization bounds to demonstrate the advantage of
non-linear learning. Although we motivate our work from symmetric functions on
finite sets, there are applications in multi-label learning [Fro+15] and
evolving population dynamics [HGJ16] that require functions of measures.

##### Roadmap:

We introduce notation and summarize the infinite-dimensional convex network
theory theory [Bac17] in Section 2. In Section 3 we introduce measure networks
and characterize their relationship to symmetric functions. Section 4 gives
our main result, separating several classes of measure networks according to
the degree of non-linear learning, and Section 5 introduces generalization
results. Finally, we detail several experiments with the finite instantiation
of measure networks in Section 6.

##  2 Preliminaries

###  2.1 Problem Setup

Let $\mathbb{I}\subseteq\mathbb{R}^{d}$ be a convex domain, and
$N\in\mathbb{N}$. A _symmetric_ function $f:\mathbb{I}^{N}\to\mathbb{R}$ is
such that $f(x_{1},\dots x_{N})=f(x_{\pi(1)},\dots x_{\pi(N)})$ for any
$x\in\mathbb{I}^{N}$ and any permutation $\pi\in\mathcal{S}_{N}$. In this
work, we are interested in learning symmetric functions defined independently
of $N$. Let $\overline{\mathbb{I}}=\bigcup_{N=1}^{\infty}\mathbb{I}^{N}$, then
$f:\overline{\mathbb{I}}\to\mathbb{R}$ is symmetric if $f$ restricted to
$\mathbb{I}^{N}$ is symmetric for each $N\in\mathbb{N}$. Let
$\mathcal{F}_{\mathrm{sym}}$ denote the space of symmetric functions defined
on $\overline{\mathbb{I}}$. This setting is motivated by applications in
statistical mechanics and particle physics, where $N$ is a sampling parameter.

We focus on the realizable regression setting, where we observe a dataset
$\\{(\bm{x}_{i},f^{*}(\bm{x}_{i}))\in\overline{\mathbb{I}}\times\mathbb{R}\\}_{i=1,\dots
n}$ of $n$ samples from an unknown symmetric function $f^{*}$, and
$\bm{x}_{i}$ are drawn iid from a distribution $\mathcal{D}$ on
$\overline{\mathbb{I}}$. The goal is to find a proper estimator
$\hat{f}\in\mathcal{F}_{\mathrm{sym}}$ such that the population error
$\mathbb{E}_{\bm{x}\sim\mathcal{D}}\ell(f^{*}(\bm{x}),\hat{f}(\bm{x}))$ is
low, where $\ell$ is a convex loss.

Following a standard Empirical Risk Minimisation setup [SB14, Bac17], we will
construct hypothesis classes $\mathcal{F}\subset\mathcal{F}_{\mathrm{sym}}$
endowed with a metric $\|f\|_{\mathcal{F}}$, and consider

$\hat{f}\in\operatorname{argmin}_{f\in\mathcal{F};\|f\|_{\mathcal{F}}\leq\delta}\frac{1}{n}\sum_{i=1}^{n}\ell(f^{*}(\bm{x}_{i}),f(\bm{x}_{i}))~{},$
(1)

where $\delta$ is a regularization parameter that is optimised using e.g.
cross-validation. We focus on the approximation and statistical aspects of
this estimator for different choices of $\mathcal{F}$; solving the
optimization problem (1) is not the focus of the present work and will be
briefly discussed in Section 7.

###  2.2 Symmetric Polynomials

A simplest way to approximate symmetric functions is with symmetric
polynomials. Combining Weierstrass approximation theory with a symmetrization
argument, it can be seen that assuming $d=1$, any symmetric continuous
function $f:\mathbb{I}^{N}\rightarrow\mathbb{R}$ can be uniformly approximated
by symmetric polynomials (see [Yar18] for a proof). There are several
canonical bases over the ring of symmetric polynomials, but we will consider
the one given by the power sum polynomials, given by
$p_{k}(x)=\sum_{i=1}^{N}x_{i}^{k}$, with $x\in\mathbb{I}^{N}$.

######  Theorem 2.1 ((2.12) in [Mac98]).

For any symmetric polynomial $f$ on $N$ inputs, there exists a polynomial $q$
such that $f(x)=q(p_{1}(x),\dots,p_{N}(x))$.

If $q$ is linear, this theorem suggests a simple predictor for symmetric
functions across varying $N$. If $x\in\mathbb{I}^{M}$, we can consider
$x\mapsto\sum_{i=1}^{N}c_{i}\left(\frac{1}{M}p_{i}(x)\right)=\sum_{i=1}^{N}c_{i}\mathbb{E}_{y\sim\mu}(y^{i})$
where $\mu=\frac{1}{M}\sum_{j=1}^{M}\delta_{x_{j}}$. The truncated moments of
the empirical distribution given by $x$ act as linear features, which yield an
estimator over any input size $M$. We will consider a generalization of this
decomposition, by moving beyond the polynomial kernel to a general RKHS (see
Section 3.1).

###  2.3 Convex Shallow Neural Networks

By considering the limit of infinitely many neurons [Ben+06, Ros+07], [Bac17]
introduces two norms on shallow neural representation of functions $\phi$
defined over $\mathbb{R}^{d}$. For a constant $R\in\mathbb{R}$, a fixed
probability measure $\kappa\in\mathcal{P}(\mathbb{S}^{d})$ with full support,
a signed Radon measure $\nu\in\mathcal{M}(\mathbb{S}^{d})$, a density $p\in
L_{2}(d\kappa)$, and the notation that $\tilde{x}=[x,R]^{T}$, define:

$\displaystyle\gamma_{1}(\phi)=\inf\left\\{\|\nu\|_{\mathrm{TV}};\,\phi(x)=\int_{\mathbb{S}^{d}}\sigma(\langle
w,\tilde{x}\rangle)\nu(dw)\right\\}~{},\text{ and }$ (2)
$\displaystyle\gamma_{2}(\phi)=\inf\left\\{\|p\|_{L_{2}(d\kappa)};\,\phi(x)=\int_{\mathbb{S}^{d}}\sigma(\langle
w,\tilde{x}\rangle)p(w)\kappa(dw)\right\\}~{},$ (3)

where $\|\nu\|_{\mathrm{TV}}:=\sup_{|g|\leq 1}\int gd\nu$ is the _Total
Variation_ of $\nu$ and $\sigma_{\alpha}(t)=\max(0,t)^{\alpha}$ is the ReLU
activation raised to the positive integer power $\alpha$. These norms measure
the minimal representation of $\phi$, using either a Radon measure $\nu$ over
neuron weights, or a density $p$ over the fixed probability measure $\kappa$.
The norms induce function classes:

$\mathcal{F}_{1}=\\{\phi\in
C_{0}(\mathbb{I}):\gamma_{1}(\phi)<\infty\\}~{},\text{
and}~{}\mathcal{F}_{2}=\\{\phi\in
C_{0}(\mathbb{I}):\gamma_{2}(\phi)<\infty\\}~{}.$ (4)

We also assume that the input domain $\mathbb{I}$ is bounded with
$\sup_{x\in\mathbb{I}}\|x\|_{2}\leq R$.

These two functional spaces are fundamental for the theoretical study of
shallow neural networks and capture two distinct regimes of
overparametrisation: whereas the so-called _lazy_ or kernel regime corresponds
to learning in the space $\mathcal{F}_{2}$ [CB18, JGH18], which is in fact an
RKHS with kernel given by
$k(x,y)=\mathbb{E}_{w\sim\kappa}\left[\sigma_{\alpha}(\langle
w,\tilde{x}\rangle)\sigma_{\alpha}(\langle w,\tilde{y}\rangle)\right]$ [Bac17]
111Or a modified NTK kernel that also includes gradients with respect to
first-layer weights [JGH18] , the mean-field regime captures learning in
$\mathcal{F}_{1}$, which satisfies $\mathcal{F}_{2}\subset\mathcal{F}_{1}$
from Jensen’s inequality, and can efficiently approximate functions with
hidden low-dimensional structure, as opposed to $\mathcal{F}_{2}$ [Bac17].

Finally, one can leverage the fact that the kernel above is an expectation
over features to define a finite-dimensional random feature kernel
$k_{m}(x,y)=\frac{1}{m}\sum_{j=1}^{m}\sigma_{\alpha}(\langle
w_{j},\tilde{x}\rangle)\sigma_{\alpha}(\langle w_{j},\tilde{y}\rangle)$ with
$w_{j}\stackrel{{\scriptstyle i.i.d.}}{{\sim}}\kappa$, which defines a
(random) RKHS $\mathcal{F}_{2,m}$ converging to $\mathcal{F}_{2}$ as $m$
increases [Bac17a, RR08]. The empirical norm $\gamma_{2,m}$ can be defined
similarly to $\gamma_{2}$, where the density $p$ is replaced by coefficients
over the sampled basis functions $\sigma_{\alpha}(\langle
w_{j},\cdot\rangle)$.

###  2.4 Symmetric Neural Networks

A universal approximator for symmetric functions was proposed by [Zah+17],
which proved that for any fixed $N$ and
$f_{N}\in\mathcal{F}_{\mathrm{sym}}^{N}$ there must exist
$\Phi:\mathbb{I}\rightarrow\mathbb{R}^{L}$ and
$\rho:\mathbb{R}^{L}\rightarrow\mathbb{R}$ such that

$f_{N}(x)=\rho\left(\frac{1}{N}\sum_{n=1}^{N}\Phi(x_{n})\right)~{}.$ (5)

However, universality is only proven for fixed $N$. Given a symmetric function
$f\in\mathcal{F}_{\mathrm{sym}}$ we might hope to learn $\rho$ and $\Phi$ such
that this equation holds for all $N$. Note that the fraction $\frac{1}{N}$ is
not present in their formulation, but is necessary for generalization across
$N$ to be feasible (as otherwise the effective domain of $\rho$ could grow
arbitrarily large as $N\rightarrow\infty$).

Treating the input to $\rho$ as an average motivates moving from sets to
measures as inputs, as proposed in [PK19, DPC19]. Given $x\in\mathbb{I}^{N}$,
let $\mu^{(N)}=\frac{1}{N}\sum_{i=1}^{N}\delta_{x_{i}}$ denote the empirical
measure in the space $\mathcal{P}(\mathbb{I})$ of probability measures over
$\mathbb{I}$. Then (5) can be written as
$f_{N}(x)=\rho\left(\int_{\mathbb{I}}\Phi(u)\mu^{(N)}(du)\right)~{}.$

##  3 From Set to Measure Functions

###  3.1 Neural Functional Spaces for Learning over Measures

Equipped with the perspective of (5) acting on an empirical measure, we
consider shallow neural networks that take probability measures as inputs,
with test functions as weights. We discuss in Section 3.2 which functions
defined over sets admit an extension to functions over measures.

Let $\mathcal{A}$ be a subset of $C_{0}(\mathbb{I})$, equipped with its Borel
sigma algebra. For $\mu\in\mathcal{P}(\mathbb{I})$, and a signed Radon measure
$\chi\in\mathcal{M}(\mathcal{A})$, define
${f}:\mathcal{P}(\mathbb{I})\rightarrow\mathbb{R}$ as

${f}(\mu;\chi)=\int_{\mathcal{A}}\widetilde{\sigma}(\langle\phi,\mu\rangle)\chi(d\phi)~{}.$
(6)

where $\widetilde{\sigma}$ is again a scalar activation function, such as the
ReLU, and $\langle\phi,\mu\rangle:=\int_{\mathbb{I}}\phi(x)\mu(dx)$.
Crucially, the space of functions given by ${f}(\cdot;\chi)$ were proven to be
dense in the space of real-valued continuous (in the weak topology) functions
on $\mathcal{P}(\mathbb{I})$ in [PK19, DPC19], and so this network exhibits
universality.

Keeping in mind the functional norms defined on test functions in Section 2.3,
we can introduce analogous norms for neural networks on measures. For a fixed
probability measure $\tau\in\mathcal{P}(\mathcal{A})$, define

$\|f\|_{1,\mathcal{A}}=\inf\left\\{\|\chi\|_{\mathrm{TV}};\,f(\mu)=\\!\int_{\mathcal{A}}\widetilde{\sigma}(\langle\phi,\mu\rangle)\chi(d\phi)\right\\}~{},$
(7)
$\|f\|_{2,\mathcal{A}}=\inf\left\\{\|q\|_{L_{2}};\,f(\mu)=\\!\int_{\mathcal{A}}\widetilde{\sigma}(\langle\phi,\mu\rangle)q(\phi)\tau(d\phi)\right\\}~{},$
(8)

where we take the infima over Radon measures $\chi\in\mathcal{M}(\mathcal{A})$
and densities $q\in L_{2}(d\tau)$. Analogously these norms also induce the
respective function classes
$\mathcal{G}_{1}(\mathcal{A})=\\{f:\|f\|_{1,\mathcal{A}}<\infty\\}$,
$\mathcal{G}_{2}(\mathcal{A})=\\{f:\|f\|_{2,\mathcal{A}}<\infty\\}$. The
argument in Appendix A of [Bac17] implies $\mathcal{G}_{2}(\mathcal{A})$ is an
RKHS, with associated kernel
$k_{\mathcal{G}}(\mu,\mu^{\prime})=\int_{\mathcal{A}}\widetilde{\sigma}(\langle\phi,\mu\rangle)\widetilde{\sigma}(\langle\phi,\mu^{\prime}\rangle)\tau(d\phi)$.

Moving from vector-valued weights to function-valued weights presents an
immediate issue. The space $C_{0}(\mathbb{I})$ is infinite-dimensional, and it
is not obvious how to learn a measure $\chi$ over this entire space. Moreover,
our ultimate goal is to understand finite-width symmetric networks, so we
would prefer the function-valued weights be efficiently calculable rather than
pathological. To that end, we choose the set of test functions $\mathcal{A}$
to be representable as regular neural networks.

Explicitly, using the function norms of Section 2.3, we define

$\displaystyle\mathcal{A}_{1,m}$ $\displaystyle:=$
$\displaystyle\left\\{\phi;~{}\phi(x)=\sum_{j=1}^{m}\alpha_{j}\sigma(\langle
w_{j},\tilde{x}\rangle)~{},\,\|w_{j}\|_{2}\leq 1,\|\alpha\|_{1}\leq
1\right\\},$ $\displaystyle\mathcal{A}_{2,m}$ $\displaystyle:=$
$\displaystyle\left\\{\phi\in\mathcal{F}_{2,m}:\,\gamma_{2,m}(\phi)\leq
1\right\\}~{}.$

$\mathcal{A}_{1,m}$ thus contains functions in the unit ball of
$\mathcal{F}_{1}$ that can be expressed with $m$ neurons, and
$\mathcal{A}_{2,m}$ contains functions in the (random) RKHS
$\mathcal{F}_{2,m}$ obtained by sampling $m$ neurons from $\kappa$. By
definition $\mathcal{A}_{2,m}\subset\mathcal{A}_{1,m}$ for all $m$.
Representational power grows with $m$, and observe that the approximation rate
in the unit ball of $\mathcal{F}_{1}$ or $\mathcal{F}_{2}$ is in $m^{-1/2}$,
obtained for instance with Monte-Carlo estimators [Bac17, MWE19]. Hence we can
also consider the setting where $m=\infty$, with the notation
$\mathcal{A}_{\\{i,\infty\\}}=\\{\phi\in\mathcal{F}_{i}:\gamma_{i}(\phi)\leq
1\\}$. Note also that there is no loss of generality in choosing the radius to
be $1$, as by homogeneity of $\sigma$ any $\phi$ with
$\gamma_{i}(\phi)<\infty$ can be scaled into its respective norm ball.

We now examine the combinations of $\mathcal{G}_{i}$ with $\mathcal{A}_{i}$:

  * •

$\mathcal{S}_{1,m}:=\mathcal{G}_{1}(\mathcal{A}_{1,m})$; the measure $\chi$ is
supported on test functions in $\mathcal{A}_{1,m}$.

  * •

$\mathcal{S}_{2,m}:=\mathcal{G}_{1}(\mathcal{A}_{2,m})$; $\chi$ is supported
on test functions in $\mathcal{A}_{2,m}$.

  * •

$\mathcal{S}_{3,m}:=\mathcal{G}_{2}(\mathcal{A}_{2,m})$; $\chi$ has a density
with regards to $\tau$, which is supported on $\mathcal{A}_{2,m}$.

  * •

The remaining class $\mathcal{G}_{2}(\mathcal{A}_{1,m})$ requires defining a
probability measure $\tau$ over $\mathcal{A}_{1,m}$ that sufficiently spreads
mass outside of any RKHS ball. Due to the difficulty in defining this measure
in finite setting, we omit this class.

Note that from Jensen’s inequality and the inclusion
$\mathcal{A}_{2,m}\subset\mathcal{A}_{1,m}$ for all $m$, we have the
inclusions
$\mathcal{S}_{3,m}\subset\mathcal{S}_{2,m}\subset\mathcal{S}_{1,m}$. And
$\mathcal{S}_{3,m}$ is clearly an RKHS, since it is a particular instantiation
of $\mathcal{G}_{2}(\mathcal{A})$. In the sequel we will drop the subscript
$m$ and simply write $\mathcal{A}_{i}$ and $\mathcal{S}_{i}$.

These functional spaces provide an increasing level of adaptivity: while
$\mathcal{S}_{2}$ is able to adapt by selecting ‘useful’ test functions
$\phi$, it is limited to smooth test functions that lie on the RKHS, whereas
$\mathcal{S}_{1}$ is able to also adapt to more irregular test functions that
themselves depend on low-dimensional structures from the input domain. We let
$\|f\|_{\mathcal{S}_{i}}$ denote the associated norm, i.e.
$\|f\|_{\mathcal{S}_{1}}:=\|f\|_{1,\mathcal{A}_{1}}$.

##### Finite-Width Implementation:

For any $m$, these classes admit a particularly simple interpretation when
implemented in practice. On the one hand, the spaces of test functions are
implemented as a single hidden-layer neural network of width $m$. On the other
hand, the integral representations in (7) and (8) are instantiated by a
finite-sum using ${m^{\prime}}$ neurons, leading to the finite analogues of
our function classes given in Table 1. Specifically,

$\displaystyle
f(\mu)=\frac{1}{m^{\prime}}\\!\sum_{j^{\prime}=1}^{m^{\prime}}b_{j^{\prime}}\widetilde{\sigma}\\!\left(\\!\\!\frac{1}{m}\sum_{j=1}^{m}c_{j^{\prime},j}\int\sigma_{\alpha}(\langle
w_{j^{\prime},j},\tilde{x}\rangle)\mu(dx)\\!\\!\right)$

One can verify [NTS15] that the finite-width proxy for the variation norm is
given by

$\|f\|_{1}=\frac{1}{m^{\prime}}\\!\sum_{j^{\prime}}|b_{j^{\prime}}|\|\phi_{j^{\prime}}\|_{1}\leq\frac{1}{mm^{\prime}}\\!\sum_{j^{\prime},j}|b_{j^{\prime}}||c_{j^{\prime},j}|\|w_{j^{\prime},j}\|~{},$

which in our case corresponds to the so-called path norm [NTS14]. In
particular, under the practical assumption that the test functions
$\phi_{j^{\prime}}$ are parameterized by two-layer networks with shared first
layer, the weight vectors $w_{j^{\prime},j}$ only depend on $j$ and this norm
may be easily calculated as a matrix product of the network weights. We can
control this term by constraining the weights of the first two layers to obey
our theoretical assumptions (of bounded weights and test functions in
respective RKHS balls), and regularize the final network weights. See Section
6 and the Appendix for practical relaxations of the constraints.

|  | First Layer | Second Layer | Third Layer |
---|---|---|---|---|---
| $\mathcal{S}_{1}$ | Trained | Trained | Trained |
| $\mathcal{S}_{2}$ | Frozen | Trained | Trained |
| $\mathcal{S}_{3}$ | Frozen | Frozen | Trained |
Table 1: Training for finite function approximation

###  3.2 Continuous Extension

In general, the functions we want to represent don’t take in measures
$\mu\in\mathcal{P}(\mathbb{I})$ as inputs. In this section, we want to
understand when a function $f$ defined on the power set
$f:\overline{\mathbb{I}}\to\mathbb{R}$ can be extended to a continuous map
$\bar{f}:\mathcal{P}(\mathbb{I})\to\mathbb{R}$ in the weak topology, in the
sense that for all $N\in\mathbb{N}$ and all $(x_{1},\dots
x_{N})\in\mathbb{I}^{N}$,
$\bar{f}\left(\frac{1}{N}\sum_{i=1}^{N}\delta_{x_{i}}\right)=f(x_{1},\dots,x_{N})$.

Observe that by construction $\bar{f}$ captures the permutation symmetry of
the original $f$. Define the mapping
$D:\overline{\mathbb{I}}\rightarrow\mathcal{P}(\mathbb{I})$ by
$D(x_{1},\dots,x_{N})=\frac{1}{N}\sum_{i=1}^{N}\delta_{x_{i}}$. Let
$\hat{\mathcal{P}}_{N}(\mathbb{I}):=D(\mathbb{I}^{N})$ and
$\hat{\mathcal{P}}(\mathbb{I})=\bigcup_{N=1}^{\infty}\hat{\mathcal{P}}_{N}(\mathbb{I})$,
so that $\hat{\mathcal{P}}(\mathbb{I})$ is the set of all finite discrete
measures. For $\mu\in\hat{\mathcal{P}}(\mathbb{I})$, let $N(\mu)$ be the
smallest dimension of a point in $D^{-1}(\mu)$, and let $x$ be this point
(which is unique up to permutation). Then define
$\hat{f}:\hat{\mathcal{P}}(\mathbb{I})\rightarrow\mathbb{R}$ such that
$\hat{f}(\mu)=f_{N}(x)$.

We also write $W_{1}(\mu,\mu^{\prime})$ as the Wasserstein 1-metric under the
$\|\cdot\|_{2}$ norm [Vil08]. The following proposition establishes a
necessary and sufficient condition for continuous extension of $f$:

######  Proposition 3.1.

There exists a continuous extension $\bar{f}$ iff $\hat{f}$ is uniformly
continuous with regard to the $W_{1}$ metric on its domain.

This result formalises the intuition that extending a symmetric function from
sets to measures requires a minimal amount of regularity _across_ sizes. We
next show examples of symmetric families that can be extended to
$\mathcal{P}(\mathbb{I})$.

###  3.3 Examples of Eligible Symmetric Families

##### Moment-based Functions:

Functions based on finite-range interactions across input elements admit
continuous extensions. For example, a function of singleton and pairwise
interactions

$f(x)=\rho\left(\frac{1}{N}\sum_{i=1}^{N}\phi_{1}(x_{i}),\frac{1}{N^{2}}\sum_{i_{1},i_{2}=1}^{N}\phi_{2}(x_{i_{1}},x_{i_{2}})\right)$

is a special case of the continuous measure extension
$\bar{f}(\mu)=\rho\left(\langle\phi_{1},\mu\rangle,\langle\phi_{2},\mu\otimes\mu\rangle\right)$
when $\mu=D(x)$.

##### Ranking:

Suppose that $\mathbb{I}\subseteq\mathbb{R}$. The max function
$f_{N}(x)=\max_{i\leq N}x_{i}$ cannot be lifted to a function on measures due
to discontinuity in the weak topology. Specifically, consider $\mu=\delta_{0}$
and $\nu_{N}=\frac{N-1}{N}\delta_{0}+\frac{1}{N}\delta_{1}$. Then
$\nu_{N}\rightharpoonup\mu$, but for $\hat{f}$ as in Proposition 3.1,
$\hat{f}(\nu_{N})=1\neq 0=\hat{f}(\mu)$.

Nevertheless, we can define an extension on a smooth approximation via the
softmax, namely
$g_{N}^{\lambda}(x)=\frac{1}{\lambda}\log\frac{1}{N}\sum_{i=1}^{N}\exp(\lambda
x_{i})$. This formulation, which is the softmax up to an additive term, can
clearly be lifted to a function on measures, with the bound
$\|g_{N}^{\lambda}-f_{N}\|_{\infty}\leq\frac{\log N}{\lambda}$. Although we
cannot learn the max family across all $N$, we can approximate arbitrarily
well for bounded $N$.

##### Counterexamples:

Define the map $\Delta_{k}:\mathbb{R}^{N}\rightarrow\mathbb{R}^{kN}$ such that
$\Delta_{k}(x)$ is a vector of $k$ copies of $x$. Then a necessary condition
for the function $\hat{f}$ introduced in Proposition 3.1 to be uniformly
continuous is that $f_{N}(x)=f_{kN}(\Delta_{k}(x))$ for any $k$. Intuitively,
if $f_{N}$ can distinguish the input set beyond the amount of mass on each
point, it cannot be lifted to measures. This fact implies any continuous
approximation to the family $f_{N}(x)=x_{[2]}$, the second largest value of
$x$ will incur constant error.

##  4 Approximation and Function Class Separation

###  4.1 Approximation of single ‘neurons’

In the same spirit as the “separations” between $\mathcal{F}_{1}$ and
$\mathcal{F}_{2}$, we characterise prototypical functions that belong to
$\mathcal{S}_{i}$ but have poor approximation rates in $\mathcal{S}_{i+1}$ for
$i=\\{1,2\\}$ in terms of the relevant parameters of the problem, the input
dimensionality $d$ and the bandwidth parameter $m$. Such functions are given
by single neurons in a spherical input regime (details for this setting are
given in the Appendix).

For the remainder of this work, we consider $\widetilde{\sigma}=\sigma$ as the
ReLU activation, and choose $\alpha=2$ such that $\sigma_{2}(t)=\sigma(t)^{2}$
is the squared ReLU.

######  Theorem 4.1 (informal).

Assume $m=\infty$. For appropriate choices of the kernel base measures
$\kappa$ and $\tau$, there exist $f_{1}$ with $\|f_{1}\|_{\mathcal{S}_{1}}\leq
1$ and $f_{2}$ with $\|f_{2}\|_{\mathcal{S}_{2}}\leq 1$ such that:

$\displaystyle\inf_{\|f\|_{\mathcal{S}_{3}}\leq\delta}\|f-f_{2}\|_{\infty}$
$\displaystyle\gtrsim d^{-2}\delta^{-5/d}~{},$
$\displaystyle\inf_{\|f\|_{\mathcal{S}_{2}}\leq\delta}\|f-f_{1}\|_{\infty}$
$\displaystyle\gtrsim|d^{-11}-d^{-d/3}\delta|~{}.$

The choice of the squared ReLU activation in the parameterization of the test
functions is required in the proof separating $\mathcal{S}_{1}$ and
$\mathcal{S}_{2}$. This follows from some properties of spherical harmonic
parity and the decomposition of signed measures into probability measures.

These separations use the infinity norm rather than an appropriate $L_{2}$
norm, and therefore hold in a weaker norm than separation between
$\mathcal{F}_{1}$ and $\mathcal{F}_{2}$. Nevertheless, these separations
confirm that symmetric network expressiveness is _graded_ by the degree of
non-linear learning.

Both results hold in the domain $m=\infty$, so from the concentration of the
empirical kernel $k_{m}\rightarrow k$, with high probability these
approximation lower bounds will still hold for sufficiently large $m$. In
finite-width implementations, however, $m$ may be sufficiently small that the
random kernel more explicitly determines the expressiveness of
$\mathcal{S}_{i,m}$. We experimentally test the presence of these depth
separations with finite $m$ in Section 6.

###  4.2 Approximation of variational symmetric function via Laplace method

Consider any symmetric family $f_{N}(x)=\operatorname{argmin}_{t\in
T}\langle\hat{\mu}_{x},\phi_{t}\rangle$ where $\hat{\mu}_{x}$ is the empirical
measure of $x$, ie, $\hat{\mu}_{x}=\frac{1}{N}\sum_{i}\delta_{x_{i}}$, $T$ is
a Euclidean subset, and $t\mapsto\phi_{t}$ is measurable. For example
$T=\mathbb{R}$ and $\phi_{t}(x)=|t-x|$ yields $f_{N}$ as the median.

Although this function family isn’t necessarily uniformly continuous in the
weak topology, we highlight the option of a Laplace approximation. Define
$E_{\mu}(t):=\langle\mu,\phi_{t}\rangle$ and introduce the density
$p_{\beta}(t)=\frac{1}{Z}e^{-\beta E_{\mu}(t)}$ where $Z=\int_{T}e^{-\beta
E_{\mu}(t)}dt$ is the partition function. Then consider the Gibbs
approximation
$g_{\beta}(\mu):=\mathbb{E}_{p_{\beta}}[t]=\frac{1}{Z}\int_{T}te^{-\beta
E_{\mu}(t)}dt$.

One can verify (e.g. [RRT17]) that $g_{\beta}\to g$ pointwise at a rate
$\sim\frac{d\log(\beta+1)}{\beta}$. As $g_{\beta}$ is continuous, by
universality it can be represented in $\mathcal{S}_{i}$ for all
$i=\\{1,2,3\\}$. An approximation of $g_{\beta}$ is given as a ratio of two
shallow networks
$g_{\beta}(\mu)=\frac{\int_{T}t\sigma_{1}(\langle\mu,\phi_{t}\rangle)dt}{\int_{T}\sigma_{1}(\langle\mu,\phi_{t}\rangle)dt}$,
with $\sigma_{1}(u)=e^{-\beta u}$. However, the approximation rates blow-up as
$\beta\to\infty$ with an exponential dependency on the dimension of $T$.

##  5 Generalization and Concentration

###  5.1 Generalization Bounds

Despite being a larger function class than $\mathcal{F}_{2}$, the class
$\mathcal{F}_{1}$ enjoys a nice generalization bound [Bac17]. Crucially, this
property is inherited when we lift to functions on measures, controlling the
generalization of functions in $\mathcal{S}_{1}$:

######  Proposition 5.1.

Assume for given $\delta$, for all $y$ the loss function $\ell(y,\cdot)$ is
$G$-Lipschitz on $B_{0}(2R^{2}\delta)$, and $l(y,0)\leq RG\delta$. Then with
probability at least $1-t$,

$\sup_{\|f\|_{\mathcal{S}_{1}}\leq\delta}\left|\mathbb{E}_{\mu\sim\mathcal{D}}\ell(f^{*}(\mu),f(\mu))-\frac{1}{n}\sum_{i=1}^{n}\ell(f^{*}(\mu_{i}),f(\mu_{i}))\right|\\\
\leq\frac{2RG\delta+16R^{4}G\delta}{\sqrt{n}}+(4R^{2}G\delta+2RG\delta)\sqrt{\frac{\log
1/t}{2n}}~{}.$

This proposition demonstrates that learning in $\mathcal{S}_{1}$ is not cursed
by the dimension of the underlying input space $\mathbb{I}$. In other words,
the main price for learning in $\mathcal{S}_{1}$ is not in generalization,
despite the size of this class relative to $\mathcal{S}_{2}$ and
$\mathcal{S}_{3}$. In the absence of a lower bound on generalization error for
the RKHS function classes, our experiments investigate the generalization of
these models in practice.

Although $d$ and $N$ do not appear in this bound, these parameters
nevertheless impact the generalization of our function classes
$\mathcal{S}_{i}$. The input dimension controls the separation of the classes
according to Theorem 4.1, and therefore larger $d$ weakens the generalization
of $\mathcal{S}_{2}$ and $\mathcal{S}_{3}$; compare Figure 1 and Figure 4 (in
the Appendix) for how RKHS methods suffer in higher dimensions. Whereas large
$N$ and a natural choice of $\mathcal{D}$ make generalization for
$\mathcal{S}_{1}$, and hence all three classes, nearly trivial, as discussed
in section 5.2.

###  5.2 Concentration across Input Size

Consider the data distribution from which we sample, namely a measure from
$\mathcal{P}\left(\bar{\mathbb{I}}\right)$ to sample finite sets. A natural
way to draw data is to consider the following sampling procedure: given
$\xi\in\mathcal{P}(\mathcal{P}(\mathbb{I}))$ and
$\Omega\in\mathcal{P}(\mathbb{N})$, draw $\mu\sim\xi$ and $N\sim\Omega$,
sample $N$ independent points $x_{i}\sim\mu$, and return
$\\{x_{1},\dots,x_{N}\\}$. If $\xi$ is too peaked, this sampling process will
concentrate very rapidly:

######  Proposition 5.2.

For $\xi=\delta_{\mu^{*}}$, then
$\mathbb{E}\sup_{\|f\|_{\mathcal{S}_{1}}\leq\delta}\left|\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}f(\mu_{i})\right|\lesssim\delta
R^{2}(n^{-1/2}+\mathbb{E}_{N\sim\Omega}[N^{-1/d}])$.

Hence, the question of generalization across differently sized sets becomes
trivial if $N$ is large and $d$ is small. In our experiments, $N\approx d$, so
we will nevertheless choose $\xi=\delta_{\mu}$ for some
$\mu\in\mathcal{P}(\mathbb{I})$. We consider more exotic data distributions
over measures in the experiments on robust mean estimation in Section 6.2.

##  6 Experiments

Figure 1: Test Error for $d=10$ on the neural architectures of Section 3.1

###  6.1 Symmetric Function Approximation

We consider the task of learning several common symmetric functions (see
Figure 1). Our aim is to practically understand the approximation bounds of
Theorem 4.1, as well as the generalization result of Proposition 5.1.
Furthermore, by training and testing on sets of different sizes, we may
consider how the models perform on out-of-distribution generalization across
input size.

##### Experimental Setup:

We instantiate our three function classes in the finite network setting, as
outlined in Table 1. We use input dimension $d=10$. For the finite realization
of $\mathcal{S}_{1}$, we use first hidden layer size $m=100$ and second hidden
layer size $h=100$. Crucially, after fixing the finite architecture
representing $\mathcal{S}_{1}$, we scale up the width by 10 for the models
with frozen weights. That is, the first hidden layer in $\mathcal{S}_{2}$, and
both hidden layers in $\mathcal{S}_{3}$, have width equal to 1000. Increasing
the width makes the $\mathcal{S}_{2}$ and $\mathcal{S}_{3}$ models strictly
more powerful, and this setup allows us to inspect whether a larger number of
random kernel features can compensate for a smaller, trained weight in
approximation. For each model, we use its associated functional norm for
regularization.

Each network is trained on a batch of 100 input sets. For our data
distribution we consider the base domain $\mathbb{I}=[-3,3]^{d}$, and the
distribution over input measures $\xi$ places all its mass on the uniform
measure $U([-3,3]^{d})$. We choose to train with $N=4$, i.e. all networks
train on input sets of size 4, and test on sets of varying size. From the
results we can measure out-of-distribution generalization of finite sets.

The one-dimensional symmetric functions are defined on sets of vectors by
first applying inverse norms, i.e. $f_{N}(x)=\max_{1\leq i\leq
N}\|x_{i}\|_{2}^{-1}$. The potential function calculates the normalized
gravitational potential among equal masses, i.e.
$f_{N}(x)=\frac{2}{N(N-1)}\sum_{i<j}\frac{1}{\|x_{i}-x_{j}\|_{2}}$. The
planted neuron and smooth neuron are given as single-neuron networks, where
following from the proof of Theorem 4.1, the planted neuron weight
initialization is distinct from the model weight initialization. Further
details are given in the Appendix.

We additionally consider an applied experiment on a variant of MNIST to
observe how the finite-width implementations perform on real-world data, by
first mapping images to point clouds. Due to space limitations, details and
results are given in the Appendix.

Figure 2: Planted neurons for $m=100$ (left two) and $m=200$ (right two). The
smooth neuron has weights sampled consistently with $\mathcal{F}_{2}$ while
the regular neuron has weights sampled distinctly from the network
initialization.

##### Discussion:

We observe in Figure 1 that $\mathcal{S}_{3}$ performs substantially worse in
several cases, consistent with this function class being the smallest of those
considered. The classes $\mathcal{S}_{2}$ and $\mathcal{S}_{1}$ are
competitive for some functions, although we observe a trend where
$\mathcal{S}_{1}$ still has better generalization performance. Therefore, the
larger number of random kernel features doesn’t compensate for training a
smaller weight matrix in $\mathcal{S}_{1}$, empirically confirming Theorem
4.1.

The test error on sets of larger size than the training data corroborates the
conclusion of Proposition 3.1. The second-largest-element function generalizes
extremely poorly, consistent with the observation in Section 3.3 that this
function family cannot be approximated without constant error. In particular,
all function classes more effectively generalize across different $N$ on the
softmax than the max, seeing as the latter lacks uniform continuity in measure
space.

The other essential takeaway is the performance of the three models on the
planted neurons in Figure 2. By using a distinct weight initialization for the
neuron, its first layer will have very little mass under $\kappa$, and its
first two layers will have little mass under $\tau$, and therefore random
features will not suffice to approximate this neuron. This is true even with
the scaling of $\mathcal{S}_{2}$ and $\mathcal{S}_{3}$ to enable more random
kernel features, reiterating that these single neuron functions realize a
meaningful separation between the classes. We observe a more similar
performance of $\mathcal{S}_{1}$ and $\mathcal{S}_{2}$ on the smooth_neuron,
as this function is chosen to be exactly representable with the random kernel
features sampled by $\mathcal{S}_{2}$. According to the function class
inclusion it is still representable by $\mathcal{S}_{1}$, but from Theorem 4.1
not efficiently representable by $\mathcal{S}_{3}$, which is consistent with
the results.

Figure 3: Test error for $\mathcal{S}_{1}$ versus unnormalized DeepSets
architecture.

On increasing $m$, the standard deviations of $\mathcal{S}_{2}$ and
$\mathcal{S}_{3}$ shrink with more random kernel features, but
$\mathcal{S}_{1}$ still achieves the best approximation on the neuron. For the
smooth neuron, $\mathcal{S}_{1}$ and $\mathcal{S}_{2}$ perform comparably, but
$\mathcal{S}_{3}$ performs worse even for larger $m$. In Figure 3 we confirm
the need for taking averages rather than sums in the DeepSets architecture, as
the unnormalized model cannot generalize outside of the value of $N=4$ where
it was trained.

###  6.2 Robust Mean Estimation

Symmetric functions naturally arise in the context of empirical estimators. We
consider specifically the task of robust mean estimation [Dia+17], where one
seeks to estimate $\mathbb{E}_{X\sim P}[X]$ given samples drawn from the
mixture distribution $(1-\epsilon)P+\epsilon Q$. For simplicity, we consider
an oblivious contamination model where the true distribution $P$ and the noise
distribution $Q$ have similar mean vectors. Explicitly, each input set is
derived as follows: we sample $m\sim\mathcal{N}(0,\sigma_{m}^{2}I)$,
$m^{\prime}\sim\mathcal{N}(m,\sigma_{m^{\prime}}^{2}I)$, and define
$P=\mathcal{N}(m,\sigma_{P}^{2}I)$ and
$Q=\mathcal{N}(m^{\prime},\sigma_{Q}^{2}I)$. Then each input sets consist of
$N$ samples $(X_{1},\dots,X_{N})$ where
$X_{i}\overset{iid}{\sim}(1-\epsilon)P+\epsilon Q$. Note that each input set
is a corrupted sample with a different true mean vector $m$.

|  | $N=10$ | $\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}N=20$ | $N=30$ | $N=40$
---|---|---|---|---|---
| $\mathcal{S}_{1}$ | $0.335\pm 0.153$ | $\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0.131\pm 0.018$ | $0.091\pm 0.011$ | $0.076\pm 0.011$
| $\mathcal{S}_{2}$ | $0.342\pm 0.153$ | $\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0.137\pm 0.019$ | $0.098\pm 0.012$ | $0.082\pm 0.011$
| $\mathcal{S}_{3}$ | $0.361\pm 0.162$ | $\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0.144\pm 0.020$ | $0.103\pm 0.013$ | $0.087\pm 0.013$
| Sample Mean | $0.385\pm 0.172$ | $\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0.153\pm 0.068$ | $0.093\pm 0.042$ | $0.096\pm 0.043$
| Geometric Median | $0.321\pm 0.144$ | $\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0.138\pm 0.062$ | $0.087\pm 0.039$ | $0.077\pm 0.034$
| Adversarial Estimator | $0.612\pm 0.495$ | $\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0.469\pm 0.550$ | $0.417\pm 0.549$ | $0.420\pm 0.564$
Table 2: Mean squared test error for robust mean estimation among the finite
model instantiations and baselines.

##### Experimental Setup:

The network architecture is the same as above, with $d=10$. We use
$\sigma_{m}=1$, $\sigma_{m^{\prime}}=2$, $\sigma_{P}=\sigma_{Q}=1.5$, and
$\epsilon=0.2$. All networks train on sets of size $N=20$, and test on sets of
varying size, with mean squared error as the objective. As baselines we
consider the naive sample mean, the geometric median, and the adversarially
robust mean estimator proposed in [Dia+17]. The results are given in Table 2.

##### Discussion:

Although the variance is quite high due to the sampling procedure, performance
in this setting confirms that robust mean estimation also realizes the class
separation, and that for this simple corruption model learning is competitive
and in some cases superior to fixed estimators. In particular, the advantage
of $\mathcal{S}_{1}$ over the baselines is most clear for $N=20$, the setting
where it was trained. Although the dependence of the fixed estimators on
$\sigma_{P}$ and $\sigma_{Q}$ vanishes as $N\rightarrow\infty$, the dependence
on these parameters is non-negligible in the regime where $N$ is small, and
therefore the robust mean may not generalize in the sense of Proposition 3.1.
We explore training on different $N$ sizes further in the Appendix. The poor
performance of the adversarial estimator can mainly be attributed to the fact
that the number of samples is considerably smaller than the setting studied in
[Dia+17], weakening the concentration of the empirical covariance matrix on
which this estimator relies.

##  7 Conclusion

In this work, we have analyzed learning and generalization of symmetric
functions through the lens of neural networks defined over probability
measures, which formalizes the learning of symmetric function families across
varying input size. Our experimental data confirms the theoretical insights
distinguishing tiers of non-linear learning, and suggests that symmetries in
the input might be a natural device to study the functional spaces defined by
deeper neural networks. Specifically, and by focusing on shallow
architectures, our analysis extends the fundamental separation between
adaptive and non-adaptive neural networks from [Bac17] to symmetric functions,
leading to a hierarchy of functional spaces
$\mathcal{S}_{3}\subset\mathcal{S}_{2}\subset\mathcal{S}_{1}$, in which
nonlinear learning is added into the parametrization of the network weights
($\mathcal{S}_{2}$), and into the parametrization of test functions
($\mathcal{S}_{1}$) respectively.

A crucial aspect we have not addressed, though, is the computational cost of
learning in $\mathcal{S}_{1}$ through gradient-based algorithms. An important
direction of future work is to build on recent advances in mean-field theory
for learning shallow neural networks [CB20, MWE19, MW+20, DB20].

##### Acknowledgements:

We thank Raghav Singhal for helpful discussions regarding the proof of Theorem
4.1. This work has been partially supported by the Alfred P. Sloan Foundation,
NSF RI-1816753, NSF CAREER CIF-1845360, and NSF CCF-1814524.

## References

  * [Bac17] Francis Bach  “Breaking the curse of dimensionality with convex neural networks”  In _The Journal of Machine Learning Research_ 18.1 JMLR. org, 2017, pp. 629–681
  * [Bac17a] Francis Bach  “On the equivalence between kernel quadrature rules and random feature expansions”  In _The Journal of Machine Learning Research_ 18.1 JMLR. org, 2017, pp. 714–751
  * [Ben+06] Yoshua Bengio et al.  “Convex neural networks”  In _Advances in neural information processing systems_ , 2006, pp. 123–130
  * [CB18] Lenaic Chizat and Francis Bach  “A note on lazy training in supervised differentiable programming”  In _arXiv preprint arXiv:1812.07956_ , 2018
  * [CB20] Lenaic Chizat and Francis Bach  “Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Loss”  In _arXiv preprint arXiv:2002.04486_ , 2020
  * [DB20] Jaume Dios and Joan Bruna  “On Sparsity in Overparametrised Shallow ReLU Networks”  In _arXiv preprint arXiv:2006.10225_ , 2020
  * [Dia+17] Ilias Diakonikolas et al.  “Being robust (in high dimensions) can be practical”  In _International Conference on Machine Learning_ , 2017, pp. 999–1008  PMLR
  * [DPC19] Gwendoline De Bie, Gabriel Peyré and Marco Cuturi  “Stochastic deep networks”  In _International Conference on Machine Learning_ , 2019, pp. 1556–1565
  * [EF14] Costas Efthimiou and Christopher Frye  “Spherical harmonics in p dimensions”  World Scientific, 2014
  * [FG15] Nicolas Fournier and Arnaud Guillin  “On the rate of convergence in Wasserstein distance of the empirical measure”  In _Probability Theory and Related Fields_ 162.3-4 Springer, 2015, pp. 707–738
  * [Fro+15] Charlie Frogner et al.  “Learning with a Wasserstein loss”  In _Advances in neural information processing systems_ , 2015, pp. 2053–2061
  * [He+15] Kaiming He, Xiangyu Zhang, Shaoqing Ren and Jian Sun  “Delving deep into rectifiers: Surpassing human-level performance on imagenet classification”  In _Proceedings of the IEEE international conference on computer vision_ , 2015, pp. 1026–1034
  * [HGJ16] Tatsunori Hashimoto, David Gifford and Tommi Jaakkola  “Learning population-level diffusions with generative RNNs”  In _International Conference on Machine Learning_ , 2016, pp. 2417–2426
  * [JGH18] Arthur Jacot, Franck Gabriel and Clément Hongler  “Neural tangent kernel: Convergence and generalization in neural networks”  In _Advances in neural information processing systems_ , 2018, pp. 8571–8580
  * [KB14] Diederik P Kingma and Jimmy Ba  “Adam: A method for stochastic optimization”  In _arXiv preprint arXiv:1412.6980_ , 2014
  * [LeC+98] Yann LeCun, Léon Bottou, Yoshua Bengio and Patrick Haffner  “Gradient-based learning applied to document recognition”  In _Proceedings of the IEEE_ 86.11 Ieee, 1998, pp. 2278–2324
  * [Mac98] Ian Grant Macdonald  “Symmetric functions and Hall polynomials”  Oxford university press, 1998
  * [Mar+19] Haggai Maron, Ethan Fetaya, Nimrod Segol and Yaron Lipman  “On the Universality of Invariant Networks”  In _International Conference on Machine Learning_ , 2019, pp. 4363–4371
  * [MH97] Hrushikesh Narhar Mhaskar and Nahmwoo Hahm  “Neural networks for functional approximation and system identification”  In _Neural Computation_ 9.1 MIT Press, 1997, pp. 143–159
  * [MW+20] Chao Ma and Lei Wu  “The Quenching-Activation Behavior of the Gradient Descent Dynamics for Two-layer Neural Network Models”  In _arXiv preprint arXiv:2006.14450_ , 2020
  * [MWE19] Chao Ma, Lei Wu and Weinan E  “Barron spaces and the compositional function spaces for neural network models”  In _arXiv preprint arXiv:1906.08039_ , 2019
  * [NTS14] Behnam Neyshabur, Ryota Tomioka and Nathan Srebro  “In search of the real inductive bias: On the role of implicit regularization in deep learning”  In _arXiv preprint arXiv:1412.6614_ , 2014
  * [NTS15] Behnam Neyshabur, Ryota Tomioka and Nathan Srebro  “Norm-Based Capacity Control in Neural Networks” arXiv: 1503.00036  In _arXiv:1503.00036 [cs, stat]_ , 2015  URL: http://arxiv.org/abs/1503.00036
  * [PK19] Tomas Pevny and Vojtech Kovarik  “Approximation capability of neural networks on spaces of probability measures and tree-structured domains”  In _arXiv preprint arXiv:1906.00764_ , 2019
  * [Qi+17] Charles R Qi, Hao Su, Kaichun Mo and Leonidas J Guibas  “Pointnet: Deep learning on point sets for 3d classification and segmentation”  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2017, pp. 652–660
  * [RC05] Fabrice Rossi and Brieuc Conan-Guez  “Functional multi-layer perceptron: a non-linear tool for functional data analysis”  In _Neural networks_ 18.1 Elsevier, 2005, pp. 45–60
  * [Ros+07] Saharon Rosset, Grzegorz Swirszcz, Nathan Srebro and Ji Zhu  “$\ell_{1}$ regularization in infinite dimensional feature spaces”  In _International Conference on Computational Learning Theory_ , 2007, pp. 544–558  Springer
  * [RR08] Ali Rahimi and Benjamin Recht  “Random features for large-scale kernel machines”  In _Advances in neural information processing systems_ , 2008, pp. 1177–1184
  * [RRT17] Maxim Raginsky, Alexander Rakhlin and Matus Telgarsky  “Non-convex learning via stochastic gradient Langevin dynamics: a nonasymptotic analysis”  In _arXiv preprint arXiv:1702.03849_ , 2017
  * [SB14] Shai Shalev-Shwartz and Shai Ben-David  “Understanding machine learning: From theory to algorithms”  Cambridge university press, 2014
  * [Sca+08] Franco Scarselli et al.  “The graph neural network model”  In _IEEE Transactions on Neural Networks_ 20.1 IEEE, 2008, pp. 61–80
  * [Sti99] Maxwell B Stinchcombe  “Neural network approximation of continuous functionals and continuous functions on compactifications”  In _Neural Networks_ 12.3 Elsevier, 1999, pp. 467–477
  * [SX96] Irwin W Sandberg and Lilian Xu  “Network approximation of input-output maps and functionals”  In _Circuits, Systems and Signal Processing_ 15.6 Springer, 1996, pp. 711–725
  * [Vil08] Cédric Villani  “Optimal transport: old and new”  Springer Science & Business Media, 2008
  * [Wag+19] Edward Wagstaff et al.  “On the Limitations of Representing Functions on Sets”  In _International Conference on Machine Learning_ , 2019, pp. 6487–6494
  * [Yar18] Dmitry Yarotsky  “Universal approximations of invariant maps by neural networks”  In _arXiv preprint arXiv:1804.10306_ , 2018
  * [Zah+17] Manzil Zaheer et al.  “Deep sets”  In _Advances in neural information processing systems_ , 2017, pp. 3391–3401

##  Appendix A Omitted Proofs

Table 3: Summary of Notation Notation |  Definition
---|---
$\mathbb{I}$ |  Input domain, subset of $\mathbb{R}^{d}$
$\overline{\mathbb{I}}$ |  $\bigcup_{N=1}^{\infty}\mathbb{I}^{N}$
$\mathcal{A}_{i}$ |  Classes of test functions $\mathbb{I}\rightarrow\mathbb{R}$
$\gamma_{i}$ |  Test function norm
$\mathcal{S}_{i}$ |  Class of functions mapping $\mathcal{P}(\mathbb{I})\rightarrow\mathbb{R}$
$\|\cdot\|_{\mathcal{S}_{i}}$ |  Measure network norm
$D$ |  Map from vectors to empirical measures s.t. $D(x_{1}\dots x_{n})=\sum_{i=1}^{n}\delta_{x_{i}}$
$\hat{\mathcal{P}}(\mathbb{I})$ |  $\bigcup_{N=1}^{\infty}D(\mathbb{I}^{N})$
$\kappa$ |  Fixed probability measure over $\mathbb{S}^{d}$ in first layer
$\nu$ |  Signed measure over $\mathbb{S}^{d}$ in first layer
$\tau$ |  Fixed probability measure over $\mathcal{A}_{i}$ in second layer
$\chi$ |  Signed measure over $\mathcal{A}_{i}$ in second layer
$Y_{k,j}$ |  Orthogonal basis polynomial of degree $k$ and index $j$ on $\mathbb{S}^{d}$
$P_{k}$ |  Legendre polynomial of degree $k$
$g_{k}$ |  the $k$th spherical harmonic of a function $g:\mathbb{S}^{d}\rightarrow\mathbb{R}$

###  A.1 Proof of Proposition 3.1

###### Proof.

We remind our notation. Given $f:\mathbb{I}\rightarrow\mathbb{R}$, the
empirical extension
$\hat{f}:\hat{\mathcal{P}}(\mathbb{I})\rightarrow\mathbb{R}$ is defined as
$\hat{f}(\mu):=f(x_{\mu})$ where $x_{\mu}\in D^{-1}(\mu)$ and
$\|x_{\mu}\|_{0}=\min_{x\in D^{-1}(\mu)}\|x\|_{0}$. And for
$\bar{f}:\mathcal{P}(\overline{\mathbb{I}})\rightarrow\mathbb{R}$, we say this
is a continuous extension of $f$ if $\bar{f}$ is continuous in under the
Wasserstein metric, and $f(x)=\bar{f}(D(x))$ for every real, finite-
dimensional vector $x$.

For the forward implication, if $\bar{f}$ is a continuous extension, then
clearly $\bar{f}=\hat{f}$ restricted to $\hat{\mathcal{P}}(\mathbb{I})$.

Furthermore, continuity of $\bar{f}$ and compactness of
$\mathcal{P}(\mathbb{I})$ implies $\bar{f}$ is uniformly continuous, and
therefore $\hat{f}$ is as well.

For the backward implication, we introduce
$\hat{f}_{\epsilon}(\mu)=\sup_{\nu\in
B_{\epsilon}(\mu)\cap\hat{\mathcal{P}}(\mathbb{I})}\hat{f}(\nu)$ where the
ball $B_{\epsilon}(\mu)$ is defined with the Wasserstein metric. Note that
$\hat{f}_{\epsilon}$ is defined over arbitrary probability measures, not just
discrete measures. Now, we introduce
$\bar{f}(\mu)=\inf_{\epsilon>0}\hat{f}_{\epsilon}(\mu)$, where density of the
discrete measures and uniform continuity of $\hat{f}$ guarantees that
$\bar{f}$ is well-defined and finite.

Uniform continuity implies if $\mu\in\hat{\mathcal{P}}(\mathbb{I})$ then
$\bar{f}(\mu)=\hat{f}(\mu)$. Consider any $y\in\mathbb{I}^{M}$ such that
$\mu=D(y)$, and define a sequence of vectors $y^{i}=(z_{i},y_{2},\dots,y_{M})$
where $z_{i}\rightarrow y_{1}$ and all $z_{i}$ are distinct from elements of
$y$. Every point $y^{i}\in\mathbb{I}^{M}$ has a unique coordinate and
therefore $\hat{f}(D(y^{i}))=f_{M}(y^{i})$. Because $D(y^{i})\rightharpoonup
D(y)$, continuity implies $\hat{f}(D(y))=f_{M}(y)$. Thus, for any
$y\in\mathbb{I}^{M}$, $\bar{f}(D(y))=f_{M}(y)$, which implies $\bar{f}$ is an
extension.

Now, suppose we have an arbitrary convergent sequence of probability measures
$\mu_{n}\rightharpoonup\mu$. By the density of discrete measures, we can
define sequences $\mu_{n}^{m}\rightharpoonup\mu_{n}$ where
$\mu_{n}^{m}\in\hat{\mathcal{P}}(\mathbb{I})$. In particular, we may choose
these sequences such that for all $n$,
$W_{1}(\mu_{n}^{m},\mu_{n})\leq\frac{1}{m}$. Then for any $\epsilon>0$,

$\displaystyle|\bar{f}(\mu)-\bar{f}(\mu_{n})|\leq|\bar{f}(\mu)-\hat{f}_{\epsilon}(\mu)|+|\hat{f}_{\epsilon}(\mu)-\hat{f}(\mu_{n}^{n})|+|\hat{f}(\mu_{n}^{n})-\hat{f}_{\epsilon}(\mu_{n})|+|\hat{f}_{\epsilon}(\mu_{n})-\bar{f}(\mu_{n})|~{}.$

Consider the simultaneous limit as $n\rightarrow\infty$ and
$\epsilon\rightarrow 0$. On the RHS, the first term vanishes by definition,
and the fourth by uniform continuity. For any $\nu\in
B_{\epsilon}(\mu)\cap\hat{\mathcal{P}}(\mathbb{I})$,
$W_{1}(\nu,\mu_{n}^{n})\leq
W_{1}(\nu,\mu)+W_{1}(\mu,\mu_{n})+W_{1}(\mu_{n},\mu_{n}^{n})\rightarrow 0$ in
the limit. So the second term vanishes as well by uniform continuity of
$\hat{f}$. Similarly, for any $\nu\in
B_{\epsilon}(\mu_{n})\cap\hat{\mathcal{P}}(\mathbb{I})$,
$W_{1}(\nu,\mu_{n}^{n})\leq
W_{1}(\nu,\mu_{n})+W_{1}(\mu_{n},\mu_{n}^{n})\rightarrow 0$, and the third
term vanishes by uniform continuity. This proves continuity of $\bar{f}$.

∎

###  A.2 Proof of Proposition 5.1

###### Proof.

We can decompose the generalization error:

$\displaystyle\mathbb{E}$
$\displaystyle\sup_{\|f\|_{\mathcal{S}_{1}}\leq\delta}\left|\mathbb{E}_{\mu\sim\mathcal{D}}\ell(f^{*}(\mu),f(\mu))-\frac{1}{n}\sum_{i=1}^{n}\ell(f^{*}(\mu_{i}),f(\mu_{i}))\right|$
$\displaystyle\leq
2\mathbb{E}\sup_{\|f\|_{\mathcal{S}_{1}}\leq\delta}\left|\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}\ell(f^{*}(\mu_{i}),f(\mu_{i}))\right|$
$\displaystyle\leq
2\mathbb{E}\sup_{\|f\|_{\mathcal{S}_{1}}\leq\delta}\left|\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}\ell(f^{*}(\mu_{i}),0)\right|+2\mathbb{E}\sup_{\|f\|_{\mathcal{S}_{1}}\leq\delta}\left|\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}(\ell(f^{*}(\mu_{i}),0)-\ell(f^{*}(\mu_{i}),f(\mu_{i})))\right|$
$\displaystyle\leq\frac{2RG\delta}{\sqrt{n}}+4R^{2}G\mathbb{E}\sup_{\|f\|_{\mathcal{S}_{1}}\leq\delta}\left|\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}f(\mu_{i})\right|~{},$

where the second step uses symmetrization through the Rademacher random
variable $\epsilon$, and the fourth is by assumption on the loss function
$\ell$, from the fact that $\|f\|_{\mathcal{S}_{1}}\leq\delta$ implies
$\|f\|_{\infty}\leq 2R^{2}\delta$. We decompose the Rademacher complexity
(removing the absolute value by symmetry):

$\displaystyle\mathbb{E}\left[\sup_{\|f\|_{\mathcal{S}_{1}}\leq\delta}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}f(\mu_{i})\right]$
$\displaystyle=\mathbb{E}\left[\sup_{\begin{subarray}{c}\chi\in\mathcal{M}(\mathcal{A})\\\
\|\chi\|_{TV}\leq\delta\end{subarray}}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}\int\sigma(\langle\phi,\mu_{i}\rangle)\chi(d\phi)\right]$
$\displaystyle=\delta\mathbb{E}\left[\sup_{\gamma_{1}(\phi)\leq
1}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}\sigma(\langle\phi,\mu_{i}\rangle)\right]$
$\displaystyle\leq\delta\mathbb{E}\left[\sup_{\gamma_{1}(\phi)\leq
1}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}\langle\phi,\mu_{i}\rangle\right]~{},$

where the last step uses the contraction lemma and that $\sigma$ is
1-Lipschitz.

Now, using the neural network representation of $\phi$:

$\displaystyle\mathbb{E}\left[\sup_{\|f\|_{\mathcal{S}_{1}}\leq\delta}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}f(\mu_{i})\right]$
$\displaystyle\leq\delta\mathbb{E}\left[\sup_{\|\nu\|_{TV}\leq
1}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}\int_{\mathbb{R}^{d}}\int_{\mathbb{S}^{d}}\sigma(\langle
w,\tilde{x}_{i}\rangle)^{2}\nu(dw)\mu_{i}(dx_{i})\right]$
$\displaystyle\leq\delta\mathbb{E}\left[\sup_{\|w\|_{2}\leq
1}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}\mathbb{E}_{\mu_{i}}[\sigma(\langle
w,\tilde{x}_{i}\rangle)^{2}]\right]$
$\displaystyle\leq\delta\mathbb{E}_{\mu_{1},\dots,\mu_{n}}\left[\mathbb{E}\left[\sup_{\|w\|_{2}\leq
1}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}\sigma(\langle
w,\tilde{x}_{i}\rangle)^{2}\middle|x_{1},\dots,x_{n}\right]\right]~{},$

where the last step uses Jensen’s inequality and Fubini’s theorem. The
conditional expectation is itself a Rademacher complexity, so we may apply the
contraction lemma again as the $\sigma(\langle w,\tilde{x}_{i}\rangle)^{2}$
activation is $2\sqrt{2}R$-Lipschitz for the domain $\mathbb{I}$ of
$\tilde{x}_{i}$. Using the variational definition of the $l_{2}$ norm we have
the bound:

$\displaystyle\mathbb{E}\left[\sup_{\|f\|_{\mathcal{S}_{1}}\leq\delta}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}f(\mu_{i})\right]\leq\frac{4R^{2}\delta}{\sqrt{n}}~{}.$

The high probability bound then follows from McDiarmid’s inequality.

∎

###  A.3 Proof of Proposition 5.2

###### Proof.

We appeal to the following concentration inequality for empirical measures
under the Wasserstein metric:

######  Theorem A.1 (Theorem 1 in [FG15]).

Let $\hat{\mu}_{N}=\frac{1}{N}\sum_{j=1}^{N}\delta_{X_{j}}$ where
$X_{i}\sim\mu\in\mathcal{P}(\mathbb{I})$ iid. Then
$\mathbb{E}[W_{1}(\hat{\mu}_{N},\mu)]\lesssim N^{-1/d}$ where $d>2$ is the
dimension of $\mathbb{I}$.

It’s easy to see that any $\phi\in\mathcal{A}_{2}$ has Lipschitz constant
bounded above by $2\sqrt{2}R$, and therefore
$\sup_{\phi\in\mathcal{A}_{2}}|\langle\phi,\mu-\mu^{*}\rangle|\leq
2\sqrt{2}RW_{1}(\mu,\mu^{*})$. Therefore

$\displaystyle\mathbb{E}\left[\sup_{\phi\in\mathcal{A}}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}\left\langle\phi,\mu_{i}\right\rangle\right]$
$\displaystyle\leq\mathbb{E}\left[\sup_{\phi\in\mathcal{A}}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}\left\langle\phi,\mu^{*}\right\rangle\right]+\mathbb{E}\left[\sup_{\phi\in\mathcal{A}}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}\left\langle\phi,(\mu^{*}-\mu_{i})\right\rangle\right]$
$\displaystyle\leq
2R^{2}\mathbb{E}\left[\left|\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}\right|\right]+2\sqrt{2}R\mathbb{E}[W_{1}(\mu_{i},\mu^{*})]$
$\displaystyle\lesssim R^{2}(n^{-1/2}+\mathbb{E}_{N\sim\Omega}[N^{-1/d}])~{}.$

The conclusion then follows from the same Rademacher decomposition as in
Proposition 5.1.

∎

###  A.4 Proof of Theorem 4.1

For simplicity, we consider spherical inputs rather than Euclidean inputs, and
so we may consider $k(x,y)=\int_{\mathbb{S}^{d}}\sigma(\langle
w,x\rangle)\sigma(\langle w,y\rangle)\kappa(dw)$ without the $\tilde{x}$ bias
terms, and assume $x\in\mathbb{S}^{d}$. Note that the Euclidean inputs may be
seen as a restriction of the spherical inputs to an appropriate spherical cap,
see [Bac17] for details of this construction.

####  A.4.1 Spherical Harmonics and Kernel Norm Background

We’ll use $\simeq$ to denote equality up to universal constants. To understand
functions in $\mathcal{A}_{2}$, we require the following details of spherical
harmonics [EF14].

A basis on $\mathbb{S}^{d}$ is given by the orthogonal polynomials $Y_{k,j}$,
where $k\geq 0$ and $1\leq j\leq N(d,k)$ where

$\displaystyle N(d,k)$
$\displaystyle\simeq\frac{k+d}{k}\frac{\Gamma(k+d-1)}{\Gamma(d)\Gamma(k)}$
$\displaystyle\simeq\frac{k+d}{k}\frac{(k+d)^{k+d-3/2}}{d^{d-1/2}k^{k-1/2}}$

The Legendre polynomials $P_{k}(t)$ act on one dimensional real inputs and
satisfy the addition formula

$\displaystyle\sum_{j=1}^{N(d,k)}Y_{k,j}(x)Y_{k,j}(y)=N(d,k)P_{k}(\langle
x,y\rangle)$

Finally, given a function $g:\mathbb{S}^{d}\rightarrow\mathbb{R}$, the $k$th
spherical harmonic of $g$ is the degree $k$ component of $g$ in the orthogonal
basis, equivalently written as

$\displaystyle g_{k}(x)=\int_{\mathbb{S}^{d}}g(y)P_{k}(\langle
x,y\rangle)\kappa(dy)$

We also require several calculations on functions with bounded functional norm
and projections [Bac17], where we remind that we’re using the activation
$\sigma(x)^{2}$. For $g\in\mathcal{A}_{2}$ or $g(x)=\sigma(\langle
w,x\rangle)^{2}$ for any $w\in\mathbb{S}^{d}$, we have that $g_{2k}=0$ for all
$k\geq 2$.

For $g\in\mathcal{A}_{2}$, the norm of each harmonic satisfies
$\|g_{k}\|_{2}^{2}=\lambda_{k}^{2}N(d,k)$, and the kernel norm can be
calculated explicitly as

$\displaystyle\gamma_{2}(g)^{2}=\sum_{k=0,\lambda_{k}\neq
0}^{\infty}\lambda_{k}^{-2}\|g_{k}\|_{L_{2}}^{2}$

We have that $\lambda_{1}\simeq d^{-1}$, $\lambda_{k}=0$ for $k\geq 3$ and $k$
even, and for $k\geq 3$ and $k$ odd:

$\lambda_{k}\simeq\pm\frac{d^{d/2+1/2}k^{k/2-3/2}}{(d+k)^{k/2+d/2+1}}$ (9)

####  A.4.2 Separation of $\mathcal{S}_{1}$ and $\mathcal{S}_{2}$

Let $g(x)=\sigma(\langle x,w\rangle)^{2}$ for an arbitrary
$w\in\mathbb{S}^{d}$, we have that $\|g_{k}\|_{2}^{2}=\lambda_{k}^{2}N(d,k)$.
Define $\tilde{g}=g-\sum_{i=0}^{d^{2}-1}g_{i}$.

The following lemmas capture that $\tilde{g}$ has high correlation with $g$
and exponentially small correlation with functions in $\mathcal{A}_{2}$.

######  Lemma A.2.

The correlation lower bound $\langle g,\tilde{g}\rangle\gtrsim d^{-21/2}$
holds.

###### Proof.

Note that

$\langle
g,\tilde{g}\rangle=\sum_{k=d^{2}}\|g_{k}\|_{2}^{2}=\sum_{k=d^{2}}\lambda_{k}^{2}N(d,k)$
(10)

We can calculate, because $k+d\leq 2k$:

$\displaystyle\lambda_{k}^{2}N(d,k)$
$\displaystyle\simeq\frac{d^{d+1}k^{k-3}}{(d+k)^{k+d+2}}\cdot\frac{k+d}{k}\frac{(k+d)^{k+d-3/2}}{d^{d-1/2}k^{k-1/2}}$
$\displaystyle\simeq d^{3/2}k^{-7/2}(k+d)^{-7/2}$ $\displaystyle\gtrsim
d^{3/2}k^{-7}$

And therefore

$\displaystyle\langle
g,\tilde{g}\rangle\gtrsim\sum_{k=d^{2}}^{\infty}d^{3/2}k^{-7}\geq
d^{3/2}\int_{d^{2}}^{\infty}k^{-7}dk\simeq d^{3/2}(d^{2})^{-6}$

which yields the desired lower bound.

∎

######  Lemma A.3.

The value of the optimization problem

$\displaystyle\max_{\phi}$ $\displaystyle\langle\phi,\tilde{g}\rangle_{L_{2}}$
s.t. $\displaystyle\gamma_{2}(\phi)^{2}\leq\delta^{2}$

is upper bounded by $\delta\cdot d^{1/2-d/3}$

###### Proof.

By orthogonality we may assume
$\phi_{k}=\alpha_{k}\tilde{g}_{k}=\alpha_{k}g_{k}$, where $\alpha_{k}=0$ for
$k<d^{2}$. Then the problem is equivalently

$\displaystyle\min_{\alpha}$
$\displaystyle-\sum_{k=d^{2}}^{\infty}\alpha_{k}\|g_{k}\|_{2}^{2}$ s.t.
$\displaystyle\sum_{k=d^{2}}^{\infty}\alpha_{k}^{2}\lambda_{k}^{-2}\|g_{k}\|_{2}^{2}\leq\delta^{2}$

Taking $\lambda$ as a Lagrangian multiplier yields the optimality condition
$\alpha_{k}=(2\lambda)^{-1}\lambda_{k}^{2}$.

Plugging this into the constraint and introducing notation $S$ yields

$\displaystyle(2\lambda)^{-2}S:=(2\lambda)^{-2}\sum_{k=d^{2}}^{\infty}\lambda_{k}^{2}\|g_{k}\|_{2}^{2}\leq\delta^{2}$

Then the objective (returned to a maximum) obeys the bound

$\displaystyle\sum_{k=d^{2}}(2\lambda)^{-1}\lambda_{k}^{2}\|g_{k}\|_{2}^{2}$
$\displaystyle=(2\lambda)^{-1}S$ $\displaystyle\leq\delta\sqrt{S}$

So it remains to calculate $S$. Plugging in the value of $\|g_{k}\|_{2}^{2}$
gives

$S=\sum_{k=d^{2}}^{\infty}\lambda_{k}^{4}N(d,k)$

We can give the form of each term, using that $k\geq d^{2}$:

$\displaystyle\lambda_{k}^{4}N(d,k)$ $\displaystyle\lesssim
d^{3/2}k^{-7}\frac{d^{d+1}k^{k-3}}{(d+k)^{k+d+2}}$ $\displaystyle\lesssim
d^{3/2}k^{-7}\frac{d^{d+1}k^{k-3}}{k^{k+d+2}}$ $\displaystyle\lesssim
d^{5/2}k^{-12}\left(\frac{d}{k}\right)^{d}$ $\displaystyle\lesssim
d^{5/2}k^{-12}\left(\frac{d}{k^{1/2}}\cdot\frac{1}{k^{1/2}}\right)^{d}$
$\displaystyle\lesssim d^{5/2}k^{-12}k^{-d/2}$

For sufficiently large $d$, we may ignore the lower terms and reduce the
exponential term to $k^{-d/3}$, then:

$\displaystyle
S\lesssim\sum_{k=d^{2}}^{\infty}k^{-d/3}\simeq\int_{d^{2}}^{\infty}k^{-d/3}\simeq
d^{-1}(d^{2})^{1-d/3}$

The bound follows.

∎

Let $h=g-g_{0}-g_{2}$, and define $f_{1}(\mu)=d^{-1}\sigma(\langle
h,\mu\rangle)$, remembering that we’re using the regular ReLU for the measure
network activation.

######  Lemma A.4.

$\|f_{1}\|_{\mathcal{S}_{1}}\lesssim 1$.

###### Proof.

It suffices to bound $\gamma_{1}(h)$, remembering that our test functions are
defined using networks with the squared ReLU activation. Clearly
$\gamma_{1}(g)\leq 1$ as it itself a single neuron. For the other terms, we
can write the harmonics explicitly, using the fact that $P_{0}(t)=1$ and
$P_{2}(t)=\frac{(d+1)t^{2}-1}{d}$. Starting with the constant term $g_{0}$:

$\displaystyle g_{0}(x)$ $\displaystyle=\int_{\mathbb{S}^{d}}g(y)\kappa(dy)$
$\displaystyle=\int_{\mathbb{S}^{d}}\sigma(\langle w,y\rangle)^{2}\kappa(dy)$
$\displaystyle=\int_{\mathbb{S}^{d}}\sigma(y_{1})^{2}\kappa(dy)$
$\displaystyle=\frac{1}{2(d+1)}$

Note that $\sigma(z)^{2}+\sigma(-z)^{2}=z^{2}$, so we can represent a constant
function as a neural network via:

$\displaystyle\sum_{i=1}^{d+1}\sigma(\langle
e_{i},x\rangle)^{2}+\sigma(\langle-e_{i},x\rangle)^{2}$
$\displaystyle=\sum_{i=1}^{d+1}\langle e_{i},x\rangle^{2}$
$\displaystyle=\|x\|_{2}=1$

So we have $\gamma_{1}(g_{0})\leq 1$.

The second spherical harmonic is given as:

$\displaystyle g_{2}(x)$
$\displaystyle=N(d,2)\int_{\mathbb{S}^{d}}g(y)\frac{(d+1)\langle
x,y\rangle^{2}-1}{d}\kappa(dy)$
$\displaystyle=\frac{N(d,2)}{d}\left((d+1)\int_{\mathbb{S}^{d}}g(y)\langle
x,y\rangle^{2}\kappa(dy)-\int_{\mathbb{S}^{d}}g(y)\kappa(dy)\right)$

We can represent the constant term as above, and the first integral as

$\displaystyle\int_{\mathbb{S}^{d}}\sigma(\langle w,y\rangle)^{2}\langle
x,y\rangle^{2}\kappa(dy)$ $\displaystyle=\int_{\mathbb{S}^{d}}\sigma(\langle
w,y\rangle)^{2}(\sigma(\langle x,y\rangle)^{2}+\sigma(\langle
x,-y\rangle)^{2})\kappa(dy)$
$\displaystyle=\int_{\mathbb{S}^{d}}\sigma(\langle
x,y\rangle)^{2}(\sigma(\langle w,y\rangle)^{2}+\sigma(\langle
w,-y\rangle)^{2})\kappa(dy)$
$\displaystyle=\int_{\mathbb{S}^{d}}\sigma(\langle x,y\rangle)^{2}\langle
w,y\rangle^{2}\kappa(dy)$

This last line is a convex neural network representation using the squared
ReLU activation, and thus we have
$\gamma_{1}\left(\int_{\mathbb{S}^{d}}g(y)\langle
x,y\rangle^{2}\kappa(dy)\right)\leq\int_{\mathbb{S}^{d}}\langle
w,y\rangle^{2}\kappa(dy)=\frac{1}{d+1}$.

Thus, $\gamma_{1}(g_{2})\leq\frac{N(d,2)}{d}\left(1+1\right)\lesssim d$. And
all together,
$\gamma_{1}(h)\leq\gamma_{1}(g)+\gamma_{1}(g_{0})+\gamma(g_{2})\lesssim d$.

So by homogeniety the bound on $\|f\|_{\mathcal{S}_{1}}$ follows.

∎

Our choice of $f_{1}$ induces a separation between $S_{1}$ and $S_{2}$.

######  Theorem A.5.

We have that $\|f_{1}\|_{\mathcal{S}_{1}}\lesssim 1$, and

$\inf_{\|f\|_{\mathcal{S}_{2}}\leq\delta}\|f-f_{1}\|_{\infty}\gtrsim|d^{-11}-d^{-d/3}\delta|$
(11)

###### Proof.

Because we’ve subtracted out the $0$th and $2$nd harmonics, and all other even
harmonics are zero, $\tilde{g}$ and $h$ are odd functions.

Consider the signed measure
$\nu(dx):=\frac{2\tilde{g}(x)}{\|\tilde{g}\|_{L_{1}}}\kappa(dx)$, with Jordan
decomposition $\nu=\nu^{+}-\nu^{-}$ with the positive measures
$\nu^{+}(dx):=\frac{2\sigma(\tilde{g}(x))}{\|\tilde{g}\|_{L_{1}}}\kappa(dx)$
and
$\nu^{-}(dx):=\frac{2\sigma(-\tilde{g}(x))}{\|\tilde{g}\|_{L_{1}}}\kappa(dx)$.

Note that from the oddness of $\tilde{g}$ and symmetry of $\kappa$:

$\displaystyle TV(\nu^{-})$
$\displaystyle=\frac{2}{\|\tilde{g}\|_{L_{1}}}\int_{\mathbb{S}^{d}}\sigma(-\tilde{g}(x))\kappa(dx)$
$\displaystyle=\frac{2}{\|\tilde{g}\|_{L_{1}}}\int_{\mathbb{S}^{d}}\sigma(\tilde{g}(-x))\kappa(dx)$
$\displaystyle=\frac{2}{\|\tilde{g}\|_{L_{1}}}\int_{\mathbb{S}^{d}}\sigma(\tilde{g}(x))\kappa(dx)$
$\displaystyle=TV(\nu^{+})$

Because $TV(\nu^{+})+TV(\nu^{-})=TV(\nu)=2$, we conclude $\nu^{+}$ and
$\nu^{-}$ are both probability measures. We’ll use these measures to separate
$f$ and $f_{1}$. By Lipschitz continuity of $\sigma$:

$\displaystyle|f(\nu^{+})-f(\nu^{-})|$
$\displaystyle=\left|\int_{\mathbb{S}^{d}}\sigma(\langle\phi,\nu^{+}\rangle)-\sigma(\langle\phi,\nu^{-}\rangle)\chi(d\phi)\right|$
$\displaystyle\leq\int_{\mathbb{S}^{d}}|\sigma(\langle\phi,\nu+\nu^{-}\rangle)-\sigma(\langle\phi,\nu^{-}\rangle)|\chi(d\phi)$
$\displaystyle\leq\sup_{\gamma_{2}(\phi)\leq
1}|\langle\phi,\nu\rangle|\|f\|_{\mathcal{S}_{2}}$
$\displaystyle\leq\frac{2}{\|\tilde{g}\|_{L_{1}}}\sup_{\gamma_{2}(\phi)\leq
1}|\langle\phi,\tilde{g}\rangle|\|f\|_{\mathcal{S}_{2}}$
$\displaystyle\lesssim\frac{2}{\|\tilde{g}\|_{L_{1}}}d^{1/2-d/3}\delta$

where in the last line we use Lemma A.3.

Concerning the function $f_{1}$, we first use oddness again to notice:

$\displaystyle\langle h,\nu^{-}\rangle$
$\displaystyle=\frac{2}{\|\tilde{g}\|_{L_{1}}}\int_{\mathbb{S}^{d}}h(x)\sigma(-\tilde{g}(x))\kappa(dx)$
$\displaystyle=\frac{2}{\|\tilde{g}\|_{L_{1}}}\int_{\mathbb{S}^{d}}h(x)\sigma(\tilde{g}(-x))\kappa(dx)$
$\displaystyle=\frac{2}{\|\tilde{g}\|_{L_{1}}}\int_{\mathbb{S}^{d}}h(-x)\sigma(\tilde{g}(x))\kappa(dx)$
$\displaystyle=-\langle h,\nu^{+}\rangle$

So $\langle h,\nu\rangle=\langle h,\nu^{+}-\nu^{-}\rangle=2\langle
h,\nu^{+}\rangle$, and therefore from Lemma A.2 with $\alpha=2$,

$\displaystyle d^{-21/2}\lesssim\langle g,\tilde{g}\rangle$
$\displaystyle=\langle h,\tilde{g}\rangle$
$\displaystyle=\frac{\|\tilde{g}\|_{L_{1}}}{2}\langle h,\nu\rangle$
$\displaystyle=\|\tilde{g}\|_{L_{1}}\langle h,\nu^{+}\rangle$

So $\langle h,\nu^{+}\rangle\gtrsim\frac{d^{-21/2}}{\|\tilde{g}\|_{L_{1}}}$,
and we conclude

$\displaystyle|f_{1}(\nu^{+})-f_{1}(\nu^{-})|$
$\displaystyle=d^{-1}|\sigma(\langle h,\nu^{+}\rangle)-\sigma(\langle
h,\nu^{-}\rangle)|$ $\displaystyle=d^{-1}\sigma(\langle h,\nu^{+}\rangle)$
$\displaystyle\gtrsim\frac{d^{-23/2}}{\|\tilde{g}\|_{L_{1}}}$

Now, suppose $\|f-f_{1}\|_{\infty}\leq\epsilon$. Then

$\displaystyle\frac{d^{-23/2}}{\|\tilde{g}\|_{L_{1}}}$
$\displaystyle\lesssim|f_{1}(\nu^{+})-f_{1}(\nu^{-})|$
$\displaystyle\leq|f_{1}(\nu^{+})-f(\nu^{+})|+|f(\nu^{+})-f(\nu^{-})|+|f(\nu^{-})-f_{1}(\nu^{-})|$
$\displaystyle\lesssim\epsilon+\frac{2}{\|\tilde{g}\|_{L_{1}}}d^{1/2-d/3}\delta+\epsilon$

So for sufficiently large $d$, we have
$\frac{|d^{-23/2}-d^{1/2-d/3}\delta|}{\|\tilde{g}\|_{L_{1}}}\lesssim\epsilon$.
Finally, note by Jensen’s inequality and spherical harmonic orthogonality that
$\|\tilde{g}\|_{L_{1}}\leq\|\tilde{g}\|_{L_{2}}\leq\|g\|_{L_{2}}\lesssim
d^{-1/2}$.

∎

####  A.4.3 Separation of $\mathcal{S}_{2}$ and $\mathcal{S}_{3}$

In order to instantiate the class $\mathcal{S}_{3}$, we must fix $\tau$, the
base probability measure over test functions in $\mathcal{A}_{2}$. Consider
some probability distribution $\zeta$ over the square-summable sequences
$l_{2}(\mathbb{R^{+}})$ such that for $c\in supp(\zeta)$,
$\sum_{k=0}^{\infty}c_{k}^{2}=1$. Furthermore, we will make the simplyfing
assumption that $c_{0}=0$. For each $k$ let $\kappa_{k}$ be uniform over
$\mathbb{S}^{N(d,k)-1}$, and note that $N(d,1)=d+1$ so $\kappa=\kappa_{1}$.

Then we sample $\phi\sim\tau$ as
$\phi=\sum_{k=1}^{\infty}\sum_{j=0}^{N(d,k)}\lambda_{k}c_{k}\alpha_{kj}Y_{kj}$
where $c\sim\zeta$ and $\alpha_{k}\sim\kappa_{k}$. Observe that

$\gamma_{2}(\phi)^{2}=\sum_{k=1,\lambda_{k}\neq
0}^{\infty}\sum_{j=1}^{N(d,k)}\lambda_{k}^{-2}\lambda_{k}^{2}c_{k}^{2}\alpha_{kj}^{2}=1$

so $\tau$ indeed samples functions from $\mathcal{A}_{2}$.

We define $f_{2}(\mu)=\sigma(\langle g,\mu\rangle)$ where
$g=\lambda_{1}Y_{1,1}$. Clearly
$\gamma_{2}(g)^{2}=\lambda_{1}^{-2}\lambda_{1}^{2}\|Y_{1,1}\|_{L_{2}}^{2}=1$,
so $\|f_{2}\|_{\mathcal{S}_{2}}\leq 1$.

######  Theorem A.6.

We have that $\|f_{2}\|_{\mathcal{S}_{2}}\leq 1$, and

$\inf_{\|f\|_{\mathcal{S}_{3}}\leq\delta}\|f-f_{2}\|_{\infty}\gtrsim
d^{-2}\delta^{-5/d}$ (12)

###### Proof.

Consider the function $h(x)=\sum_{j=1}^{N(d,1)}\beta_{1,j}Y_{1,j}$ and
probability measure
$\mu_{\beta}^{*}(dx)=\frac{h(x)+\|h\|_{\infty}}{\|h+\|h\|_{\infty}\|_{L_{1}}}\kappa(dx)$.
Observe that

$\displaystyle
f_{2}(\mu_{\beta}^{*})=\frac{\lambda_{1}}{\|h+\|h\|_{\infty}\|_{L_{1}}}\sigma(\langle
e_{1},\beta\rangle)$

For a function $f\in\mathcal{S}_{3}$ with density $q$ with respect to $\tau$,
we have:

$\displaystyle f(\mu_{\beta}^{*})$
$\displaystyle=\int_{\mathcal{A}_{2}}\sigma(\langle\phi,\mu_{\beta}^{*}\rangle)q(\phi)\tau(d\phi)$
$\displaystyle=\frac{\lambda_{1}}{\|h+\|h\|_{\infty}\|_{L_{1}}}\int_{l_{2}(\mathbb{R^{+}})}\int_{\mathbb{S}^{d}}\sigma(\langle
c_{1}\alpha_{1},\beta\rangle)\hat{q}(c,\alpha_{1})\kappa(d\alpha_{1})\zeta(dc)$
$\displaystyle=\frac{\lambda_{1}}{\|h+\|h\|_{\infty}\|_{L_{1}}}\int_{\mathbb{S}^{d}}\sigma(\langle\alpha_{1},\beta\rangle)\left[\int_{l_{2}(\mathbb{R^{+}})}c_{1}\hat{q}(c,\alpha_{1})\zeta(dc)\right]\kappa(d\alpha_{1})$

where $\hat{q}$ marginalizes out all other $\alpha_{k}$ terms. Let
$\tilde{q}(\alpha_{1})=\int_{l_{2}(\mathbb{R^{+}})}c_{1}\hat{q}(c,\alpha_{1})\zeta(dc)$.
From the fact that $c_{1}\leq 1$, and by Jensen’s inequality,
$\|\tilde{q}\|_{L_{2}(\kappa)}\leq\|\hat{q}\|_{L_{2}(\kappa\times\zeta)}\leq\|q\|_{L_{2}(\tau)}$.

Now we may appeal to a separation of test function representations acting on
spherical inputs. From D.5 in [Bac17], there exists some
$\beta\in\mathbb{S}^{d}$ such that

$\displaystyle|\sigma(\langle
e_{1},\beta\rangle)-\int_{\mathbb{S}^{d}}\sigma(\alpha_{1},\beta)\tilde{q}(\alpha_{1})\kappa(d\alpha_{1})\|$
$\displaystyle\gtrsim\|\tilde{q}\|_{L_{2}}^{-5/d}\geq\|q\|_{L_{2}}^{-5/d}$

Therefore

$\displaystyle|f_{2}(\mu_{\beta}^{*})-f(\mu_{\beta}^{*})|\gtrsim\frac{\lambda_{1}}{\|h+\|h\|_{\infty}\|_{L_{1}}}\|q\|_{L_{2}}^{-5/d}$

Finally, note that $\lambda_{1}\simeq d^{-1}$, and by the addition formula and
the fact $P_{k}(1)=1$ for all $k$:

$\displaystyle\|h+\|h\|_{\infty}\|_{L_{1}}$ $\displaystyle\leq
2\|h\|_{\infty}$
$\displaystyle=2\max_{x\in\mathbb{S}^{d}}\sum_{j=1}^{N(d,1)}\beta_{1,j}Y_{1,j}(x)$
$\displaystyle\leq
2\max_{x\in\mathbb{S}^{d}}\|\beta\|_{2}\sqrt{\sum_{j=1}^{N(d,1)}Y_{1,j}(x)^{2}}$
$\displaystyle\leq 2N(d,1)$ $\displaystyle\lesssim d$

So we arrive at the desired bound.

∎

##  Appendix B Experimental Details and Additional Data

##### Synthetic Details:

For all experiments we use the same architecture. Namely, for an input set
$x=(x_{1},\dots,x_{N})$, the network is defined as
$f_{N}(x)=w_{3}^{T}\sigma(W_{2}\frac{1}{N}\sum_{i=1}^{N}\sigma(W_{1}\tilde{x}_{i}))$,
where we choose the architecture as $W_{1}\in\mathbb{R}^{h_{1}\times d}$,
$W_{2}\in\mathbb{R}^{h_{2}\times h_{1}}$, and $w_{3}\in\mathbb{R}^{h_{2}}$.
Here, $h_{1},h_{2}=100$ for $\mathcal{S}_{1}$, $h_{1}=100$ and $h_{2}=1000$
for $\mathcal{S}_{2}$, and $h_{1}=h_{2}=1000$ for $\mathcal{S}_{3}$. The
weights are initialized with the uniform Kaiming initialization [He+15] and
frozen as described in Table 1.

We relax the functional norm constraints to penalties, by introducing
regularizers of the form $\lambda\|f_{N}\|_{\mathcal{S}_{i}}$ for $\lambda$ a
hyperparameter. Let $K(\cdot)$ map a matrix to the vector of row-wise squared
norms, and let $|\cdot|$ denote the element-wise absolute value of a matrix.
Then we calculate the functional norms via the path norm as follows:

  * •

For $\mathcal{S}_{1}$,
$\|f_{N}\|_{\mathcal{S}_{1}}=|w_{3}|^{T}|W_{2}|K(W_{1})$

  * •

For $\mathcal{S}_{2}$, we explicitly normalize the frozen matrix $W_{1}$ to
have all row-wise norms equal to 1, then
$\|f_{N}\|_{\mathcal{S}_{2}}=|w_{3}|^{T}K(W_{2})$

  * •

For $\mathcal{S}_{3}$, we normalize the rows of $W_{1}$ and $W_{2}$, which
simply implies $\|f_{N}\|_{\mathcal{S}_{3}}=\|w_{3}\|_{2}$

We optimized via Adam [KB14] with an initial learning rate of 0.0005, for 5000
iterations. Under this architecture, all $\mathcal{S}_{1}$, $\mathcal{S}_{2}$
and $\mathcal{S}_{3}$ functions achieved less than $10^{-15}$ training error
without regularization on all objective functions (listed below) on training
sets of 100 samples.

We use the following symmetric functions for our experiments:

  * •

$f_{N}^{*}(x)=\mathrm{max}_{i}(\|x_{i}\|_{2}^{-1})$

  * •

$f_{N}^{*}(x)=\lambda\log\left(\sum_{i=1}^{N}\exp(\|x_{i}\|_{2}^{-1}/\lambda)\right)$
for $\lambda=0.1$

  * •

$f_{N}^{*}(x)=\mathrm{median}(\\{\|x_{i}\|_{2}^{-1}\\}_{i=1}^{N})$

  * •

$f_{N}^{*}(x)=\mathrm{second}_{i}(\|x_{i}\|_{2}^{-1})$ i.e. the second largest
value in a given set

  * •

$f_{N}^{*}(x)=\frac{1}{N}\sum_{i=1}^{N}(\|x_{i}\|_{2}^{-1})$

  * •

$f_{N}^{*}(x)=\frac{2}{N(N-1)}\sum_{i<j}\frac{1}{\|x_{i}-x_{j}\|_{2}}$

  * •

$f_{N}^{*}(x)$ is an individual neuron, parameterized the same as $f_{N}$ but
with different hidden layer sizes. For the neuron, $h_{1}=h_{2}=1$, for the
smooth_neuron, $h_{1}=100$ and $h_{2}=1$. Additionally, the proof of Theorem
A.5 dictates that we must choose the neuron’s test function to have large
kernel norm, so we initialize $W_{1}$ elementwise from the Gaussian mixture
with density $0.5*\mathcal{N}(1,0.5)+0.5*\mathcal{N}(-1,0.5)$.

Note that in order to guarantee the “smooth_neuron" is representable by our
finite-width networks, we explicitly set $W_{1}$ in the $\mathcal{S}_{2}$ and
$\mathcal{S}_{3}$ models to equal the $W_{1}$ matrix of the “smooth_neuron".

For each model in each experiment, $\lambda$ was determined through cross
validation over $\lambda\in[0,10^{-6},10^{-4},10^{-2}]$ using fresh samples of
training data, and choosing the value of $\lambda$ with lowest generalization
error, which was calculated from another 1000 sampled points.

Then, with determined $\lambda$, each model was trained from scratch over 10
runs with independent random initializations. The mean and standard deviation
of the generalization error, testing on varying values of $N$, are plotted in
Figure 1.

##### Application Details:

For the MNIST experiment with results given in Table 4, we follow a similar
setup to [DPC19]. From an image in $\mathbb{R}^{28\times 28}$, we produce a
point cloud by considering a set of tuples of the form $(r,c,t)$, which are
the row, column and intensity respectively for each pixel. We restrict to
pixels where $t>0.5$, and select the pixels with the top 200 intensities to
comprise the point cloud (if there are fewer than 200 pixels remaining after
thresholding, we resample among them). Furthermore, we normalize the row and
column values among all the points in the cloud. This process maps an image to
a set $S\subseteq\mathbb{R}^{3}$ such that $|S|=200$.

For this dataset we consider $h_{1}=500$ and $h_{2}=500$ for our
$\mathcal{S}_{i}$ finite-width architectures.

We perform cross-validation by setting aside $10\%$ of the data as a
validation set, and calculate the mean and standard deviation of the
generalization error over five runs. In order to study generalization in this
setting, we test on point clouds of different size, $100$ and $200$, and show
the results in Table 4. The starting learning rate is $0.001$. Otherwise, all
other experimental details are the same as above.

##### Robust Mean Details:

We use the regular ReLU activation in the first layer for training stability.
Each network is trained on a batch of 5000 input sets sampled as above, as the
task of robust estimation appears more susceptible to overfitting than the
simpler symmetric objectives learned in the previous section. All networks are
trained for 30000 iterations, and all other details of training are kept
consistent with the previous section (including the larger number of random
kernel features).

The hyperparameters required for the adversarial estimator in [Dia+17] are
$\tau$ and “cher", which both control the thresholding of which vectors are
discarded according to the projection on the maximal eigenvector of the
empirical covariance. Cross validation over the sets $[0.1,0.15,0.2]$ and
$[1.5,1.8,2.0,2.3]$ yielded the choices $\tau=0.1$ and “cher" $=1.5$.

##### Additional Experiments

In Figure 4 we consider higher dimensional vectors for our set inputs to the
symmetric models. In Figure 5 we consider training over multiple set sizes as
well, with the input size sampled uniformly from ${4,5,6}$.

Figure 4: Test Error for $d=20$

Figure 5: Test Error for varied input size training

We consider the Pointcloud MNIST dataset, after mapping our image to sets.
This dataset is substantially more difficult than regular MNIST, as the
induced sets obfuscate the geometric structure of the original images. The
results on Pointcloud MNIST, across differently-sized set representations of
images, are given in Table 4. The fact that we only consider three-layer
networks limits the ability of the model to reconstruct the original image
representation and perform comparably to a model acting on regular MNIST.
Nevertheless, we still observe the expected ordering of our functional spaces.
When testing on smaller sets than training, the generalization error increases
faster for $\mathcal{S}_{3}$ than for $\mathcal{S}_{1}$ and $\mathcal{S}_{2}$.

|  | Error ($N=100$) | Error ($N=200$)
---|---|---|---
| $\mathcal{S}_{1}$ | $8.03$ | $5.62$
| $\mathcal{S}_{2}$ | $8.25$ | $5.78$
| $\mathcal{S}_{3}$ | $14.45$ | $10.80$
Table 4: Classification test error on Pointcloud MNIST in percent, after
images are compressed into sets of size $N$, trained with $N=200$.

In Table 5 we consider the robust mean experiment, using the same
hyperparameters except training on sets of larger size ($N=60$) and plotting
MSE on sets of varying size. As with the smaller scale experiment, we observe
that $\mathcal{S}_{1}$ enjoys a slight advantage over the other methods when
restricting attention to the in-distribution generalization setting of $N=60$,
but outside that range the performance is comparable to the naive sample mean,
suggesting that out-of-distribution generalization for the robust mean is not
easily attainable for these networks.

|  | $N=20$ | $N=40$ | $N=60$ | $N=80$ | $N=100$
---|---|---|---|---|---|---
| $\mathcal{S}_{1}$ | $0.149\pm 0.039$ | $0.073\pm 0.023$ | $0.043\pm 0.004$ | $0.034\pm 0.004$ | $0.028\pm 0.003$
| $\mathcal{S}_{2}$ | $0.151\pm 0.039$ | $0.076\pm 0.023$ | $0.045\pm 0.004$ | $0.036\pm 0.004$ | $0.030\pm 0.003$
| $\mathcal{S}_{3}$ | $0.159\pm 0.039$ | $0.081\pm 0.023$ | $0.050\pm 0.004$ | $0.040\pm 0.004$ | $0.034\pm 0.003$
| Sample Mean | $0.152\pm 0.069$ | $0.066\pm 0.029$ | $0.055\pm 0.025$ | $0.034\pm 0.015$ | $0.026\pm 0.012$
| Geometric Median | $0.137\pm 0.062$ | $0.063\pm 0.028$ | $0.047\pm 0.021$ | $0.032\pm 0.014$ | $0.025\pm 0.011$
| Adversarial Estimator | $0.472\pm 0.545$ | $0.386\pm 0.555$ | $0.346\pm 0.546$ | $0.282\pm 0.521$ | $0.206\pm 0.455$
Table 5: Mean squared test error for robust mean estimation among the finite
model instantiations and baselines.