On the Limitations of Representing Functions on Sets

Introduction

Machine learning models have had great success in taking advantage of structure in their input spaces: recurrent neural networks are popular models for sequential data (Sutskever et al., 2014) and convolutional neural networks are the state-of-the-art for many image-based problems (He et al., 2016). Recently, however, models for unstructured inputs in the form of sets have rapidly gained attention (Ravanbakhsh et al., 2016; Zaheer et al., 2017; Qi et al., 2017a; Lee et al., 2018; Murphy et al., 2018; Korshunova et al., 2018).

Importantly, a range of machine learning problems can naturally be formulated in terms of sets; e.g. parsing a scene composed of a set of objects (Eslami et al., 2016; Kosiorek et al., 2018), making predictions from a set of points forming a 3D point cloud (Qi et al., 2017a, b), or training a set of agents in reinforcement learning (Sunehag et al., 2017). Furthermore, attention-based models perform a weighted summation of a set of features (Vaswani et al., 2017; Lee et al., 2018). Hence, understanding the mathematical properties of set-based models is valuable both in terms of set-structured applications as well as better understanding the capabilities and limitations of attention-based models.

We refer to $Z$ here as the latent space. Since summation is permutation-invariant, a sum-decomposition is also permutation-invariant. Ravanbakhsh et al. (2016), Zaheer et al. (2017) and Qi et al. (2017b) have also considered the idea of enforcing permutation invariance using other operations, e.g. $\text{\tt{max}}(\cdot)$. In this paper we concentrate on a detailed analysis of sum-decomposition, but some of the limitations we discuss also apply when $\text{\tt{max}}(\cdot)$ is used instead of summation.

Our main contributions can be summarised as follows.

In contrast to previous work (Zaheer et al., 2017; Qi et al., 2017a), which considers sufficient conditions for universal function representation, we establish a necessary condition for a sum-decomposition-based model to be capable of universal function representation. Additionally, we provide weaker sufficient conditions which imply a stronger version of universality. Specifically, we show that the dimension of the latent space being at least as large as the maximum number of input elements is both necessary and sufficient for universal function representation.

While primarily targeted at neural networks, these results hold for any implementation of sum-decomposition, e.g. using Gaussian processes, as long as it provides universal function approximation for continuous functions. Proofs of all novel results are available in Appendix B.

Preliminaries

In this section we recount the theorems and proofs on sum-decomposition from Zaheer et al. (2017). We begin by introducing important definitions and the notation used throughout our work. Note that we focus on permutation-invariant functions and do not discuss permutation equivariance which is also considered in Zaheer et al. (2017).

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$.

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

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

Given a latent space $Z$, we say that $f$ is sum-decomposable via $Z$ when this expression holds for some $\phi$ whose codomain is $Z$, i.e. $\phi:\mathfrak{X}\to Z$.

We say that $f$ is continuously sum-decomposable when this expression holds for some continuous functions $\rho$ and $\phi$.

We will also consider sum-decomposability where the inputs to $f$ are vectors rather than sets - in this context, the sum is over the elements of the input vector.

Denote the power set of a set $\mathfrak{X}$ by $2^{\mathfrak{X}}$.

Denote the set of finite subsets of a set $\mathfrak{X}$ by $\mathfrak{X}^{\mathcal{F}}$.

Denote the set of subsets of a set $\mathfrak{X}$ containing at most $M$ elements by $\mathfrak{X}^{\leq M}$.

Throughout, we discuss expressions of the form $\Phi(X)=\Sigma_{x\in X}\phi(x)$, where $X$ is a set. Note that care must be taken in interpreting this expression when $X$ is not finite – we discuss this issue fully in Section A.1.

2 Background Theorems

Zaheer et al. (2017) consider the two cases where $X$ is a subset of, or drawn from, a countable and an uncountable universe $\mathfrak{X}$. We now outline the theorems and proofs relating to these two cases.

Now consider $\phi(x)=4^{-c(x)}$. Under this mapping, each $X\subset\mathfrak{X}$ corresponds to a unique real number expressed in base 4. Therefore $\Phi$ is injective, and the conclusion follows. ∎

This construction works for any set size $M$, and even for sets of infinite size. However, it assumes that $X$ is a set with no repeated elements, i.e. multisets are not supported. Specifically, the construction will fail with multisets because $\Phi$ fails to be injective if its domain includes multisets. In Section A.3, we extend Theorem 2.8 to also support multisets, with the restriction that infinite sets are no longer supported.

