Title: LIMITATIONS FOR LEARNING FROM POINT CLOUDS Anonymous

Abstract: In this paper we prove new universal approximation theorems for deep learning on point clouds that do not assume fixed cardinality. We do this by first generalizing the classical universal approximation theorem to general compact Hausdorff spaces and then applying this to the permutation-invariant architectures presented in PointNet (Qi et al) and Deep Sets (Zaheer et al). Moreover, though both architectures operate on the same domain, we show that the constant functions are the only functions they can mutually uniformly approximate. In particular, DeepSets architectures cannot uniformly approximate the diameter function but can uniformly approximate the center-of-mass function but it is the other way around for PointNet. Additionally, even when the point clouds are limited to at most k points, PointNet cannot uniformly approximate center-of-mass and we obtain explicit error bounds and a method to produce geometrically derived adversarial examples.

1. INTRODUCTION:

Recently, architectures proposed in PointNet (Qi et al., 2017) and Deep Sets (Zaheer et al., 2017) have allowed for the direct processing of point clouds within a deep learning framework. These methods produce outputs that are permutation-invariant with respect to the member points and work for point clouds of arbitrarily large cardinality. A common source of such data is LIDAR measurements from autonomous vehicles. Zaheer et al. (2017) also presents a permutation-equivariant architecture which we do not discuss here.

Each of of these works provide their own universal approximation theorem (UAT) to support the empirical success of their architectures. However, both results assume the cardinality of the point cloud is fixed to some size n. In this work we refine these results, remove the cardinality limitation, use weaker architecture assumptions, and arrive at three main results which can be summarized roughly as follows (assuming unrestricted finite cardinality for the input point clouds):

1) PointNet (DeepSets) architectures can uniformly approximate real-valued functions that are uniformly continuous with respect to the Hausdorff (Wasserstein) metric and nothing else (Theorem 3.4).

2) Only the constant functions can be uniformly approximated by both architectures. In particular, PointNet architectures can uniformly approximate the diameter function but DeepSets architectures cannot. Conversely, DeepSets architectures can uniformly approximate the center-of-mass function but PointNet architectures cannot (Theorem 4.1).

3) We prove explicit error lower bounds and produce adversarial examples to show that even when limited to point clouds of size k, PointNet cannot uniformly approximate center-ofmass (Theorem 4.2).

To do this we extend the many universal approximation results for feed-forward networks (Cybenko, 1989; Hornik et al., 1989; Leshno et al., 1993; Stinchcombe, 1999) to the abstract setting of general compact Hausdorff spaces. We then find appropriate compact metric spaces over which PointNet and DeepSets architectures can be easily analyzed and then finally we observe the resulting consequences in the original setting of interest, i.e. point clouds.

2. PRELIMINARIES 2.1 POINTNET AND DEEPSETS ARCHITECTURES:

In practice, the implementations of the architectures presented in PointNet and Deep Sets can involve many additional tricks, but the essential ideas are quite simple. We do however make a small modification to the Deep Sets model. For A ⊆ R n of cardinality |A| < ∞, we have Qi et al. (2017) and Zaheer et al. (2017) suggesting scalar-output neural networks of the form

F P N (A) = ρ max a∈A ϕ(a) , and F DS (A) = ρ b + 1 |A| a∈A ϕ(a) ,

respectively. Here ϕ : R n → R m creates features for each point in A, then a symmetric operation is applied, and then ρ : R m → R combines these features into a scalar output (here max is the component-wise maximum). In practice, we need both ρ and ϕ to be neural networks. Note that because we use a symmetric operation before ρ, the output will not depend on the ordering of points in the point cloud, and because the max and sum operations scale to arbitrary finite cardinalities the size of the point cloud is not an issue. The original model in Deep Sets did not have a bias term b and used a sum instead of the averaging we use here. This change will help us later in our theoretical analysis.

It will help to introduce some simplifying notation. Let F(Ω) denote the set of all nonempty finite subsets of a set Ω (i.e. point clouds in Ω), F ≤k (Ω) the set of nonepmty subsets of size ≤ k, and

F k (Ω) the set of k-point subsets. Now consider Ω ⊆ R N and define max f , ave f,b : F(Ω) → R which are given by max f (A) = max a∈A f (a) and ave f,b (A) = b + 1 |A| a∈A f (a)

