Year: 2019

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.

text: 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.

heading: 1 INTRODUCTION
text: 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.

heading: 2 PRELIMINARIES

heading: 2.1 POINTNET AND DEEPSETS ARCHITECTURES
text: 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 ⊆ Rn of cardinality |A| <∞, we have Qi et al. (2017) and Zaheer et al. (2017) suggesting scalar-output neural networks of the form
FPN (A) = ρ ( max a∈A ϕ(a) ) , and FDS(A) = ρ ( b+ 1 |A| ∑ a∈A ϕ(a) ) ,
respectively. Here ϕ : Rn → Rm creates features for each point in A, then a symmetric operation is applied, and then ρ : Rm → 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 Fk(Ω) the set of k-point subsets. Now consider Ω ⊆ RN and define maxf , avef,b : F(Ω) → R which are given by maxf (A) = maxa∈A f(a) and avef,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, FPN = ρ ◦ maxϕ and FDS = ρ ◦ 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 forF(Ω) that makes these architectures continuous, 2) how expressive are these approaches, and 3) how deep is deep enough for function approximation?

heading: 2.2 FUNCTION SPACES AND UNIFORM APPROXIMATION
text: 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 Cb(X) be the set of continuous and bounded continuous functions on a topological space X (respectively), and let U(M) and Ub(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 = supa∈A |f(a)| – we reserve ‖∗‖ for the Euclidean norm. This makes them all normed spaces, with B(A), Cb(X) and Ub(M) additionally being Banach spaces. Moreover, if X is compact and (M,d) has compact metric completion, then C(X) = Cb(X) and U(M) = Ub(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.
Lemma 2.1. LetN ⊆ 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 ofN in B(D) is r(C(X)) = U(D) where r : C(X)→ Cb(D) is the domain restriction map.
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.

heading: 2.3 METRICS ON THE SPACE OF POINT CLOUDS
text: From now on we will assume (Ω, d) is a compact metric space and when Ω ⊆ Rn 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 dH (Munkres, 2000) is a natural metric for K(Ω) and 1-Wasserstein metric dW (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 dW . This means that dW (µn, µ)→ 0 iff ∫ f dµn → ∫ f dµ for all f ∈ C(Ω).
Next, note that F(Ω) ⊆ K(Ω) and let iK denote the natural inclusion map. We can also define an injective map iP : F(Ω) → P(Ω) by mapping A ∈ F(Ω) to its associated empirical measure iP(A) = µA = 1 |A| ∑ a∈A δa ∈ P(Ω) where δa is the Dirac delta measure supported at a. The injective maps iK and iP allow us to induce the dH and dW metrics on F(Ω). We will denote the metrized versions by FH(Ω) and FW (Ω) respectively and use the same convention for FkH(Ω) and FkW (Ω). Another important fact to know is that iK and iP 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 Maxf : K(Ω) → R and Avef,b : P(Ω) → R as the functions Maxf (K) = maxx∈K f(x) and Avef,b(µ) = b+ ∫ Ω f dµ.
Lemma 2.2. Let (Ω, d) be compact, f ∈ C(Ω), and b ∈ R. Then Maxf ∈ C(K(Ω)) and Avef,b ∈ C(P(Ω)) and Maxf ◦iK = maxf and Avef,b ◦iP = avef,b. As a consequence, PointNet and DeepSets are uniformly continuous on FH(Ω) and FW (Ω) 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(Ω).

heading: 2.4 GENERALIZED NEURAL NETWORK NOTATION
text: ForA 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} and similarly for right-composition. Next, let Aff denote the set of all affine functionals on RN , i.e. any function of the form f(x) = w·x+b. LetN σ := 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 σPN := N σ;∅ PN := span {maxf | f ∈ N σ} then define N σ;τ PN := span {τ ◦ N σPN}. Like before, we can inductively define deeper networks, but we can also use deeper weight networks as well to create Nσ;τPN – thus we have two distinct notions of depth.
Next, we do the same for DeepSets. Let N σDS := N σ;∅ DS := span {avef,b | f ∈ N σ, b ∈ R}. Note that avef,b + aveg,c = avef+g,b+c and α avef,b = aveαf,αb. Thus since N σ is a linear space, taking the span has no effect and N σDS = {avef,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 maxf with Maxf and avef,b with Avef,b. Thus
MσPN = span {Maxf | f ∈ N σ} , M σ;τ PN = span {τ ◦ N σ PN} , MσDS = span {Avef,b | f ∈ N σ, b ∈ R} , M σ;τ DS = span {τ ◦M σ DS} .
As before, the linear structure of N σ makesMσDS = {Avef,b | f ∈ N σ}

heading: 3 MAIN RESULTS

heading: 3.1 TOPOLOGICAL UAT
text: 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 6= y there is an f ∈ S so that f(x) 6= 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(σ ◦ spanS) 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 = spanS. 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 = (s1, . . . , sN ) where si ∈ S, so that G = p ◦ s. Since all si ∈ C(X) and X is compact, the image s(X) ⊆ RN is compact. By the classical UAT (Leshno et al., 1993), there exists an η ∈ N σ such that |p(x)− η(x)| < /2 for all x ∈ RN . Thus,
|F (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 aiσ(wi · s(a) + bi) for some ai, bi ∈ R and wi ∈ RN . Since S constains a nonzero constant, spanS contains every constant and sowi ·s+bi ∈ spanS. Thus η ◦ s ∈ span(σ ◦ spanS) as desired. Lastly, if S is also linear subspace, then S = spanS and so span(σ ◦ S) is dense in C(X).

heading: 3.2 POINT CLOUD UAT
text: We have met almost all the conditions required to use the topological-UAT on K(Ω) and P(Ω). We just need to show that Maxf and Avef,b yield nonzero constants and can separate points even when we limit ourselves to f ∈ N σ . Lemma 3.2 (Separation Lemma). Let Ω ⊆ RN be compact and σ ∈ U(R). Then SPN = {Maxf | f ∈ N σ} and SDS = {Avef,b | f ∈ N σ, 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) 6= 0. This means Maxh ∈ SPN and Aveh,0 ∈ SDS are both constant. Now we just need to show that SPN and SDS separate points.
(SPN separates points): Let A,B ∈ K(Ω) with A 6= B. Without loss of generality, A \ B 6= ∅ 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 (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 Maxg ∈ SPN and that Maxg(A) > 1/2 and Maxg(B) < 1/2. Since A and B were arbitrary, this shows SPN separates point in K(X).
(SDS separates points): Given µ1, µ2 ∈ P(Ω) with µ1 6= µ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 = Aveg,0 ∈ SDS separates µ1 and µ2. Since µ1 and µ2 were arbitrary, it follows that SDS 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 Ω ⊆ RN be compact and σ, τ ∈ U(R). ThenMσ;τPN andM σ;τ DS are dense in C(A) and C(B) respectively, where A ⊆ K(Ω) and B ⊆ P(Ω) are closed subsets.
Proof. Recall Mσ;τPN = span {τ ◦ spanSPN} and M σ;τ DS = span {τ ◦ SDS}. Since K(Ω) and P(Ω) are compact metric spaces, A and B are compact Hausdorff. By Lemma 3.2 we know SPN and SDS 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 Ω ⊆ RN be compact. If σ, τ ∈ U(R), then the uniform closure of N σ;τPN and N σ;τ DS within B(F(Ω)) is U(FH(Ω)) and U(FW (Ω)) respectively.
Proof. FH(Ω) and FW (Ω) are isometrically isomorphic to iK(F(Ω)) and iP(F(Ω)) which are in turn dense in (K(Ω), dH) and (P(Ω), dW ). By Lemma 2.2 we have that N σ;τPN and N σ;τ DS continuously extend to K(Ω) and P(Ω) asMσ;τPN andM σ;τ DS . By Theorem 3.3 we knowM σ;τ PN andM σ;τ 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 Ω ⊆ RN be compact. If σ, τ ∈ U(R), then the uniform closure of N σ;τPN and N σ;τDS within B(Fk(Ω)) are U(Fk(Ω)H) and U(Fk(Ω)W ) respectively.
Proof. FkH(Ω) and FkW (Ω) are isometrically isomorphic to iK(Fk(Ω)) and iP(Fk(Ω)) which are in turn dense in their respective closures which we denote GH(Ω) ⊆ K(Ω) and GW (Ω) ⊆ P(Ω). Thus by Lemma 2.2 and Theorem 3.3 we have thatMσ;τPN andM σ;τ DS are dense in C(GH(Ω)) and C(GW (Ω)). Finally, by Lemma 2.1 we have the desired result.

heading: 4 LIMITATIONS OF POINTNETS AND DEEPSETS
text: Note that unlike the classical universal approximation theorem we should not expect to be able uniformly approximate C(FH(Ω)) or C(FW (Ω)) since their elements might not even be bounded functions. For example, αK(A) = dH(A,K)−1 is unbounded but continuous on FH(Ω) whenever K ∈ K(Ω) but K /∈ F(Ω). Subtler still, we do not even obtain all elements of Cb(FH(Ω)) and
Cb(FW (Ω)). As an example of this, observe that βK = sin ◦αK is bounded and is also continuous on FH(Ω) because αK is. We’ll now compare the representation power of these two architectures. Let Ω ⊆ RN be compact. We define the point cloud diameter function Diam : F(Ω) → R and point cloud center-of-mass function Cent : F(Ω)→ RN by Diam(A) = maxx,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 dH and dW 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.
Proof. Assume f : F(Ω) → R is both dH -continuous and dW -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 letAn = A′n∪(A\{p}).
Observe that An dH→ A and An dW→ {p}. Thus,
f(A) = f ( dH lim n→∞ An ) = lim n→∞ f(An) = f ( dW lim n→∞ An ) = 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 6= C. Without loss of generality assume q ∈ B \ C and q 6= 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)| ≤ 2dH(A,B) and hence is dH - continuous on K(Ω) and Cent is dW -continuous on P(Ω) because Aveπi,0 is dW -continuous (here πi is the projection onto the i-th component map). This means they are uniformly continuous on FH(Ω) and FW (Ω) 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 Ω ⊆ Rd be an infinite compact set with no isolated points. Then for every dH -continuous F : F≤k(Ω)→ Rd there exists A ∈ Fk(Ω) such that
‖F (A)− Cent(A)‖ ≥ k − 2 2k Diam(Ω).

heading: In particular, since PointNet architectures are dH -continuous they cannot uniformly approximate center-of-mass when k ≥ 3 and suffer from the above uniform-norm error lower-bound.
text: 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 2- element cloud in a dH -continuous way. By dH -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, we need a slightly more detailed result. Lemma 4.3. Let Ω ⊆ Rd be infinite with no isolated points and F : F≤k(Ω) → Rd an arbitrary dH -continuous map. Then for every distinct p, q ∈ Ω and 0 < τ < 1 there exists an A ∈ Fk(Ω) such that p, q ∈ A and
‖F (A)− Cent(A)‖ > (1− τ) ( k − 2
2k
) ‖p− q‖

heading: In particular, since PointNet architectures are dH -continuous they must satisfy this error bound.
text: Proof. Assume k ≥ 3 since the inequality is trivial for k = 1, 2. Let Cp := p+qk + ( k−2 k )p and Cq := p+q k + ( k−2 k )q and observe that ‖Cp − Cq‖ = k−2 k ‖p− q‖. Now let = τ ‖Cp − Cq‖ /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 dH -continuous and A p, A q dH→ {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)− Cp∥∥ < and ∥∥Cent(A q)− Cq∥∥ < . Now we can consider the triangle in Rd formed by Cp, Cq, and F ({p, q}) and realize by basic geometry that one of ‖F ({p, q})− Cp‖ or ‖F ({p, q})− Cq‖must greater than or equal to ‖Cp − Cq‖ /2 (see Figure 1b). Without loss of generality, let ‖F ({p, q})− Cq‖ ≥ ‖Cp − Cq‖ /2. Then,
‖Cp − Cq‖ 2 ≤ ∥∥F ({p, q})− F (A q)∥∥︸ ︷︷ ︸
<
+ ∥∥F (A q)− Cent(A q)∥∥+ ∥∥Cent(A q)− Cq∥∥︸ ︷︷ ︸
<
Thus, ∥∥F (A q)− Cent(A q)∥∥ ≥ ‖Cp − Cq‖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.

heading: 5 EXPERIMENTS
text: 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 convex – e.g. the unit disk D in R2 – 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
bound. In the following experiment, we train a simple PointNet architecture to learn the center-ofmass for 10-element point clouds in D. We train on a synthetic data set of 1 million point clouds (each element uniformly sampled fromD) labeled with their center-of-mass. The PointNet architecture has 500K trainable parameters. The network has the form F (A) = ρ(maxa∈Aϕ(a)) where ϕ has 2-D input layer, 500-D hidden layer, and 500-D linear output layer, and ρ has 500-D input layer, 500-D hidden layer and 2-D linear output layer (in accordance with the Point-Cloud-UAT). 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 L2 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.

heading: 6 CONCLUSIONS AND FUTURE WORK
text: 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 RN , 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?

heading: A APPENDIX
text: Proof of Lemma 2.1. First we show that the r is a linear isometry. SinceX is compact for f ∈ C(X) there is a p ∈ X so that |f(p)| = |||f |||X . By density of D there is a sequence pn ∈ D that limits to p. So
|||f |||X = |f(p)| = limn→∞ |f(pn)| ≤ supx∈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 Cb(X) is complete that means r(C(X)) is closed. Thus,
r(C(X)) = r(N ′) ⊆ r(N ′) ⊆ r(C(X)) = r(C(X))
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 Maxf is dH -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 dH(A,B) < δ. By definition this means A ⊆ Bδ and B ⊆ Aδ . By the triangle inequality we have
|Maxf (A)−Maxf (B)| ≤ |Maxf (A)−Maxf (Aδ)|+ |Maxf (Aδ)−Maxf (B)|
Since Aδ is compact there is a p ∈ Aδ so that Maxf (Aδ) = f(p). Observe that if q ∈ K ⊆ Aδ with d(p, q) < 2δ then |f(p)− f(q)| < /2 and f(p) = Maxf (Aδ) ≥ Maxf (K) ≥ f(q). This implies |Maxf (Aδ)−Maxf (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) ≤ dH(Aδ, B) ≤ dH(Aδ, A) + dH(A,B) < 2δ.
Thus |Maxf (Aδ)−Maxf (A)| and |Maxf (Aδ)−Maxf (B)| are less than /2 and so |Maxf (A)−Maxf (B)| < as desired. To see why Avef,b is dW -continuous recall that the topology of dW is the same as the weak-* topology for measures and so the map µ 7→ ∫ f dµ is by definition continuous whenever f ∈ C(Ω).
Avef,b(iP(A)) = Avef,b
( 1
n ∑ a∈A δa
) = b+ 1
n ∑ a∈A ∫ f dδa = b+ 1 n ∑ a∈A f(a) = avef,b(A)
It’s clear that Maxf ◦iK = maxf . The other identity follows from the linearity of integration. 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 FH(Ω) and FW (Ω).

Review summaries:
PointNet (Qi et al, 2017) and Deep sets (Zaheer et al, 2017) have allowed to use deep architectures that deal with point clouds as inputs, taking into account the invariance in the ordering of points. However, existing results on their approximation abilities are limited to fixed cardinalities. This paper removes the cardinality limitation and gives two kinds of results:

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.