Introduction
Deep learning on point clouds and sets presents unique challenges, primarily because the input data is permutation-invariant (the order of points does not matter) and can have variable cardinality. While architectures like PointNet and DeepSets have achieved widespread empirical success, their theoretical limits have remained partially obscured. Previous Universal Approximation Theorems (UATs) for these models often assumed a fixed number of points or failed to account for model behavior as the number of points approaches infinity. This paper provides a rigorous mathematical comparison of the representation power of PointNet and DeepSets, answering exactly what types of functions these networks can represent and where they fundamentally fail.
Theoretical Framework: Metrics and Pooling
The authors employ tools from functional analysis and topology to study three variations of "Set Pooling Networks":
- PointNet, which utilizes max-pooling to aggregate point features.
- DeepSets, which traditionally relies on sum-pooling.
- Normalized-DeepSets, a variant emphasized by the authors that uses average-pooling.
The core contribution lies in linking these architectures to specific mathematical metrics. The authors prove that PointNet is continuous with respect to the Hausdorff metric, which measures the distance between two sets based on their "outlines" or boundaries. In contrast, Normalized-DeepSets is continuous with respect to the 1-Wasserstein metric (often called the Earth Mover's Distance), which measures the distance between probability distributions. By establishing these topological links, the authors derive new UATs (notably Theorem 3.4) that precisely characterize the function classes each network can approximate.
Key Insights: Blindness and Inductive Biases
A major finding of the paper is PointNet's "blindness" to point distribution. Because PointNet relies on max-pooling, it only captures the "extremes" of a point cloud. It cannot distinguish between a set of points forming a thin shell and a set of points densely filling the interior of that shell, provided their boundaries are identical.
This leads to a striking limitation: PointNet cannot accurately calculate the center-of-mass (average position) of a set of points. The authors formalize this in Theorem 4.2, providing an explicit mathematical lower bound for the error PointNet will inevitably make on this task.
However, this limitation acts as a powerful inductive bias. PointNet's inability to see internal distributions means it ignores potentially distracting density variations when the task only requires understanding the overall shape.
Furthermore, the authors highlight a theoretical advantage of average-pooling over sum-pooling. Standard DeepSets (sum-pooling) is mathematically difficult to analyze as the number of points approaches infinity because the sum "blows up." Average-pooling (Normalized-DeepSets) remains well-behaved, allowing for robust theoretical analysis of large point clouds.
Empirical Validation
To validate these theoretical differences, the authors designed synthetic datasets tailored to isolate shape versus distribution:
- Center-of-Mass Task: Using 1 million point clouds (10 points each) sampled from a unit disk, the authors empirically verified the theoretical error bounds of PointNet.
- RingLine Dataset: A binary classification task where a "ring" and a "line" share the same shape envelope but have different point distributions. Here, DeepSets rapidly reached near-zero loss, while PointNet failed to learn entirely.
- DiscSquare Dataset: A classification task between a "disc" and a "square" (different shapes, similar internal distributions). In this scenario, PointNet's inductive bias shone, converging roughly 10x faster than DeepSets by ignoring internal distribution and focusing solely on the boundary.
Limitations and Future Work
The authors acknowledge certain limitations in their theoretical framework. They could not provide a full UAT for standard sum-pooling DeepSets in the infinite-cardinality limit, as sum-pooling lacks a compact Hausdorff space for continuous extension. Additionally, the study primarily focuses on "shallow" pooling networks (one hidden layer before and after pooling), leaving the topological impact of deeper architectures for future research. Finally, the authors suggest extending this topological framework to analyze more complex, modern architectures like Transformers, which are increasingly dominant in set-based data processing.
Summary updated