respectively. We make sense of this in the natural way if we use vector-valued f and b by operating componentwise. We call these operations max neurons and biased-averaging neurons respectively.

Once again letting ρ and ϕ be neural networks, F P N = ρ • max ϕ and F DS = ρ • ave ϕ,b will be the general form of what we call the PointNet and DeepSets architectures (resp.) in this paper. Some natural questions are 1) is there a topology for F(Ω) that makes these architectures continuous, 2) how expressive are these approaches, and 3) how deep is deep enough for function approximation?

2.2. FUNCTION SPACES AND UNIFORM APPROXIMATION:

From now on, we only consider R-valued functions unless otherwise stated. Let B(A) be the set of bounded functions on a set A, let C(X) and C b (X) be the set of continuous and bounded continuous functions on a topological space X (respectively), and let U(M ) and U b (M ) be the uniformly continuous and bounded uniformly continuous functions on a metric space (M, d) (respectively). We equip all of these with the uniform norm i.e. |||f ||| A = sup a∈A |f (a)| -we reserve * for the Euclidean norm. This makes them all normed spaces, with B(A), C b (X) and U b (M ) additionally being Banach spaces. Moreover, if X is compact and (M, d) has compact metric completion, then C(X) = C b (X) and U(M ) = U b (M ) and hence are also Banach spaces. For background see Rudin (2006) .

If given an injective map i : A → X, then we say that ϕ : A → R (uniquely) continuously extends to X if there is a (unique) ϕ ∈ C(X) such that ϕ • i = ϕ. We say a family of funcntions N on A (uniquely) continuously extends to X if every ϕ ∈ N (uniquely) continuously extends to X.

We will make use of the following lemma which is proved in the appendix. Letting D = F(Ω), this lemma suggest the following plan of attack: find a compact metric space (X, d) in which we can realize F(Ω) as a dense subset and hope that our class of neural networks N continuously extends to a dense subset of C(X). If we can do that, then we know the uniform closure of our class of neural networks are precisely the uniformly continuous functions on F(Ω) with respect to the metric inherited from X. This motivates the next subsection.

2.3. METRICS ON THE SPACE OF POINT CLOUDS:

From now on we will assume (Ω, d) is a compact metric space and when Ω ⊆ R n it will be compact and equipped with the Euclidean metric. Let K(Ω) denote the set of all compact subsets of Ω and P(Ω) denote the set of all Borel probability measures on Ω. The Hausdorff metric d H (Munkres, 2000) is a natural metric for K(Ω) and 1-Wasserstein metric d W (Villani, 2009) (also called the Earth-mover distance) is a natural metric for P(Ω). With these metrics, K(Ω) and P(Ω) become compact metric spaces of their own. From now on we will assume these two spaces are always equipped with the aforementioned metrics.

We also briefly mention M (Ω) the Banach space of finite signed regular Borel measures on Ω. By the Riesz-Markov theorem it is the topological dual space of C(Ω). Of interest to us is that P(Ω) ⊆ M (Ω) and that the weak-* topology on P(Ω) coincides with the topology induced by d W . This means that d

W (µ n , µ) → 0 iff f dµ n → f dµ for all f ∈ C(Ω).

Next, note that F(Ω) ⊆ K(Ω) and let i K denote the natural inclusion map. We can also define an injective map i P : F(Ω) → P(Ω) by mapping A ∈ F(Ω) to its associated empirical measure i

P (A) = µ A = 1 |A| a∈A δ a ∈ P(Ω)

where δ a is the Dirac delta measure supported at a. The injective maps i K and i P allow us to induce the d H and d W metrics on F(Ω). We will denote the metrized versions by F H (Ω) and F W (Ω) respectively and use the same convention for F k H (Ω) and F k W (Ω). Another important fact to know is that i K and i P embed F(Ω) as dense subset of K(Ω) and P(Ω). The former follows from compactness of the members of K(Ω) and to see why the latter is true see Fournier & Guillin (2015) ; Villani (2009) For

