🤖 machine learning

When and How to Canonize: A Generalization Perspective

This paper establishes a theoretical framework demonstrating that the generalization performance of canonized models depends critically on the regularity of the canonization method, proving that Hilbert curve serialization offers polynomial complexity and superior bounds compared to exponential lexicographical sorting, thereby providing the first formal justification for its empirical success in point cloud processing.

Original authors: Yonatan Sverdlov, Benjamin Friedman, Snir Hordan, Nadav Dym

Published 2026-05-13

📖 6 min read🧠 Deep dive

CC0 1.0

Original authors: Yonatan Sverdlov, Benjamin Friedman, Snir Hordan, Nadav Dym

Original paper dedicated to the public domain under CC0 1.0 (http://creativecommons.org/publicdomain/zero/1.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a robot to recognize a specific object, like a chair, no matter how it is turned, flipped, or shuffled around. In the world of machine learning, this is called dealing with symmetry. If you rotate a chair, it's still the same chair. A smart learning system should understand this without needing to see every single possible angle of that chair.

This paper is about finding the best way to teach a robot to handle these symmetries. The researchers compare three main strategies, using a concept called "covering numbers" as their ruler to measure how hard the learning task is. Think of a "covering number" as the number of "snapshots" or "reference points" you need to fully describe a shape. The fewer snapshots you need, the easier it is for the robot to learn and generalize (apply what it learned to new data).

Here is the breakdown of their findings using simple analogies:

1. The Three Strategies for Handling Symmetry

The paper looks at three ways to make a robot "symmetry-aware":

The "Do Nothing" Approach (Non-invariant): You just feed the robot raw data. If the chair is upside down, the robot sees it as a completely different object. It has to memorize every single variation. This is the hardest way to learn.
The "Group Averaging" Approach: Imagine you have a table with 100 different photos of the same chair (rotated, flipped, etc.). Instead of showing the robot just one, you show it the average of all 100 photos. This creates a perfect, symmetrical "ghost" of the chair. This is the gold standard for learning because it removes all confusion. However, it's computationally expensive, like trying to average 100 photos in real-time for every single object you see.
The "Canonization" Approach: This is the paper's main focus. Instead of averaging, you pick one specific "canonical" (standard) version of the chair. For example, you decide: "No matter how the chair is turned, we will always rotate it so the legs point down and the back faces North." You then feed this single, standardized version to the robot. This is very fast and efficient.

2. The Big Discovery: Not All "Standardizers" Are Created Equal

The authors prove a hierarchy of how well these methods work:

The Hierarchy: The "Group Averaging" method is theoretically the best (lowest error). The "Canonization" method sits in the middle: it can be just as good as averaging, or it can be just as bad as doing nothing.
The Catch: Whether canonization works well or poorly depends entirely on how you choose the standard version.

3. The "Smooth" vs. "Jumpy" Standardizer

The paper introduces a crucial concept: Continuity.

The Smooth Standardizer (Optimal): Imagine a rule that says, "If you tilt the chair slightly, the standardized version tilts slightly." This is a smooth, continuous rule. The paper proves that if your standardization rule is smooth, the robot learns almost as well as if you had used the expensive "Group Averaging" method.
The Jumpy Standardizer (Poor): Imagine a rule that says, "If the chair is tilted 1 degree left, we flip it upside down. If it's tilted 1 degree right, we leave it alone." This is a "discontinuous" or "jumpy" rule. A tiny change in input causes a massive, chaotic change in output. The paper proves that if you use a jumpy rule, the robot learns just as poorly as if you had done nothing at all.

Analogy: Think of sorting a deck of cards.

Smooth: You sort them by number, then suit. If you change one card slightly, the order changes slightly.
Jumpy: You decide that if the first card is a "2", you sort the whole deck alphabetically, but if it's a "3", you sort it by color. A tiny change in the first card causes the whole deck to be sorted in a completely different way. This chaos makes it impossible for the robot to learn patterns.

4. The Real-World Test: Point Clouds (3D Shapes)

The researchers tested these theories on point clouds (collections of dots that make up 3D shapes, like a 3D scan of a chair). They compared two specific ways of "standardizing" these shapes:

Lexicographical Sorting (The Jumpy One): This is like sorting words in a dictionary. You look at the first coordinate (x), then the second (y), then the third (z). The paper proves mathematically that this method is "jumpy." As the number of points in the shape increases, the difficulty of learning (the covering number) explodes exponentially. It becomes a nightmare for the robot to learn.
Hilbert Curve Sorting (The Smooth One): This uses a special, winding path (like a space-filling curve) to order the points. The paper proves this method is "smooth." As the number of points increases, the difficulty only grows polynomially (much slower and manageable).

The Result: This provides the first mathematical proof for why Hilbert Curve sorting works so well in state-of-the-art 3D AI models (like Point Transformer V3), while simple dictionary-style sorting often struggles.

5. The Experiments

The authors ran experiments to back up their math:

They showed that when they used the "smooth" Hilbert method, the AI learned better and made fewer mistakes on new data than when they used the "jumpy" sorting method.
They confirmed that while "Group Averaging" (the gold standard) is the best, it is often too slow to use. Therefore, using a "smooth" canonization (like Hilbert) is the best practical compromise: it's fast like canonization but learns almost as well as the gold standard.

Summary

The paper tells us that how you organize your data matters more than you might think.

Averaging is the best but too slow.
Canonization (picking one standard version) is fast, but only if you pick the standard version smoothly.
If you pick the standard version jumpy (like simple sorting), you lose all the benefits of symmetry.
The Hilbert Curve is a specific, smooth way to organize 3D data that allows AI to learn efficiently, explaining why it is so successful in modern technology.

Technical Summary: When and How to Canonize: A Generalization Perspective

Problem Statement

In domains involving symmetric data (e.g., graphs, 3D point clouds, molecular structures), the target functions are often invariant to specific group actions. While specialized invariant architectures are standard, there is growing interest in achieving invariance by applying canonization to non-invariant backbones. Canonization maps every group orbit to a single, consistent "canonical" element, offering computational efficiency compared to full group averaging. However, the theoretical generalization properties of canonization, particularly how they compare to group averaging and how the quality of different canonization methods affects learning, remain poorly understood. This paper addresses the lack of a rigorous theoretical framework to analyze the generalization error of canonized models.

Methodology

The authors introduce a theoretical framework based on covering numbers to analyze the generalization error of invariant models. They utilize a standard generalization bound framework (based on [32]) that relates generalization error to the Lipschitz constants of the model and target function, and the covering number of the input domain.

The study compares three types of models:

Non-invariant baselines: $h = \tilde{h}$ (no symmetry handling).
Canonized models: $h = \tilde{h} \circ c$ , where $c$ is a canonization function.
Group-averaged models: $h(x) = \int_G \tilde{h}(gx) dg$ .

The core of the methodology involves deriving upper bounds on the generalization error for these models by bounding the covering numbers of their respective domains:

Non-invariant: The original space $K$ .
Canonized: The image of the canonization $c(K)$ .
Group-averaged/Invariant: The quotient space $K/G$ .

The authors establish a hierarchy of covering numbers: $N(K/G) \leq N(c(K)) \leq N(K)$ . They further investigate the conditions under which a canonization $c$ attains the lower bound (optimal) or the upper bound (poor), linking these properties to the continuity and isometry of the canonization function.

Key Contributions

1. Generalization Hierarchy of Canonization vs. Group Averaging

The paper proves that the generalization error bounds of canonized models are at best equal to those of group-averaged models and at worst equal to non-invariant baselines.

Theoretical Result: $N(K/G, \rho_G, \epsilon) \leq N(c(K), \rho, \epsilon) \leq N(K, \rho, \epsilon)$ .
Implication: While canonization offers computational advantages (processing a single representative), it may come at the cost of reduced generalization performance compared to group averaging, depending on the specific canonization used.

2. The Role of Continuity and Isometry

The authors characterize "optimal" and "poor" canonizations based on their regularity:

Optimal Canonizations: Isometric canonizations (where $\rho(c(x), c(y)) = \rho_G([x], [y])$ ) attain the optimal lower bound on covering numbers, matching the performance of group averaging. Examples include sorting for permutations and centralization for translations. Crucially, isometric canonizations are always continuous.
Poor Canonizations: Discontinuous canonizations can lead to "poor" performance where the covering number of the canonized image equals that of the original non-invariant space. The paper demonstrates that if a canonization has $|G|$ partial limits at a point (strong discontinuity), an adversarial domain can be constructed where the generalization bound degrades to that of a non-invariant model.

3. Case Study: Lexicographical Sorting vs. Hilbert Curve Canonization

Applying the framework to point cloud processing (permutation group $S_n$ ):

Lexicographical Sorting (Lexsort): The paper proves that the covering number of Lexsort grows exponentially with the number of points $n$ (specifically, $\Omega((1/2\epsilon)^{(d-1)n+1})$ ). This is attributed to the severe discontinuities of Lexsort when the first coordinate of points is identical.
Hilbert Curve Canonization: In contrast, the covering number of the Hilbert curve canonization grows only polynomially in $n$ .
Significance: This provides the first formal theoretical justification for the empirical success of Hilbert curve serialization in state-of-the-art architectures like Point Transformer V3 [30], explaining why it outperforms Lexsort in generalization.

Experimental Results

The authors conducted experiments to validate their theoretical claims:

Coverage on ModelNet: Using real-world point cloud data, the "coverage" (a proxy for covering number) followed the theoretical hierarchy: Group distance (quotient) < Hilbert < Lexsort < Euclidean (non-invariant).
Classification Performance: On ModelNet10 and ModelNet40, a simple MLP with Hilbert canonization achieved the highest test accuracy and the lowest generalization error (Test Acc - Train Acc), outperforming both Lexsort and non-invariant baselines.
Group Averaging vs. Canonization: Experiments on ModelNet (using PCA for rotation) and Rotated MNIST confirmed that group averaging (or augmentation approximating it) generally outperforms canonization in terms of accuracy, supporting the theoretical hierarchy where averaging is optimal.
Spectral Embeddings: Additional experiments on graph spectral embeddings (ogbg-molpcba) showed that random group augmentation (approximating averaging) performed comparably to deterministic canonization, consistent with the theory that for small groups, the gap may be negligible, but the hierarchy holds.

Significance and Claims

The paper claims to provide the first formal theoretical justification for the empirical preference of Hilbert curve serialization over lexicographical sorting in point cloud processing. It establishes a rigorous methodology for comparing different canonization strategies via covering numbers, shifting the focus from merely distinguishing symmetric examples to analyzing the geometric properties (regularity/continuity) that influence generalization.

The authors conclude that while group-averaged models are theoretically preferable for generalization, they are often computationally intractable. Therefore, the choice of canonization is critical: continuous, isometric canonizations (like Hilbert curves) are necessary to approach the generalization bounds of group averaging, whereas discontinuous canonizations (like Lexsort) risk degrading performance to the level of non-invariant models. The work complements existing literature by highlighting that the quality of the canonization function, specifically its continuity, is a decisive factor in learning performance.