Research map / Learning theory and algorithms / Combinatorial and search optimization
Learning Polynomial Problems with $SL(2, \mathbb{R})$-Equivariance
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.
Applies neural networks to polynomial positivity verification (SOS/max-det certificates) and minimization, proposes an exactly SL(2,R)-equivariant architecture, proves it cannot universally approximate SL(2,R)-equivariant functions, and finds augmentation and SO(2)-equivariance work better in practice.
Problem
Positivity verification and minimization of bivariate binary forms via semidefinite programming are computationally expensive at larger degrees, and the problems are equivariant to the non-compact group SL(2,R) acting by linear change of variables.
Approach
Builds an exactly SL(2,R)-equivariant network from tensor products of binary-form irreps decomposed via transvectants (Clebsch-Gordan), then proves that polynomial-based equivariant architectures cannot universally approximate SL(2,R)-equivariant functions, motivating augmentation and SO(2)-equivariant alternatives.
Key results
- An MLP achieves NMSE around 1e-5 to 6e-5 on degree 6-14 forms and runs about two orders of magnitude faster than SCS (e.g., 0.062 min vs 3.50 min at degree 6 for 5,000 test examples).
- The paper proves an SL(2,R)-equivariant function (the max-det certificate for x^8+y^8) cannot be uniformly approximated by equivariant polynomials times invariants, so SL2Net cannot fit it.
- On untransformed test data, the best model is an MLP trained with near-rotation augmentations, followed by SO2Net and an unaugmented MLP; SO2Net has about half the parameters of the MLP.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use an MLP instead of SCS | Polynomial positivity verification · Degree 6 | time (min): 3.50 -> 0.062 | Helped |
| use an MLP instead of SCS | Polynomial positivity verification · Degree 6 | NMSE: 2.7e-5 -> 9.5e-6 | Helped |
| train the MLP with augmentations close to rotations | Positivity verification models · Untransformed test set | test error | Helped |
| train the MLP with high-condition-number augmentations | MLP · Untransformed test set | test error | Hurt |
| apply increasingly transformed test inputs | MLP, rotation-augmented MLP, and SO2Net · Positivity verification test set | test error | Hurt |
| use SL2Net instead of other tested architectures | Polynomial minimization models · Ill-conditioned SL(2,R) transformations | test error | Hurt |
| use SL2Net instead of SO2Net or MLP | Polynomial minimization models · Ill-conditioned SL(2,R) transformations | equivariance error | Helped |
| increase the maximum internal irrep degree (ablation) | SL2Net · Positivity verification equivariance tests | equivariance error | Hurt |
| use SO2Net instead of SL2Net | Hard-example fit at x^8 + y^8 · Single input datapoint | MSE loss | Helped |
Surprising findings
- Data augmentation with SL(2,R) transformations outperforms the fully SL(2,R)-equivariant architecture in practice.
- The SL(2,R)-equivariant architecture cannot universally approximate SL(2,R)-equivariant functions even though it represents all equivariant polynomials.
Limitations
- Experiments restricted to binary forms (d=2 variables) and low degrees, with the solver comparison only up to degree 14.
- Any SL(2,R) augmentation induces distribution shift because the group is non-compact.
- Normalization by norm breaks exact SL(2,R)-equivariance, and the proposed SO(2) architecture is not SL(2,R)-equivariant.
Experimental setup
Datasets: random rotationally symmetric binary forms (Wishart-style Gram construction) Delsarte spherical code bound polynomials synthetic minimization polynomials
Benchmarks: random rotationally symmetric positivity verification Delsarte spherical code positivity verification polynomial minimization synthetic
Metrics: normalized MSE equivariance error wall-clock time
Baselines: MLP MLP with augmentation SO2Net SCS Mosek
Builds on: Lorentz-group equivariant architecture (Bogatskiy et al.) frame averaging sum of squares / SDP certificates
Closest papers by meaning
- Permutation Equivariant Neural Networks for Symmetric Tensors (ICML 2025 · similarity 0.86)
- Neural Fourier Transform: A General Approach to Equivariant Representation Learning (ICLR 2024 · similarity 0.86)
- On the hardness of learning under symmetries (ICLR 2024 · similarity 0.86)
- Equivariant Polynomial Functional Networks (ICML 2025 · similarity 0.86)
- Lie Group Decompositions for Equivariant Neural Networks (ICLR 2024 · similarity 0.86)
- Learning with Exact Invariances in Polynomial Time (ICML 2025 · 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.