f ∈ C(Ω) and b ∈ R, define Max f : K(Ω) → R and Ave f,b : P(Ω) → R as the functions Max f (K) = max x∈K f (x) and Ave f,b (µ) = b + Ω f dµ. Lemma 2.2. Let (Ω, d) be compact, f ∈ C(Ω), and b ∈ R. Then Max f ∈ C(K(Ω)) and Ave f,b ∈ C(P(Ω)) and Max f •i K = max f and Ave f,b •i P = ave f,b .

As a consequence, PointNet and DeepSets are uniformly continuous on F H (Ω) and F W (Ω) respectively. This lemma (proved in the appendix) tells us that the max neurons and biased-averaging neurons continuously extend to K(Ω) and P(Ω) and hence so do PointNet and DeepSets architectures (since we merely compose with the continuous ρ after). Thus, we wil be able analyze such architectures as continuous functions on compact metric spaces, which is mathematically a much nicer problem than studying them as set-theoretic functions on an un-metrized F(Ω).

2.4. GENERALIZED NEURAL NETWORK NOTATION:

For A a collection of functions from X to Y and B a collection of functions from Y to Z, we denote the set of all compositions by 

B • A = {f • g | f ∈ B, g ∈ A}. In the case of a single function σ : Y → Z we let σ • A = {σ • f | f ∈ A}

M σ P N = span {Max f | f ∈ N σ } , M σ;τ P N = span {τ • N σ P N } , M σ DS = span {Ave f,b | f ∈ N σ , b ∈ R} , M σ;τ DS = span {τ • M σ DS } .

As before, the linear structure of

N σ makes M σ DS = {Ave f,b | f ∈ N σ }

3. MAIN RESULTS:

3.1 TOPOLOGICAL UAT Leshno et al. (1993) prove that N σ with σ ∈ C(R) has universal approximation property iff σ is not a polynomial. For this reason, we will say a σ ∈ C(R) is 'universal' if it is non-polynomial and denote the set of all such such functions by U(R). Using this theorem and Stone-Weierstrass we prove a UAT for certain kinds of two-hidden-layer 'neural networks' on an abstract compact Hausdorff space.

Recall that a family of functions S on Ω separates points if for any x = y there is an f ∈ S so that f (x) = f (y).

Theorem 3.1 (Topological-UAT). Let X be a compact Hausdorff space and σ ∈ U(R). If S ⊆ C(X) separates points and contains a nonzero constant, then span(σ

• span S) is dense in C(X).

Additionally, if S also happens to be a linear subspace, then span(σ

• S) is dense in C(X).

Proof. Let S and σ satisfy the above and let V = span S. Let Alg(V ) denote the algebra generated by V , i.e. all possible finite products, sums and scalar multiples of the elements of V . Then Alg(V ) is unital subalgebra of C(X) that seperates points. By the Stone-Weierstrass theorem Alg(V ) is dense in C(X). Now let F ∈ C(X) and > 0 be arbitrary. By density there is a G ∈ Alg(V ) such that |F (a) -G(a)| < /2 for all a ∈ X. Since G ∈ Alg(V ) there is an N -variable polynomial p and s = (s 1 , . . . , s N ) where s i ∈ S, so that G = p • s. Since all s i ∈ C(X) and X is compact, the image s(X) ⊆ R N is compact. By the classical UAT (Leshno et al., 1993) , there exists an η ∈ N σ such that |p(x) -η(x)| < /2 for all x ∈ R N . Thus, Lastly, if S is also linear subspace, then S = span S and so span(σ • S) is dense in C(X).

|F

3.2. POINT CLOUD UAT:

We have met almost all the conditions required to use the topological-UAT on K(Ω) and P(Ω). We just need to show that Max f and Ave f,b yield nonzero constants and can separate points even when we limit ourselves to f ∈ N σ . Lemma 3.2 (Separation Lemma). Let Ω ⊆ R N be compact and σ ∈ U(R). (Leshno et al., 1993 ) N σ is dense in C(Ω), so there is a g ∈ N σ so that |f (x) -g(x)| < 1/2 for all x ∈ Ω. Note Max g ∈ S P N and that Max g (A) > 1/2 and Max g (B) < 1/2. Since A and B were arbitrary, this shows S P N separates point in K(X).

