# Universal Approximation of Functions on Sets

Edward Wagstaff<EMAIL_ADDRESS>
Fabian B. Fuchs<EMAIL_ADDRESS>
Martin Engelcke<EMAIL_ADDRESS>
Michael A. Osborne<EMAIL_ADDRESS>
Ingmar Posner<EMAIL_ADDRESS>
Department of Engineering Science
University of Oxford
Oxford, UK

###### Abstract

Modelling functions of sets, or equivalently, _permutation-invariant_
functions, is a long-standing challenge in machine learning. Deep Sets is a
popular method which is known to be a universal approximator for continuous
set functions. We provide a theoretical analysis of Deep Sets which shows that
this universal approximation property is only guaranteed if the model’s latent
space is sufficiently high-dimensional. If the latent space is even one
dimension lower than necessary, there exist piecewise-affine functions for
which Deep Sets performs no better than a naïve constant baseline, as judged
by worst-case error. Deep Sets may be viewed as the most efficient incarnation
of the Janossy pooling paradigm. We identify this paradigm as encompassing
most currently popular set-learning methods. Based on this connection, we
discuss the implications of our results for set learning more broadly, and
identify some open questions on the universality of Janossy pooling in
general.

Keywords: Deep Learning, Sets, Permutation Invariance, Equivariance, Universal
Function Approximation, Janossy Pooling, Self-Attention

##  1 Introduction

Many applications of machine learning work with collections of inputs or
features which are best modelled as _sets_. Crucially, these collections have
no intrinsic ordering, which distinguishes them from other commonly-
encountered types of data such as images or audio. Examples are plentiful: a
point cloud obtained from a LIDAR sensor; a group of atoms which together form
a molecule; or a collection of objects appearing in an image. Although the
data for these problems is not ordered, standard machine learning techniques
usually impose an ordering on the data, either by representing it as a vector
or matrix and applying order-sensitive operations, or by iterating over data
points in a stateful fashion. Any function with set-valued inputs is
insensitive to this imposed ordering, in the sense that the output does not
change when the input is reordered. This property is known as _permutation
invariance_.

Tasked with learning a permutation-invariant target function, we may build
this invariance into our model – we can regard this as giving the model an
inductive bias. A family of techniques have been proposed in recent years to
build and train deep permutation-invariant machine learning models. Most
notably, the seminal work by Zaheer et al. (2017) introduces _Deep Sets_. The
central idea of Deep Sets is to process the individual elements of a set in
parallel using a shared encoding function before aggregating these encodings
using a _symmetric function_ – for example summation, averaging, or max-
pooling. We refer to the vector space in which this aggregation happens as the
model’s _latent space_. This design ensures that the model is exactly
permutation-invariant. A similar model is also explored in Qi et al. (2017a).

While easy to implement and parallelise, processing each input individually
and pooling globally hinders relational reasoning (Santoro et al., 2017;
Battaglia et al., 2018). Arguably the most popular alternatives are self-
attention mechanisms, which perform weighted summation to aggregate
information via input-dependent attention weights. Self-attention explicitly
performs relational reasoning by processing elements in pairs, rather than
individually – working with relationships between pairs of elements is
therefore an in-built feature of the model. This stands in contrast to Deep
Sets, where no facility for relational reasoning is built into the model
(though such reasoning can still be learned). While self-attention has
famously been widely applied in natural language processing (Vaswani et al.,
2017), it has also been applied to sets (Lee et al., 2019) and is popular in
the literature on graph learning (Veličković et al., 2018).

Although Deep Sets and self-attention may not immediately appear to be closely
related, both can be viewed as special cases of $k$-ary _Janossy pooling_
(Murphy et al., 2019). Deep Sets is the most restricted instance of Janossy
pooling, which makes it a good starting point for fuller theoretical
characterisation of these methods. In this work, we contribute to this
theoretical understanding by considering how the dimensionality of the Deep
Sets model’s latent space affects its expressive capacity. This extends the
partial characterisation provided in Zaheer et al. (2017).

Firstly, we follow Zaheer et al. (2017) in considering the conditions under
which Deep Sets is capable of _exactly representing_ any continuous target
function (i.e. _universal representation_). We show that the sufficient
condition on the model’s latent space dimension given in Zaheer et al. (2017)
is essentially the best possible – it can be lowered, but only by $1$, and
this weakened sufficient condition is in fact also a _necessary_ condition.
Secondly, we consider universal _approximation_ , a weaker and more
practically important property. We demonstrate that this is subject to the
same necessary and sufficient conditions as universal representation. In fact,
we show that if the latent dimension is even $1$ lower than necessary, there
exist piecewise-affine functions for which the model’s worst-case error is no
better than the worst-case error of a model which simply outputs $0$. Finally,
we consider the implications of our findings for other related architectures
such as self-attention, and discuss the universality properties of other set-
learning methods.

In summary, this work makes the following contributions:

  * •

Section 2 provides an overview of the most popular deep learning architectures
for learning functions on sets, including Deep Sets, and discusses their
unification as instances of the _$k$ -ary Janossy pooling_ paradigm;

  * •

Section 3 proves a necessary and sufficient condition for _representing_
arbitrary continuous functions on sets with the Deep Sets architecture;

  * •

Section 4 furthers our analysis of the Deep Sets architecture by proving a
necessary and sufficient condition for _approximating_ arbitrary continuous
functions on sets;

  * •

Section 5 discusses other models for deep learning on sets;

  * •

Section 6 discusses universal approximation criteria for architectures beyond
Deep Sets, and identifies some open questions of interest.

Section 3 of this paper is a revised and abridged version of work previously
presented in Wagstaff et al. (2019). This paper provides a more extensive and
comprehensive discussion of the subject and extends the work in Wagstaff et
al. (2019) by providing additional results for architectures other than Deep
Sets and a theoretical characterisation of universal function approximation.

##  2 Models For Learning on Sets

In this section, we examine deep learning architectures for data that consists
of unordered sets of elements. We are centrally concerned with the property of
permutation invariance as introduced above, but we briefly note that functions
working with set-valued data may also be _permutation-equivariant_. In the
simplest case, equivariance appears in the context of mapping sets to sets.
Although the ordering of elements is arbitrary, we may still want the ordering
of the input set to be consistent with the ordering of the output set – that
is, any permutation of the input results in a corresponding permutation of the
output. This consistency of ordering is _permutation equivariance_. Romero and
Cordonnier (2021) provide a full mathematical definition of permutation
equivariance, along with a detailed analysis of the equivariance properties of
self-attention. We do not consider permutation-equivariant set functions in
detail in this paper.

Returning to permutation _invariance_ , a core consideration for the design of
permutation-invariant models is how to maintain maximum expressivity (in the
sense of being able to model a broad class of functions) while also ensuring
permutation invariance. Murphy et al. (2019) introduce _Janossy pooling_ as a
unifying framework of methods that learn either strictly permutation-invariant
functions or suitable approximations. Janossy pooling is known to be highly
expressive, and in fact it is trivially shown to be universal in the sense
that any permutation-invariant function may be represented within the Janossy
pooling framework.

In its most general form, Janossy pooling considers all possible permutations
$\pi$ of the input elements $x_{i}$. Each permutation $\pi(\mathbf{x})$ is
separately passed through the same permutation-sensitive function $\phi$. The
outputs for the different permutations are then aggregated by computing the
average (or by another global pooling operation). If two inputs $\mathbf{x}$
and $\mathbf{y}$ are permutations of one another, this process will give the
same output for both inputs. As noted above, we refer to the space in which
the aggregation happens as the model’s _latent space_.

Mathematically, the procedure outlined above can be written as

$\widehat{f}(\mathbf{x})=\frac{1}{|S_{M}|}\sum_{\pi\in
S_{M}}\phi\bigl{(}\pi\left(\mathbf{x}\right)\bigr{)}$ (1)

where $\mathbf{x}$ has $M$ elements, and $S_{M}$ is the group of all
permutations $\pi$ of $M$ elements. A permutation-invariant function
$\widehat{f}$ is thereby constructed from a permutation-sensitive function
$\phi$. This permutation-sensitive function is typically implemented as a
neural network, but other function approximators such as Gaussian processes
may also be used. The architecture is illustrated in Figure 1. This figure
also illustrates that a second function may optionally be used to post-process
the output of the aggregation operation:

$f(\mathbf{x})=\rho\bigl{(}\widehat{f}\left(\mathbf{x}\right)\bigr{)}$ (2)

This second function $\rho$ does not need to follow any constraints to
guarantee invariance because its input, $\widehat{f}(\mathbf{x})$, is already
permutation-invariant. In other words, the ordering information is already
lost by the point that $\rho$ is reached in Figure 1.

Figure 1: The Janossy pooling paradigm applies the same permutation-sensitive
network to each possible permutation of the input set. When using a
permutation-invariant pooling operation, such as averaging or summation,
information about the ordering is eliminated. A second neural network may be
used to predict the final output. This paradigm guarantees permutation
invariance of the output without imposing restrictions on any of the neural
network components.

One drawback of this scheme is that it can become prohibitively expensive for
large set sizes $M$, because of the large number of terms in the sum in
Equation 1. The computational complexity scales at least linearly with the
cardinality of $S_{M}$, which is $M!$. To remedy this, Murphy et al. (2019)
discuss several options for reducing the computational complexity: (i)
sorting; (ii) sampling; (iii) restricting permutations to $k$-tuples.

Rather than considering all permutations, sorting only considers a single
canonical permutation, which is obtained by sorting the input. The sorting
operation may be hand-specified, or it may be learned. Sampling, by contrast,
aggregates over a randomly-sampled subset of permutations (so that the sum in
Equation 1 is over a randomly chosen subset of $S_{M}$). While the output in
this case is only approximately rather than strictly permutation invariant,
Murphy et al. (2019) show that this works reasonably well empirically.
Nevertheless, most models that are used in practice (e.g. Zaheer et al., 2017;
Qi et al., 2017b; Lee et al., 2019) fall into the third category of
restricting permutation to $k$-tuples. The theoretical analysis conducted in
our work focuses on this third category, which we describe in more detail in
the reaminder of this section.

###  2.1 Limiting the Number of Elements in Permutations

Equation 1 considers all possible $M$-tuples from an $M$ element set. To save
computation, one can instead consider all $k$-tuples111We require that the
tuples we discuss here consist of distinct elements from our input set. So in
this case, $(2,2)$ is not a valid 2-tuple from the set $\\{1,2,3\\}$. This
restriction is not always observed, for instance self-attention _does_ allow
such 2-tuples, but for brevity we restrict ourselves to discussing the case of
distinct elements. with $k<M$. The models obtained by setting $k=1$ and $k=2$
are visualised in Figure 2. Mathematically, letting $\mathbf{x}_{\\{k\\}}$
denote a $k$-tuple from $\mathbf{x}$, we have

$\displaystyle\widehat{f}(\mathbf{x})=\frac{1}{P(M,k)}\sum_{\mathbf{x}_{\\{k\\}}}\phi(\mathbf{x}_{\\{k\\}})\text{
, where }P(M,k)=\frac{M!}{(M-k)!}.$ (3)

For clarity, we provide an example for $M=4$ and $k=2$. If the input set is
$\\{w,x,y,z\\}$, the sum will be over all 2-tuples from the set, namely:

$\displaystyle\leavevmode\nobreak\ (w,x),\leavevmode\nobreak\ (x,w),(w,y),$
$\displaystyle\leavevmode\nobreak\ (y,w),\leavevmode\nobreak\
(w,z),\leavevmode\nobreak\ (z,w),$ $\displaystyle(x,y),\leavevmode\nobreak\
(y,x),\leavevmode\nobreak\ (x,z),$ $\displaystyle\leavevmode\nobreak\
(z,x),\leavevmode\nobreak\ (y,z),\leavevmode\nobreak\ (z,y)$

For sufficiently small $k$, this gives a sum with far fewer than $M!$ terms,
leading to a computationally tractable method in many practical cases. For
fixed $k$ and varying $M$, the number of terms in the sum is
$\mathcal{O}(M^{k})$. Setting $k=1$ therefore provides a model whose cost is
linear in the size of the input set. Increasing $k$ comes at the cost of
additional computational complexity, but as we will discuss in the following
subsection, also allows for more explicit relational reasoning.

(a) Janossy pooling with $k=1$ (_Deep Sets_)

(b) Janossy pooling with $k=2$

(c) Self-attention

Figure 2: Different versions and variations of Janossy pooling. Permutation
invariance is guaranteed by processing all combinations of $k$ elements and
then aggregating via a sum (or softmax in the case of attention). Self-
attention, a variant of Janossy pooling with $k=2$, focuses on one node at a
time (the darkest node here), computing an output for this specific node. It
is often employed for all nodes in parallel in a permutation-equivariant
manner, mapping sets of points to sets of points (Lee et al., 2019).

####  2.1.1 Expressivity and Interactions

The terms relational reasoning and interactions are often encountered in the
deep learning literature (Battaglia et al., 2016; Santoro et al., 2017; Fuchs
et al., 2019). We use the expression interactions between elements in a set to
refer to the fact that the output may depend not only on the individual
contribution of each element, but may also depend on the fact that multiple
elements appear together in the same set. Relational reasoning describes the
act of modelling and using these interactions. To illustrate this with a
simple example, consider the task of assessing how well a set of ingredients
go together for cooking a meal. If we set $k=1$, the function $\phi$ can take
into account relevant individual attributes, but will be unable to spot any
clashes between ingredients (like garlic and vanilla). Increasing $k$ allows
$\phi$ to see multiple elements at once, and therefore perform relational
reasoning about pairs of ingredients, enabling a more expressive model of what
tastes good. If we view $\phi$ as an “encoder” and $\rho$ as a “decoder”,
$\phi$ is capable of encoding information about interactions, which $\rho$ can
then make use of during decoding.

If we set $k=1$, this is no longer the case. Zaheer et al. (2017) show that
the encoder $\phi$ can encode the entire set when $k=1$, and therefore the
decoder $\rho$ can in principle recover all the input information and perform
relational reasoning from there. However, any such relational reasoning is not
built into the model, and must be entirely learned. Murphy et al. (2019)
speculate that this additional burden on what must be learned by $\rho$ can
contribute to difficulties in training the $k=1$ model on some tasks which
depend heavily on relational reasoning.

Many current neural network architectures on sets and graphs resemble Janossy
pooling with $k=2$. This choice of $k$ represents a tradeoff between
computational complexity (lower $k$ is better) and ease of training for
relational reasoning (higher $k$ is better222Though we note that high $k$
being “better” here is, at least theoretically speaking, a speculative
statement. Nevertheless, the fact that $k=2$ is widely used in practice
despite the increased computational complexity strongly suggests that
increasing $k$ does indeed improve performance in some contexts.). Most
famously, self-attention algorithms (schematically depicted in Figure 2(c))
compare two elements of the set at a time, typically by performing a scalar
product (Vaswani et al., 2017; Lee et al., 2019). The results of the scalar
products are used as attention weights for aggregating information from
different points via a weighted, permutation-invariant sum. While this
mechanism is very similar to Janossy pooling with $k=2$, some additional
architecture choices are often made. For example, a softmax might be used to
ensure that the attention weights are normalised.

####  2.1.2 Deep Sets

The model obtained by setting $k=1$ is in fact a popular and well-known
special case of Janossy pooling – Deep Sets (Zaheer et al., 2017). As
discussed above, choosing $k=1$ may hinder relational reasoning, but Deep Sets
is nevertheless a widely-used architecture for permutation-invariant models,
for example forming the basis of two well-known point cloud classification
approaches, PointNet (Qi et al., 2017a) and PointNet++ (Qi et al., 2017b). As
the computationally cheapest instance of Janossy pooling, its linear scaling
in the number of inputs makes it particularly well suited to problems with
large input sets – a point cloud for example may consist of thousands of
points. Importantly, it is known to be universal, guaranteeing (at least in
principle) that it is capable of computing any permutation-invariant target
function. However, the conditions under which universality holds are not fully
characterised, either for Janossy pooling more broadly or for Deep Sets
specifically. Zaheer et al. (2017) and Han et al. (2019) provide sufficient
conditions for Deep Sets to be universal, but do not show whether universality
fails if these conditions are violated – that is, they do not give _necessary_
conditions for universality, and leave open the possibility that universality
is preserved under weaker conditions. In the following two sections, we
provide proofs of necessary conditions for the universality of Deep Sets.

##  3 Universal Function Representation with Deep Sets

This first section of our theoretical investigation focuses on function
_representation_ , building directly on the proofs and results from Zaheer et
al. (2017). By function representation, we mean the ability of a model to
_exactly represent_ a given target function. By _universal_ representation, we
mean the ability of a model to represent _all_ target functions from a given
function class (e.g. the class of all permutation-invariant functions). The
original analysis from Zaheer et al. (2017) demonstrates the universality of
Deep Sets by considering universal representation, and in this section we
present a direct continuation and refinement of this analysis. Nevertheless,
it must be noted that function representation is a stronger property than
required in practice, and we will return to analyse the weaker property of
function _approximation_ in Section 4. Proofs of all novel results from this
section are provided in Section B.

###  3.1 Preliminaries

We begin by introducing the necessary definitions and notation, before
detailing our contribution and its relationship to the original results from
Zaheer et al. (2017). Importantly, we will establish the concept of _sum-
decomposition_ , which is a concise mathematical description of the Deep Sets
architecture.

