Learning with Exact Invariances in Polynomial Time
Ashkan Soleymani, Behrooz Tahmasebi, Stefanie Jegelka, Patrick Jaillet · 2025
Read Learning with Exact Invariances in Polynomial Time by Ashkan Soleymani, Behrooz Tahmasebi, Stefanie Jegelka, Patrick Jaillet (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-19758.txt.
Introduction
Ashkan Soleymani, Behrooz Tahmasebi, Stefanie Jegelka, and Patrick Jaillet study how a learning model can respect exact symmetries in its data without slowing to a crawl, in a 2025 paper. Many tasks have built-in symmetries, such as rotations that should not change an answer. Older tricks either break the exactness or take too long, and some do not fit the kernel methods they study.
Given access to facts about the shape of the input space, their method learns in reasonable time and honors the symmetries exactly. Its error matches that of plain kernel learning without the symmetry demand. The proof draws on geometry, spectra, and optimization, and one side result may serve other problems.
Catalog record
| CREATOR | Ashkan Soleymani, Behrooz Tahmasebi, Stefanie Jegelka, Patrick Jaillet |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 79 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-19758
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Learning with Exact Invariances in Polynomial Time Ashkan Soleymani, Behrooz Tahmasebi, Stefanie Jegelka, Patrick Jaillet Abstract We study the statistical-computational trade-offs for learning with exact invariances (or symmetries) using kernel regression. Traditional methods, such as data augmentation, group averaging, canonicalization, and frame-averaging, either fail to provide a polynomial-time solution or are not applicable in the kernel setting. However, with oracle access to the geometric properties of the input space, we propose a polynomial-time algorithm that learns a classifier with exact invariances. Moreover, our approach achieves the same excess population risk (or generalization error) as the original kernel regression problem. To the best of our knowledge, this is the first polynomial-time algorithm to achieve exact (not approximate) invariances in this context. Our proof leverages tools from differential geometry, spectral theory, and optimization. A key result in our development is a new reformulation of the problem of learning under invariances as optimizing an infinite number of linearly constrained convex quadratic programs, which may be of independent interest. † † affiliationnotice: Equal contribution 1 Introduction While humans can readily observe symmetries or invariances in systems, it is generally challenging for machines to detect and exploit these properties from data. The objective of machine learning with invariances is to develop approaches that enable models to be trained and utilized under the symmetries inherent in the data. This framework is broadly applicable across various domains in the natural sciences and physics, including atomistic systems ( Grisafi et al., 2018 ) , molecular wavefunctions and electronic densities ( Unke et al., 2021 ) , interatomic potentials ( Batzner et al., 2022 ) , and beyond ( Batzner et al., 2023 ) . While many applications involve Euclidean symmetries ( Smidt, 2021 ) , the scope of such methods extends well beyond them to other geometries ( Bronstein et al., 2017 ) . Learning with invariances has a longstanding history in machine learning ( Hinton, 1987 ; Kondor, 2008 ) . In recent years, there has been significant interest in the development and analysis of learning methods that account for various types of invariances. This surge in interest is strongly motivated by many models showing considerable success in practice. Empirical evidence suggests the existence of algorithms that can effectively learn under invariances while exhibiting strong generalization and computational efficiency. However, from a theoretical perspective, much of the focus has been on the expressive power of models, generalization bounds, and sample complexity. There remains a relative lack of understanding regarding the statistical-computational trade-offs in learning under invariances, even in foundational settings such as kernel regression. Symmetries can be incorporated into learning in multiple ways. An immediate solution for learning with invariances seems to be data augmentation over the elements of the group. Moreover, some approaches to learning with invariances rely on group averaging , a technique that involves summing over group elements. However, the typically large size of the group can make both of these approaches computationally prohibitive, even super-exponential in the dimension of input data. Alternative approaches, such as canonicalization and frame averaging , also suffer from issues like discontinuities and scalability challenges ( Dym et al., 2024 ) . This paper seeks to address the following question: Can we obtain an invariant estimator for learning with invariances that achieves both strong generalization and computational efficiency? The first contribution of this work is a detailed study of the problem of learning with invariances in the context of kernel methods. Kernels, which have been among popular learning approaches, offer both statistical and computational efficiency ( Scholkopf & Smola, 2018 ) . We argue that while group averaging fails to produce exactly invariant estimators within a computationally efficient time frame, alternative algorithms can generate invariant estimators for the kernel regression problem in time that is polylogarithmic in the size of the group. In other words, we demonstrate that it is possible to achieve an invariant estimator that is both computationally efficient and exhibits strong generalization. At first glance, this result may seem counterintuitive and even impossible, since it implies that enumerating all possible invariances is not required to design statistically efficient learning algorithms. This provides theoretical support for the empirical observation that computational efficiency and strong generalization are attainable in learning with invariances. To the best of our knowledge, this is the first algorithm that is both statistically and computationally efficient for learning with invariances in the kernel setting, Learning with invariances can be formulated as a nonconvex optimization problem, which is not tractable directly. To design an efficient algorithm, we leverage the spectral theory of the Laplace-Beltrami operator on manifolds. Notably, since this operator commutes with all (isometric) group actions on the manifold, it is possible to find an orthonormal basis of Laplacian eigenfunctions such that each group action on the manifold acts on the eigenspaces of the Laplacian via orthogonal matrices. This theoretical framework allows us to reformulate the original problem of learning with invariances on manifolds as an infinite collection of finite-dimensional convex quadratic programs –one for each eigenspace–each constrained by linear conditions . By truncating the number of quadratic programs solved, we can efficiently approximate solutions to the primary nonconvex optimization problem, thereby approximating kernel solutions to the problem of learning with invariances. This reformulation not only enables us to derive a polynomial-time algorithm for kernel regression under invariances, but it may also have broader applications, the exploration of which we defer to future research. Finally, we emphasize again that this work is centered on achieving exact invariance, as many applications—especially neural networks with strong empirical performance—are explicitly designed to incorporate exact invariances by construction. In summary, this paper makes the following contributions: • We initiate the exploration of statistical-computational trade-offs in the context of learning with exact invariances, focusing specifically on kernel regression. • We reformulate the problem of learning under invariances in kernel methods, leveraging differential geometry and spectral theory, and cast it as infinitely many convex quadratic programs with linear constraints, for which we derive an efficient solution in terms of time complexity. We trade off computational and statistical complexity by controlling the number of convex quadratic programs solved to obtain the estimator. • We introduce the first polynomial algorithm for learning with invariances in the general setting of kernel regression over manifolds. 2 Related Work Generalization bounds and sample complexity for learning with invariances have been extensively studied, particularly in the context of invariant kernels. Works such as Elesedy (2021) , Bietti et al. (2021) , Tahmasebi & Jegelka (2023) , and Mei et al. (2021) provide insights into this area. Additionally, studies on equivariant kernels ( Elesedy & Zaidi, 2021 ; Petrache & Trivedi, 2023 ) further our understanding of how equivariances affect learning. PAC-Bayesian methods have also been applied to derive generalization bounds under equivariances ( Behboodi et al., 2022 ) . More recently, Kiani et al. (2024) explored the complexity of learning under symmetry constraints for gradient-based algorithms. For studies on the optimization of kernels under invariances, see Teo et al. (2007) . A variety of methods have been proposed to enhance the performance of kernel-based learning models. One prominent approach is the use of random feature models ( Rahimi & Recht, 2007 ) , which approximate kernels