Then S P N = {Max f | f ∈ N σ } and S DS = {Ave f,b | f ∈ N σ ,

(S DS separates points): Given µ 1 , µ 2 ∈ P(Ω) with µ 1 = µ 2 , by the Hahn-Banach separation theorem there exists a weak-* continuous linear functional L : M (Ω) → R that separates them. Let δ = |L(µ 1 ) -L(µ 2 )|. The topological dual of M (Ω) with the weak-* topology is equivalent to C(Ω) and so there is an f ∈ C(Ω) so that L(η) = f dη for all η ∈ M (Ω). Since N σ is dense in C(Ω) there is a g ∈ N σ so the that |f (x) -g(x)| < δ/2 for all x ∈ Ω. Define J(η) = g dη. Then for all η ∈ P(Ω) we have |L(η) -J(η)| ≤ |f -g| dη < δ 2 dη = δ/2. Applying the triangle inequality we obtain,

δ = |L(µ 1 ) -L(µ 2 )| ≤ |L(µ 1 ) -J(µ 1 )| <δ/2 + |J(µ 1 ) -J(µ 2 )| + |J(µ 2 ) -L(µ 2 )| <δ/2

Thus 0 < |J(µ 1 ) -J(µ 2 )| and so J = Ave g,0 ∈ S DS separates µ 1 and µ 2 . Since µ 1 and µ 2 were arbitrary, it follows that S DS seperates points in P(Ω).

The following theorems show that one hidden layer in the weight networks and one hidden layer of the of the other kind suffice to prove the universal approximation theorems for PointNet and DeepSets. Theorem 3.3. Let Ω ⊆ R N be compact and σ, τ ∈ U(R). Then M σ;τ P N and M σ;τ DS are dense in C(A) and C(B) respectively, where A ⊆ K(Ω) and B ⊆ P(Ω) are closed subsets.

Proof. Recall M σ;τ P N = span {τ • span S P N } and M σ;τ DS = span {τ • S DS }. Since K(Ω) and P(Ω) are compact metric spaces, A and B are compact Hausdorff. By Lemma 3.2 we know S P N and S DS separate points and contain nonzero constants and so the topological-UAT (Theorem 3.1) yields the desired result.

Theorem 3.4 (Point-Cloud-UAT). Let Ω ⊆ R N be compact. If σ, τ ∈ U(R), then the uniform closure of N σ;τ P N and N σ;τ DS within B(F(Ω)) is U(F H (Ω)) and U(F W (Ω)) respectively.

Proof. F H (Ω) and F W (Ω) are isometrically isomorphic to i K (F(Ω)) and i P (F(Ω)) which are in turn dense in (K(Ω), d H ) and (P(Ω), d W ). By Lemma 2.2 we have that N σ;τ P N and N σ;τ DS continuously extend to K(Ω) and P(Ω) as M σ;τ P N and M σ;τ DS . By Theorem 3.3 we know M σ;τ P N and M σ;τ DS are dense in C(K(Ω)) and C(P(Ω)). Finally, by Lemma 2.1 we have the desired result.

It's worth noting that we could have used Stinchcombe's generalization of the UAT to the case of neural networks on compact subsets of locally convex spaces (Stinchcombe, 1999) to prove that M σ;τ DS is dense in C(P(Ω)) but we chose the above route for consistency of technique and to be self-contained.

We now prove as a corollary a refinement of the universal approximation theorems of Qi et al. (2017) and Zaheer et al. (2017) , both of which applied to the the case of k-point point clouds. In this version of the theorem we are able to restrict the depth of the neural network to just two hidden layers. The proof is essentially the same as Theorem 3.4. Corollary 3.5. Let Ω ⊆ R N be compact. If σ, τ ∈ U(R), then the uniform closure of N σ;τ P N and

N σ;τ DS within B(F k (Ω)) are U(F k (Ω) H ) and U(F k (Ω) W ) respectively.

Proof. F k H (Ω) and F k W (Ω) are isometrically isomorphic to i K (F k (Ω)) and i P (F k (Ω)) which are in turn dense in their respective closures which we denote G H (Ω) ⊆ K(Ω) and G W (Ω) ⊆ P(Ω). Thus by Lemma 2.2 and Theorem 3.3 we have that M σ;τ P N and M σ;τ DS are dense in C(G H (Ω)) and C(G W (Ω)). Finally, by Lemma 2.1 we have the desired result.

4. LIMITATIONS OF POINTNETS AND DEEPSETS:

Note that unlike the classical universal approximation theorem we should not expect to be able uniformly approximate C(F H (Ω)) or C(F W (Ω)) since their elements might not even be bounded functions. For example, α

K (A) = d H (A, K) -1 is unbounded but continuous on F H (Ω) whenever K ∈ K(Ω) but K / ∈ F(Ω).

Subtler still, we do not even obtain all elements of C b (F H (Ω)) and C b (F W (Ω)). As an example of this, observe that β K = sin • α K is bounded and is also continuous on F H (Ω) because α K is.

We'll now compare the representation power of these two architectures. Let Ω ⊆ R N be compact. Proof. Assume f : F(Ω) → R is both d H -continuous and d W -continuous. Let A ∈ F(Ω) and let p ∈ A. For each n = 1, 2, . . . choose A n ∈ F(Ω) to be an n-point set contained within the 1/n-ball around p. We can do this because Ω is infinite without isolated points. Now let

A n = A n ∪(A\{p}). Observe that A n d H → A and A n d W → {p}. Thus, f (A) = f d H lim n→∞ A n = lim n→∞ f (A n ) = f d W lim n→∞ A n = f ({p})

Note that A was arbitrary so f must always give a set and any of its singleton subsets the same value. Now let B, C ∈ F(Ω) such that B = C. Without loss of generality assume q ∈ B \ C and q = r ∈ C. Thus by the above,

f (B) = f ({q}) = f ({q, r}) = f ({r}) = f (C)

thus f must be constant. Conversely, constant maps are always continuous.

Finally, it's known that the Diam satisfies |Diam(A) -Diam(B)| ≤ 2d H (A, B) and hence is d Hcontinuous on K(Ω) and Cent is d W -continuous on P(Ω) because Ave πi,0 is d W -continuous (here π i is the projection onto the i-th component map). This means they are uniformly continuous on F H (Ω) and F W (Ω) respectively and so the result follows from the above and Theorem 3.4.

While it is interesting to know that these neural networks describe fundamentally different kinds of functions when we allow for unbounded cloud cardinality, in practice there is always a bound due to computational resource limitations. The next result shows that even when we bound the cloud cardinality, PointNet still cannot uniformly approximate the center-of-mass function.

Theorem 4.2. Let Ω ⊆ R d be an infinite compact set with no isolated points. Then for every d H -continuous F :

F ≤k (Ω) → R d there exists A ∈ F k (Ω) such that F (A) -Cent(A) ≥ k -2 2k Diam(Ω).

In particular, since PointNet architectures are d H -continuous they cannot uniformly approximate center-of-mass when k ≥ 3 and suffer from the above uniform-norm error lower-bound.

It is possible to see that PointNet cannot uniformly approximate Cent by considering Figure 1a . Moving k -2 points in a k-element cloud to either of the remaining two points produce the same 2element cloud in a d H -continuous way. By d H -continuity, this means PointNet must output similar centers for the cloud in the top-right and bottom-right -this introduces error. To obtain the explicit error lower bound in Theorem 4.2, need a slightly more detailed result. Lemma 4.3. Let Ω ⊆ R d be infinite with no isolated points and F : F ≤k (Ω) → R d an arbitrary d H -continuous map. Then for every distinct p, q ∈ Ω and 0 < τ < 1 there exists an A ∈ F k (Ω) such that p, q ∈ A and

F (A) -Cent(A) > (1 -τ ) k -2 2k p -q

In particular, since PointNet architectures are d H -continuous they must satisfy this error bound.

Proof. Assume k ≥ 3 since the inequality is trivial for

k = 1, 2. Let C p := p+q k + ( k-2 k )p and C q := p+q k + ( k-2 k )q and observe that C p -C q = k-2 k p -q . Now let = τ C p -C q /4

and choose A p and A q to be k-point supersets of {p, q} such that A p \ {q} ⊆ B (p) and A q \ {p} ⊆ B (q). We can do this because p and q are not isolated points. Since F is d H -continuous and

A p , A q d H

→ {p, q} as → 0, we can additionally demand that F (A p ) -F ({p, q}) < and

F (A q ) -F ({p, q}) < . Next observe that Cent(A p ) = p + q k + (1/k) a∈A p \{p,q} a, Cent(A q ) = p + q k + (1/k) a∈A q \{p,q} a.

By the triangle inequality it follows that Cent(A p ) -C p < and Cent(A q ) -C q < . Now we can consider the triangle in R d formed by C p , C q , and F ({p, q}) and realize by basic geometry that one of F ({p, q}) -C p or F ({p, q}) -C q must greater than or equal to C p -C q /2 (see Figure 1b ). Without loss of generality, let F ({p, q}) -C q ≥ C p -C q /2. Then,

C p -C q 2 ≤ F ({p, q}) -F (A q ) < + F (A q ) -Cent(A q ) + Cent(A q ) -C q < Thus, F (A q ) -Cent(A q ) ≥ C p -C q 2 -2 = (1 -τ ) k -2 2k p -q .

Thus A q is the promised set which achieves the desired uniform-norm error.

Theorem 4.2 now follows easily.

proof of Theorem 4.2. Choose p, q ∈ Ω so p -q = Diam(Ω) and take τ → 0 in Lemma 4.3.

5. EXPERIMENTS:

The proof of Lemma 4.3 not only establishes the error bound but also suggest an algorithmic approach to finding point clouds that exhibit the failure of uniform approximation. This let's us produce adversarial examples to the centor-of-mass problem for PointNet. When Ω is additionally convexe.g. the unit disk D in R 2 -it becomes fairly easy to construct many examples of A p and A q explicitly for a given PointNet model, allowing us to empirically verify the uniform-norm error lower The hidden layers of ϕ and ρ are ReLU. Since it is not possible to train with respect to the uniform-norm, we opt for the traditional L 2 loss. In Figure 2a we can see the training curve settles after about 50 epochs. The loss at the 50th epoch however is 3-orders-of-magnitude greater than the predict worst case.

To form our adversarial examples, we pick a nonzero τ = 0.01 and two distinct points p, q ∈ D at random. We set = τ p -q /4. We then sample D another 8 times. We then linearly pull those 8 points towards p and towards q, sufficiently close so that the criteria in the proof of Lemma 4.3 are satisfied. This {p, q} adjoined with the 8 points pulled towards p and q form A p and A q . We are theoretically ensured one of these two will have error larger than our bound. In Figure 2b we plot the the produced adversarial error vs the distance between p and q that were used to make A p and A q . As predicted, all the adversarial errors lie above the line representing the uniform-norm error lower bound.

6. CONCLUSIONS AND FUTURE WORK:

The failure of the perceptron model to learn the XOR function was a blow that motivated the search for new models. When classical feed-forward neural networks began to be successful, the spectre of limited representation power loomed over the field until the universal approximation theorem Cybenko (1989 )Hornik et al. (1989 )Leshno et al. (1993) resolved the question. In this work we resolved the same question for the case of two current deep learning models for point clouds, and laid out a program that could work for other models as well. However, unlike the case of classical neural networks on compact domains of R N , the same question for point clouds has a less definitive answer even after having determined all of the uniformly approximable functions. Each method explored here has their strengths and limitations but the presence of useful functions out-of-reach of PointNet and DeepSets -even when considering bounded cardinality -opens the door for further research.

There are still many questions. Will merging PointNet and DeepSets in a way to obtain greater approximation power? Are there other useful topologies on F(Ω) for which new kinds of continuous neural networks can be constructed? How much do these limitations matter in practice? And finally, are there ways of developing architectures from the ground up with desirable yet different approximation capabilities on point clouds and what are they like?

A APPENDIX:

Proof of Lemma 2.1. First we show that the r is a linear isometry. Since X is compact for f ∈ C(X) there is a p ∈ X so that |f where the first subset results from continuity. Thus N = r(N ) = r(C(X)).

Finally, to show r(C(X)) = U(D) note that every uniformly continuous function g on D continuously extends to a function on X (because D is dense in X) placing this extension in C(X) and so g ∈ r(C(X)). The reverse inclusion follows as well because restriction preserves uniform continuity.

Proof of Lemma 2.2. First we show that Max f is d H -continuous. Let > 0. Since Ω is compact, f is uniformly continuous and so there is a δ > 0 so that |f (x) -f (y)| < /2 whenever d(x, y) < 2δ. Now let A, B ∈ K(Ω) and suppose d H (A, B) < δ. By definition this means A ⊆ B δ and B ⊆ A δ . By the triangle inequality we have

|Max f (A) -Max f (B)| ≤ |Max f (A) -Max f (A δ )| + |Max f (A δ ) -Max f (B)|

Since A δ is compact there is a p ∈ A δ so that Max f (A δ ) = f (p). Observe that if q ∈ K ⊆ A δ with d(p, q) < 2δ then |f (p) -f (q)| < /2 and f (p It's clear that Max f •i K = max f . The other identity follows from the linearity of integration.

) = Max f (A δ ) ≥ Max f (K) ≥ f (q).

Lastly, by composition of continuous functions it follows that PointNet and DeepSets continuously extend to K(Ω) and P(Ω). Since (Ω, d) compact implies both K(Ω) and P(Ω) are compact, we can deduce that PointNet and DeepSets are uniformly continuous on F H (Ω) and F W (Ω).

:



Figures and Tables:

Lemma 2.1. Let N ⊆ B(D) where D is a dense subset of a compact metric space (X, d). Suppose N has a continuous extension to X denoted by N ⊆ C(X) which is dense. Then the uniform closure of N in B(D) is r(C(X)) = U(D) where r : C(X) → C b (D) is the domain restriction map.

and similarly for right-composition. Next, let Aff denote the set of all affine functionals on R N , i.e. any function of the form f (x) = w•x+b. Let N σ := span {σ • Aff} denote the set of single hidden-layer neural networks with linear output-layer and activation function σ, and then denote an H-layered network by N σ where σ = (σ 1 , . . . , σ H ) is a list of H-many activation functions where N (σ,τ ) := N σ,τ := span(τ • N σ ). Next we define various classes of PointNet networks whose weight functions are themselves neural networks. Let N σ P N := N σ;∅ P N := span {max f | f ∈ N σ } then define N σ;τ P N := span {τ • N σ P N }. Like before, we can inductively define deeper networks, but we can also use deeper weight networks as well to create N σ;τ P N -thus we have two distinct notions of depth. Next, we do the same for DeepSets. Let N σ DS := N σ;∅ DS := span {ave f,b | f ∈ N σ , b ∈ R}. Note that ave f,b + ave g,c = ave f +g,b+c and α ave f,b = ave αf,αb . Thus since N σ is a linear space, taking the span has no effect and N σ DS = {ave f,b | f ∈ N σ , b ∈ R}. Going one layer deeper yields N σ;τ DS := span {τ • N σ DS } which gets us new functions. Like with PointNet, we can inductively develop deeper families in two ways. By Lemma 2.2 we can extend all the operations of our neural networks to K(Ω) and P(Ω) in a natural way. This let's us talk about about PointNet networks on K(Ω) and DeepSets networks on P(Ω) which we'll define analogously by replacing max f with Max f and ave f,b with Ave f,b . Thus

(a) -(η • s)(a)| ≤ |F (a) -p(s(a))| + |p(s(a)) -η(s(a))| < /2 + /2 = for every a ∈ X. Finally note that η(s(a)) = m i=1 a i σ(w i • s(a) + b i ) for some a i , b i ∈ R and w i ∈ R N . Since S constains a nonzero constant, span S contains every constant and so w i •s+b i ∈ span S. Thus η • s ∈ span(σ • span S) as desired.

b ∈ R} separate points and contain constants. Proof. Let d denote the Euclidean distance. First note that the constant function h = σ(c) ∈ N σ for some c ∈ R. Since σ is not a polynomial, there is a choice of c for which σ(c) = 0. This means Max h ∈ S P N and Ave h,0 ∈ S DS are both constant. Now we just need to show that S P N and S DS separate points. (S P N separates points): Let A, B ∈ K(Ω) with A = B. Without loss of generality, A \ B = ∅ so choose a ∈ A \ B. Let f (x) = min {1, d(x, B)/d(a, B)} and note that f (a) = 1, f (B) = {0} and f (Ω) = [0, 1]. By the classical UAT