####  3.1.1 Definitions and Notation

###### Notation 1

We denote sets of inputs in boldface with subscript-indexed elements, e.g. the
set $\mathbf{x}$ has elements $x_{1},\ldots,x_{M}$.

###### Notation 2

Throughout, the variable $M$ refers to the number of elements in the input
sets under consideration.

###### Notation 3

We denote the group of all permutations of $M$ elements by $S_{M}$. A
permutation $\pi\in S_{M}$ may be thought of as a bijection from
$\\{1,\ldots,M\\}$ to itself.

###### Definition 4

A function $f(\mathbf{x})$ is _permutation-invariant_ if
$f(x_{1},\dots,x_{M})=f\bigl{(}x_{\pi(1)},\dots,x_{\pi(M)}\bigr{)}$ for all
$\pi\in S_{M}$.

###### Definition 5

We say that a function $f$ is _sum-decomposable_ if there are functions $\rho$
and $\phi$ such that

$f(\mathbf{x})=\rho\bigl{(}\sum_{i}\phi(x_{i})\bigr{)}.$ (4)

In this case, we say that $(\rho,\phi)$ is a _sum-decomposition_ of $f$.

Note that sum-decomposition is equivalent to Janossy pooling with $k=1$, i.e.
Deep Sets. Comparing Equation 4 with Equations (2) and (3), these expressions
differ only in dividing $\phi$ by an integer, and can be made equal simply by
rescaling $\phi$.

###### Notation 6

Given a sum-decomposition $(\rho,\phi)$, we write
$\Phi(\mathbf{x}):=\sum_{i}\phi(x_{i})$. With this notation, we can write
Equation 4 as $f(\mathbf{x})=\rho\big{(}\Phi(\mathbf{x})\big{)}$. We may also
refer to the function $\rho\circ\Phi$ as a sum-decomposition.

###### Definition 7

Let $(\rho,\phi)$ be a sum-decomposition. Write $Z$ for the domain of $\rho$
(which is also the codomain of $\phi$, and the space in which the summation
happens in Equation 4). We refer to $Z$ as the _latent space_ of the sum-
decomposition $(\rho,\phi)$.

###### Definition 8

Given a space $Z$, we say that $f$ is _sum-decomposable via $Z$_ if $f$ has a
sum-decomposition whose latent space is $Z$.

###### Definition 9

We say that $f$ is _continuously sum-decomposable_ when there exists a sum-
decomposition $(\rho,\phi)$ of $f$ such that both $\rho$ and $\phi$ are
continuous. $(\rho,\phi)$ is then a _continuous sum-decomposition_ of $f$.

###### Notation 10

Denote the power set of a space $X$ (that is, the set of all subsets of $X$)
by $2^{X}$.

####  3.1.2 Our Contribution

As noted above, the Deep Sets model uses sum-decomposition to represent
permutation-invariant functions. Our contribution is to show that the
universality of sum-decomposition is dependent on the dimensionality of the
latent space $Z$. Specifically, we show that $\dim(Z)$ must be at least $M$,
where $M$ is the number of elements in the input sets. We refine the analysis
from Zaheer et al. (2017), relying on the observation that some of the
mappings used for the proofs of universality in the original analysis are
highly discontinuous, and cannot be computed in practice. By considering
continuous mappings,333This function class includes, for instance, all
functions which can be computed by neural networks with continuous activation
functions, or by Gaussian processes with continuous kernels. we provide a
proof of the above lower bound on $\dim(Z)$. Because this section directly
follows on from the analysis given in Zaheer et al. (2017), we first give a
brief reproduction of the statement and proof of two key theorems from that
work.

####  3.1.3 Background Theorems

Zaheer et al. (2017) consider two cases. First, where $\mathbf{x}$ is a subset
of, or drawn from, a _countably infinite_ universe $\mathfrak{U}$. Second, the
case where $\mathfrak{U}$ is _uncountably infinite_.

######  Theorem 11 (Countable case)

Let $f:2^{\mathfrak{U}}\to\mathbb{R}$ where $\mathfrak{U}$ is countable. Then
$f$ is sum-decomposable via $\mathbb{R}$.

Proof  Since $\mathfrak{U}$ is countable, each $x\in\mathfrak{U}$ can be
mapped to a unique element in $\mathbb{N}$ by a bijective function
$c(x):\mathfrak{U}\to\mathbb{N}$. If we can choose $\phi$ so that $\Phi$ is
invertible, then we can set $\rho=f\circ\Phi^{-1}$, giving

$\displaystyle f=\rho\circ\Phi$

i.e. f is sum-decomposable via $\mathbb{R}$.

Now consider $\phi(x)=4^{-c(x)}$. Under this mapping, each set
$\mathbf{x}\subset\mathfrak{U}$ corresponds to a unique real number. The real
number $r:=\Phi(\mathbf{x})$ can be decoded to the set $\mathbf{x}$ by looking
at the base 4 expansion of $r$. The element $c^{-1}(n)\in\mathfrak{U}$ belongs
to $\mathbf{x}$ if and only if the $n$-th digit of $r$ is $1$. This decoding
procedure shows that $\Phi$ is invertible, and the conclusion follows.

For the uncountable case, we consider $M$-element sets from the universe
$\mathfrak{U}=[0,1]$.

######  Theorem 12 (Uncountable case)

Let $M\in\mathbb{N}$, and let $f:[0,1]^{M}\to\mathbb{R}$ be a continuous
permutation-invariant function. Then $f$ is continuously sum-decomposable via
$\mathbb{R}^{M+1}$.

Another way of stating Theorem 12, which brings the terminology more in line
with Deep Sets, is as follows:

######  Theorem 0 (Deep Sets terminology)

Deep Sets can represent any continuous permutation-invariant function of $M$
elements if the dimension of the model’s latent space is at least $M+1$.

Proof  The proof by Zaheer et al. (2017) of Theorem 12 is more involved than
for Theorem 11. We do not include it here in detail, but we summarise the main
points as follows.

  1. 1.

Show that the mapping $\Phi:[0,1]^{M}\to\mathbb{R}^{M+1}$ defined by
$\Phi_{q}(\mathbf{x})=\sum_{i=1}^{M}(x_{i})^{q}$ for $q=0,\dots,M$ is
injective and continuous444In the original proof, $\Phi$ is denoted $E$..

  2. 2.

Show that $\Phi$ has a continuous inverse.

  3. 3.

Define $\rho:\mathbb{R}^{M+1}\to\mathbb{R}$ by $\rho=f\circ\Phi^{-1}$.

  4. 4.

Define $\phi(x):\mathbb{R}\to\mathbb{R}^{M+1}$ by $\phi_{q}(x)=x^{q}$.

  5. 5.

Note that, by definition of $\rho$ and $\phi$, $(\rho,\phi)$ is a continuous
sum-decomposition of $f$ via $\mathbb{R}^{M+1}$.

In light of these theorems, our key conclusions can be summarised as follows:

  * •

In Section 3.2 we argue that the guarantee of sum-decomposability via
$\mathbb{R}$ given by Theorem 11 cannot hold in practice. This is because the
necessary mappings are highly discontinuous and cannot be computed.

  * •

In Section 3.3 we prove that the guarantee of sum-decomposability via
$\mathbb{R}^{M+1}$ given by Theorem 12 is essentially the best possible. The
dimension of the latent space must be at least $M$, or universality is lost.

Additionally, we contribute some results on universal representation with
discontinuous sum-decompositions. These results are not relevant for
practice555One of our proofs depends on the axiom of choice, bringing us
firmly beyond the realm of computability! but are included for mathematical
interest, and can be found in Appendix B.

###  3.2 The Importance of Continuity

Theorem 11 appears to give a strong guarantee on the universality of sum-
decomposition via $\mathbb{R}$. The theorem applies even when the domain is
allowed to be infinite, and so any task implemented on real hardware, where
inputs belong to large but finite domains, satisfies the conditions of the
theorem. Nevertheless, an insurmountable problem arises when trying to apply
the construction from the proof of Theorem 11, with the consequence that
Theorem 11 cannot be applied on real hardware. That is, sum-decomposition via
$\mathbb{R}$ does _not_ provide a guarantee of universal function
representation in practice. We illustrate the problem by considering an
example with the domain of all $256\times 256$ pixel images in 8-bit
greyscale, which we denote $\mathcal{I}$.

Suppose, as required by the construction used in the proof, that we have a
counting function $c$ which assigns an integer to each element of
$\mathcal{I}$. There are $2^{2^{19}}$ elements in $\mathcal{I}$, so even if
$c$ counts all “interesting” images666That is, images which are not just
random noise, but have meaningful visual content. first, there must be
“interesting” images mapping to very large numbers under $c$. Consider for
instance the $2^{2^{16}}$th image $\iota:=c^{-1}(2^{2^{16}})$, and suppose
that, given a set of images $\mathbf{x}$, our target function $f$ needs to
compute whether or not $\iota\in\mathbf{x}$. Under the encoding/decoding
procedure from the proof of Theorem 11, the decoder function $\rho$ is given
as input the real number $r:=\Phi(\mathbf{x})$. Recalling that the
construction has $\phi(x):=4^{-c(x)}$, the presence or absence of the image
$\iota$ in the set $\mathbf{x}$ will affect the value of $r$ by one part in
$4^{{2^{2^{16}}}}$. Any decoder $\rho$ implemented on real hardware will
therefore be unable to distinguish between sets containing $\iota$ and sets
without $\iota$.

The essential problem here is an extreme degree of _discontinuity_.
Intuitively speaking, a function is continuous if, at every point in the
domain, the variation of the output is insensitive to small variations in the
input. In the example above, a successful decoder $\rho$ must be sensitive to
vanishingly small perturbations in the input, across its entire input space,
and this property renders it impossible to compute in practice. We can avoid
this problem by requiring that the functions under consideration are all
continuous. This requirement is ubiquitous in work on the function
approximation properties of machine learning models, including the universal
approximation theorem for neural networks (Cybenko, 1989), the universality of
Gaussian processes with certain kernels (Rasmussen and Williams, 2006), the
literature on approximating functions on sets (Han et al., 2019; Segol and
Lipman, 2020), and indeed in function approximation results outside machine
learning (such as the well-known Stone-Weierstrass theorem, Stone, 1948). In
practice, neural networks with continuous activation functions777I.e.
essentially all popular activation functions, including ReLU, ELU, sigmoid,
and tanh. can only compute continuous functions, and the same is true of
Gaussian processes with continuous kernels.

To continue our analysis of sum-decomposition, we therefore adopt the
assumption that the target functions and sum-decompositions under
consideration are all continuous. This aligns with the conditions in Theorem
12, and in the next section we show that the conclusion of Theorem 12 is
essentially the strongest result that can be achieved under these assumptions.

###  3.3 Function Representation With Continuous Mappings

The following theorem is our central result on the function representation
properties of continuous sum-decomposition.

theoremmaxnotdecomp Let $M,N\in\mathbb{N}$, with $M>N$. Then there exist
permutation-invariant continuous functions $f:\mathbb{R}^{M}\to\mathbb{R}$
which are not continuously sum-decomposable via $\mathbb{R}^{N}$.

Restated in more practical terms, this implies that for Deep Sets to be
capable of representing _arbitrary_ continuous functions on sets of size $M$,
the dimension of the model’s latent space (denoted $N$ in the theorem
statement above) must be at least $M$. A similar statement is also true for
models based on the similar concept of _max-decomposition_ , as considered by
Qi et al. (2017a) – details are provided in Section B.6.

In terms of concrete recommendations for practitioners, Section 3.3 suggests
that when deploying a model based on Deep Sets, the choice of latent space
should depend on the number of elements in the input sets under consideration.
Referring back to our depiction of Deep Sets in Figure 2(a), this means that
the cardinality of the input sets should be taken into account when choosing
the length of the vectors output by the $\phi$ blocks. Choosing a latent space
which is not sufficiently high-dimensional may mean that the target function
cannot be successfully modelled. It must be noted, however, that Section 3.3
places restrictions on function _representation_ , but not on function
_approximation_. Function approximation comes closer to describing what is
needed in practice, and we will return to address this point in Section 4,
where we prove that this restriction on the latent space dimension also holds
for function _approximation_ with Deep Sets. We discuss the practical
implications of Section 3.3 in more detail in Section 3.3.2.

In addition to showing that an $M$-dimensional latent space is necessary, we
adapt the proof from Zaheer et al. (2017) of Theorem 12 to strengthen the
result in two ways. Proofs of these two results can be found in Section B.
Firstly, we lower the bound on the sufficient latent space dimension by $1$,
concluding that an $M$-dimensional latent space is _necessary and sufficient_
for universal representation.

theoremoriunc Let $M\in\mathbb{N}$, and let $f:\mathbb{R}^{M}\to\mathbb{R}$ be
a continuous permutation-invariant function. Then $f$ is continuously sum-
decomposable via $\mathbb{R}^{M}$.

Secondly, we show that the model can deal with variable set sizes $\leq M$.
That is, the model is not only capable of modelling functions on sets of size
_exactly_ $M$, but also on sets of size _up to_ $M$. At least in principle,
the model is therefore applicable in settings where the input sets may contain
variable numbers of points.

[Variable set size]theoremarbitrary Denote the set of subsets of $[0,1]$
containing at most $M$ elements by $[0,1]^{\leq M}$. Let $f:[0,1]]^{\leq
M}\to\mathbb{R}$ be continuous888Note that we must take some care with the
notion of continuity here – see Section A.2. and permutation-invariant. Then
$f$ is continuously sum-decomposable via $\mathbb{R}^{M}$.

####  3.3.1 Proof of Section 3.3

Our proof of Section 3.3 relies on showing that the permutation-invariant
function max, applied to $M$-element sets of real numbers, is not sum-
decomposable via $\mathbb{R}^{M-1}$. To show this, we need the following
lemma.

###### Lemma 1

Let $M,N\in\mathbb{N}$, and suppose $\phi:\mathbb{R}\to\mathbb{R}^{N}$,
$\rho:\mathbb{R}^{N}\to\mathbb{R}$ are functions such that

$\texttt{\emph{max}}(\mathbf{x})=\rho\bigl{(}\sum_{i}\phi(x_{i})\bigr{)}.$ (5)

Recall that $\Phi(\mathbf{x})=\sum_{i}\phi(x_{i})$, and write $\Phi_{M}$ for
the restriction of $\Phi$ to sets of size $M$.

Then $\Phi_{M}$ is injective for all $M$.

Proof  We proceed by induction. The base case $M=1$ is clear.

Now let $M\in\mathbb{N}$, and suppose that $\Phi_{M-1}$ is injective. Suppose
there are sets $\mathbf{x},\mathbf{y}$ such that
$\Phi_{M}(\mathbf{x})=\Phi_{M}(\mathbf{y})$. First note that, by Equation 5,
we must have

$\texttt{max}(\mathbf{x})=\texttt{max}(\mathbf{y}).$ (6)

So now write

$\mathbf{x}=\\{x_{\texttt{max}}\\}\cup\mathbf{x}_{\text{rem}}\leavevmode\nobreak\
;\leavevmode\nobreak\
\mathbf{y}=\\{y_{\texttt{max}}\\}\cup\mathbf{y}_{\text{rem}},$ (7)

where $x_{\texttt{max}}=\texttt{max}(\mathbf{x})$, and
$y_{\texttt{max}}=\texttt{max}(\mathbf{y})$. But now we have

$\begin{split}\Phi_{M}(\mathbf{x})&=\Phi_{M-1}(\mathbf{x}_{\text{rem}})+\phi(x_{\texttt{max}})\\\
&=\Phi_{M-1}(\mathbf{y}_{\text{rem}})+\phi(y_{\texttt{max}})\\\
&=\Phi_{M}(\mathbf{y}).\end{split}$

From the central equality, and Equation 6, we have

$\Phi_{M-1}(\mathbf{x}_{\text{rem}})=\Phi_{M-1}(\mathbf{y}_{\text{rem}}).$

Now by injectivity of $\Phi_{M-1}$, we have
$\mathbf{x}_{\text{rem}}=\mathbf{y}_{\text{rem}}$. Combining this with
Equations (6) and (7), we must have $\mathbf{x}=\mathbf{y}$, and so $\Phi_{M}$
is injective.

Equipped with this lemma, we can now prove Section 3.3.

Proof  We proceed by contradiction. Suppose that functions $\phi$ and $\rho$
exist satisfying Equation 5. Define $\Phi_{M}:\mathbb{R}^{M}\to\mathbb{R}^{N}$
by

$\Phi_{M}(\mathbf{x}):=\Sigma_{i=1}^{M}\phi(x_{i}).$

Denote by $\mathbb{R}_{\text{ord}}^{M}$ the set of all
$\mathbf{x}\in\mathbb{R}^{M}$ such that $x_{1}<x_{2}<...<x_{M}$. Let
$\Phi_{M}^{\text{ord}}$ be the restriction of $\Phi_{M}$ to
$\mathbb{R}_{\text{ord}}^{M}$. Since $\Phi_{M}^{\text{ord}}$ is a sum of
continuous functions, it is also continuous, and by Lemma 1, it is injective.

