Research map / Optimization / Implicit bias and generalization
On the hardness of learning under symmetries
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.
Shows that imposing known symmetries (permutation/sign/cyclic invariance, frame averaging, GNNs) does not overcome the exponential CSQ/SQ hardness of learning shallow neural networks with gradient descent, and gives NP-hardness for proper GNN training.
Problem
Whether known problem symmetries (equivariance/invariance) make learning shallow neural networks with gradient descent computationally tractable, given that fully-connected shallow nets are exponentially hard in the CSQ model.
Approach
Extends CSQ/SQ hardness proofs for shallow fully-connected nets to invariant classes (GNNs, CNNs via frame averaging, invariant polynomials), showing symmetry reduces but does not remove hardness, by symmetrizing hard families or constructing new hard invariant families, plus an NP-hardness reduction for proper GNN training.
Key results
- Boolean SQ lower bound: queries at least tau^2 ||p_O||^{-2}/2, giving Omega(2^{O(n^2)}) for the symmetric group on n x n graphs.
- Exponential CSQ lower bound for one-hidden-layer GNNs in feature dimension: class of size 2^{Omega(d^{Omega(1)})} requires 2^{d^{Omega(1)}} queries or very high precision.
- Superpolynomial CSQ lower bound n^{Omega(log n)} for sign-invariant frame averaging, and separation showing sparse invariant polynomials are SQ-learnable in O(kr^2 log r) queries while CSQ needs Omega(r^d).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Train an overparameterized GNN on targets from H_ER,15 | GNN · H_ER,15 (225 Erdős–Rényi graphs) | training fit | Hurt |
| Train an overparameterized CNN on targets from C^B_F | CNN · C^B_F, n=50 (500 examples) | training fit | Helped |
| Train an overparameterized CNN on targets from C^B_F | CNN · C^B_F, n=50 (500 examples) | mean squared error generalization | Hurt |
Surprising findings
- A single message-passing layer already yields exponentially hard functions, contrary to intuition that hardness grows with number of message passing steps.
- In experiments, an overparameterized GNN could not fit even 225 training graphs with n=15 nodes.
Limitations
- Results are for SQ/CSQ query models, which cover gradient descent but not all learning algorithms; not PAC-model unconditional hardness.
- Frame-averaging lower bounds assume polynomial-sized groups or sign-invariant frames, and some results are only sketched in the main text.
- Experiments are small-scale and only illustrative.
Experimental setup
Metrics: training fit generalization MSE
Baselines: fully-connected shallow network CSQ lower bounds
Builds on: CSQ lower bounds for shallow ReLU networks Growing-basis algorithm for sparse polynomials frame averaging Boolean SQ pairwise-independence lower bound
Closest papers by meaning
- On Universality Classes of Equivariant Networks (NeurIPS 2025 · similarity 0.91)
- Improving Equivariant Networks with Probabilistic Symmetry Breaking (ICLR 2025 · similarity 0.91)
- A Tale of Two Symmetries: Exploring the Loss Landscape of Equivariant Models (NeurIPS 2025 · similarity 0.91)
- Learning (Approximately) Equivariant Networks via Constrained Optimization (NeurIPS 2025 · similarity 0.90)
- A Characterization Theorem for Equivariant Networks with Point-wise Activations (ICLR 2024 · similarity 0.89)
- Scale Equivariant Graph Metanetworks (NeurIPS 2024 · similarity 0.89)
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.