(a) dH -continuous closed loop. (b) Illustration of Lemma 4.3.

Figure 1: In (a) we see a d H -continuous loop in F ≤4 H where 'x' marks the center-ofmass. Though the point cloud continuously changes from a 4-point set to a 2-point set, the center of mass discontinuously changes at the moment of convergence. In (b) we see the triangle formed by C p , C q and F ({p, q}) in Lemma 4.3 and how the ball of radius less than C p -C q /4 ensures the predicted error for |||F -Cent|||.

We define the point cloud diameter function Diam : F(Ω) → R and point cloud center-of-mass function Cent : F(Ω) → R N by Diam(A) = max x,y∈A d(x, y) and Cent(A) = 1 |A| x∈A x. Theorem 4.1. Let (Ω, d) be an infinite compact metric space with no isolated points. Then a function f : F(Ω) → R is continuous with respect to both d H and d W iff it is constant. As a corollary, Diam is uniformly approximable by PointNet networks but not DeepSets networks and Cent is uniformly approximable by DeepSets networks but not PointNet networks.

(a) Training curve of a PointNet model learning Cent. (b) Experimental test of error lower bound.

Figure 2: In (a) we see the training curve for the PointNet model learning the centerof-mass of random 10-element point clouds. In (b) we see that we are always able to find adversarial examples to this task producing errors at least as large as the theoretical gaurantee.

