# Approximating invariant functions with the sorting trick is theoretically justified

arXiv: https://arxiv.org/abs/2403.01671 · HTML: https://mlsanity.com/paper/2403.01671/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 30 references that are in the map.
- First posted on arXiv 4 Mar 2024.

## Builds on (most cited first, 16 of 16)

- [Frame Averaging for Invariant and Equivariant Network Design](https://mlsanity.com/paper/2110.03336/) (2021)
- [Equivariance with Learned Canonicalization Functions](https://mlsanity.com/paper/2211.06489/) (2022)
- [Learning with invariances in random features and kernel models](https://mlsanity.com/paper/2102.13219/) (2021)
- [SE(3) Equivariant Graph Neural Networks with Complete Local Frames](https://mlsanity.com/paper/2110.14811/) (2021)
- [FAENet: Frame Averaging Equivariant GNN for Materials Modeling](https://mlsanity.com/paper/2305.05577/) (2023)
- [FSPool: Learning Set Representations with Featurewise Sort Pooling](https://mlsanity.com/paper/1906.02795/) (2019)
- [Approximation-Generalization Trade-offs under (Approximate) Group Equivariance](https://mlsanity.com/paper/2305.17592/) (2023)
- [Equivariant Frames and the Impossibility of Continuous Canonicalization](https://mlsanity.com/paper/2402.16077/) (2024)
- [Generalization Error of Invariant Classifiers](https://mlsanity.com/paper/1610.04574/) (2016)
- [Improved Generalization Bounds of Group Invariant / Equivariant Deep Networks via Quotient Feature Spaces](https://mlsanity.com/paper/1910.06552/) (2019)
- [Approximation beats concentration? An approximation view on inference with smooth radial kernels](https://mlsanity.com/paper/1801.03437/) (2018)
- [Provably Strict Generalisation Benefit for Invariance in Kernel Methods](https://mlsanity.com/paper/2106.02346/) (2021)
- [Learning Representations of Sets through Optimized Permutations](https://mlsanity.com/paper/1812.03928/) (2018)
- [Learning with Group Invariant Features: A Kernel Perspective](https://mlsanity.com/paper/1506.02544/) (2015)
- [On the Sample Complexity of Learning under Invariance and Geometric Stability](https://mlsanity.com/paper/2106.07148/) (2021)
- [Group invariant machine learning by fundamental domain projections](https://mlsanity.com/paper/2202.02164/) (2022)

## Abstract (arXiv)

Many machine learning models leverage group invariance which is enjoyed with a wide-range of applications. For exploiting an invariance structure, one common approach is known as frame averaging. One popular example of frame averaging is the group averaging, where the entire group is used to symmetrize a function. Another example is the canonicalization, where a frame at each point consists of a single group element which transforms the point to its orbit representative, for example, sorting. Compared to group averaging, canonicalization is more efficient computationally. However, it results in non-differentiability or discontinuity of the canonicalized function. As a result, the theoretical performance of canonicalization has not been given much attention. In this work, we establish an approximation theory for canonicalization. Specifically, we bound the point-wise and L2(mathbbP) approximation errors as well as the eigenvalue decay rates associated with a canonicalization trick applied to reproducing kernels. We discuss two key insights from our theoretical analyses and why they point to an interesting future research direction on how one can choose a design to fully leverage canonicalization in practice.