The proof by Zaheer et al. (2017) of Theorem 2.9 is more involved than for Theorem 2.8. We do not include it here in full detail, but briefly summarise below.

Show that $\Phi$ has a continuous inverse.

Zaheer et al. (2017) conjecture that any continuous permutation-invariant function $f$ on $2^{}$, the power set of $$, is continuously sum-decomposable. In Section 3, we show that this is not possible, and in Section 4 we show that even if the domain of$f$is restricted to$^{\mathcal{\leq F}}$, the finite subsets of$$, then$N\geq M$is a necessary condition for arbitrary functions$f$to be continuously sum-decomposable. Additionally, we prove that$N=M$ is a sufficient condition – implying together with the above that it is not possible to do better than this.

The Importance of Continuity

In this section, we argue that continuity is essential to discussions of function representation, that it has been neglected in prior work on permutation-invariant functions, and that this neglect has implications for the strength and generality of existing results.

Intuitively speaking a function is continuous if, at every point in the domain, the variation of the output can be made arbitrarily small by limiting the variation in the input. Continuity is the reason that, for instance, working to machine precision usually produces sensible results. Truncating to machine precision alters the input to a function slightly, but continuity ensures that the change in output is also slight.

It is not possible to represent an everywhere-discontinuous $\phi$ with a neural network. We therefore view Theorem 2.8 as being of limited practical relevance and as not providing a reliable intuition for what should be possible in the uncountable case. We do however see this result as mathematically interesting, and have obtained the following result extending it to the case where the domain $\mathfrak{X}$ is uncountable. This result is slightly weaker than the countable case, in that the domain of $f$ can contain arbitrarily large finite sets, but not infinite sets.

Once again, the sum-decomposition is highly discontinuous. The limitation that $f$ is not defined on infinite sets cannot be overcome:

To summarise, we show why considering countable domains can lead to results of limited practical value and why considering continuity on uncountable domains is necessary. We point out that some of the previous work is therefore of limited practical relevance, but regard it as mathematically interesting. In this vein, we extend the analysis of sum-decomposability when continuity is not required.

Practical Function Representation

A latent dimensionality of $M$ is sufficient for representing all continuous permutation-invariant functions on sets of size $\leq M$.

The key result which is the basis of the second statement and which underpins this discussion is as follows.

Restated in more practical terms, this implies that for a sum-decomposition-based model to be capable of representing arbitrary continuous functions on sets of size $M$, the latent space in which the summation happens must be chosen to have dimension at least $M$. A similar statement is true for the analogous concept of max-decomposition – details are available in Section B.6.

To prove this theorem, we first need to state and prove the following lemma.

Now let $\Phi(X)=\Sigma_{x\in X}\phi(x)$, and write $\Phi_{M}$ for the restriction of $\Phi$ to sets of size $M$.

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

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

where $x_{\text{max}}=\text{max}(X)$, and similarly for $y_{\text{max}}$.

From the central equality, and (3), we have:

Now by injectivity of $\Phi_{M-1}$, we have $X_{\text{rem}}=Y_{\text{rem}}$. Combining this with (3) and (4), we must have $X=Y$, and so $\Phi_{M}$ is injective. ∎

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

It is crucial to note that functions $f$ for which a lower-dimensional sum-decomposition does not exist need not be “badly-behaved” or difficult to specify. The limitation extends to functions of genuine interest. For our proof, we have specifically demonstrated that even $\text{\tt{max}}(X)$ is not continuously sum-decomposable when $N<M$.

Secondly, we can deal with variable set sizes $\leq M$:

Note that we must take some care over the notion of continuity in this theorem – see Section A.2.

Section 4 does not imply all functions require $N=M$. Some functions, such as the mean, can be represented in a lower dimensional space. The statement rather says that if we do not want to impose any limitations on the complexity of the function, the latent space needs to have dimensionality at least $M$.

Lemma 4.1 suggests that sum-decomposition via a latent space with dimension $N=M$ should suffice to model any function. Neural network models in the recent literature, however, deviate from these guidelines in several ways, indicating a disconnect between theory and practice. For example, the models in Zaheer et al. (2017) and Qi et al. (2017a) are considerably more complex than Equation 1, e.g. they apply several permutation-equivariant layers to the input before a permutation-invariant layer.