(p)| = |||f ||| X . By density of D there is a sequence p n ∈ D that limits to p. So |||f ||| X = |f (p)| = lim n→∞ |f (p n )| ≤ sup x∈D |f (x)| = |||r(f )||| D ≤ sup x∈X |f (x)| = |||f ||| X Next, since C(X) is complete, so is its isometric image r(C(X)) and because C b (X) is complete that means r(C(X)) is closed. Thus, r(C(X)) = r(N ) ⊆ r(N ) ⊆ r(C(X)) = r(C(X))

This implies |Maxf (A δ ) -Max f (K)| < /2.In particular, since p ∈ A δ there is an a ∈ A such that d(p, a) < δ, and since B is compact there is a b ∈ B closest to p and so,d(p, b) = d(p, B) ≤ d H (A δ , B) ≤ d H (A δ , A) + d H (A, B) < 2δ. Thus |Max f (A δ ) -Max f (A)| and |Max f (A δ ) -Max f (B)| are less than /2 and so |Max f (A) -Max f (B)| < as desired.To see why Ave f,b is d W -continuous recall that the topology of d W is the same as the weak-* topology for measures and so the map µ → f dµ is by definition continuous whenever f ∈ C(Ω). Ave f,b (i P (A)) = Ave f,b 1 n a∈A δ a = b + 1 n a∈A f dδ a = b + 1 n a∈A f (a) = ave f,b (A)

