Limitations for Learning from Point Clouds
Authors: Christian Bueno
Alan G. Hylton
Venue:  (2020)
Keywords: universal approximation
point clouds
deep learning
hausdorff metric
wasserstein metric

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. 

Under review as a conference paper at ICLR 2020
LIMITATIONS FOR LEARNING FROM POINT CLOUDS
Anonymous authors Paper under double-blind review
ABSTRACT
In this paper prove new universal approximation theorems for deep learning on point clouds that do not assume fixed cardinality. We do this by first general- izing the classical universal approximation theorem to general compact Hausdorff spaces and then applying this to the permuuaaiooninvariinn in PointNer (Qi et al) and Deep Sets (Zaheer al). Moreover, though both archi- tectures operate on the same domain, we show that the constant functions are the only functions they can mutually uniformly approximate. architectures cannot uniformly approximate the diameter function but can uni- formly approximate the center-of-man function but is the other way around for PointNet. A Additionally, even when the point clouds are limited to at most ls points, PointNet cannot uniformly approximate center-of-matt oa-mass and obtain explicit er- ror bounds and a method to produce geometrically derived adversarial examples.
architectures presented
particular, DeepSets
INTRODUCTION
Recently, architectures proposed in PointNer (Qi 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-invariint with respect the member points and work for point clouds of arbitrarily large cardinality. A common source of such data is LIDAR mea- surements from autonomous vehicles, Zaheer et al. (2017) also presents a permutation-equivariiee architecture which we do not discuss here.
Each of of these works provide their own universal approximation theorem (UAT) support the empirical success of their architectures. However, both results assume the cardinality of the point cloud 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.4p.
2) Only the constant functions can be uniformly approximated by both architectures. In partic- ular, 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 size k. PointNet cannot uniformly approximate center-of- mass (Theorem 4.2
To do this extend the many universal approximation results for feed-forward networks (Cybenko 1989 Horii 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 conse- quences in the original setting of interest, i.e. point clouds.

---

Under review as a conference paper at ICLR 2020
2 PRELIMINARIES
2.1 POINTNET AND DEEPSETS ARCHITECTURES
In practice, the implementations of the architectures presented in PointNet and Deep Sets can in- volve many additional tricks, but the essential ideas are quite simple. We do however make a small modification to the Deep Sets model. For A S II" of cardinality |A] < co, we have Qi et al. (2017) and Zaheer et al. 2017) suggesting scalar-output neural networks of the form
((()) and FDS(A)= = ( b+ aE
1 |A|
Σ v((a)) aEA
(AN(() =
max
respectively. Here s R Th creates features for each point in A, then symmetric operation is applied, and then R + R combines these features into a scalar output (here max is the component-wise maximum). In practice, we need both p and şo because we use 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 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.
neural networks. Note that
will help to introduce some simplifying notation. Let F(22) denote the set of all nonempty finite subsets of set Ω (i.e. point clouds in Q), FS) the set of nonepmty subsets of size < k, and (22) the set of k-point subsets. Now consider Q C RN and define max,, ave F()) + R which are given by max, (A) = maxaga (a) and (A) = b + ΣAΣ Σasa l(a respectively.
We make sense of this in the natural way if we use vector-valued f and b by operating component- wise. We call these operations max neurons and biased-averaging neurons respectively.
Once again letting P and be neural networks, FPN = o max and FDs p ave 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(22) 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 RR-val functions unless otherwise stated. Let B(A) be the set of bounded functions on set A, let C(X) and (x( be the set of continuous and bounded continu- ous functions on a topological space X (respectively), and let (MM and (.M be the uniformly continuous and bounded uniformly continuous functions
metric space (M,d) d) (respectively). We equip all of these with the uniform norm i.e. Ill = supa5. [f(a)] we reserve ||* for the Euclidean norm. This makes them all norned spaces, with B(A), (x() and (MM additionally being Banach spaces. Moreover, if X is compact and (M, d) has compact metric completion, then C(X)= = Cx(X) and (MM) = Uts (M) and hence are also Banach spaces. For background see Rudin 2006).
If given an injective map i : - X, then we say that yp : + R (uniquely) continuously extends to X if there is (unique) ē C(X) such that i = sp We say a family of funcntions. N on A (uniquely) continuously extends to if every o E (uniquely) continuously extends to X.
We will make use of the following lemma which is proved in the appendix.
Lemma 2.1. Let N C B(D) where D is 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(((X)) = ((D) where C(X) Cs(D) is the domain restriction map.
Letting D = F(R), this lemma suggest the following plan of attack: find compact metric space (X,d) in which we can realize F(2) as a dense subset and hope that our class neural networks N continuously extends to dense subset of C(X). If can do that, then we know the uniform closure of our class of neural networks are precisely the uniformly continuous functions on F(2) with respect to the metric inherited from X. This motivates the next subsection.
2

---

Under review as a conference paper at ICLR 2020
2.3 METRICS ON THE SPACE OF POINT CLOUDS
From now on we will assume (92, d) a compact metric space and when 9t R" it will be compact and equipped with the Euclidean metric. Let (( denote the set of all compact subsets of Ω and P(2)) denote the set of all Borel probability measures on f2. The Hausdorff metric dæ (Munkres 2000 is a natural metric for K([2) and I-Wasserstein metric dw (Villani 2009) (also called the Earth-mover distance) is a natural metric for P(22). With these metrics, (S2) and P(2)) 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 ( the Banach space of finite signed regular Borel measures Ω. By the Riesz-Markov theorem it is the topological dual space of C(?). Of interest to us is that P(2)) _ (St) and that the weak-* topology on ((52) coincides with the topology induced by dw- This means that dw (Jon, (1) - 0 iff f + f f du for all f E C(D).
Next, note that F(22 K((S)) and let in denote the natural inclusion map. We can also define an injective map ip F(22 - ((S)) by mapping A E F(22) to its associated empirical measure (A( Mad T Eoer 8. P(2t) where 8₂ is the Dirac delta measure supported at a. The injective maps ix and ip allow us to induce the dæ and dw metrics on F(L)). We will denote the metrized versions by (S2) and Fw(()) respectively and use the same convention for F (S2) and Fly FW-(S) (12). Another important fact to know is that ix and ip embed F(l2) dense subset of K(()) and P(Ω). The former follows from compactness of the members of (C(S2) and to see why the latter
true see see/Fourneer & Guillin 2015): Villani (2009)
For f E &C(2) and b E R. define Max, : XC(2) + R and Ave P(2) - R as the functions Max, (K) max K (xx and Avez,(u) = b- Ja du.
Lemma 2.2. Let (S2, d) be compact, f f C(S2), and b E R. Then Max, E C(K(S))) and Ave C(P(2)) and Maxy oig = max, and Ave cip = ave As consequence, PointNet and DeepSets uniformly continuous on F()) and Fw respectively.
This lemma (proved in the appendix) tells us that the max neurons and biased-averaging neurons continuously extend K(()) and P(2) and hence so do PointNet and DeepSets architectures (since we merely compose with the continuous p after), Thus, we wil be able analyze such architectures as continuous functions on compact metric spaces, which is mathematically much nicer problem than studying them as set-theoretic functions on an un-metrized F(?)..
2.4 GENERALIZED NEURAL NETWORK NOTATION
For 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 ffogl E B, E A). the case of a single function o: Y + Z we let o o A = fo o f E A} and similarly for cogpt-composition.
Next, let Aff denote the set of all affine functionals on R-V, i.e. any function of the form f(x) w.r-bb. b. Let == span (a e Aff) denote the set of single hidden-layer neural networks with linear output-layer and activation function a, and then denote an H-layered network by A where (o1....,0H) a list of H- --many activation functions where Alo,,) := Na. == span(T o No).
Next we define various classes of PointNet networks whose weight functions are themselves neural networks. Let Npx == & := span {max, If E EV" then define N := span {T o }. Like before, we can inductively define deeper networks, but we can also use deeper weight networks as well to create Np PN thus we have two distinct notions of depth.
Next, do the same for DeepSets. Let Net := N DS span fave I e A" N RJ. Note that ave + a = bv and a a = a Thus since N is a linear space, taking the span has effect and N fave f A/" E RR. Going one layer deeper yields NBS == span {r o/g 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 KC(2) and P(12) in a natural way. This let's us talk about about PointNet networks on K(()) and DeepSets networks on
3

---

Under review as a conference paper at ICLR 2020
P(2) which we'll define analogously by replacing max, with Maxy and f with A Thus
Myn span {Max, I E
MpN span fr NPN).. M span fr Mbs)
Ds span (Avers (EEN,EER))
As before, the linear structure of No makes Mas = (Aveςá 1S ESNN
MAIN RESULTS
3.1 TOPOLOGICAL UAT
Leshno et al. 1993 prove that Vo with C(IR) has universal approximation property iff o is not a polynomial. For this reason, we will say a a E C(R) "universal" if it is non-polynomial and denote the of all such such functions by (() Using this theorem and Moone-Weierstrars we prove a UAT for certain kinds of two-hidden-llayr 'neural networks' on an abstract compact Hausdorff space.
Recall that a family of functions S on Z separates points if for any # y there is an f E S so that f(x) + fly)
Theorem 3.1 (Topologica--UAT) Let X be compact Hausdorff space and E M(R.). S C C(X) separates points and contains a nonzero constant, then span( span S) is dense in C(X). Additionally, if S also happens be a linear subspace, then span(o o S) is dense in C(X).
Proof. Let S and a 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 E C(X) and > be arbitrary. By density there is G E Alg(V) such X. Since G Alg(V) there is N-variable polynomial p
that [F()) G(a)] < e/2 for all and 8 = (S...... SN) where 8; E S, so that G = po 8. Since all s, E C(X) and is compact, the image s s(X) C R is compact. By the classical UAT (Leshno et al. 1993), there exists 1j N such that (p(2 ()) - n)xx) < c/2 for all x E R. Thus,
(F(a) (n) o (a) - [(a)) p(s(a))) + (p(s(a)) - n(s(a)) < <c/2+
for every a E X. Finally note that r7ss(a)= = Ei= a:o(w, s(a) + b.) for some a; by E R and
w; E RRV. Since S constains a nonzero constant, span S contains every constant and so w. 8 + by E
span S. Thus 17 o E span(o span S) as desired.
Lastly, if S is also linear subspace, then S = span S and so span(o o S) is dense in C(X).
3.2 POINT CLOUD UAT
We have met almost all the conditions required to use the topological-UAT on K((?) and P(2). We just need to show that Max, and Ave,.6 yield nonzero constants and can separate points even when we limit ourselves to f E N
Lemma 3.2 (Separation Lemma). Ler Ω C I be compact and a E M(().. Then Spn (Max, If E A² and Sns {Ave,, If E be R} separate points and contain constants.
Proof. Let d denote the Euclidean distance. First note that the constant function h = (cc) E a for some E Since a is not polynomial, there choice for which a(e) * 0. This means Max, SpN and Ave E Sps are both constant. Now we just need to show that Spx and Sps separate points.
(SPN separates points): Let A, E IC(2.) with A of B. Without loss of generality, A B BB s choose a E A \ B. Let f(x) = min (1, d(x, B) B)} and note that f(a) = 1, f(B) = {0) and f(2) [0. 1]. By the classical UAT (Leshno et al. 1993) N is dense in C()), so there is g E n so that [f(x) g(x) < 1/2 for all x E Q. Note Max, E Spx and that Max, (A) > 1/2
and (B) < 1/2. Since A and B were arbitrary, this shows Spy separates point in K(X).
4

---

Under review as a conference paper at ICLR 2020
(Sps separates points): Given μl, M2
separation theorem there exists a weak-* * continuous linear functional L M - R that separates them. Let 6 = ( [( The topologiaal dual of ( with the weak- topology is equivalent to C(S2) and so there is an f E C(2) so that T(n) = f f dr for all r E ((2). Since No is dense in C(2)) there is a E N so the that (f(x) g(x)) < 6/2 for all x E Qt Define J(7) = f g dr,. Then
P( with μl # M2. by the
for all !/ E P(22 we have [L(n) - J(n) - f [ - gl dn < $ dn = 6/2. Applying the triangle inequality we obtain,
8 (L(m)) L(u2)1 s [(ni) (mm) + (m() ((2)] + (((2)) L(Ma)
<6/2
<6/2
Thus < -
- J(2z) and so J = Aveg.0 Sps separates fa and Jzz. Since μr and P2 were arbitrary, it follows that Sps seperates points in P(ft).
L
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 S RN be compact and o, T M(R).. Then MpN and M' are dense in C(A) and (BB respectively, where A S ((()) and B - P(()) are closed subsets.
Proof. Recall M span {r span }PN} and DS span {r Sps). Since K((?) and P(I)) are compact metric spaces, A and B are compact Hausdorff. By Lemma 3.2 we know Spn and Sps 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 Z closure of NPx
R be compact. If E S((R), then the uniform PN and NDS within ((F())) is (FF und respectively.
Proof. Fn and Fw (12) are isometrically isomorphic ix (F())) and ip (F(I)) which are in turn dense in (XC(2), d and (P(S2), d. By Lemma 2.2 we have that Ny and N M continu- ously extend to KC(S)) and ((2)) as PN and M By Theorem 3.3 we know MpN and p
M
are dense in ((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 Mps dense in C(P())) but we chose the above route for consistency of technique and to be self-contained.
We now prove corollary a refinement of the universal approximation theorems of et (2017) and Zaheer et al. (207)) 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 Ω C N be compact. af E I(R),, then the uniform closure of New and NBS within ( (2)) are ((F*(())))) and ((F(((())) respectively.
Proof. (12) and (S)) are isometrically isomorphic to ix ixc (1)) and ip (f(F(())) which are in turn dense in their respective closures which we denote (n()) C KC(()) and (I)) C P(2). Thus by Lemma 2.2 and Theorem 3.3 we have that M and Mas are dense in ((Gn(()) and C(Gw(S)) Finally, by Lemma 2.1 we have the desired result.
LIMITATIONS OF POINTNETS AND DEEPSETS
Note that unlike the classical universal approximation theorem we should not expect to be able uniformly approximate C(F (S2) or C(Fw since their elements might not even be bounded functions. For example, ax (A) = d dA, K) is unbounded but continuous on Fir whenever K E K( but K & F()). Subtler still, do not even obtain all elements of (F(n()) and
5

---

Under review as a conference paper at ICLR 2020
F(Ag
Cp
Ca
Conn(Ay)
F((v.a))
Cp
C
(a) dg-coontnuous closed loop.
(b) Illustration of Lemma 4.3
In (a) we see a d continuuus loop F where 'x' marks the center-of- mass. Though the point cloud continuously changes from 4-point set to 2-point set, the center of mass discontinuously changes at the moment of convergence. In (b) see the triangle formed by Cp, Cg and F ((p. q}) in Lemma 4.3 and how the ball of radius less than |C2p C, /4 ensures the predicted error for | Cent]ll-
Figure I:
Co(F (1)). As example of this, observe that 8x sin og is bounded and is also continuous on (Q) because & is.
We'll now compare the representation power of these two architectures. Let Ω C R be compact.
We define the point cloud diameter function Diam F(22) + and point cloud center-of-mass function Cent:: F(2)) RR. by Diam (A) max d(x, y) and Cent(A) І ExEA æ.
Theorem 4.1. Let (S2 d) be an infinite compact metric space with no isolated points. Then a func- tion J F(Z) + IR is continuous with respect both dæ and dw iff it is constant. As a corollary, Diam is uniformly approximable by PointNet networks but not DeepSets networks and Cent is uni- formly approximable by DeepSets networks but not PointNet networks.
Proof. Assume f F(?) + IR is both conttnniss and dyy-contnuous. Let A E F(22) and let p E A. For each n = 2...... choose A', E F(2) 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 An A', ((A) {p)).
Observe that An dy A and An dy [F}. Thus,
dæ lim An 110000
lim f(Am) 5 ( n-2oc
dw lim n-
f(A) =
A,
f((x))
Note that A was arbitrary so must always give set and any of its singleton subsets the same value. Now let B,C E F(22) such that + C. Without loss generality assume E B \ and q # r C. Thus by the above,
=(B)= = f((a)) (((a)))))((())))==)))))))>>>
f(C)
thus f must be constant. Conversely, constant maps are always continuous.
Finally, it's known that the Diam satisfies Diam (A) DDam 2d (A, B) and hence is du- continuous on XC(2) and Cent is continuiss on P(22) because Ave is dy-cconinuous (here π, the projection onto the i-th component map). This means they are uniformly continuous on (2) and Fw (S2 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 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.

---

Under review as a conference paper at ICLR 2020
Theorem 4.2. Let Q C Rd be infinite compact set with isolated points. Then for every d conttnnuuuuus F: ( - R there exists A E ( such that
k- Diam(S?).
[[A Cent(AA)l
2
In particular, since PointNet architectures are dg-continuous they cannot uniformly approximate center-of-mass when k 2 3 and suffer from the above uniform-norm error lower-bound.
is possible to see that PointNet cannot uniformly approximate Cent by considering Figure Ta Moving k points in k-element cloud either of the remaining two points produce the same 2- element cloud in ddz-conninuous way. By dn dgg-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 Z C TRd be infinite with no isolated points and F FF) - Ted an arbitrary du-continuous map. Then for every distinct p.q E Zi and 0 < 1 there exists A E F such that p, Q E A and
2-2
[[(AA) - Cent(A)ll (1 - 7)
||p 1 -ll
2k
In particular, since PointNet architectures are dy-continuous they must satisfy this ervor bound.
Proof. Assume k 2 3 since the inequality is trivial for k 2, Let Cp ptu + (k-2) )p and
Cy:= == 2ta + (k=2)g and observe that ||Cp - C. k=2 ||p q/1. Now let c T|C Cg /4
and choose Aú and At to be k-point supersets of [p. g) such that A; \ (g) C (p(p) and A (p} S
(a).). We can do this because and are not isolated points. Since F is dy--continous and
AS, A d {p.9} as + 0, we can additionally demand that |F(A5)) ((((,.)))l < and [F(AG)
- (((p.9))) < E. Next observe that
k p+q + (1/k) Σ a Cent(Ar))
Cent(AA)) p P+ + (1/k)
Σ aEA; (p
k
and [|Cent -Cyll e. Now we can consider the triangle in Rd formed by Cp. Cg. and F(Ip, q}) and realize by basic geometry that one of [[P,, q}) Cpll [[F((,, q}) Cgll must greater than or equal to ||C, C₂ /2 (see Figure lb). Without loss of generality, let [[((()))) Cgll 2 1|C - Call Then,
By the triangle inequality follows that || (Ce) Cpll < -
1C, - Cpll <
[((p, at) - F(A (I Cent (4$11 + ||Cent(A)) (A3) - Cgll
2
Thus,
1C, Cyll
2
(F(A)) - ((en((A))) >
2 (1 (1-r)
l| 9ll
2
2k
Thus AG is the promised set which achieves the desired uniform-now -ortommm-ormmmmmo error.
Theorem 4.2 now follows easily.
proof of Theorem 4.2
Choose p.q S |pp 411 Diamm{?) 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 ap- proach to finding point clouds that exhibit the failure of uniform approximation. This let's us produce adversarial examples to the centor-of-ne of-aas problem for PointNet. When Ω is additionally convex e.g. the unit disk D in ? it becomes fairly easy to construct many examples of AG and A ex- plicitly for given PointNet model, allowing empirically verify the uniform-norm error lower
7

---

Under review as a conference paper at ICLR 2020
PonttNer1500 (50 opochs, b3tchsite-5))
Advarsarial Errors vs Predicted Ernor Lower Bound PointNel|500-500.0
0.834
ning Lonc Velcatoon
Lower Bound
0.-
Adversanal Example
0.000
0.006
02
0.0
0.000
apors
(b) Experimental test of error lower bound.
Training curve of PointNet model learning Cent.
Figure 2: In (a) we see the training curve for the PointNet model learning the center- of-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 theoret- ical gaurantee.
bound. In the following experiment, train simple PointNet architecture learn the center-of- mass for 10-element point clouds in D. We train on a synthetic data set of million point clouds (each element uniformly sampled from D) labeled with their center-of-mass. The PointNet architec- ture has 500K trainable parameters. The network has the form F(A) = p(maxae (a)) where yp has 2-D input layer, 500-D hidden layer, and 500-D linear output layer, and p has 500-D input layer, 500-D hidden layer and 2-D linear output layer (in accordance with the Point-Cloud-UAT) The hid- den layers of & and p are ReLU. Since it is not possible train with respect the uniform-nome norm,, we opt for the traditional L 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 nonzero r 0.01 and two distinct points p, q E D at random. We set points towards p and towards sufficiently close so that the criteria in the proof of Lemma 4.3 satisfied. This {p, q} adjoined with the points pulled towards p and g form A and A We are theoretically ensured one these two will have error larger than our bound. In Figure 2b we plot the the produced adversarial error the distance between p and q that were used to make AS, and A As predicted, all the adversarial errors lie above the line representing the uniform-norm error lower bound.
|pp 4l1 /4. We then sample D another 8 times. We then linearly pull those
CONCLUSIONS AND FUTURE WORK
The failure of the perceptron model to learn the XOR function 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 Hornik Hornik et al.] Leshoo 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 I. N the same question for point clouds has 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 way to obtain greater approximation power? Are there other useful topologies on F(22) for which new kinds of contin- 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 they like?
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
George Cybenko. Approximation by superpositions of sigmoidal function. Mathematics control, signals and systems, 2(4):303-314, 1989.
Nicolas Fournier and Arnaud Guillin. On the rate of convergence wasserstein distance of the empirical measure. Probability Theory and Related Fields, 162(3-4):007-738, 2015.
Kurt Homik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks uni- versal approximators. Neural networks, 2(5):359-366, 1989.
Moshe Leshno, Vladimir Ya Lin, Allan Pinkus, and Shimon Schocken. Multilayer feedforward net- works with nonpolynomial activation function can approximate any function. Neural networks, 6(6):861-86 1993.
James Raymond. Munkres. Topology. Prentice Hall, 2000.
Charles R Qi, Hao Su, Kaichun Mo, and Leonidas J Guibas. Pointnet: Deep learning on point sets for classification and segmentation. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp.
2017.
Walter Rudin. Real and complex analysis. Tata McGraw-hill education, 2006.
M.b. Stinchcombe. Neural network approximation of continuous functionals and continuous func- tions on compactifications. Neural Networks, 12(3):467477, 1999. doi: 10. 1001///093660000999 00108-7.
Cedric Villani. Optimal transport: old and new. Springer, 2009.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Ruslan R Salakhutdinov, and Alexander J Smola. Deep sets. In Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems 30, pp. 3391-3401, Curran Associates, Inc., 2017. URL http: http:///ppperseeeeee nips cctcccc/ppppcc nips.cc/paprr/ paper/ 6931 1131-deere 6931-deep- sets.. pdf

---

Under review as a conference paper at ICLR 2020
A
APPENDIX
Proof of Lemma 2. First we show that the r is a linear isometry. Since X compact for f E C(X)
there is p X so that [f(p)] xll By density of D there is a sequence pn. D that limits to So
Il = 1f()) = lim If(p))) - sup [f(x)
[Ir & sup #cX If(x) ll
n-=00
=ED
Next, since C(X) is complete, so is its isometric image r(C(X)) and because Cs(X) is complete that means r()()) is closed. Thus,
r(C(x)) = r(V) S C(N)) C -[(c(())=<(cc
where the first subset results from continuity. Thus N = r r(C(X)).
Finally, to show r(C(X)) = M(D) note that every uniformly continuous function on D con- tinuously extends to function on X (because /) is dense in X) placing this extension in C(X) and so E r(C())). The reverse inclusion follows as well because restriction preserves uniform continuity.
Proof of Lemma 2.2 First we show that Max is dur-continuous. Let > 0. Since Ω is compact, f uniformly continuous and so there is so that [f( - f(y)] < e/2 whenever d(x,, y) < 26. Now let A, B e X(12) and suppose du (A, B) < 8. By definition this means A B5 and B Ass- By the triangle inequality we have
Max,
(ax)(B)) S MMxx(())
(Ax)) + (Ax) Max)
Since As is compact there is a Ag so that (A8) = f()). Observe that if q K C As with d(p.q) < 20 then (p) f44) < e/2 and fp) = (ax)(AA)) 2 Max 2 f()). This implies |Maxy (As) Max (K)l e/2. In particular, since p As there is a E such that d(p, a) < 8, and since B is compact there is b E B closest to and so,
d(p, d(p, B) & di (Ag, B) S dns (Ag. A) + d < 26.
Thus (Aax)(As) Max (A)l and |Max, (As) Max, (B)l are less than c/2 and so [Max (A) - Max (B)) < as desired.
To see why Ave do-continuuus recall that the topology of dw the same as the weak-* topology for measures and so the map ~ f. du is by definition continuous whenever f E C()).
1 E 80 = 1 ''E
1
1 Σ f(a) (A) | fdd. b- n acA
Aver,s(ip(A)) A
aeA"
It's clear that Maxy oig maxy. 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(I) and P(2). Since (S2, d) compact implies both XC(S2) and P(2) are compact, we can deduce that PointNet and DeepSets are uniformly continuous on Fu (2) and Fw (22).
10


Reviews:
[{"review_id": "rJxCrFiDKH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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:\n\n1.\tPointNet (resp. Deep sets) can approximate uniformly real-valued functions that are uniformly continuous with respect to the Hausdorff (resp. Wasserstein) metric;\n2.\tOnly constant functions can be uniformly approximated by both (PointNet, Hausdorff metric) and (Deep sets, Wasserstein).\n\nThis paper brings a valuable theoretical contribution to the existing state of the art of their approximation abilities. With some improvements, I am willing to increase the score.\n\n1.\tThe introduction lacks insight into the literature on point cloud or measure networks, including in practice, which would motivate the subject and place it more precisely within the literature.\n2.\tNotations in the section 2.4 make the reading particularly unclear. Notations should showcase the result that theoretically, only two hidden layers (with appropriate definitions) are needed.\n3.\tThe paper lacks an experimental section. It would be interesting to investigate empirically the limitations of these architectures, for instance by playing with the diameter and center of mass functions as suggested in 3.3.\n\n- Post rebuttal: the authors have addressed 3., therefore I am leaning towards accept.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "rJgDrkcXqr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper aims to establish novel theoretical properties of known point-based architectures for deep learning, PointNet and DeepSets. To this end, the authors prove a series of theoretical results and establish limitations of these architectures for learning from point clouds. \n\nUnfortunately, due to a delay with my review, I cannot afford the joy of carefully examining the proofs. \n\nI do not find significant practical value in the obtained results. While the theorems proved in the paper are original and novel, they are a refinement of the already known results regarding approximation theorems for PointNet and DeepSets, respectively, hence only a marginal improvement in understanding these function classes. ", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "BJl_MskAFS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\n- 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.\n\n- 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.\n\n- 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).\n\nSummary: 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. \n\nDisclaimer: 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.\n\n=== Post rebuttal update ===\nI'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", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The present paper establishes uniform approximation theorems (UATs) for PointNet and DeepSets that do not fix the cardinality of the input set. 

Two nonexperts read the paper and came away not understanding what this exercise has taught us and why the weakening of the hypotheses was important. The authors made no attempt to argue these points in their rebuttals and so I went looking at the paper to find the answer in their revisions, but did not find it after scanning through the paper. I think a paper like this needs to explain what is gained and what obstructions earlier approaches met, and why the current techniques side step those. One of the reviewers felt that the fixed cardinality assumption was mild. I'm really not sure why the authors didn't attack this idea. Maybe it is mild in some technical sense?

What I read of the paper seemed excellent in term of style and clarity. I think the paper simply needs to make a better case that it is not merely an exercise in topology. I think the result here is publishable on its own grounds, but for the paper to effectively communicate those findings, the authors should have revised it to address these issues. They chose not to and so I recommend ICLR take a pass. Once the reviewers revised the framing and scope/impact, provided it doesn't sound trivial, I think it'll be ready for publication.


Decision: Reject