Research map / Learning theory and algorithms / Kernels and regression theory
Learning with Exact Invariances in Polynomial Time
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Spec-Avg, a spectral averaging method that enforces exact group invariance in kernel regression on manifolds in polynomial time by reducing constraints to a generating set and solving per-eigenspace projection QPs.
Problem
Learning regression functions with exact group invariances via kernel methods is computationally intractable because group averaging and data augmentation scale with group size |G|, and canonicalization/frame averaging suffer from continuity issues.
Approach
Reformulate invariant kernel regression on a manifold as per-eigenspace convex QPs with linear constraints given by a small generating set of G (size at most log|G|), using Laplace-Beltrami eigenfunctions and the commutation of the Laplacian with isometric group actions; truncate eigenspaces at a cutoff D chosen from Sobolev smoothness.
Key results
- Spec-Avg is exactly invariant (invariance discrepancy zero by construction) while KRR has nonzero invariance discrepancy in experiments.
- Spec-Avg with D=176 achieves the same order of test error as KRR with regularization lambda=50 on the d=10 torus experiment.
- Theorem: runs in O(log^3|G| n^{3/(1+alpha)} + n^{(2+alpha)/(1+alpha)}) time and attains the KRR excess risk rate O(n^{-s/(s+d/2)}).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Spec-Avg to impose exact group invariance | Kernel regression on Sobolev spaces · Sobolev regression on compact manifolds | excess population risk: \mathcal{O}\big(n^{-s/(s+d/2)}\big) | No clear effect |
| Use Spec-Avg instead of unconstrained KRR | Kernel regression under sign-invariances · Sign-invariance on \mathbb{T}^d, d = 10 | Invariance Discrepancy | Helped |
Surprising findings
- KRR is not G-invariant in practice even when trained on invariant data, so invariant kernels are needed for exact invariance.
- Exact invariance can be achieved with polylogarithmic dependence on group size without enumerating the group, with no statistical loss in rate.
Limitations
- Does not improve sample complexity over standard KRR rate; minimax-improved rates for invariant learning remain open in polynomial time.
- Requires oracle access to Laplace-Beltrami eigenfunctions and group-action matrices D^lambda(g), assumed cheap only when D_lambda is poly(n,d).
- Assumes isometric actions on compact boundaryless manifolds and uniform sampling; experiments are small (d=10, test set of 100).
Experimental setup
Datasets: synthetic torus regression data (d=10, sign-invariance group)
Benchmarks: synthetic torus sign-invariance regression
Metrics: excess population risk invariance discrepancy
Baselines: KRR group averaging kernel (K_inv) constrained ERM
Builds on: kernel ridge regression group averaging Sobolev RKHS spectral theory
Closest papers by meaning
- A Canonicalization Perspective on Invariant and Equivariant Learning (NeurIPS 2024 · similarity 0.87)
- Generalization in Kernel Regression Under Realistic Assumptions (ICML 2024 · similarity 0.87)
- Generalization error of spectral algorithms (ICLR 2024 · similarity 0.86)
- The Implicit Bias of Heterogeneity towards Invariance: A Study of Multi-Environment Matrix Sensing (NeurIPS 2024 · similarity 0.86)
- Learning Polynomial Problems with $SL(2, \mathbb{R})$-Equivariance (ICLR 2024 · similarity 0.85)
- Learning Conditional Invariances through Non-Commutativity (ICLR 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.