Now note that $\mathbb{R}_{\text{ord}}^{M}$ is a convex open subset of
$\mathbb{R}^{M}$, and is therefore homeomorphic to $\mathbb{R}^{M}$.
Therefore, our continuous injective $\Phi_{M}^{\text{ord}}$ can be used to
construct a continuous injection from $\mathbb{R}^{M}$ to $\mathbb{R}^{N}$.
But it is known that no such continuous injection exists when $M>N$. Therefore
our decomposition from Equation 5 cannot exist.

####  3.3.2 Implications and Limitations

In light of Theorems 3.3 and 3.3, we now have a necessary and sufficient
condition for universal function representation with Deep Sets. Given a
continuous target function $f$ on sets of size at most $M$, $f$ can be
represented using a Deep Sets-based model if and only if the model’s latent
space is at least $M$-dimensional. We now provide a brief discussion of the
implications of this result and the limitations which must be taken into
account when considering how the result applies in practice.

We can concisely summarise the practical implications of Theorems 3.3 and 3.3
as follows. When deploying a Deep Sets-based model, the choice of latent space
should depend on the cardinality of the sets being processed. Larger input
sets demand a larger latent space. We emphasise that, although our results
give a precise figure for the necessary and sufficient latent dimension $M$,
this should not be interpreted as meaning that exactly $M$ dimensions should
always be used in practice, for the following reasons.

First note that Section 3.3 does not imply that _all_ functions require an
$M$-dimensional latent space. Some functions can be represented in a lower
dimensional space – take for instance the sum of all elements, which is
trivially represented by setting both $\phi$ and $\rho$ to be the identity
function. The statement rather says that _some_ functions require an
$M$-dimensional latent space. It is still possible that, in a given
application, the target function does not require $M$ dimensions. While we do
not characterise exactly which functions require an $M$-dimensional sum-
decomposition, we do note that such functions need not be “badly-behaved” or
difficult to specify. Our proof specifically demonstrates that even max, which
is trivial to specify, is not continuously sum-decomposable with a latent
space dimension less than $M$.

Second, although Section 3.3 shows that an $M$-dimensional latent space
suffices to model any target function, we also know from Section 3.3 that $M$
dimensions is the _bare minimum_ needed to guarantee this property. In
practice, a model using only this minimum capacity of $M$ dimensions is not
guaranteed to provide good results. One reason for this is that, while the
necessary functions $\phi$ and $\rho$ certainly _exist_ , we have no guarantee
that they can be successfully _learned_. It is entirely possible, even in
light of our results, that increasing the latent dimension above $M$ leads to
more efficient training and superior results in practice.

A final, major weakness of Section 3.3 is that, in following the mathematical
framework developed in Zaheer et al. (2017), it addresses function
_representation_ rather than function _approximation_. This leaves open the
possibility that, while an $M$-dimensional latent space is needed for exact
representation, we can achieve arbitrarily good approximation of any target
function using only a $1$-dimensional latent space. Addressing this weakness
requires significantly more complicated mathematics, and we devote the next
section to proving that an analogue of Section 3.3 does indeed hold for
universal approximation, and $M$ dimensions are still required.

##  4 Universal Function Approximation with Deep Sets

In the previous section, we considered the problem of function
_representation_ – showing that there exists an instance of a given model
which exactly computes a target function. But exactly representing target
functions is generally _not_ our goal – typically, we are concerned with
_approximating_ a target function. In this section, we extend our analysis of
the Deep Sets architecture to assess its ability to perform approximation.

To see concretely why function approximation requires a separate analysis, we
return to the max function on a set of $M$ elements. As proved above, for an
exact sum-decomposition, the latent space must be at least $M$-dimensional.
But as noted by Zaheer et al. (2017) in an appendix to their work, max can be
approximated arbitrarily well with only a $2$-dimensional latent space. In
fact, one dimension will suffice. Let $a\in\mathbb{R}$ and set $\phi$ and
$\rho$ as follows:

$\displaystyle\phi(x)$ $\displaystyle=e^{ax}$ $\displaystyle\rho(x)$
$\displaystyle=\frac{\log x}{a}.$ (8)

Thus, our sum-decomposition approximation for max is

$\widehat{f}_{a}(X)=\frac{1}{a}\text{log}\left(\sum_{x\in X}e^{ax}\right).$
(9)

For input sets of size $M$, it is easily shown that

$\texttt{max}(X)\leq\widehat{f}_{a}(X)\leq\texttt{max}(X)+\frac{\text{log}M}{a}.$

That is, the worst-case error in this approximation is
$\frac{\text{log}M}{a}$. For fixed set size $M$, we can therefore achieve
arbitrarily good approximation by increasing the value of $a$, even though we
have only used a $1$-dimensional latent space.

In the specific case of max, this demonstrates that there is a wide gap
between what is necessary for representation and what is necessary for
approximation. max is in some sense “as hard as possible” to represent,
requiring $M$ latent dimensions, but “as easy as possible” to approximate,
requiring only $1$ latent dimension. This naturally raises the question of
whether the approximation problem is somehow fundamentally easier. We state a
more precise form of this question as follows: _is it the case that every
permutation-invariant function of $M$ elements has an approximate sum-
decomposition via fewer than $M$ dimensions_? Our analysis answers this
question in the negative – there exist functions which cannot be closely
approximated with a lower-dimensional latent space. Moreover, low-dimensional
sum-decomposition is guaranteed to fail very badly for these functions – in
terms of worst-case error, approximation with sum-decomposition performs as
badly as approximation with a constant function.

###  4.1 A Necessary Condition For Function Approximation by Sum-Decomposition

The question above mentions _approximate sum-decomposition_ – in order to
state and prove our result, we must define precisely what we mean by this. In
the following definitions, let $M$ be a positive integer,
$U\subset\mathbb{R}^{M}$ be compact,999This compactness requirement is
necessary when discussing universal function approximation. Of particular
relevance here is the fact that the universal approximation theorem for neural
networks also requires a compact domain (Cybenko, 1989; Funahashi, 1989;
Hornik et al., 1989). This compactness requirement is a fundamental constraint
which is also necessary for other function approximation results, for example
the Stone-Weierstrass theorem (Stone, 1948). and $f:U\to\mathbb{R}$. We
maintain the convention that $\Phi(\mathbf{x})=\sum_{i=1}^{M}\phi(x_{i})$.

###### Definition 2

Let $\epsilon>0$. $(\phi,\rho)$ is a _within- $\epsilon$ sum-decomposition_ of
$f$ if $|f(\mathbf{u})-\rho(\Phi(\mathbf{u}))|<\epsilon$ for every
$\mathbf{u}\in U$.

For example, if we let $a=\frac{\text{log}M}{\epsilon}$, then the sum-
decomposition defined by Equation 8 is a within-$\epsilon$ continuous sum-
decomposition of max via $\mathbb{R}$.

###### Definition 3

A sequence $(\phi,\rho)_{k}=\\{(\phi_{k},\rho_{k});k\in\mathbb{N}\\}$ is an
_approximate sum-decomposition_ of $f$ if, for any $\epsilon>0$, there is some
$K\in\mathbb{N}$ such that $(\phi_{K},\rho_{K})$ is a within-$\epsilon$ sum-
decomposition of $f$. We also require that $(\phi_{k},\rho_{k})$ is a
within-$\epsilon$ sum-decomposition of $f$ for every $k\geq K$. Put more
loosely, $(\phi_{k},\rho_{k})$ is a sequence of ever-closer approximations to
$f$. The existence of an approximate sum-decomposition of $f$ guarantees that
$f$ can be approximated arbitrarily closely by sum-decomposition.

Given a set $Y$, we say that the approximate sum-decomposition
$(\phi,\rho)_{k}$ is _via $Y$_ if $(\phi_{k},\rho_{k})$ is via $Y$ for every
$k$.

For example, letting $a=1,2,\ldots$, the sequence $(\phi,\rho)_{a}$ as defined
by Equation 8 is a continuous approximate sum-decomposition of max via
$\mathbb{R}$.

With these definitions in hand, we now state our main result on approximation.

###### Theorem 4

Let $M,N\in\mathbb{N}$ with $M>N$, and let
$I_{M}:=[-1,1]^{M}\subset\mathbb{R}^{M}$. Then there exists a continuous
permutation-invariant function $f:I_{M}\to\mathbb{R}$ which has no continuous
approximate sum-decomposition via $\mathbb{R}^{N}$.

Our proof of this theorem actually provides stronger conclusions than stated
above. The following paragraphs explain these additional conclusions in
detail, and a theorem statement incorporating these conclusions is included in
Section B.7.

Since the target function $f$ is continuous on a compact domain, we know that
its output is bounded, say by $y_{\text{min}}\leq f(\mathbf{u})\leq
y_{\text{max}}$. A worst-case error101010By worst-case error we mean
$\text{max}_{\mathbf{u}}|f(\mathbf{u})-\widehat{f}(\mathbf{u})|$. of
$E:=\frac{y_{\text{max}}-y_{\text{min}}}{2}$ can trivially be achieved by
approximating $f$ with the constant function
$\widehat{f}(\mathbf{u})=\frac{y_{\text{max}}+y_{\text{min}}}{2}$. We show
that there exist permutation-invariant functions $f_{*}$ on $\mathbb{R}^{M}$
which have no within-$E$ continuous sum-decomposition via $\mathbb{R}^{N}$. In
other words, any attempt to sum-decompose $f_{*}$ via $\mathbb{R}^{N}$ is
doomed to have the same worst-case error as simply approximating $f_{*}$ by a
constant value.

In addition, we explicitly construct a permutation-invariant function $f_{*}$
for which sum-decomposition via $\mathbb{R}^{N}$ must have worst-case error
$E$ as defined above. Letting $U=[\shortminus 1,1]^{M}$, this $f_{*}$ has a
simple form:111111The extra $\shortminus 1$ for even $M$ is to ensure that
$f_{*}$ is bounded between $\shortminus 1$ and $1$. This isn’t necessary,
indeed the bias term could be removed from Equation 10 without affecting our
result, but reasoning about $f_{*}$ is simpler if its range is fixed.

$\displaystyle f_{*}(\mathbf{u})$
$\displaystyle:=\mathbf{w}^{\intercal}\texttt{sort}(\mathbf{u})+b$ (10)
$\displaystyle w_{i}$ $\displaystyle:=(\shortminus 1)^{i+1}$ $\displaystyle b$
$\displaystyle:=\begin{cases}\shortminus 1&M\leavevmode\nobreak\
\text{even}\\\ 0&M\leavevmode\nobreak\ \text{odd}\end{cases}$

Here, sort sorts the elements of $\mathbf{u}$ in descending order. This
definition may look a little arbitrary, but we will justify it in Section 4.2
and provide some intuition for why it is hard to approximate in Section 4.3.
The function $f_{*}$ is trivial to represent using the sorting framework
mentioned in Section 2,121212We discuss sorting in more detail in Section 5.1.
but impossible to approximate using a continuous sum-decomposition via
$\mathbb{R}^{N}$. This gives mathematical support to the proposition that
there is no true “one size fits all” approach – for a given task, performance
may vary greatly between different methods of achieving permutation
invariance.

Finally we note that poor approximation behaviour is not confined to a single
point. This follows from the fact that both $f_{*}$ and the sum-decomposition
are continuous, and so the approximation error also varies continuously – if
the error is high at one point, it must also be high in some region around
that point.

Having stated the key conclusions, we now present the proof of Theorem 4. We
omit some details, particularly in the proof of Lemma 7. Full details are
included in Section B.7.

###  4.2 Proving Necessity for Universal Approximation

$\displaystyle x$$\displaystyle-1$$\displaystyle 1$$\displaystyle
y$$\displaystyle-1$$\displaystyle 1$$\displaystyle
z$$\displaystyle-1$$\displaystyle 1$ (a) The boundary of $\Delta_{3}$.

$\displaystyle-1$$\displaystyle 1$ (b) The image of $\Delta_{3}$ under
$f_{*}$.

$\displaystyle-0.33$$\displaystyle
0.33$$\displaystyle\widetilde{x}$$\displaystyle 0.0$$\displaystyle
0.5$$\displaystyle\widetilde{y}$ (c) The image of $[\shortminus 1,1]$ under
$\phi$.

$\displaystyle-1$$\displaystyle 1$$\displaystyle\widetilde{x}$$\displaystyle
0.0$$\displaystyle 1.5$$\displaystyle\widetilde{y}$ (d) The image of
$\Delta_{3}$ under $\Phi$.

Figure 3: A visualisation of sum-decomposition when the input sets are of size
$3$ and the latent space is $2$-dimensional. For the purposes of this
illustration, we pick $\phi$ to send the interval $[\shortminus 1,1]$ to a
semicircle. With this choice of $\phi$, we see that two disjoint regions of
the surface of $\Delta_{3}$, highlighted with solid red lines, intersect under
the application of $\Phi$. By contrast, $f_{*}$ separates these highlighted
regions, sending them to opposite ends of the interval $[\shortminus 1,1]$.
Since these regions are already “mixed together” by $\Phi$, there is no
function $\rho$ which can separate them out again to approximate $f_{*}$, so
sum-decomposition of $f_{*}$ fails. Our proof demonstrates that an
intersection under $\Phi$ which causes this problem for $f_{*}$ is forced for
any continuous $\phi$ and in any number of dimensions, as long as the
dimension of the latent space is less than the number of inputs.

The overall proof strategy is best understood by thinking topologically – that
is, by considering how the encoding map $\Phi$ and the target function $f$
deform the input space, squashing it onto lower-dimensional output spaces. To
understand this perspective we will consider an example with $M=3$ and $N=2$,
since this is high-dimensional enough to illustrate the key points and low-
dimensional enough to visualise. For this example, we choose $\phi$ to send
$[\shortminus 1,1]$ to a semicircle. This choice is made purely for easy
visualisation of $\phi$ and $\Phi$.

Any continuous target function $f:[\shortminus 1,1]^{3}\to\mathbb{R}$ may be
thought of as deforming a cube into a line segment. We actually do not need to
consider the whole cube – since $f$ is permutation-invariant, it is fully
determined by its behaviour on the set of points with descending-ordered
coordinates. In general we will denote this set $\Delta_{n}$,

$\Delta_{n}:=\left\\{\mathbf{x}\in\mathbb{R}^{n}:1\geq x_{1}\geq
x_{2}\geq\ldots\geq x_{n}\geq\shortminus 1\right\\}.$ (11)

Considering $\Delta_{3}$ instead of the whole cube allows us to think more
freely about $f$, without worrying about permutation invariance – as long as
$f$ is continuous on $\Delta_{3}$, it can be extended in a continuous and
permutation-invariant way to $[\shortminus 1,1]^{3}$. In general, if we want
to define a function $f$ by its behaviour on $\Delta_{n}$ and implicitly
extend it to the rest of the space, we can simply write it as a function of
$\texttt{sort}(\mathbf{x})$. This accounts for the appearance of sort in
Equation 10, which can be thought of as saying
“$f_{*}(\mathbf{x})=\mathbf{w}^{\intercal}\mathbf{x}+b$ on $\Delta_{M}$, and
$f_{*}$ is permutation-invariant”.

In general $\Delta_{n}$ is an $n$-simplex, so $\Delta_{3}$ is a tetrahedron.
From our topological perspective, sum-decomposition via $\mathbb{R}^{2}$
attempts to break down the tetrahedron-to-line deformation $f$ by first
sending $\Delta_{3}$ onto the plane under $\Phi$, then sending the plane onto
a line under $\rho$. Figures 3(c), 3(a) and 3(d) visualise the action of
$\Phi$, showing how the boundaries of $\Delta_{3}$ are mapped to the plane for
our example choice of $\phi$. Crucially, note that some of these boundaries
intersect under $\Phi$. Once two regions have been brought together by $\Phi$,
they cannot be separated again – $\rho$ cannot send the point of intersection
to two places at once. Therefore if $f$ _does_ separate these regions, sending
them to opposite ends of $[\shortminus 1,1]$ as illustrated in Figure 3(b),
then the sum-decomposition $\rho\circ\Phi$ must fail with worst-case error at
least $1$.

Figure 3 only shows that this intersection problem occurs for our example
choice of $\phi$ and $M$, but we prove below that the general case also holds
– for every $M$, and for any continuous $\phi$ which maps into
$\mathbb{R}^{M-1}$, there are two disjoint regions of the surface of
$\Delta_{M}$ which intersect under $\Phi$. We denote the two regions
$X_{M}^{+1}$ and $X_{M}^{\shortminus 1}$ – the solid red regions in Figure
3(a) are $X_{3}^{+1}$ and $X_{3}^{\shortminus 1}$. Our $f_{*}$ from Equation
10 is defined so that it separates $X_{M}^{+1}$ and $X_{M}^{\shortminus 1}$,
and it is just one among many continuous functions which have this property.
In some sense it is the simplest, since it is affine on $\Delta_{M}$. Our
proof that $\Phi(X_{M}^{+1})$ and $\Phi(X_{M}^{\shortminus 1})$ always
intersect relies on the structure of $\Phi$ as a sum over inputs.

We define $X_{M}^{+1}$ and $X_{M}^{\shortminus 1}$ as follows:

$\displaystyle X_{M}^{+1}$
$\displaystyle:=\left\\{\mathbf{x}\in\Delta_{M}:1=x_{1}\geq
x_{2}=x_{3}\geq\ldots\text{$\nicefrac{{$=$}}{{$\geq$}}$}\leavevmode\nobreak\
x_{M}\leavevmode\nobreak\ \text{$\nicefrac{{$\geq$}}{{$=$}}$}\shortminus
1\right\\}$ (12) $\displaystyle X_{M}^{\shortminus 1}$
$\displaystyle:=\left\\{\mathbf{x}\in\Delta_{M}:1\geq x_{1}=x_{2}\geq
x_{3}=\ldots\text{$\nicefrac{{$\geq$}}{{$=$}}$}\leavevmode\nobreak\
x_{M}\leavevmode\nobreak\ \text{$\nicefrac{{$=$}}{{$\geq$}}$}\shortminus
1\right\\}$ (13)

The rightmost equality $x_{M}=\shortminus 1$ applies to $X_{M}^{+1}$ when $M$
is even, and $X_{M}^{\shortminus 1}$ when $M$ is odd. We can view these
equations as modifying the definition of $\Delta_{M}$ (Equation 11) by
changing either the odd- or the even-numbered $\geq$ signs into $=$ signs. It
follows directly from the definition of $f_{*}$ (Equation 10) that
$f_{*}(X_{M}^{+1})=1$ and $f_{*}(X_{M}^{\shortminus 1})=\shortminus 1$.

The above discussion can be summarised by the following claim:

###### Claim 5

Let $N=M-1$. There exist two subsets $X_{M}^{+1}$ and $X_{M}^{\shortminus 1}$
of $\Delta_{M}$ such that:

  1. 1.

$f_{*}$ separates $X_{M}^{+1}$ from $X_{M}^{\shortminus 1}$:
$f_{*}(X_{M}^{+1})=1$ and $f_{*}(X_{M}^{\shortminus 1})=\shortminus 1$.

  2. 2.

$\Phi$ cannot separate $X_{M}^{+1}$ from $X_{M}^{\shortminus 1}$: For any
continuous $\phi:[\shortminus 1,1]\to\mathbb{R}^{N}$, $\Phi(X_{M}^{\shortminus
1})\cap\Phi(X_{M}^{+1})$ is non-empty.

Theorem 4 follows immediately, since the above points imply that $f_{*}$ has
no within-1 continuous sum-decomposition via $\mathbb{R}^{N}$.

As noted, point 1 is true by definition, so we only need to prove point 2 to
complete the proof of Theorem 4. The proof of point 2 has two parts:

  1. 1.

Lemma 6: Construct a function $\Gamma_{N}$ which has a zero only if
$\Phi(X_{M}^{\shortminus 1})\cap\Phi(X_{M}^{+1})$ is non-empty.

  2. 2.

Lemma 7: Show that $\Gamma_{N}$ has a zero.

The main idea in constructing $\Gamma_{N}$ is to subtract
$\Phi(X_{M}^{\shortminus 1})$ from $\Phi(X_{M}^{+1})$. This clearly evaluates
to zero only where the two sets intersect. The subtraction idea is slightly
obscured in the formal statement and proof of the following Lemma, but it is
the key idea on which the Lemma is based. The subscript on $\Gamma$ is $N$,
rather than $M$, because there are a total of $N=M-1$ degrees of freedom in
$X_{M}^{+1}$ and $X_{M}^{\shortminus 1}$ – this is most easily seen by
considering $M=1$, which gives zero degrees of freedom.131313Equations 12 and
13 imply that $X_{1}^{+1}=\\{1\\}$ and $X_{1}^{\shortminus 1}=\\{\shortminus
1\\}$.

Straightforwardly using this idea results in a function whose input space is
$X_{M}^{+1}\times X_{M}^{\shortminus 1}$, but we will instead define
$\Gamma_{N}$ to have input space $\Delta_{N}$. As shown below, any point
$\mathbf{z}\in\Delta_{N}$ may be used to construct a pair of points
$(\mathbf{x}^{+},\mathbf{x}^{-})\in X_{M}^{+1}\times X_{M}^{\shortminus 1}$,
and the subtraction idea can then be applied to this pair of points. We define
$\Gamma_{N}$ in this way because $\Delta_{N}$ turns out to have useful
structure which we can exploit for the proof of Lemma 7.

Importantly, the following statement of Lemma 6 requires that
$\phi(\shortminus 1)=\mathbf{0}$. From now on we will assume this without loss
of generality, since otherwise we can reason identically about
$\widetilde{\phi}(x):=\phi(x)-\phi(\shortminus 1)$, which does satisfy
$\widetilde{\phi}(\shortminus 1)=\mathbf{0}$.

###### Lemma 6

Let $\phi:[\shortminus 1,1]\to\mathbb{R}^{N}$, with $\phi(\shortminus
1)=\mathbf{0}$. Define $\Gamma_{N}:\Delta_{N}\to\mathbb{R}^{N}$ by

$\Gamma_{N}(\mathbf{x}):=\sum_{i=1}^{N}(\shortminus
1)^{i}\phi(x_{i})+\frac{\phi(1)}{2}.$ (14)

Suppose $\Gamma_{N}$ has a zero in $\Delta_{N}$. Then there exist
$\mathbf{x}^{+}\in X_{M}^{+1}$, $\mathbf{x}^{-}\in X_{M}^{\shortminus 1}$ with

$\Phi(\mathbf{x}^{+})=\Phi(\mathbf{x}^{-}).$

Proof  Let $\mathbf{z}\in\Delta_{N}$ with $\Gamma_{N}(\mathbf{z})=\mathbf{0}$.
Define $\mathbf{x}^{+}\in X_{M}^{+1}$ and $\mathbf{x}^{-}\in
X_{M}^{\shortminus 1}$:

$\displaystyle\begin{split}x^{+}_{i}&=z_{i}\quad\text{for even }i\\\
x^{-}_{i}&=z_{i}\quad\text{for odd }i\end{split}$ (15)

The remaining coordinates of $\mathbf{x}^{+}$ and $\mathbf{x}^{-}$ are fixed
by the equalities in Equations 13 and 12. Note in particular that Equation 12
implies that $x^{+}_{1}=1$. Taking these constraints together with the
condition that $\phi(\shortminus 1)=\mathbf{0}$, we obtain

$\displaystyle\begin{split}\Phi(\mathbf{x}^{+})&=\phi(1)+2\sum_{i\text{
even}}\phi(x_{i}^{+})\\\ \Phi(\mathbf{x}^{-})&=2\sum_{i\text{
odd}}\phi(x_{i}^{-})\end{split}$ (16)

Plugging $\mathbf{z}$ into Equation 14 and pulling the odd terms of the sum to
the left hand side (and recalling that $\Gamma_{N}(\mathbf{z})=\mathbf{0}$),
we obtain

$\sum_{i\text{ odd}}\phi(z_{i})=\sum_{i\text{
even}}\phi(z_{i})+\frac{\phi(1)}{2}.$ (17)

Now we apply Equation 15 to obtain

$\sum_{i\text{ odd}}\phi(x_{i}^{-})=\sum_{i\text{
even}}\phi(x_{i}^{+})+\frac{\phi(1)}{2}.$ (18)

This equates the right hand sides of the two lines of Equation 16, so the left
hand sides must also be equal, i.e.
$\Phi(\mathbf{x}^{+})=\Phi(\mathbf{x}^{-})$.

All that remains is to show that $\Gamma_{N}$ has a zero. To understand
$\Gamma_{N}$, we exploit the alternating sum form of Equation 14, and in
particular we will see how this constrains the behaviour of $\Gamma_{N}$ on
the surface of $\Delta_{N}$. Each face of the surface is itself a
simplex141414At this stage of the argument, it is helpful to have a way of
visualising high-dimensional simplices and their faces. We discuss such a
visualisation in Section A.4. of dimension $N-1$, defined by changing one of
the inequalities in Equation 11 into an equality, i.e. by applying the
constraint $x_{i}=x_{i+1}$. We denote the corresponding face
$\smash{\Delta_{N}^{(i)}}$. For $1\leq i<N$, this constraint leads to the
cancellation of two consecutive terms of the sum in Equation 14. Each of these
faces therefore has the same image under $\Gamma_{N}$ – for example, the
following points belong to different faces of $\Delta_{4}$, but because equal
pairs cancel out they all go to the same point under $\Gamma_{4}$.

$\displaystyle\big{(}\tfrac{2}{3},\tfrac{2}{3},\tfrac{1}{2},0\big{)}\in\Delta_{4}^{(1)}$
$\displaystyle\big{(}\tfrac{1}{2},\tfrac{1}{3},\tfrac{1}{3},0\big{)}\in\Delta_{4}^{(2)}$
$\displaystyle\big{(}\tfrac{1}{2},0,\shortminus\tfrac{1}{2},\shortminus\tfrac{1}{2}\big{)}\in\Delta_{4}^{(3)}$

There are two more faces to consider – $\Delta_{N}^{(0)}$ and
$\Delta_{N}^{(N)}$, corresponding to the constraints $x_{1}=1$ and
$x_{N}=\shortminus 1$ respectively. We can observe an interesting behaviour of
$\Gamma_{N}$ here, which is in fact a symmetry: if we apply a “coordinate left
shift” to a point in $\Delta_{N}^{(0)}$, the output of $\Gamma_{N}$ is
multiplied by $\shortminus 1$. By “coordinate left shift”, we mean the
bijection $\alpha:\Delta_{N}^{(0)}\to\Delta_{N}^{(N)}$ defined as follows:

$\displaystyle\alpha(\mathbf{x})_{i}=\begin{cases}x_{i+1}&i<N\\\ \shortminus
1&i=N\end{cases}$

Applying $\alpha$ moves each coordinate one place to the left, deleting the
$1$ in the leftmost place and padding with a $\shortminus 1$ in the rightmost
place. For example, consider the point
$(1,\tfrac{2}{3},0,\shortminus\tfrac{1}{2})\in\Delta_{4}^{(0)}$:

$\alpha\Big{(}(1,\tfrac{2}{3},0,\shortminus\tfrac{1}{2})\Big{)}=(\tfrac{2}{3},0,\shortminus\tfrac{1}{2},\shortminus
1)\in\Delta_{4}^{(4)}$

Now apply $\Gamma_{4}$ to $(1,\tfrac{2}{3},0,\shortminus\tfrac{1}{2})$ and
$(\tfrac{2}{3},0,\shortminus\tfrac{1}{2},\shortminus 1)$:

$\displaystyle\Gamma_{4}\Big{(}(1,\tfrac{2}{3},0,\shortminus\tfrac{1}{2})\Big{)}$
$\displaystyle=-\phi(1)+\phi(\tfrac{2}{3})-\phi(0)+\phi(\shortminus\tfrac{1}{2})+\frac{\phi(1)}{2}$
$\displaystyle\Gamma_{4}\Big{(}(\tfrac{2}{3},0,\shortminus\tfrac{1}{2},\shortminus
1)\Big{)}$
$\displaystyle=\quad\quad\quad-\phi(\tfrac{2}{3})+\phi(0)-\phi(\shortminus\tfrac{1}{2})+\phi(\shortminus
1)+\frac{\phi(1)}{2}$

Simplifying the $\phi(1)$ terms, and recalling that $\phi(\shortminus 1)=0$,
we obtain

$\Gamma_{4}\Big{(}(\tfrac{2}{3},0,\shortminus\tfrac{1}{2},\shortminus
1)\Big{)}=-\Gamma_{4}\Big{(}(1,\tfrac{2}{3},0,\shortminus\tfrac{1}{2})\Big{)}$

It is easily seen that this generalises to any
$\mathbf{x}\in\Delta_{N}^{(0)}$:

$\Gamma_{N}\big{(}\alpha(\mathbf{x})\big{)}=-\Gamma_{N}\big{(}\mathbf{x}\big{)}$
(19)

We can exploit this symmetry to show that $\Gamma_{N}$ has a zero. To do this,
we will need the Borsuk-Ulam theorem (Borsuk, 1933 – see Lloyd, 1978 for a
detailed English-language treatment). One statement of the theorem is as
follows.

######  Theorem 7 (Borsuk-Ulam)

Let $I_{n}:=[\shortminus 1,1]^{n}$ be the unit $n$-cube. Let $\partial I_{n}$
be the surface of $I_{n}$, $\partial I_{n}:=\\{\mathbf{x}\in I_{n}:x_{i}=\pm
1\text{ for some }i\\}$. Suppose $f:I_{n}\to\mathbb{R}^{n}$ is continuous, and
for every $\mathbf{x}\in\partial I_{n}$ we have

$f(\shortminus\mathbf{x})=-f(\mathbf{x})$ (20)

Then there is some $\mathbf{z}\in I_{n}$ such that $f(\mathbf{z})=0$.

There is a clear similarity between Equations 20 and 19, but we cannot
directly apply Borsuk-Ulam to $\Gamma_{N}$. We need to bridge the two
equations, relating the left-shift $\alpha$ on the left hand side of Equation
19 to the negation on the left hand side of Equation 20. We can do this by
finding a continuous function $\nu_{N}:I_{N}\to\Delta_{N}$ which turns
negation on $\partial I_{N}$ into a left-shift on
$\partial\Delta_{N}$:151515Here, we are glossing over the fact that $\alpha$
is only defined on part of $\partial\Delta_{N}$. We will come back to this
when proving Lemma 7.

$\nu_{N}(\shortminus\mathbf{x})=\alpha(\nu_{N}(\mathbf{x}))$ (21)

That is, we want to be able to apply Borsuk-Ulam to $\Gamma_{N}\circ\nu_{N}$:

$\displaystyle
f(\shortminus\mathbf{x}):=\Gamma_{N}\Big{(}\nu_{N}(\shortminus\mathbf{x})\Big{)}$
$\displaystyle=\Gamma_{N}\Big{(}\alpha\big{(}\nu_{N}(\mathbf{x})\big{)}\Big{)}$
$\displaystyle=-\Gamma_{N}\Big{(}\nu_{N}(\mathbf{x})\Big{)}=-f(\mathbf{x})$

Showing that a suitable $\nu_{N}$ exists will complete the proof.

lemmalemmanu Let $n\in\mathbb{N}$. Let $\Gamma_{n}$ be defined as in Equation
14. Then there exists a continuous function $\nu_{n}:I_{n}\to\Delta_{n}$ such
that, for $\mathbf{x}\in\partial I_{n}$

$\Gamma_{n}\big{(}\nu_{n}(\shortminus\mathbf{x})\big{)}=-\Gamma_{n}\big{(}\nu_{n}(\mathbf{x})\big{)}$
(22)

We present a partial proof here, with full details available in Section B.7.

$I_{2}$$\nu_{2}$$\Delta_{2}$

$I_{3}^{+}$$\cong I_{2}$$\mathbf{x}$$I_{3}^{-}$$\cong
I_{2}$$\shortminus\mathbf{x}$$\nu_{3}$$\Delta_{3}^{(0)}$$\cong\Delta_{2}$$\Delta_{3}^{(3)}$$\cong\Delta_{2}$$\nu_{3}(\mathbf{x})$$\nu_{3}(\shortminus\mathbf{x})$$\alpha$

Figure 4: For the first part of the construction of $\nu_{n}$, we use
$\nu_{n-1}$ to define $\nu_{n}$ on the top and bottom faces of $I_{n}$. The
$n=3$ case is illustrated here. $\nu_{n}$ uses $\nu_{n-1}$ to send the top
face of $I_{n}$ to $\Delta_{n}^{(0)}$, and the bottom face to
$\Delta_{n}^{(n)}$. We construct $\nu_{n}$ so that opposite points
$\mathbf{x}$ and $\shortminus\mathbf{x}$ on the top and bottom faces go to
points in $\Delta_{n}$ which are related by the left-shift function $\alpha$ –
that is, $\nu_{n}(\shortminus\mathbf{x})=\alpha(\nu_{n}(\mathbf{x}))$.

$\mathbf{x}^{+}$$\mathbf{x}^{-}$$\mathbf{x}$$\mathbf{y}^{+}$$\mathbf{y}^{-}$$\mathbf{y}\scriptstyle{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}=}{\color[rgb]{0.57421875,0.23046875,0.234375}\definecolor[named]{pgfstrokecolor}{rgb}{0.57421875,0.23046875,0.234375}\shortminus\mathbf{x}}}$$I_{n}$

$\overline{\mathbf{x}}$$\overline{\mathbf{y}}\scriptstyle{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}=}{\color[rgb]{0.57421875,0.23046875,0.234375}\definecolor[named]{pgfstrokecolor}{rgb}{0.57421875,0.23046875,0.234375}\shortminus\overline{\mathbf{x}}}}$$I_{n-1}$

Figure 5: For the second part of the construction of $\nu_{n}$, we note that
any point $\mathbf{x}$ lies on a “vertical” line, i.e. an $n$-th-axis-aligned
line, meeting the top face at $\mathbf{x}^{+}$ and the bottom face at
$\mathbf{x}^{-}$. We complete the construction of $\nu_{n}$ by interpolating
along these lines. For a pair of opposite points
$\mathbf{y}=\shortminus\mathbf{x}$, we see that
$\mathbf{y}^{-}=\shortminus\mathbf{x}^{+}$. To ensure that $\nu_{n}$ has the
desired properties, we must pay particular attention to the surface of $I_{n}$
without the top and bottom faces, i.e. $\partial I_{n}\backslash(I_{n}^{+}\cup
I_{n}^{-})$. If $\mathbf{x}$ lies on this part of the surface (as in this
figure), then the point $\overline{\mathbf{x}}$, which is the projection of
$\mathbf{x}$ along the vertical, lies on the surface $\partial I_{n-1}$.