In light of Section 4, this disconnect becomes less surprising. We have shown that, for a target function of sufficient complexity, $N=M$ is the bare minimum required for the model to be capable of representing the target function. Achieving this would rely on the parameterisation of $\phi$ and $\rho$ being flexible enough and on the availability of a suitable optimisation method. In practice, we should not be surprised that more than the bare minimum capacity in our model is required for good performance. Even with $N>M$, the model might not converge to the desired solution. At the same time, when we are dealing with real datasets, the training data may contain noise and redundant information, e.g. in the form of correlations between elements in the input, inducing functions of limited complexity that may in fact be representable with $N<M$.

2 Illustrative Example

We now use a toy example to illustrate some practical implications of our results. Based on Section 4, we expect the number of input elements $M$ to have an influence on the required latent dimension $N$, and in particular, we expect that the required latent dimension may increase without bound.

We vary the latent dimension $N$ and the input set size $M$ to investigate the link between these two variables and the predictive performance. The MLPs parameterising $\phi$ and $\rho$ are given comparatively many layers and hidden units, relative to the simplicity of the task, to ensure that the latent dimension is the bottleneck. Further details are described in Appendix D.

Figure 3(a) shows the RMSE depending on the latent dimension for different input sizes. We make three observations.

For each set size, the error decreases monotonically with the dimension of the latent space.

Beyond a certain point, increasing the dimension of the latent space does not further reduce the error. We denote this the “critical point”.

As the set size increases, so does the latent dimension at the critical point.

Figure 3(b) shows the critical points as a function of the input size, indicating a roughly linear relationship between the two. Note that the critical points occur at $N<M$. This can be explained by the fact that the models do not learn an algorithmic solution for computing the median, but rather to estimate it given samples drawn from the specific input distribution seen during training. Furthermore, estimating the median of a distribution, like other functions, renders some information in the input redundant. Therefore, the mapping from input to latent space does not need to be injective, allowing a model to solve the task with a smaller value of $N$.

Related Work

Much of the recent work on deep learning with unordered sets follows the paradigm discussed in (Ravanbakhsh et al., 2016), Zaheer et al. (2017), and Qi et al. (2017a) which leverage the structure illustrated in Figure 1. Zaheer et al. (2017) provide an in-depth theoretical analysis which is discussed in detail in Section 2. Qi et al. (2017a) also derive a sufficiency condition for universal function approximation. In their proof, however, they set the latent dimension $N$ to $\left\lceil 1/\delta_{\epsilon}\right\rceil$ where $\delta_{\epsilon}$ depends on the error tolerance for how closely the target function has to be approximated. As a result, the latent dimension $N$ goes to infinity for exact representation. In similar vain, Herzig et al. (2018) consider permutation-invariant functions on graphs.

A key application domain of set-based methods is the processing of point clouds, as the constituent points do not have an intrinsic ordering. The work by Qi et al. (2017a) on 3D point clouds, one of the first to use a permutation-invariant neural networks, is extended in Qi et al. (2017b) by sampling and grouping points in a hierarchical fashion to model the interaction between nearby points in the input space more explicitly. Qi et al. (2018) combine RGB and lidar data for object detection by using image detectors to generate bounding box proposals which are then further processed by a set-based model. Achlioptas et al. (2018) and Yi et al. (2018) show that set-based models can also be used to learn generative models of point clouds.

Vinyals et al. (2015) suggest that even though recurrent networks are universal approximators, the ordering of the input is crucial for good performance. Hence, they propose model that relies on attention to achieve permutation invariance in order to solve a sorting task. In general, it is worth noting that there exists a connection between the model in Zaheer et al. (2017) and recent attention-based models such as the one proposed in Vaswani et al. (2017). In this case, the aggregation layer includes a weighting parameter which is computed based on a key-query system which is also permutation invariant. Since the value of the weighting parameters could be learned to be $1.0$, it is trivial to show that such an attention algorithm is also in principle able to approximate any permutation-invariant function, of course depending on the remaining parts of the architecture. Inspired by inducing point methods, Set Transformer (Lee et al., 2018) propose a computationally more efficient attention-module and demonstrate better performance on a range of set-based tasks. While stacking several of attention-modules can capture higher order dependencies, a more general treatment of this is offered by permutation-invariant, learnable Janossy Pooling (Murphy et al., 2018).

Similar to the methods considered here, Neural Processes (Garnelo et al., 2018b) and Conditional Neural Processes (Garnelo et al., 2018a) also rely on aggregation via summation in order to infer a distribution from a set of data points. Kim et al. (2019) add an attention mechanism to neural processes to improve empirical performance. Generative Query Networks (Eslami et al., 2018; Kumar et al., 2018) can be regarded as an instantiation of neural processes to learn useful representations of 3D scenes from multiple 2D views. Yang et al. (2018) also aggregate information from multiple views to compute representations of 3D objects.

