Research map / Learning theory and algorithms / Kernels and regression theory

Feature emergence via margin maximization: case studies in algebraic tasks

ICLR 2024 · Learning theory and algorithms › Kernels and regression theory · approach: Generalization theory of deep networks · 0 citations (OpenAlex)

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 via margin maximization (max-min duality certificate pairs) that quadratic-activation one-hidden-layer networks provably learn Fourier features for modular addition, sparse-parity-aligned neurons for k-sparse parity, and irreducible-representation features for finite group composition.

Problem

Explaining why trained neural networks adopt particular computational strategies (e.g., Fourier features for modular addition, irreducible representations for group composition) rather than other solutions that fit the same data.

Approach

Characterize max-normalized-margin solutions of one-hidden-layer homogeneous (quadratic / x^k) networks by exhibiting a certificate pair (network, data distribution) that certifies optimality via max-min duality, using class-weighted margins to decompose the problem into single-neuron optimizations, then verify that gradient descent with small L_{2,nu} regularization approaches these max-margin so

Key results

• For modular addition with quadratic activations, the maximum L_{2,3}-margin is sqrt(2/27)/(p^{1/2}(p-1)) and every max-margin neuron is single-frequency (Fourier-sparse).
• For the (10,4) sparse parity with x^4 activations, the L_{2,5} margin approaches the predicted maximum margin in training.
• For S5 with L_{2,3} regularization, trained networks' neurons concentrate on a single irreducible representation as predicted, and the normalized margin approaches the theoretical maximum.

Surprising findings

• Alternative solutions exist that fit all data perfectly but are dense in Fourier space; they have lower margin and are not reached by training.

Limitations

• Theory applies to stylized one-hidden-layer networks with quadratic (x^k) activations and L_{2,nu} norms; ReLU and transformer results are only empirical.
• Group theorem requires conditions on characters (sum d^1.5 chi(C) < 0) that hold only for some groups, e.g., S_k up to k=5.
• Requires large widths (m >= 4(p-1) or 2 sum d^3) for the characterization.

Experimental setup

Datasets: modular addition mod p dataset (n,k)-sparse parity dataset group composition tables for S3, S4, S5

Metrics: normalized L_{2,nu} margin maximum Fourier power of neuron embeddings neuron frequency/representation concentration

Baselines: ReLU network with L2 regularization

Builds on: grokking max-margin implicit bias Nanda et al. modular addition circuit analysis Lyu & Li normalized margin convergence

Closest papers by meaning

• Emergence in non-neural models: grokking modular arithmetic via average gradient outer product (ICML 2025 · similarity 0.86)
• Learning High-Degree Parities: The Crucial Role of the Initialization (ICLR 2025 · similarity 0.86)
• Global Convergence and Rich Feature Learning in $L$-Layer Infinite-Width Neural Networks under $\mu$ Parametrization (ICML 2025 · similarity 0.85)
• Uncovering a Universal Abstract Algorithm for Modular Addition in Neural Networks (NeurIPS 2025 · similarity 0.85)
• Composing Global Solutions to Reasoning Tasks via Algebraic Objects in Neural Nets (NeurIPS 2025 · similarity 0.85)
• Sharp feature-learning transitions and Bayes-optimal neural scaling laws in extensive-width networks (NeurIPS 2026 · similarity 0.85)