Proof  First, we must point out that the proof strategy is not quite as simple
as suggested above. Since $\alpha$ is only defined on $\Delta_{n}^{(0)}$, and
not on the rest of $\partial\Delta_{n}$, we cannot in fact satisfy Equation 21
for every $\mathbf{x}$ on $\partial I_{n}$. Nevertheless, we can still satisfy
Equation 22 for every $\mathbf{x}$ on $\partial I_{n}$, and we reach this
conclusion by showing that Equation 21 holds on part of $\partial I_{n}$.

We proceed by induction – the base case $\nu_{1}(\mathbf{x}):=\mathbf{x}$ is
trivial. Consider the “top” and “bottom” faces of $I_{n}$:

$\displaystyle I_{n}^{+}$ $\displaystyle:=\\{\mathbf{x}\in I_{n}:x_{n}=1\\}$
The top face. $\displaystyle I_{n}^{-}$ $\displaystyle:=\\{\mathbf{x}\in
I_{n}:x_{n}=\shortminus 1\\}$ The bottom face.

Note that $I_{n}^{+}$ and $I_{n}^{-}$ are naturally equivalent to $I_{n-1}$ –
we can map bijectively from either face to $I_{n-1}$ by dropping the last
coordinate of $\mathbf{x}$. For any point $\mathbf{x}$, we’ll denote the
corresponding point in $I_{n-1}$ by $\overline{\mathbf{x}}$ – that is,
$\overline{\mathbf{x}}$ is $\mathbf{x}$ with the last coordinate removed.

Note also that $\Delta_{n}^{(0)}$ and $\Delta_{n}^{(n)}$ are naturally
equivalent to $\Delta_{n-1}$ – any point $\mathbf{x}\in\Delta_{n}^{(0)}$ can
be written as $(1,\mathbf{x}^{\prime})$, where
$\mathbf{x}^{\prime}\in\Delta_{n-1}$. Similarly any point in
$\Delta_{n}^{(n)}$ can be written as $(\mathbf{x}^{\prime},\shortminus 1)$. We
can use these equivalences to the lower-dimensional case to come up with a
partial definition of $\nu_{n}$ in terms of $\nu_{n-1}$.

The idea of how to begin constructing $\nu_{n}$ using these equivalences is
illustrated in Figure 4. In the following, we will choose the definition of
$\nu_{n}$ on $I_{n}^{+}$ and $I_{n}^{-}$ to satisfy what is shown in this
figure. That is, by viewing $I_{n}^{+}$ as a copy of $I_{n-1}$, and
$\Delta_{n}^{(0)}$ as a copy of $\Delta_{n-1}$, we can map from $I_{n}^{+}$ to
$\Delta_{n}^{(0)}$ using $\nu_{n-1}:I_{n-1}\to\Delta_{n-1}$. Crucially, note
that the truth of Equation 21 for $\mathbf{x}\in I_{n}^{+}$ depends on how
$\nu_{n}$ behaves on $I_{n}^{-}$. There is only one way to define $\nu_{n}$ on
$I_{n}^{-}$ so that Equation 21 is true on $I_{n}^{+}$, and this is the
definition that we choose.

Written mathematically, we define $\nu_{n}$ on $I_{n}^{+}$ and $I_{n}^{-}$ as
follows:

$\displaystyle\nu_{n}(\mathbf{x})$
$\displaystyle:=\begin{cases}\big{(}1,\nu_{n-1}(\overline{\mathbf{x}})\big{)}\quad\text{for
}\mathbf{x}\in I_{n}^{+}\\\
\alpha\big{(}\nu_{n}(\shortminus\mathbf{x})\big{)}=\big{(}\nu_{n-1}(\shortminus\overline{\mathbf{x}}),\shortminus
1\big{)}\quad\text{for }\mathbf{x}\in I_{n}^{-}\end{cases}$

So by definition, $\nu_{n}$ satisfies Equation 21 for $\mathbf{x}\in
I_{n}^{+}$. This immediately implies Equation 22 on $I_{n}^{+}$ and, by
symmetry, on $I_{n}^{-}$.

We have established that Equation 22 holds on $I_{n}^{+}\cup I_{n}^{-}$ for
our partially defined $\nu_{n}$. We now need to extend $\nu_{n}$ to the rest
of $I_{n}$. We will define this extension by interpolating along the vertical
lines joining $I_{n}^{+}$ and $I_{n}^{-}$. By “vertical”, we mean parallel to
the $n$-th coordinate axis.

Consider a point $\mathbf{x}$ lying on the part of $\partial I_{n}$ that we
have not yet considered, i.e. $\partial I_{n}\backslash(I_{n}^{+}\cup
I_{n}^{-})$. Any such point lies on a vertical line which meets $\partial
I_{n}^{+}$ and $\partial I_{n}^{-}$ at points $\mathbf{x}^{+}$ and
$\mathbf{x}^{-}$, as depicted in Figure 5. We refer to these vertical line
segments on $\partial I_{n}$ as _surface verticals_. Crucially, $\partial
I_{n}\backslash(I_{n}^{+}\cup I_{n}^{-})$ is entirely covered by surface
verticals.

We want to ensure that Equation 22 holds on all of $\partial I_{n}$, and
because we have already shown this for $I_{n}^{+}\cup I_{n}^{-}$, it only
remains to ensure that it holds on all of the surface verticals. One way to
achieve this is to make $\Gamma_{n}\circ\nu_{n}$ constant on each surface
vertical. To see that this would imply Equation 22, consider a pair of
antipodal161616That is, such that $\mathbf{y}=\shortminus\mathbf{x}$. points
$\mathbf{x}$ and $\mathbf{y}$ on $\partial I_{n}\backslash(I_{n}^{+}\cup
I_{n}^{-})$. As illustrated in Figure 5, $\mathbf{x}^{+}$ and $\mathbf{y}^{-}$
are also antipodal. Since $\mathbf{x}^{+}$ and $\mathbf{y}^{-}$ belong to
$I_{n}^{+}\cup I_{n}^{-}$, we know that Equation 22 holds:

$\Gamma_{n}\big{(}\nu_{n}(\mathbf{x}^{+})\big{)}=-\Gamma_{n}\big{(}\nu_{n}(\mathbf{y}^{-})\big{)}$

If $\Gamma_{n}\circ\nu_{n}$ is constant on surface verticals, it follows that
$\Gamma_{n}\big{(}\nu_{n}(\mathbf{x}^{+})\big{)}=\Gamma_{n}\big{(}\nu_{n}(\mathbf{x})\big{)}$
and
$\Gamma_{n}\big{(}\nu_{n}(\mathbf{y}^{-})\big{)}=\Gamma_{n}\big{(}\nu_{n}(\mathbf{y})\big{)}$,
and therefore Equation 22 also holds for $\mathbf{x}$ and $\mathbf{y}$:

$\Gamma_{n}\big{(}\nu_{n}(\mathbf{x})\big{)}=\Gamma_{n}\big{(}\nu_{n}(\mathbf{x}^{+})\big{)}=-\Gamma_{n}\big{(}\nu_{n}(\mathbf{y}^{-})\big{)}=-\Gamma_{n}\big{(}\nu_{n}(\mathbf{y})\big{)}$

Because the ends of a surface vertical, $\mathbf{x}^{+}$ and $\mathbf{x}^{-}$,
belong to $I_{n}^{+}$ and $I_{n}^{-}$, the behaviour here is already fixed by
our partial definition of $\nu_{n}$. Therefore, to have any hope of holding
$\Gamma_{n}\circ\nu_{n}$ constant on surface verticals, we must first show
that
$\Gamma_{n}\big{(}\nu_{n}(\mathbf{x}^{+})\big{)}=\Gamma_{n}\big{(}\nu_{n}(\mathbf{x}^{-})\big{)}$
under our existing partial definition of $\nu_{n}$.

By expanding the definition of $\Gamma_{n}$, consider
$\Gamma_{n}\big{(}\nu_{n}(\mathbf{x}^{+})\big{)}$:

$\displaystyle\Gamma_{n}\big{(}\nu_{n}(\mathbf{x}^{+})\big{)}$
$\displaystyle=\Gamma_{n}\Big{(}\big{(}1,\nu_{n-1}(\overline{\mathbf{x}})\big{)}\Big{)}$
$\displaystyle=-\phi(1)-\Big{(}\Gamma_{n-1}\big{(}\nu_{n-1}(\overline{\mathbf{x}})\big{)}-\frac{\phi(1)}{2}\Big{)}+\frac{\phi(1)}{2}$
$\displaystyle=-\Gamma_{n-1}\big{(}\nu_{n-1}(\overline{\mathbf{x}})\big{)}$

Similarly we find that for $\mathbf{x}^{-}$:

$\displaystyle\Gamma_{n}\big{(}\nu_{n}(\mathbf{x}^{-})\big{)}$
$\displaystyle=\Gamma_{n-1}\big{(}\nu_{n-1}(\shortminus\overline{\mathbf{x}})\big{)}$

But note that $\overline{\mathbf{x}}\in\partial I_{n-1}$, as illustrated in
Figure 5. By induction, Equation 22 therefore applies:

$\displaystyle\Gamma_{n-1}\big{(}\nu_{n-1}(\shortminus\overline{\mathbf{x}})\big{)}$
$\displaystyle=-\Gamma_{n-1}\big{(}\nu_{n-1}(\overline{\mathbf{x}})\big{)}$
$\displaystyle\Gamma_{n}\big{(}\nu_{n}(\mathbf{x}^{-})\big{)}$
$\displaystyle=\Gamma_{n}\big{(}\nu_{n}(\mathbf{x}^{+})\big{)}$ (23)

We have shown that $\Gamma_{n}\circ\nu_{n}$ takes the same value at either end
of each surface vertical. It remains to extend $\nu_{n}$ so that
$\Gamma_{n}\circ\nu_{n}$ remains constant along the entire surface vertical.
We can perform this extension by interpolating along the vertical between
$I_{n}^{+}$ and $I_{n}^{-}$. Linear interpolation does _not_ respect this
condition of constancy – the definition and justification of the correct
interpolation scheme are given in Section B.7.

With $\nu_{N}$ in hand, the proof of Theorem 4 is complete. We briefly
summarise the chain of reasoning from this section, which is now fully
justified by the proof of the above Lemma.

  1. 1.

We are attempting to model permutation-invariant functions on the input space
$[\shortminus 1,1]^{M}$ using sum-decomposition, where the dimension of the
latent space, $N$, is one less than that of the input space, $M$.

  2. 2.

We have shown that, for any choice of continuous encoding map
$\phi:[\shortminus 1,1]\to\mathbb{R}^{N}$, the function $\Gamma_{N}$ (which
depends on $\phi$) has a zero.

  3. 3.

Because of the way $\Gamma_{N}$ was constructed, this implies that there are
two disjoint regions of the input space171717Strictly speaking, two disjoint
regions of the ordered input space $\Delta_{M}$. $[\shortminus 1,1]^{M}$ which
collide under the application of $\Phi$.

  4. 4.

Any target function which widely separates these regions is therefore
impossible to approximate by sum-decomposition – there will always be a pair
of points which collide under the sum-decomposition but are widely separated
by the target.

  5. 5.

One example of such a function, which therefore cannot be approximated via
$\mathbb{R}^{N}$, is given by Equation 10.

###  4.3 Some Visual Intuition

$\displaystyle 0$$\displaystyle 10$$\displaystyle x$$\displaystyle
0$$\displaystyle 10$$\displaystyle
y$$\displaystyle\widehat{f}_{2}(x,y)$$\displaystyle 0$$\displaystyle
10$$\displaystyle x$$\displaystyle 0$$\displaystyle 10$$\displaystyle
y$$\displaystyle\widehat{f}_{6}(x,y)$$\displaystyle 0$$\displaystyle
10$$\displaystyle x$$\displaystyle 0$$\displaystyle 10$$\displaystyle
y$$\displaystyle\texttt{max}(x,y)$ Figure 6: Contours of sum-decomposition
approximations to max compared to the true max function. The sum-
decompositions $\widehat{f}_{2}$ and $\widehat{f}_{6}$ are defined by Equation
9, with $a=2,6$ respectively. As $a$ increases, the corners become sharper,
but never perfectly sharp.

We have shown mathematically that there exist functions which cannot be
approximately sum-decomposed via a low-dimensional latent space. In contrast
to the heavy mathematical content above, we now provide some less formal
intuition as to why this particular function is so hard to approximate. To
that end, we will gloss over some details for the sake of readability.

We consider the contours of the encoding map $\Phi=\sum\phi$. This provides a
useful visual perspective on sum-decomposition, helping to develop some
intuition for the behaviour of functions represented in this form. Contours of
$\Phi$ must also be contours of the full sum-decomposition $\rho\circ\Phi$: if
$\Phi(X)=\Phi(Y)$ then $\rho\circ\Phi(X)=\rho\circ\Phi(Y)$.

We plot the contours of max in Figure 6, as well as the contours of two terms
from an approximate sum-decomposition of max via $\mathbb{R}$. As can be seen
here, the contours of max have sharp corners on the line $y=x$, whereas the
contours of the approximations have a soft corner here. It is easily seen that
a sum-decomposition via $\mathbb{R}$ cannot have the same sharp contours as
max – we can push the contours as close to the corner as desired, providing
ever-better approximation, but we cannot make the contours sharp like the true
function. This picture of pushing the sum-decomposition contours closer to the
true contours gives some intuition for why arbitrarily close approximation can
be possible even when exact representation is not.

$\displaystyle 0$$\displaystyle 1$$\displaystyle x$$\displaystyle
0$$\displaystyle 1$$\displaystyle y$$\displaystyle f_{*}(x,y)$ Figure 7:
Contours of the function $f_{*}$ as defined by Equation 10.

This contour perspective can also give some intuition for the case we have
addressed in this section, where even approximation is not possible. As long
as the sum-decomposition $\widehat{f}$ is differentiable and goes via
$\mathbb{R}$, any contour of $\widehat{f}$ which meets the line $y=x$ must do
so at right angles, as is the case for the sum-decompositions plotted in
Figure 6.181818Neural networks can, of course, represent non-differentiable
functions, but if we need to construct a $\phi$ which is non-differentiable in
infinitely many places, things get more complicated. max does not violate this
condition so badly that we cannot approximate it – its contours do at least
cross $y=x$. But as Figure 7 shows, the function $f_{*}$ from our proof of
Theorem 4 violates this condition very badly, having a contour along $y=x$,
perpendicular to the contours of any sum-decomposition. Again, what we show in
Figure 6 and Figure 7 does not prove anything, as we have glossed over many
details – such as the ability of neural networks to represent non-
differentiable functions. But perhaps this provides some intuition for why
this function should be so difficult to model with sum-decomposition.

##  5 Other Methods for Achieving Permutation Invariance

In this section we discuss methods for achieving permutation invariance beyond
$k$-ary Janossy pooling. In particular, we cover two paradigms mentioned in
passing in Section 2, which are also discussed in Murphy et al. (2019):
methods which achieve exact permutation invariance through sorting, and
methods which do not achieve exact permutation invariance, but only
approximate this property. We also provide a brief discussion of the
relationship between learning permutation-invariant functions for sets and
learning on graphs.

###  5.1 Sorting

When a set is represented as an ordered structure, it is generally assumed
that the order can be arbitrary. That is, two representations $\mathbf{x}$ and
$\mathbf{y}$ of the same set, where the elements are ordered differently, are
both regarded as valid representations of the set. However, one could also say
that each set has only one valid representation, corresponding to some
canonical ordering of the elements. If it is ensured that only this valid
representation is seen by the model by first sorting the elements, then
permutation invariance is guaranteed. This is, in most cases, computationally
cheaper than permuting and pooling. The only additional computation necessary
is the sorting of the elements into their canonical representation, which is
$O(n\log n)$. This method, visualised in Figure 8, does have some drawbacks.

Figure 8: Achieving permutation invariance via sorting. Finding or learning a
canonical way of sorting the elements of a set before feeding it into a
permutation-sensitive network yields a permutation-invariant output – if the
sorting does not depend on the initial order of the elements.

First, there is an inherent ambiguity of how to pick the canonical ordering.
This choice can be made manually, but the choice of ordering may in fact
affect the performance of the model. This is because the ordering may or may
not be meaningful in the context of the task. To illustrate this, consider two
ways of sorting the integers. First, sorting according to the usual order
relation on the integers ($1<2<3$), and second, sorting alphabetically by the
representation of each integer as an English word (“one” $<$ “three” $<$
“two”). If we want to compute the max of a set of integers, the first choice
of sort operation renders the task trivial, while the second choice of sort
operation does not.

