Research map / Optimization / Implicit bias and generalization
Learnability of high-dimensional targets by two-parameter models and gradient flow
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 two-parameter models can GF-learn d-dimensional targets with arbitrarily high probability under a known distribution, while underparameterized models (W<d) have non-learnable target sets dense in R^d and elementary-function models have measure-zero learnable sets.
Problem
Whether models with fewer parameters than the target dimension (W<d) can learn high-dimensional targets by gradient flow, given that small models have rough loss surfaces with spurious local minima.
Approach
Constructs a C-infinity two-parameter map Phi: R^2 -> R^d via an infinite hierarchical (aligned box-splitting) construction so that gradient flow from w=0 converges for a Cantor set of targets of almost full measure; also proves that GF-learnable sets are not dense for W<d under nondegeneracy, and that Pfaffian (hence most elementary) models have measure-zero learnable sets.
Key results
- For any Borel probability measure mu on R^d and epsilon>0, there is a C-infinity map Phi: R^2 -> R^d with mu(R^d minus F_Phi) < epsilon (main theorem).
- If W<d and Phi is C^2 with full-rank Jacobian at 0, the GF-learnable set F_Phi is not dense in R^d.
- For Pfaffian maps Phi: R^W -> R^d with W<d, the closure of the image has Lebesgue measure 0, so learnable targets have Lebesgue measure 0.
Surprising findings
- Two parameters suffice for almost-guaranteed GF learning of arbitrary-distribution targets, despite small-model pessimism.
- A simple sin-based model with dense image still has Lebesgue-measure-zero learnable set.
Limitations
- Main construction is non-elementary and hand-crafted, so not practically implementable by standard models.
- Results restricted to finite-dimensional targets and probability (finite-measure) distributions; infinite-dimensional and infinite-measure cases are open.
- Elementary-function non-learnability is proven only for Pfaffian models; the general conjecture remains open.
Experimental setup
Metrics: Lebesgue measure of learnable set mu-measure of non-learnable set
Builds on: Kolmogorov-Arnold superposition theorem Khovanskii Pfaffian theory Borsuk-Ulam theorem
Closest papers by meaning
- Asymptotics of feature learning in two-layer networks after one gradient-step (ICML 2024 · similarity 0.85)
- The Benefits of Reusing Batches for Gradient Descent in Two-Layer Networks: Breaking the Curse of Information and Leap Exponents (ICML 2024 · similarity 0.84)
- Testably Learning Polynomial Threshold Functions (NeurIPS 2024 · similarity 0.84)
- Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale (NeurIPS 2026 · similarity 0.84)
- Multiclass Loss Geometry Matters for Generalization of Gradient Descent in Separable Classification (NeurIPS 2025 · similarity 0.84)
- Gradient Flow Provably Learns Robust Classifiers for Orthonormal GMMs (ICML 2025 · similarity 0.83)
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.