Peer review (iclr2020):
This work examines the fundamental properties of two popular architectures -- PointNet and DeepSets -- for processing point clouds (and other unordered sets). The authors provide a new universal approximation theorem on real-valued functions that doesn*t require the assumption of a fixed cardinality of the input set. They further provide examples of functions that can*t be mutually approximated by PointNets and DeepSets. - It is important in order to know the representational power and fundamental limitations of basic algorithmic building blocks. However, for the two base architectures that are examined in this work, UATs where already provided in the original manuscripts. The presentation in this paper does remove the assumption of a fixed cardinality, but since this seems to be a mild assumption, it is not clear what is gained by this (beyond mathematical elegance). The paper doesn*t give any hints here. - The paper shows two specific functions, where one can be approximated by PointNet but not by DeepSets and vice-versa. The authors again note that this might vanish when a fixed cardinality of the input point cloud is assumed. Again, it seems that this is a mild restriction and I*d like the authors to elaborate on the importance of removing this restriction. - The paper is clearly targeted at a specialist audience and invokes dense and advanced mathematical concepts. It might find a better audience at a venue that is more specialized in this type of work (e.g. applied mathematics or more theory-focused machine learning venues). Summary: UATs are important and interesting, however, they do exist for the architectures that are targeted in this paper. It is not clear what is gained by the main difference, i.e. removing the cardinality. I*d be grateful if the authors could comment on this. Disclaimer: While I believe to have a reasonable mathematical background, I*m not an expert in this field and my assessment is primarily based on the bottom line of these proofs. === Post rebuttal update === I*d like to thank the authors for their efforts and additional insights. The additional illustration improves the accessibility of the paper. However, the rebuttal does not alleviate my concerns about additional impact beyond the UATs in the original paper. I thus maintain my recommendation of weak reject