To avoid poorly-specified orderings, the ordering can instead be learned – or
more straightforwardly, a function can be learned giving a score to each
element, which is then used to sort the elements by their scores. This raises
the issue of how to learn such a scoring function. More specifically, how are
the gradients for this scoring function obtained? The ranking of elements
according to their sorting score is a piecewise constant function,191919That
is, the function taking a list of elements to a list of ranks. For
alphabetical sorting, for example, we have
$(\text{bat},\text{cat},\text{ant})\mapsto(2,3,1)$. meaning that the gradients
are zero almost everywhere and undefined at the remaining locations. This
would not be a problem if there were labels for the perfect ranking during
training time – in that case the model could just predict the ranking and
gradients could be obtained by comparing the model’s predictions to the ground
truth. But, in general, there are no labels for the perfect ranking. A good
ranking is whatever allows the decoder (the permutation-sensitive network) to
perform well. This makes getting proper gradients significantly more
difficult.

Backpropagating through piece-wise constant functions, however, is an
established task in deep learning. The straight-through estimator, for
example, is a viable tool to apply here (Bengio et al., 2013; Yin et al.,
2019). Recently, a cheap differentiable sorting operation with a computational
cost of $O(n\log n)$ was also proposed in Blondel et al. (2020). To the best
of our knowledge, this has not been applied to standard set-based deep
learning tasks, but this area could certainly provide interesting applications
of this method.

Liu et al. (2020) propose yet another approach: after ranking the inputs
according to a learned score function, a 1D convolution is applied to the
ranked values. However, in order to get gradients for the score function, Liu
et al. (2020) multiply each value with its score before feeding it into the
convolutional layer. Interestingly, while the gradients do backpropagate into
the score function, they do not come from the sorting. The gradients come from
the scores being used as features later on.

###  5.2 Approximate Permutation Invariance

One motivation for $k$-ary Janossy pooling is its low computational cost
relative to full $M$-ary Janossy pooling. Recall that the high computational
cost of $M$-ary Janossy pooling is due to the fact that $S_{M}$ consists of
$M!$ permutations, each of which must be computed. Murphy et al. (2019)
propose an alternative method of reducing this computational cost: instead of
pooling over all permutations in $S_{M}$, a fixed number $p<M!$ of
permutations are randomly sampled. The pooling is then performed only over
those random samples, yielding approximate permutation invariance. Murphy et
al. (2019) show that this method can provide good empirical results even when
setting $p=1$. It is also possible to set, e.g., $p=1$ during training and
$p>1$ at test time when fidelity of our predictions is more important, akin to
ensemble methods. This could even be a potentially useful way to obtain
uncertainty estimates for the model’s predictions.

Pabbaraju and Jain (2020) approach approximate permutation invariance in a
different way. Inspired by Generative Adversarial Networks (Goodfellow et al.,
2016), they propose to use an adversary that tries to find the permutation of
the input data which maximises the loss of the main task. This encourages the
model to become close to permutation-invariant to minimise the impact of the
adversary.

###  5.3 From Sets to Graphs

Figure 9: From sets to graphs and hyper-graphs. Sets can be extended to graphs
by introducing the notion of edges. A permutation of the input now corresponds
to a permutation of the nodes together with the respective edges.

Even though this paper is focussed on sets, not graphs, there is an obvious
link between these two topics, which we briefly discuss. Graphs typically
consist of nodes (which form sets) and edges, where each edge connects two
nodes. This can be extended to hyper-graphs which include information attached
to triplets of nodes (Yadati et al., 2018; Wei et al., 2020). From this
perspective, it becomes clear that a set can be seen as a graph without edges
(Figure 9).

Whereas a set of $M$ nodes (without edge information) can be represented as a
vector of length $M$, a fully-connected bi-directional graph has $M(M-1)$
edges, which can be captured in an $M\times M$ adjacency matrix. Analogously,
hyper-graph data can be represented with higher order adjency tensors. The
concept of permutations can now easily be extended from sets to graphs: in
addition to nodes, the adjacency matrices capturing the edge information are
transformed by the same permutation. This raises the question whether
permutation invariant architectures from the sets literature can be applied to
graphs as well. Interestingly, there is no canonical way to apply Deep Sets to
graphs as it is not clear how to process the edge information. With self-
attention algorithms (Vaswani et al., 2017), on the other hand, it is
straightforward to include edge information (Veličković et al., 2018; Fuchs et
al., 2020).

Notably, Maron et al. (2019b) study the set of independent linear,
permutation-invariant or equivariant functions (i.e. matrices) transforming
vectorised versions of the adjacency tensors. In fact, there is an orthogonal
basis of such linear, permutation-equivariant functions. The number of basis
vectors is connected to the Bell number and is, remarkably, independent of the
number of nodes in the (hyper-)graph. As an example, the edge information of a
bi-directional graph can be written as an $M\times M$ adjacency matrix or,
after vectorising this matrix, as a vector of length $M^{2}$. This vector can
now be linearly transformed by multiplying it with a matrix of size
$M^{2}\times M^{2}$. Maron et al. (2019b) show that there is an orthogonal
basis of 15 different $M^{2}\times M^{2}$ matrices which transform the
(vectorised) adjacency matrix in an equivariant manner. The number 15 is the
fourth Bell number, and is independent of the size $M$ of the graph.

This result shows a contrast between linear and nonlinear permutation-
invariant functions. The complexity of the space of linear functions does not
change as the number of inputs increases. By contrast, at least from the
perspective of Deep Sets, the “complexity” of the nonlinear function space as
measured by the necessary latent dimension increases with the number of
inputs, as is shown in Section 3. Our main result in Section 4 shows that this
is the case even if we consider not the whole function space, but also any
dense subspace.

##  6 Universality Beyond Deep Sets

We have seen that Deep Sets is theoretically capable of representing all
permutation-invariant functions if the latent space is at least as large as
the cardinality of the sets being processed. For large input set sizes, this
can be prohibitively slow and memory-consuming. Moreover, even for small set
sizes, the theoretical universality does not guarantee that this is the best
choice in practice. For example, from relational reasoning experiments (Fuchs
et al., 2019), it is known that Deep Sets is not always best at learning about
interactions between input elements. Especially when dependencies between
elements are important for the task, other architectures, such as self-
attention, are often preferred. This raises the question of how this empirical
evidence of superior performance on some tasks relates to general theoretical
limitations of these models. In the following, we provide a summary of the
sufficiency and necessity criteria for universal function representation for
different categories of set-based learning approaches.

###  6.1 Janossy Pooling

We consider $k$-ary Janossy pooling as depicted in Figure 1 and described in
Section 2. We assume a universal function approximator processing the permuted
input subsets, a sum over the processed inputs, and a final component which is
again a universal function approximator acting on the sum.

###### Definition 8

Let $M,N,k\in\mathbb{N}$, $\mathbf{x}\in\mathbb{R}^{M}$. Let
$f:\mathbb{R}^{M}\to\mathbb{R}$. Write $T_{k}(\mathbf{x})$ for the set of all
$k$-tuples of coordinates of $\mathbf{x}$. We say that $f$ has a _continuous
$k$-ary Janossy representation via $\mathbb{R}^{N}$_ if there exist continuous
functions $\phi:\mathbb{R}^{k}\to\mathbb{R}^{N}$ and
$\rho:\mathbb{R}^{N}\to\mathbb{R}$ such that:

$f(\mathbf{x})=\rho\Big{(}\sum_{\mathbf{t}\in
T_{k}(\mathbf{x})}\phi(\mathbf{t})\Big{)}$

####  6.1.1 Case $k=1$

This case is Deep Sets. In Sections 3 and 4, we provided an in-depth analysis
of this case. In a nutshell, Janossy pooling for $k=1$ can approximate all
permutation-invariant functions if the latent space $N$ is at least as large
as the number of inputs $M$. Moreover, we show that a smaller latent space
($N<M$) does not suffice in general.

####  6.1.2 Case $1<k<M$

This inherits sufficiency from the case $k=1$: the network processing inputs
of cardinality $k$ can ignore all inputs except the first. This recovers Deep
Sets, though each element is seen more than once, so the model must divide its
output by the number of inputs having the same first element. In Janossy
pooling, this number is
$(M-1)\cdot(M-2)\cdot\ldots\cdot(M-2)(M-k)=(M-1)!/(M-k-1)!$. This gives the
following statement:

###### Theorem 9

Let $f:\mathbb{R}^{M}\to\mathbb{R}$ be continuous and permutation-invariant.
Then $f$ has a continuous $k$-ary Janossy representation via $\mathbb{R}^{M}$
for any choice of $k$.

####  6.1.3 Case $k=M$

In this case, the first part of the neural network sees the entire input, and
can therefore directly approximate the desired function. The model must then
divide by a factor which takes into account the sum over the permuted terms,
namely $M!$. This means that there is no requirement anymore on the size of
the latent space, and we can make the following statement:

###### Theorem 10

Let $f:\mathbb{R}^{M}\to\mathbb{R}$ be continuous and permutation-invariant.
Then $f$ has a continuous $M$-ary Janossy representation via $\mathbb{R}$.

(a) Minimum Necessity

(b) Maximum Sufficiency

Figure 10: Necessary and sufficient conditions for the size of the latent
dimension for Janossy pooling. The large, green circles show the minimum and
maximum boundaries as according to our proofs. The smaller, purple circles
show possible true necessary and sufficient conditions for universal function
representation.

####  6.1.4 Open Questions

For the extreme cases of $k$-ary Janossy pooling, $k=1$ and $k=M$, we know a
necessary and sufficient condition on the latent space dimension required for
universal approximation. For $1<k<M$, however, there is a gap between the
largest known necessary condition and the lowest known sufficient condition.
Figure 10 visualises the conditions we derived and what the true, strongest
statements might be. As an example: for $k=2$, we know that a latent dimension
of $N=M$ is sufficient and a latent dimension of $N=1$ is necessary in order
to be able to represent all permutation-invariant functions. However, it is
possible that $N=2$ is sufficient, or that $N=M-1$ is necessary. This is an
interesting open question and we leave it for future work to further
investigate this.

The proofs of our results on Deep Sets rely on the input elements being
1-dimensional. It is known that Deep Sets is universal for approximation of
set functions with higher-dimensional inputs, and indeed sufficient conditions
on the latent space dimension are known for both invariant (Han et al., 2019)
and equivariant (Segol and Lipman, 2020; Maron et al., 2019a) set functions.
It is unknown, however, whether these known sufficiency bounds are also
necessary – indeed, no non-trivial necessary bound is known, other than the
1-dimensional case presented in Section 4.

###  6.2 Sorting

In Section 5.1, we described a category of methods which achieve permutation
invariance through sorting the inputs. We assume that a (potentially learned)
scoring function is used to sort the inputs. A list of sorted inputs is then
fed to a universal function approximator (e.g. a sufficiently large neural
network). As the order of the sorted input is invariant with respect to
permutations of the input, the whole architecture is automatically
permutation-invariant. Since the second part of the model is a universal
approximator, this architecture choice is therefore a universal function
approximator for permutation-invariant functions and we arrive at the
following conclusion:

###### Theorem 11

Let $f:\mathbb{R}^{M}\to\mathbb{R}$ be continuous and permutation-invariant.
Then for any sorted version of the inputs, $f$ has a continuous representation
which acts on these sorted inputs.

Caution must be exercised in the case where the sorting does not operate
directly on the inputs, but instead on features derived from the inputs.
Universality still holds if the features are a smooth bijective mapping from
the inputs.

###  6.3 Approximate Permutation Invariance

In Section 5.2, we mentioned two approaches to approximate permutation
invariance. These models are in some sense _too_ expressive – they may,
depending on the exact implementation details, be capable of approximating the
permutation-invariant target function, but they may also be capable of
approximating functions which are not permutation-invariant.

In the approach of Pabbaraju and Jain (2020), permutation invariance is
encouraged by the training process, but the model class is not constrained to
be permutation-invariant – if a permutation-sensitive function approximator is
used to build the model, then the trained model may retain the ability to
distinguish between different permutations of the same set. Whether the model
is capable of approximating the target function depends entirely on the model
class chosen – Pabbaraju and Jain (2020) choose an LSTM, but other models
could be trained with a similar adversarial method.

In the case of approximate Janossy pooling it is similarly clear that, if a
universal approximator is used for the function whose outputs are pooled (i.e.
for the function $f$ in the notation of Equation 1), then the overall model
inherits this universality. Although permutation invariance is not guaranteed,
the model is guaranteed to approximate permutation invariance in the following
sense. Write $p$ for the number of permutations sampled, and write $f$ for the
permutation-sensitive function whose outputs are pooled. For a given set
$\mathbf{x}$, there are $M!$ possible permutations $\pi$, and therefore $M!$
possible outputs $f\big{(}\pi(\mathbf{x})\big{)}$. When $p=1$, we get an
output sampled uniformly from these possible outputs, and we can view this
output as a random variable with variance $\sigma^{2}$. For $p>1$, the output
is the mean of a random sample of size $p$ from the set of outputs of $f$. The
variance of this random variable is

$\frac{M!-p}{M!-1}\cdot\frac{\sigma^{2}}{p}.$

This goes monotonically to $0$ as $p\to M!$.

##  7 Conclusion

This work provides a theoretical characterisation of the representation and
approximation of permutation-invariant functions. To this end, we focus on the
Deep Sets architecture from Zaheer et al. (2017) and derive sufficient and
necessary conditions for continuous function representation. This is achieved
by noting the importance of considering continuous transformations. We find
that Deep Sets is only able to represent all continuous functions if the
latent space is at least as large as the number of inputs. Further, we relate
these insights back to the broader paradigm of Janossy pooling, as introduced
by Murphy et al. (2019).

Continuing our focus on continuous transformations, we adopt a topological
perspective to answer the question of whether requiring universal function
representation is an overly strong criterion, and whether universal function
approximation would be possible even with smaller latent spaces. We turn again
to the Deep Sets architecture and answer this question in the negative. We
show that functions exist which can only be approximated very poorly (i.e. the
worst case error is no better than a constant baseline) when making the latent
space any smaller than the number of inputs.

We hope that the analytical arguments in this work inspire future theoretical
treatments of the subject while also providing practical guidance for machine
learning practitioners. Regarding future work, it would be interesting to
extend the theoretical analysis beyond scalar-valued set elements, to vector-
valued set elements, as commonly encountered in practical applications.

## Acknowledgements

We thank André Henriques, Jan Steinebrunner and Tom Zeman for a helpful
mathematical discussion, including proofs that the function $\Gamma_{N}$
defined in Equation 14 has a zero when $N=2$. This research was funded by the
EPSRC AIMS Centre for Doctoral Training at the University of Oxford.

##  A Mathematical Remarks

###  A.1 Infinite Sums

Throughout this paper we consider expressions of the form

$\Phi(X)=\Sigma_{x\in X}\phi(x)$ (24)

where $X$ is an arbitrary set. The meaning of this expression is clear when
$X$ is finite, but when $X$ is infinite, we must be precise about what we
mean.

####  A.1.1 Countable Sums

We usually denote countable sums as e.g. $\Sigma_{i=1}^{\infty}x_{i}$. Note
that there is an ordering of the $x_{i}$ here, whereas there is no ordering in
Equation 24. The reason that we consider sums is for their permutation
invariance in the finite case, but note that in the infinite case, permutation
invariance of sums does not necessarily hold! For instance, the alternating
harmonic series $\Sigma_{i=1}^{\infty}\frac{(-1)^{i}}{i}$ can be made to
converge to any real number simply by reordering the terms of the sum. For
expressions like (24) to make sense, we must require that the sums in question
are indeed permutation invariant. This property is known as _absolute
convergence_ , and it is equivalent to the property that the sum of absolute
values of the series converges. We therefore require everywhere that
$\Sigma_{x\in X}|\phi(x)|$ is convergent. For any $X$ where this is not the
case, we will set $\Phi(X)=\infty$.

####  A.1.2 Uncountable Sums

It is well known that a sum over an uncountable set of elements only converges
if all but countably many elements are 0. Allowing sums over uncountable sets
is therefore of little interest, since it essentially reduces to the countable
case.

###  A.2 Continuity of Functions on Sets

We are interested in functions on subsets of $\mathbb{R}$, i.e. elements of
$2^{\mathbb{R}}$, and the notion of continuity on $2^{\mathbb{R}}$ is not
straightforward. As a convenient shorthand, we discuss “continuous” functions
$f$ on $2^{\mathbb{R}}$, by which we mean that the function $f_{M}$ induced by
$f$ on $\mathbb{R}^{M}$ by $f_{N}(x_{1},...,x_{M})=f(\\{x_{1},...,x_{M}\\})$
is continuous for every $M\in\mathbb{N}$.

###  A.3 Remark on Theorem 11

The proof for Theorem 11 from Zaheer et al. (2017) can be extended to dealing
with multi sets, i.e. sets with repeated elements. To that end, we replace the
mapping to natural numbers $c(X):\mathbb{R}^{M}\to\mathbb{N}$ with a mapping
to prime numbers $p(X):\mathbb{R}^{M}\to\mathbb{P}$. We then choose
$\phi(x_{m})=-\log p(x_{m})$. Therefore,

$\Phi(X)=\sum_{m=1}^{M}\phi(x_{m})=\log\prod_{m=1}^{M}\frac{1}{p(x_{m})}$ (25)

which takes a unique value for each distinct $X$ therefore extending the
validity of the proof to multi-sets. This choice of $\phi$ diverges with
infinite set size.