Bloem-Reddy & Teh (2019) and Korshunova et al. (2018) consider exchangeable sequences – sequences consisting of random variables with a joint likelihood which is invariant under permutations. Bloem-Reddy & Teh (2019) provide a theorem that describes distribution-invariant models. Korshunova et al. (2018) use RealNVP (Dinh et al., 2016) as a bijective function which sequentially computes the parameters of a Student-t process.

Conclusions

This work derives theoretical limitations on the representation of arbitrary functions on sets via a finite latent space. We demonstrate why continuity requires statements on uncountable domains, as opposed to countable domains, to ensure the practical usefulness of those statements. Under this constraint, we prove that a latent space whose dimension is at least as large as the maximum input set size is both sufficient and necessary to achieve universal function representation. The models covered in this analysis are popular for a range of practical applications and can be implemented e.g. by neural networks or Gaussian processes. In future work, we would like to investigate the effect of constructing models with both permutation-equivariant and permutation-invariant modules on the required dimension of the latent space. Examining the implications of using self-attention, e.g. as in Lee et al. (2018), would be of similar interest.

Acknowledgements

This research was funded by the EPSRC AIMS Centre for Doctoral Training at the University of Oxford, an EPSRC DTA studentship, a Google studentship, and an EPSRC Programme Grant (EP/M019918/1). The authors acknowledge use of Hartree Centre resources in this work. The STFC Hartree Centre is a research collaboratory in association with IBM providing High Performance Computing platforms funded by the UK’s investment in e-Infrastructure. The authors thank Sudhanshu Kasewa and Olga Isupova for proof reading a draft of the paper.

References

Appendix A Mathematical Remarks

Throughout this paper we consider expressions of the following form:

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.

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 our expression (5). 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 (5) 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. So for (5) to make sense, we will 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

A.3 Remark on Theorem 2.8

which takes a unique value for each distinct $X$ therefore extending the validity of the proof to multi-sets. However, unlike the original series, 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:

Appendix B Proofs of Theorems

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

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

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$.

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$.

B.2 Figure 2

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.

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:

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:

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 (8), $B_{\text{max}}$ is not f.s.d., which is a contradiction. So we have that $C_{\text{ub}}$ is f.s.d.

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

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

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

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

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

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

B.3 Figure 2

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 Figure 2, $\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{X}$.

B.4 Lemma 4.1

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:

B.5 Lemma 4.1

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

which is shown above to be injective. Without loss of generality, let $\mathfrak{X}=$ as in Theorem 2.9.

We separate $\Phi_{q}(X)$ into two terms:

For an input set $X$ with $M^{\prime}=M-P$ elements and $0\leq M^{\prime},P\leq M$, we say that the set contains $M^{\prime}$ “actual elements” as well as $P$ “empty” elements which are not in fact 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. $M^{\prime}<M$.

We map those $P$ elements to a constant value $k\notin\mathfrak{X}$, preserving the injectiveness of $\Phi_{q}(X)$ for input sets $X$ of arbitrary size $M^{\prime}$:

Equation 10 is no longer strictly speaking a sum-decomposition. This can be overcome by re-arranging it:

The last term in Equation 11 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:

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

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

We can choose $\widehat{f}$ to be continuous under the notion of continuity in Section A.2. 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:

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 4, but which establishes limitations on max-decomposition, rather than sum-decomposition.

Note that this theorem rules out any max-decomposition, whether continuous or discontinuous. We specifically demonstrate that summation is not max-decomposable – as with Section 4, this theorem applies to ordinary well-behaved functions.

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

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:

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.

Define a sequence of functions $\widetilde{\Psi}_{n}$ on $$.

Show that the pointwise limit $\widetilde{\Psi}$ is continuous except at points of the form $k\cdot 2^{-m}$ for some integers $k$ and $m$, i.e. except at the dyadic rationals.

Define the function $\Psi$ on $[0,A]$ by $\Psi(x)=\widetilde{\Psi}(\frac{x}{A})$.

Note that $\Psi$ is continuous except at points of the form $A\cdot k\cdot 2^{-m}$ for some integers $k$ and $m$.

Informally, we set $\widetilde{\Psi_{0}}(x)=x$, and at iteration $n$, we split the unit interval into $2^{n}$ even subintervals. In every even-numbered subinterval, we reflect the function horizontally around the midpoint of the subinterval. We may write this formally as follows.

