Research map / Learning theory and algorithms / Kernels and regression theory
On the Minimal Degree Bias in Generalization on the Unseen for non-Boolean Functions
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.
Studies whether min-degree interpolator (MDI) bias for Boolean GOTU generalization extends to non-Boolean inputs, proving it for random feature models in the small-feature regime and showing it can fail in the sparse regime and for Transformers on integer-valued inputs.
Problem
Whether the minimal degree interpolator bias found for Boolean sparse functions under generalization on the unseen (GOTU) carries over to non-Boolean (discrete q-ary or real-valued) inputs for random feature models and Transformers.
Approach
Proves that RF models with polynomial activations in the small-feature regime (weight scale to zero, fixed dimension) converge to minimal-degree interpolators for any real inputs, and shows the sparse regime and integer-embedded inputs can break the MDI bias, while roots-of-unity embeddings restore it.
Key results
- In the small-feature regime, RF with polynomial activation converges to the minimal degree interpolator for f=1 with GOTU x1=1 (e.g., (1+x)^2 gives 0.997 constant coefficient, d=15).
- In the sparse regime with (1+x)^2 activation, RF learns a linear function instead of the constant MDI (coefficient 0.624 on constant, 0.374 on x1).
- Transformer trained on x1*x2 with GOTU (x1-1)(x2-1)=0 and lr 1e-4 converges to a degree-4 interpolator rather than the linear MDI x1+x2-1.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the small features regime instead of the sparse regime | RF with (1+x)^2 · GOTU: f(x)=1, x1=1 | coefficient of x1: 0.374 ± 0.017 -> 0.001 ± 0.003 | Helped |
| Use the small features regime instead of the sparse regime | RF with Shifted ReLU · GOTU: f(x)=1, x1=1 | coefficient of x1: 0.217 ± 0.011 -> -0.001 ± 0.003 | Helped |
| Use the small features regime instead of the sparse regime | RF with Softplus · GOTU: f(x)=1, x1=1 | coefficient of x1: 0.208 ± 0.012 -> -0.001 ± 0.003 | Helped |
| Use the small features regime instead of the sparse regime | RF with ReLU · GOTU: f(x)=1, x1=1 | coefficient of x1: 0.431 ± 0.011 -> 0.430 ± 0.010 | No clear effect |
| Replace ReLU with Shifted ReLU | RF in the small features regime · GOTU: f(x)=1, x1=1 | coefficient of x1: 0.430 ± 0.010 -> -0.001 ± 0.003 | Helped |
| Use the sparse regime with Sigmoid rather than the other tested activations | RF · GOTU: f(x)=1, x1=1 | coefficient of x1: 0.374 ± 0.017; 0.431 ± 0.011; 0.217 ± 0.011; 0.007 ± 0.002; 0.208 ± 0.012 | Helped |
| Use (1+x)^4 activation in the sparse regime | RF · GOTU: f(x)=1, x1=1 | polynomial degree learned | Hurt |
| Use learning rate 10^-4 | Transformer · GOTU: f(x)=x1x2, x in {-1, 0, 1}^d | polynomial degree learned | Hurt |
| Use learning rate 10^-5 instead of 10^-4 | Transformer · GOTU: f(x)=x1x2, x in {-1, 0, 1}^d | polynomial degree learned: 10^-4 -> 10^-5; 6·10^6 | Mixed |
| Use a non-Boolean discrete domain for the multiplication task | Transformer · GOTU: f(x)=x1x2, x in {-1, 0, 1}^d | polynomial degree learned | Hurt |
Surprising findings
- Transformer learns a degree-4 interpolator instead of the linear minimal degree interpolator on integer inputs.
- RF in sparse regime with (1+x)^4 activation learns a quadratic when the MDI is constant, exceeding MDI by more than one degree.
Limitations
- Sparse regime with polynomial activations generally does not learn the MDI, so the result is limited to the small-feature regime or special targets.
- Transformer experiments are single-setting and sensitive to learning rate; longer training not clearly converged to an MDI.
- The theory covers polynomial activations; non-polynomial case (ReLU) relies on conjecture.
Experimental setup
Datasets: synthetic Gaussian samples synthetic discrete grids (integers, roots of unity)
Benchmarks: synthetic GOTU targets f=1, f=x1*x2, f=x2^2+x2+1
Metrics: fitted polynomial/Hermite coefficients distance to minimal degree interpolator
Baselines: Abbe et al. 2023 Boolean MDI results
Builds on: Abbe et al. 2023 minimal degree bias (GOTU, Boolean) random feature models Vision Transformer AdamW
Closest papers by meaning
- Efficient Learning of Truncated Boolean Product Distributions: Influence to the Rescue (NeurIPS 2026 · similarity 0.85)
- Towards Robust Out-of-Distribution Generalization Bounds via Sharpness (ICLR 2024 · similarity 0.85)
- Dimension-free deterministic equivalents and scaling laws for random feature regression (NeurIPS 2024 · similarity 0.85)
- Learning High-Degree Parities: The Crucial Role of the Initialization (ICLR 2025 · similarity 0.85)
- Testably Learning Polynomial Threshold Functions (NeurIPS 2024 · similarity 0.85)
- Towards Generalization beyond Pointwise Learning: A Unified Information-theoretic Perspective (ICML 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.