In fact, it is straightforward to show that there is no function $\phi$ for
which $\Phi$ provides a unique mapping for arbitrary multi-sets while at same
time guaranteeing convergence for infinitely large sets. Assume a function
$\phi$ and an arbitrary point $x$ such that $\phi(x)=a\neq 0$. Then, the
multiset comprising infinitely many identical members $x$ would give:

$\Phi(X)=\sum_{i=1}^{\infty}\phi(x_{m})=\sum_{i=1}^{\infty}a=\pm\infty$ (26)

$[3]_{6}$$[5]_{6}$$[6]_{6}$$[4]_{6}$$[2]_{6}$$[0]_{6}$$[1]_{6}$$X_{6}^{+1}$$X_{6}^{\shortminus
1}$ Figure 11: The $6$-dimensional simplex $\Delta_{6}$, and the low-
dimensional faces $X_{6}^{+1}$ and $X_{6}^{\shortminus 1}$, visualised using
the complete graph $K_{7}$. Here, $[m]_{6}$ denotes the vertex of $\Delta_{6}$
whose coordinates in $\mathbb{R}^{6}$ consist of $m$ ones followed by $6-m$
negative ones.

###  A.4 Visualising High-dimensional Simplices

In the proof of Theorem 4, we make heavy use of the $N$-dimensional simplex
$\Delta_{N}$, its $N-1$-dimensional faces $\Delta_{N}^{(i)}$, and the two
opposite faces $X_{M}^{+1}$ and $X_{M}^{\shortminus 1}$ of the $M$-dimensional
simplex $\Delta_{M}$. To mentally keep track of all these different objects,
it is helpful to have a way of visualising them. Although these simplices are
high-dimensional objects, they can be visualised easily as graphs, as shown in
Figure 11.

An $N$-dimensional simplex can be defined as the convex hull of $N+1$ points
in general position.202020That is, no three points are collinear, no four
points are coplanar, etc. We can represent this as the complete graph
$K_{N+1}$, where just as any pair of vertices of the simplex are joined by an
edge, so are any pair of vertices of the graph. An $N-1$-dimensional face of
the simplex is just the convex hull of $N$ of the $N+1$ vertices, and this can
be viewed as an induced $K_{N}$ subgraph of $K_{N+1}$. Lower-dimensional faces
can be viewed similarly.

Under our definition of $\Delta_{N}$, the vertices of the simplex are the
points whose coordinates are a (possibly empty) sequence of ones followed by a
sequence of negative ones. Any vertex can be written in shorthand as
$[m]_{N}$, indicating the point in dimension $N$ consisting of $m$ ones
followed by all negative ones. For example, $[2]_{3}=(1,1,\shortminus 1)$, the
vertex of $\Delta_{3}$ beginning with two ones.

Figure 11 illustrates this way of visualising $\Delta_{N}$, showing the
6-dimensional simplex $\Delta_{6}$ represented as a complete graph with 7
vertices. With the vertices arranged appropriately, the faces
$\smash{X_{6}^{+1}}$ and $\smash{X_{6}^{\shortminus 1}}$ correspond to the
indicated subgraphs, and it is visually clear that it is sensible to describe
them as “opposite” faces of the simplex. The faces $\smash{\Delta_{6}^{(0)}}$
and $\smash{\Delta_{6}^{(6)}}$ are obtained by removing $[0]_{6}$ and
$[6]_{6}$ respectively.

###  A.5 Extending Theorem 4 to Higher Dimensions

As discussed in the main text, an interesting line of future work lies in
extending Theorem 4 to sets of higher-dimensional elements. We briefly make
note of a small obstacle to extending the arguments of this work to the
higher-dimensional case.

Our proof of Theorem 4 makes use of the fact that an arbitrary continuous
function $f$ on $\mathbb{R}^{M}$ can be used to construct a continuous
permutation-invariant function by composing with sort. This simplifies the
process of defining a hard-to-approximate continuous permutation-invariant
target function $f_{*}$, as in Equation 10. For $d$-dimensional inputs with
$d>1$, however, this simplification is not possible because there is no
continuous sorting function on $\mathbb{R}^{d}$.

In fact we can say something slightly stronger than this. The important
property of sort for the purpose above is that it maps all permutations of a
given set to the same canonical permutation. That is, it has the following two
properties:

  1. 1.

It is permutation-invariant.

  2. 2.

For any set $\mathbf{x}$, there is a permutation $\pi$ such that
$\texttt{sort}\big{(}\pi(\mathbf{x})\big{)}=\pi(\mathbf{x})$.

We refer to any function satisfying these properties as a _quasi-sorting
function_ , since this definition includes many functions which cannot be
defined by sorting according to any order relation. For sets of
$d$-dimensional elements, there is not only no continuous sorting function,
there is also no continuous quasi-sorting function. To see this, we give an
informal argument which can easily be made precise.

12${\definecolor[named]{.}{rgb}{0.39453125,0.5625,0.6171875}\color[rgb]{0.39453125,0.5625,0.6171875}\definecolor[named]{pgfstrokecolor}{rgb}{0.39453125,0.5625,0.6171875}\shortminus\text{½}\sqrt{2}}$${\definecolor[named]{.}{rgb}{0.39453125,0.5625,0.6171875}\color[rgb]{0.39453125,0.5625,0.6171875}\definecolor[named]{pgfstrokecolor}{rgb}{0.39453125,0.5625,0.6171875}\text{½}\sqrt{2}}$${\definecolor[named]{.}{rgb}{0.57421875,0.23046875,0.234375}\color[rgb]{0.57421875,0.23046875,0.234375}\definecolor[named]{pgfstrokecolor}{rgb}{0.57421875,0.23046875,0.234375}\text{½}\sqrt{2}}$${\definecolor[named]{.}{rgb}{0.57421875,0.23046875,0.234375}\color[rgb]{0.57421875,0.23046875,0.234375}\definecolor[named]{pgfstrokecolor}{rgb}{0.57421875,0.23046875,0.234375}\shortminus\text{½}\sqrt{2}}$$\left(\vbox{\hrule
height=14.99998pt,depth=14.99998pt,width=0.0pt}\right.$$\left.\vbox{\hrule
height=14.99998pt,depth=14.99998pt,width=0.0pt}\right)$$g(\mathbf{x})=\leavevmode\nobreak\
$

(a)

12${\definecolor[named]{.}{rgb}{0.39453125,0.5625,0.6171875}\color[rgb]{0.39453125,0.5625,0.6171875}\definecolor[named]{pgfstrokecolor}{rgb}{0.39453125,0.5625,0.6171875}0}$${\definecolor[named]{.}{rgb}{0.39453125,0.5625,0.6171875}\color[rgb]{0.39453125,0.5625,0.6171875}\definecolor[named]{pgfstrokecolor}{rgb}{0.39453125,0.5625,0.6171875}1}$${\definecolor[named]{.}{rgb}{0.57421875,0.23046875,0.234375}\color[rgb]{0.57421875,0.23046875,0.234375}\definecolor[named]{pgfstrokecolor}{rgb}{0.57421875,0.23046875,0.234375}0}$${\definecolor[named]{.}{rgb}{0.57421875,0.23046875,0.234375}\color[rgb]{0.57421875,0.23046875,0.234375}\definecolor[named]{pgfstrokecolor}{rgb}{0.57421875,0.23046875,0.234375}\shortminus
1}$$\left(\vbox{\hrule
height=16.1833pt,depth=16.1833pt,width=0.0pt}\right.$$\left.\vbox{\hrule
height=16.1833pt,depth=16.1833pt,width=0.0pt}\right)$$g(\mathbf{x})=\leavevmode\nobreak\
$

(b)

12${\definecolor[named]{.}{rgb}{0.39453125,0.5625,0.6171875}\color[rgb]{0.39453125,0.5625,0.6171875}\definecolor[named]{pgfstrokecolor}{rgb}{0.39453125,0.5625,0.6171875}\shortminus\text{½}\sqrt{2}}$${\definecolor[named]{.}{rgb}{0.39453125,0.5625,0.6171875}\color[rgb]{0.39453125,0.5625,0.6171875}\definecolor[named]{pgfstrokecolor}{rgb}{0.39453125,0.5625,0.6171875}\shortminus\text{½}\sqrt{2}}$${\definecolor[named]{.}{rgb}{0.57421875,0.23046875,0.234375}\color[rgb]{0.57421875,0.23046875,0.234375}\definecolor[named]{pgfstrokecolor}{rgb}{0.57421875,0.23046875,0.234375}\text{½}\sqrt{2}}$${\definecolor[named]{.}{rgb}{0.57421875,0.23046875,0.234375}\color[rgb]{0.57421875,0.23046875,0.234375}\definecolor[named]{pgfstrokecolor}{rgb}{0.57421875,0.23046875,0.234375}\text{½}\sqrt{2}}$$\left(\vbox{\hrule
height=14.99998pt,depth=14.99998pt,width=0.0pt}\right.$$\left.\vbox{\hrule
height=14.99998pt,depth=14.99998pt,width=0.0pt}\right)$$g(\mathbf{x})=\leavevmode\nobreak\
$

(c)

12${\definecolor[named]{.}{rgb}{0.39453125,0.5625,0.6171875}\color[rgb]{0.39453125,0.5625,0.6171875}\definecolor[named]{pgfstrokecolor}{rgb}{0.39453125,0.5625,0.6171875}\shortminus
1}$${\definecolor[named]{.}{rgb}{0.39453125,0.5625,0.6171875}\color[rgb]{0.39453125,0.5625,0.6171875}\definecolor[named]{pgfstrokecolor}{rgb}{0.39453125,0.5625,0.6171875}0}$${\definecolor[named]{.}{rgb}{0.57421875,0.23046875,0.234375}\color[rgb]{0.57421875,0.23046875,0.234375}\definecolor[named]{pgfstrokecolor}{rgb}{0.57421875,0.23046875,0.234375}1}$${\definecolor[named]{.}{rgb}{0.57421875,0.23046875,0.234375}\color[rgb]{0.57421875,0.23046875,0.234375}\definecolor[named]{pgfstrokecolor}{rgb}{0.57421875,0.23046875,0.234375}0}$$\left(\vbox{\hrule
height=16.1833pt,depth=16.1833pt,width=0.0pt}\right.$$\left.\vbox{\hrule
height=16.1833pt,depth=16.1833pt,width=0.0pt}\right)$$g(\mathbf{x})=\leavevmode\nobreak\
$

(d)

12${\definecolor[named]{.}{rgb}{0.39453125,0.5625,0.6171875}\color[rgb]{0.39453125,0.5625,0.6171875}\definecolor[named]{pgfstrokecolor}{rgb}{0.39453125,0.5625,0.6171875}\shortminus\text{½}\sqrt{2}}$${\definecolor[named]{.}{rgb}{0.39453125,0.5625,0.6171875}\color[rgb]{0.39453125,0.5625,0.6171875}\definecolor[named]{pgfstrokecolor}{rgb}{0.39453125,0.5625,0.6171875}\text{½}\sqrt{2}}$${\definecolor[named]{.}{rgb}{0.57421875,0.23046875,0.234375}\color[rgb]{0.57421875,0.23046875,0.234375}\definecolor[named]{pgfstrokecolor}{rgb}{0.57421875,0.23046875,0.234375}\text{½}\sqrt{2}}$${\definecolor[named]{.}{rgb}{0.57421875,0.23046875,0.234375}\color[rgb]{0.57421875,0.23046875,0.234375}\definecolor[named]{pgfstrokecolor}{rgb}{0.57421875,0.23046875,0.234375}\shortminus\text{½}\sqrt{2}}$$\left(\vbox{\hrule
height=14.99998pt,depth=14.99998pt,width=0.0pt}\right.$$\left.\vbox{\hrule
height=14.99998pt,depth=14.99998pt,width=0.0pt}\right)$$g(\mathbf{x})=\leavevmode\nobreak\
$

(e)

Figure 12: Rotating a pair of points around their midpoint, and seeing how the
canonical ordering changes. Figures 12(a) and 12(e) represent the same set, so
the canonical ordering $g(\mathbf{x})$ must be the same in both cases. This is
visually represented by the colours of the points, where the solid blue point
occupies the first row of $g(\mathbf{x})$ and the striped red point occupies
the second row of $g(\mathbf{x})$. In order for the colours in 12(a) and 12(e)
to match, point “$1$” must switch from blue to red at some point during the
180-degree rotation from 12(a) to 12(e). This switching of colours represents
swapping the rows of $g(\mathbf{x})$, which is a discontinuity.

Consider the simplest case, a set of two 2-dimensional elements, and let $g$
be a quasi-sorting function. We can visualise a set of two 2-dimensional
elements as being a pair of points in the plane. As is the case throughout
this paper, we are working with an ordered representation of this set, in this
case as an element $\mathbf{x}$ of $\mathbb{R}^{2\times 2}$. That is, we have
a $2\times 2$ matrix $\mathbf{x}$, where each row gives the coordinates of one
point.

Now rotate this pair of points around their midpoint, in a continuous motion,
through an angle of 180 degrees. This motion is illustrated in Figure 12, with
the point in the first row of $\mathbf{x}$ labelled “$1$” and the point in the
second row labelled “$2$”. The points are coloured according to which row they
belong to in the canonical permutation $g(\mathbf{x})$, with solid blue
indicating the first row and striped red indicating the second row.

After a 180 degree rotation, the set is the same as it was at the beginning.
The canonical permutation, i.e. the colouring, is also the same as at the
beginning. This means that at some point during the rotation, the colour of
each point has switched – in Figure 12, this happens between 12(b) and 12(c).
This switching of colours corresponds to swapping the rows of the output
matrix. Since the rows of the matrix are distinct (because the points
representing each row are a constant distance apart), this swapping is
discontinuous, and therefore $g$ is not continuous.

##  B Proofs and Additional Results

theoremqdiscontinuous There exist functions $f:2^{\mathbb{Q}}\to\mathbb{R}$
such that, whenever $(\rho,\phi)$ is a sum-decomposition of $f$ via
$\mathbb{R}$, $\phi$ is discontinuous at every point $q\in\mathbb{Q}$.

theoremuncdiscontinuous Let $f:\mathbb{R}^{\mathcal{F}}\to\mathbb{R}$. Then
$f$ is sum-decomposable via $\mathbb{R}$.

theoremuncfinite If $\mathfrak{U}$ is uncountable, then there exist functions
$f:2^{\mathfrak{U}}\to\mathbb{R}$ which are not sum-decomposable. This holds
even if the sum-decomposition $(\rho,\phi)$ is allowed to be discontinuous.

###  B.1 Proof of Section B

*

Proof  Consider $f(X)=\texttt{sup}(X)$, the least upper bound of $X$. Write
$\Phi(X)=\Sigma_{x\in X}\phi(x)$. So we have:

$\texttt{sup}(X)=\rho(\Phi(X))$

First note that $\phi(q)\neq 0$ for any $q\in\mathbb{Q}$. If we had
$\phi(q)=0$, then we would have, for every $X\subset\mathbb{Q}$:

$\Phi(X)=\Phi(X)+\phi(q)=\Phi(X\cup\\{q\\})$

But then, for instance, we would have:

$q=\texttt{sup}(\\{q-1,q\\})=\texttt{sup}(\\{q-1\\})=q-1$

This is a contradiction, so $\phi(q)\neq 0$.

Next, note that $\Phi(X)$ must be finite for every upper-bounded
$X\subset\mathbb{Q}$ (since sup is undefined for unbounded $X$, we do not
consider such sets, and may allow $\Phi$ to diverge). Even if we allowed the
domain of $\rho$ to be $\mathbb{R}\cup\\{\infty\\}$, suppose $\Phi(X)=\infty$
for some upper-bounded set $X$. Then:

$\displaystyle\texttt{sup}(X)$ $\displaystyle=$ $\displaystyle\rho(\Phi(X))$
$\displaystyle=$ $\displaystyle\rho(\infty)$ $\displaystyle=$
$\displaystyle\rho(\infty+\phi(\texttt{sup(X) + 1}))$ $\displaystyle=$
$\displaystyle\rho(\Phi(X\cup\\{\texttt{sup}(X)+1\\}))$ $\displaystyle=$
$\displaystyle\texttt{sup}(X\cup\\{\texttt{sup}(X)+1\\})$ $\displaystyle=$
$\displaystyle\texttt{sup}(X)+1$

This is a contradiction, so $\Phi(X)<\infty$ for any upper-bounded set $X$.

Now from the above it is immediate that, for any upper-bounded set $X$, only
finitely many $x\in X$ can have $\phi(x)>\frac{1}{n}$. Otherwise we can find
an infinite upper-bounded set $Y\subset X$ with $\phi(y)>\frac{1}{n}$ for
every $y\in Y$, and $\Phi(Y)=\infty$.

Finally, let $q\in\mathbb{Q}$. We have already shown that $\phi(q)\neq 0$, and
we will now construct a sequence $q_{n}$ with:

  1. 1.

$q_{n}\to q$

  2. 2.

$\phi(q_{n})\to 0$

If $\phi$ were continuous at $q$, we would have $\phi(q_{n})\to\phi(q)$, so
the above two points together will give us that $\phi$ is discontinuous at
$q$.

