UC Santa Barbara

Point clouds and sets are ubiquitous, unusual and unstructured data-types which present unique problems to machine learning when used as inputs. Since sets are inherently unaffected by permutations, the input space for these problems naturally forms a non-Euclidean space which is oftentimes not even a manifold. Moreover, similar inputs can have wildly varying cardinalities and so the input space is in general infinite-dimensional. Despite these mathematical difficulties, PointNet (Qi et al.) and Deep Sets (Zaheer et al.) form two foundational contributions for deep learning in this area. In this thesis we study the expressive power of such networks. To that end, we prove theorems about their Lipschitz properties, extend them to well-studied infinite-dimensional spaces, and prove new cardinality-agnostic universality results for point clouds. These results completely characterize the approximable functions and so can be used to compare the representational strength of the underlying model classes. In particular, a normalized version of the DeepSets architecture cannot uniformly approximate the diameter function but can uniformly approximate the center-of-mass function whereas PointNet can uniformly approximate the former but not the latter. Additionally, even when limited to a fixed input cardinality, PointNet cannot uniformly approximate the average value of a continuous function over sets of more than two points. We additionally obtain explicit error lower-bounds for this error of approximation and a present a simple geometric method to produce arbitrarily many examples of this failure-mode. Along the way, we also prove various general purpose universal approximation theorems, one of which is for generalized neural networks whose input space is a set of unknown or nonexistent topology.