That is, $a_{n}(x)$ is the midpoint of the unique half-open interval containing $x$:

Write $b_{n}(x)$ for the $n$-th digit in the binary expansion of $x$, and write $c_{n}(x)$ for the number of $b_{m}(x),m\leq n$ with $b_{m}(x)=1$.

Importantly, $b_{n}(x)$ is ambiguous if $x$ is a dyadic rational, since in this case $x$ has both a terminating and a non-terminating expansion. For consistency with our choice of the upward-closed interval for the definition of $a_{n}(x)$, we choose the non-terminating expansion in this case.

First, it is clear that the series for $\widetilde{\Psi}(x)$ converges absolutely at every $x$, since $|2(x-a_{i}(x))|\leq 2^{-i}$. So this function is well defined. Also note that:

Note further that $\widetilde{\Psi}_{n}$ is continuous except at points of the form $k\cdot 2^{-n}$, since $a_{m}$, $b_{m}$ and $c_{m}$ are continuous at these points for all $m\leq n$.

Now consider a point $x_{*}$ which is not a dyadic rational. We wish to show that $\widetilde{\Psi}$ is continuous at $x_{*}$. So let $\epsilon>0$. Choose $n$ so that $2^{-n}<\frac{\epsilon}{3}$. Since $x_{*}$ is not a dyadic rational, $\widetilde{\Psi}_{n}$ is continuous at $x_{*}$, i.e. there is some $\delta>0$ such that $|x_{*}-x|<\delta\implies|\widetilde{\Psi}_{n}(x_{*})-\widetilde{\Psi}_{n}(x)|<\frac{\epsilon}{3}$. But now, by Equation 15:

And so, whenever $|x_{*}-x|<\delta$, we have:

Thus, $\widetilde{\Psi}$ is continuous at $x_{*}$.

As noted above, we may now set $\Psi(x)=\widetilde{\Psi}(\frac{x}{A})$ to obtain a function which is continuous at all rational points.

Appendix D Implementation Details for Illustrative Example

The network setup follows Equation 1 with 3 fully connected layers before the summation (acting on each input independently) and 2 fully connected layers after. Each fully connected layer has 1000 hidden units and is followed by a ReLU non-linearity. However, the third hidden layer, which creates the latent space in which the summation is executed, has a variable dimension $N$. $N$ is varied for each experiment in order to examine the influence of the latent dimension on the performance.

Training was conducted using the ADAM optimizer (Kingma & Ba, 2015) with an initial learning rate of $0.001$ and an exponential decay after each batch of $0.99$. Training was ended after convergence at 500 batches with a batch size of $32$. Samples were continuously drawn from the respective distributions. Therefore, there is no notion of training vs. test data or epoch sizes. The results $r^{t}$, measured as RMSE, were smoothed using exponential smoothing with $\alpha=0.95$:

The last, smoothed RMSE is extracted from each experiment, averaged over 500 different runs with different seeds and plotted in Figure 3(a). The confidence intervals are calculated assuming a Gaussian distribution. The critical points are extracted by taking the smallest latent dimension which produces an RMSE of less than $10\%$ above the global minimum for this set size.

Out of distribution samples: We tested the performance of a trained model (500 inputs, 100 latent dimensions) on out-of-distribution samples to see to what extent the model exploits the statistical properties of the training examples. Below is a list with examples:

Input: $[1.0,1.0,\dots,1.0]$, output: $0.933$, true label: $1.0$

Input: 200 times $1.0$ and 300 times $0.0$, output: $0.413$, true label: $0.0$

Input: $[0.002,0.004,0.006,...,1.0]$, output: $0.5006$, true label: $0.5000$

The distributions the samples were drawn from during test time were the uniform distribution, a Gaussian and a Gamma distribution. Each sample consisting of 500 values was randomly drawn from one of these distributions. Hence, the first two are very unlikely samples from the provided distributions. The poor performance of the model on these two examples can therefore be taken as an indication that the model does utilize information about the underlying distributions when estimating the median. The third sample is much closer to a realistic sample from, e.g., the uniform distribution (in our case between $0.0$ and $1.0$), which makes it unsurprising that the model performs much better on this task. It is worth noting that the notion of ’likely’ examples of uniform distributions is of course an intuitive one. Given that no value is repeated, every specific set of numbers is of course equally likely as long as all numbers lie within the interval of the uniform distribution.