So now, for each $n\in\mathbb{N}$, consider the set $B_{n}$ of points which
lie within $\frac{1}{n}$ of $q$. Since only finitely many points $p\in B_{n}$
have $\phi(p)>\frac{1}{n}$, and $B_{n}$ is infinite, there must be a point
$q_{n}\in B_{n}$ with $\phi(q_{n})<\frac{1}{n}$. The sequence of such $q_{n}$
clearly satisfies both points above, and so $\phi$ is discontinuous
everywhere.

###  B.2 Proof of Section B

*

Proof  Define $\Phi:\mathbb{R}^{\mathcal{F}}\to\mathbb{R}$ by
$\Phi(X)=\Sigma_{x\in X}\phi(x)$. If we can demonstrate that there exists some
$\phi$ such that $\Phi$ is injective, then we can simply choose
$\rho=f\circ\Phi^{-1}$ and the result is proved.

Say that a set $X\subset\mathbb{R}$ is _finite-sum-distinct_ (f.s.d.) if, for
any finite subsets $A,B\subset X$, $\Sigma_{a\in A}a\neq\Sigma_{b\in B}b$.
Now, if we can show that there is a finite-sum-distinct set $D$ with the same
cardinality as $\mathbb{R}$ (we denote $|\mathbb{R}|$ by $\mathfrak{c}$), then
we can simply choose $\phi$ to be a bijection from $\mathbb{R}$ to $D$. Then,
by finite-sum-distinctness, $\Phi$ will be injective, and the result is
proved.

Now recall the statement of Zorn’s Lemma: suppose $\mathcal{P}$ is a partially
ordered set (or _poset_) in which every totally ordered subset has an upper
bound. Then $\mathcal{P}$ has a maximal element.

The set of all f.s.d. subsets of $\mathbb{R}$ (which we will denote
$\mathcal{D}$) forms a poset ordered by inclusion. Supposing that
$\mathcal{D}$ satisfies the conditions of Zorn’s Lemma, it must have a maximal
element, i.e. there is a f.s.d. set $D_{\text{max}}$ such that any set $E$
with $D_{\text{max}}\subsetneq E$ is not f.s.d. We claim that $D_{\text{max}}$
has cardinality $\mathfrak{c}$.

To see this, let $D$ be a f.s.d. set with infinite cardinality
$\kappa<\mathfrak{c}$ (any maximal $D$ clearly cannot be finite). We will show
that $D\neq D_{\text{max}}$. Define the _forbidden elements_ with respect to
$D$ to be those elements $x$ of $\mathbb{R}$ such that $D\cup\\{x\\}$ is not
f.s.d. We denote this set of forbidden elements $F_{D}$. Now note that, if $D$
is maximal, then $D\cup F_{D}=\mathbb{R}$. In particular, this implies that
$|F_{D}|=\mathfrak{c}$. But now consider the elements of $F_{D}$. By
definition of $F_{D}$, we have that $x\in F_{D}$ if and only if $\exists
c_{1},...,c_{m},d_{1},...,d_{n}\in D$ such that
$c_{1}+...+c_{m}+x=d_{1}+...+d_{n}$. So we can write $x$ as a sum of finitely
many elements of $D$, minus a sum of finitely many other elements of $D$. So
there is a surjection from pairs of finite sets of $D$ to elements of $F_{D}$.
i.e.:

$|F_{D}|\leq|D^{\mathcal{F}}\times D^{\mathcal{F}}|$

But since $D$ is infinite:

$|D^{\mathcal{F}}\times D^{\mathcal{F}}|=|D|=\kappa<\mathfrak{c}$

So $|F_{D}|<\mathfrak{c}$, and therefore $|D|$ is not maximal. This
demonstrates that $D_{\text{max}}$ must have cardinality $\mathfrak{c}$.

To complete the proof, it remains to show that $\mathcal{D}$ satisfies the
conditions of Zorn’s Lemma, i.e. that every totally ordered subset (or
_chain_) $\mathcal{C}$ of $\mathcal{D}$ has an upper bound. So consider:

$C_{\text{ub}}=\bigcup\mathcal{C}=\bigcup_{C\in\mathcal{C}}C$

We claim that $C_{\text{ub}}$ is an upper bound for $\mathcal{C}$. It is clear
that $C\subset C_{\text{ub}}$ for every $C\in\mathcal{C}$, so it remains to be
shown that $C_{\text{ub}}\in\mathcal{D}$, i.e. that $C_{\text{ub}}$ is f.s.d.

We proceed by contradiction. Suppose that $C_{\text{ub}}$ is not f.s.d. Then:

$\exists c_{1},...,c_{m},d_{1},...,d_{n}\in
C_{\text{ub}}:\Sigma_{i}c_{i}=\Sigma_{j}d_{j}$ (27)

But now by construction of $C_{\text{ub}}$ there must be sets
$C_{1},...,C_{m},D_{1},...,D_{m}\in\mathcal{C}$ with $c_{i}\in C_{i},d_{j}\in
D_{j}$. Let $\mathcal{B}=\\{C_{i}\\}_{i=1}^{m}\cup\\{D_{j}\\}_{j=1}^{n}$.
$\mathcal{B}$ is totally ordered by inclusion and all sets contained in it are
f.s.d., since it is a subset of $\mathcal{C}$. Since $\mathcal{B}$ is finite
it has a maximal element $B_{\text{max}}$. By maximality, we have
$c_{i},d_{j}\in B_{\text{max}}$ for all $c_{i},d_{j}$. But then by (27),
$B_{\text{max}}$ is not f.s.d., which is a contradiction. So we have that
$C_{\text{ub}}$ is f.s.d.

In summary:

  1. 1.

$\mathcal{D}$ satisfies the conditions of Zorn’s Lemma.

  2. 2.

Therefore there exists a maximal f.s.d. set, $D_{\text{max}}$.

  3. 3.

We have shown that any such set must have cardinality $\mathfrak{c}$.

  4. 4.

Given an f.s.d. set $D_{\text{max}}$ with cardinality $\mathfrak{c}$, we can
choose $\phi$ to be a bijection between $\mathbb{R}$ and $D_{\text{max}}$.

  5. 5.

Given such a $\phi$, we have that $\Phi(X)=\Sigma_{x\in X}\phi(x)$ is
injective on $R^{\mathcal{F}}$.

  6. 6.

Given injective $\Phi$, choose $\rho=f\circ\Phi^{-1}$.

  7. 7.

This choice gives us $f(X)=\rho(\Sigma_{x\in X}\phi(x))$ by construction.

This completes the proof.

###  B.3 Proof of Section B

*

Proof  Consider $f(X)=\texttt{sup}(X)$.

As discussed above, a sum over uncountably many elements can converge only if
countably many elements are non-zero. But as in the proof of Section B,
$\phi(x)\neq 0$ for any $x$. So it is immediate that sum-decomposition is not
possible for functions operating on uncountable subsets of $\mathfrak{U}$.

Even restricting to countable subsets is not enough. As in the proof of
Section B, we must have that for each $n\in\mathbb{N}$, $\phi(x)>\frac{1}{n}$
for only finitely many $x$. But then if this is the case, let
$\mathfrak{U}_{n}$ be the set of all $x\in\mathfrak{U}$ with
$\phi(x)>\frac{1}{n}$. Since $\phi(x)\neq 0$, we know that
$\mathfrak{U}=\bigcup\mathfrak{U}_{n}$. But this is a countable union of
finite sets, which is impossible because $\mathfrak{U}$ is uncountable.

###  B.4 Proof of Section 3.3

*

Proof  The reverse implication is clear. We already know from Zaheer et al.
(2017) that the function $\Phi:\Delta_{M}\to\mathbb{R}^{M+1}$ defined as
follows is a homeomorphism onto its image:

$\displaystyle\Phi_{q}(X)=\sum_{m=1}^{M}\phi_{q}(x_{m}),\quad q=0,\dots,M$
$\displaystyle\phi_{q}(x)=x^{q},\quad q=0,\dots,M$

Now define $\widetilde{\Phi}\to\mathbb{R}^{M}$ by

$\displaystyle\widetilde{\Phi}_{q}(X)=\sum_{m=1}^{M}\widetilde{\phi}_{q}(x_{m}),\quad
q=1,\dots,M$ $\displaystyle\widetilde{\phi}_{q}(x)=x^{q},\quad q=1,\dots,M.$

Note that $\Phi_{0}(X)=M$ for all $X$, so
$\text{Im}(\Phi)=\\{M\\}\times\text{Im}(\widetilde{\Phi})$. Since $\\{M\\}$ is
a singleton, these two images are homeomorphic, with a homeomorphism given by:

$\displaystyle\gamma:\text{Im}(\widetilde{\Phi})\to\text{Im}(\Phi)$
$\displaystyle\gamma(x_{1},\dots,x_{M})=(M,x_{1},\dots,x_{M})$

Now by definition, $\widetilde{\Phi}=\gamma^{-1}\circ\Phi$. Since this is a
composition of homeomorphisms, $\widetilde{\Phi}$ is also a homeomorphism.
Therefore $(f\circ\widetilde{\Phi}^{-1},\widetilde{\phi})$ is a continuous
sum-decomposition of $f$ via $\mathbb{R}^{M}$.

###  B.5 Proof of Section 3.3

*

Proof  We use the adapted sum-of-power mapping $\widetilde{\Phi}$ from above,
denoted in this section by $\Phi$

$\displaystyle\Phi_{q}(X)=\sum_{m=1}^{M}\phi_{q}(x_{m}),\quad q=1,\dots,M$
$\displaystyle\phi_{q}(x_{m})=(x_{m})^{q},\quad q=1,\dots,M$

which is shown above to be injective (up to reordering input sets). We
separate $\Phi_{q}(X)$ into two terms:

$\Phi_{q}(X)=\sum_{m=1}^{M^{\prime}}\phi_{q}(x_{m})+\sum_{m=M^{\prime}+1}^{M}\phi_{q}(x_{m})$
(28)

For an input set $X$ with $M^{\prime}=M-P$ elements, with $P\geq 0$, we say
that the set contains $M^{\prime}$ “actual elements” as well as $P$ “empty”
elements which are not part of the input set. Those $P$ “empty elements” can
be regarded as place fillers when the size of the input set is smaller than
$M$, i.e. when $M^{\prime}<M$.

We fill in these $P$ elements with a constant value $k\notin[0,1]$, preserving
the injectivity of $\Phi_{q}(X)$ for input sets $X$ of arbitrary size
$M^{\prime}$:

$\Phi_{q}(X)=\sum_{m=1}^{M^{\prime}}\phi_{q}(x_{m})+\sum_{m=M^{\prime}+1}^{M}\phi_{q}(k)$
(29)

Equation 29 is no longer strictly speaking a sum-decomposition. This can be
fixed by re-arranging the expression:

$\begin{split}\Phi_{q}(X)&=\sum_{m=1}^{M^{\prime}}\phi_{q}(x_{m})+\sum_{m=M^{\prime}+1}^{M}\phi_{q}(k)\\\
&=\sum_{m=1}^{M^{\prime}}\phi_{q}(x_{m})+\sum_{m=1}^{M}\phi_{q}(k)-\sum_{m=1}^{M^{\prime}}\phi_{q}(k)\\\
&=\sum_{m=1}^{M^{\prime}}\left[\phi_{q}(x_{m})-\phi_{q}(k)\right]+\sum_{m=1}^{M}\phi_{q}(k)\end{split}$
(30)

The last term in Equation 30 is a constant value which only depends on the
choice of $k$ and is independent of $X$ and $M^{\prime}$. Hence, we can
replace $\phi_{q}(x)$ by $\widehat{\phi_{q}}(x)=\phi_{q}(x)-\phi_{q}(k)$. This
leads to a new sum-of-power mapping $\widehat{\Phi}_{q}(X)$ with

$\begin{split}\widehat{\Phi}_{q}(X)&=\sum_{m=1}^{M^{\prime}}\widehat{\phi}_{q}(x_{m})\\\
&=\Phi_{q}(X)-M\cdot\phi_{q}(k).\end{split}$ (31)

$\widehat{\Phi}$ is injective since $\Phi$ is injective and the last term in
the above sum is constant. $\widehat{\Phi}$ is also in the form of a sum-
decomposition.

For each $m<M$, we can follow the reasoning used in the rest of the proof of
Theorem 12 to note that $\widehat{\Phi}$ is a homeomorphism when restricted to
sets of size $m$ – we denote these restricted functions by
$\widehat{\Phi}_{m}$. Now each $\widehat{\Phi}_{m}^{-1}$ is a continuous
function into $\mathbb{R}^{m}$. We can associate with each a continuous
function $\widehat{\Phi}_{m,M}^{-1}$ which maps into $\mathbb{R}^{M}$, with
the $M-m$ tailing dimensions filled with the value $k$.

Now the domains of the $\widehat{\Phi}_{m,M}^{-1}$ are compact, since the
domain of $\widehat{\Phi}_{m,M}^{-1}$ is just the image of the compact set
$[0,1]$ under the continuous function $\widehat{\Phi}_{m}$. The domains of the
$\widehat{\Phi}_{m,M}^{-1}$ are also disjoint, since $k\notin[0,1]$. We can
therefore find a function $\widehat{\Phi}_{C}^{-1}$ which is continuous on
$\mathbb{R}^{M}$ and agrees with each $\widehat{\Phi}_{m,M}^{-1}$ on its
domain.

To complete the proof, let $\mathcal{Y}$ be a connected compact set with
$k\in\mathcal{Y},[0,1]\subset\mathcal{Y}$. Let $\widehat{f}$ be a function on
subsets of $\mathcal{Y}$ of size exactly $M$ satisfying

$\displaystyle\widehat{f}(X)=f(X);\quad X\subset[0,1]$
$\displaystyle\widehat{f}(X)=f(X\cap[0,1]);\quad X\subset[0,1]\cup\\{k\\}.$

We can choose $\widehat{f}$ to be continuous because $f$ is continuous. Then
$(\widehat{f}\circ\widehat{\Phi}_{C}^{-1},\widehat{\phi})$ is a continuous
sum-decomposition of $f$.

###  B.6 Max-Decomposition

Analogously to sum-decomposition, we define the notion of _max-decomposition_.
A function $f$ is max-decomposable if there are functions $\rho$ and $\phi$
such that

$f(\mathbf{x})=\rho\Bigl{(}\texttt{max}_{i}\big{(}\phi(x_{i})\big{)}\Bigr{)}.$

where the max is taken over each dimension independently in the latent space.
Our definitions of decomposability via $Z$ and continuous decomposability also
extend to the notion of max-decomposition.

We now state and prove a theorem which is closely related to Section 3.3, but
which establishes limitations on max-decomposition, rather than sum-
decomposition.

###### Theorem 12

Let $M>N\in\mathbb{N}$. Then there exist permutation invariant continuous
functions $f:\mathbb{R}^{M}\to\mathbb{R}$ which are not max-decomposable via
$\mathbb{R}^{N}$.

Note that this theorem rules out any max-decomposition, whether continuous or
discontinuous. We specifically demonstrate that summation is not max-
decomposable.

Proof  Consider $f(\mathbf{x})=\sum_{i=1}^{M}x_{m}$. Let
$\phi:\mathbb{R}\to\mathbb{R}^{N}$, and let $\mathbf{x}\in\mathbb{R}^{M}$ such
that $x_{i}\neq x_{j}$ when $i\neq j$.

For $n=1,\dots,N$, let $\mu(n)\in\\{1,\dots,M\\}$ such that

$\texttt{max}_{i}\big{(}\phi(x_{i})_{n}\big{)}=\phi(x_{\mu(n)})_{n}.$

That is, $\phi(x_{\mu(q)})$ attains the maximal value in the $q$-th dimension
of the latent space among all $\phi(x_{i})$. Now since $N<M$, there is some
$m\in\\{1,\dots,M\\}$ such that $\mu(n)\neq m$ for any $n\in\\{1,\dots,N\\}$.
So now consider $\widetilde{\mathbf{x}}$ defined by:

$\displaystyle\widetilde{x}_{i}=x_{i};i\neq m$ (32)
$\displaystyle\widetilde{x}_{m}=x_{\mu(1)}$ (33)

Then:

$\texttt{max}_{i}\big{(}\phi(x_{i})\big{)}=\texttt{max}_{i}\big{(}\phi(\widetilde{x}_{i})\big{)}$

But since we chose $\mathbf{x}$ such that all $x_{i}$ were distinct, we have
$\sum_{i=1}^{M}x_{i}\neq\sum_{i=1}^{M}\widetilde{x}_{i}$ by the definition of
$\widetilde{\mathbf{x}}$. This shows that $\phi$ cannot form part of a max-
decomposition for $f$. But $\phi$ was arbitrary, so no max-decomposition
exists.

###  B.7 Function Approximation

####  B.7.1 A stronger statement of Theorem 4

Given a function $f:[\shortminus 1,1]^{M}\to\mathbb{R}$, write $V_{f}$ for the
_variation_ of $f$:

$V_{f}=\underset{\mathbf{x}}{\texttt{max}}\big{(}f(\mathbf{x})\big{)}-\underset{\mathbf{x}}{\texttt{min}}\big{(}f(\mathbf{x})\big{)}$

######  Theorem 0 (Strong Form)

Let $M,N\in\mathbb{N}$ with $M>N$. There exists a continuous, non-constant,
permutation-invariant function $f:[\shortminus 1,1]^{M}\to\mathbb{R}$ such
that:

  1. 1.