Research map / Learning theory and algorithms / Sample complexity
Learning Multi-Index Models with Neural Networks via Mean-Field Langevin Dynamics
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-layer networks trained with mean-field Langevin dynamics learn multi-index models with sample complexity governed by an effective dimension f, with computation exponential in f in general but polynomial on the hypersphere under positive Ricci curvature.
Problem
Learning multi-index models with two-layer neural networks trained by gradient-based methods: sample complexity is often tied to information/leap/generative exponents, and mean-field Langevin training may need exponential compute in the ambient dimension.
Approach
Introduces an effective dimension f = tr(Sigma)/||Sigma^{1/2}U^T||_F^2 that controls both sample and computational complexity of MFLA under subGaussian inputs with general covariance, and shows polynomial-time convergence of MFLD when weights lie on a compact manifold with positive Ricci curvature (hypersphere) under an entropy-bound assumption.
Key results
- Sample complexity n = Otilde(f) for MFLA on multi-index models with subGaussian inputs, with computational complexity possibly exp(Otilde(f)) in the Euclidean setting.
- Under spiked covariance, f scales as d^{1-max{(gamma_2-2gamma_1),0}}, so f can be polylogarithmic in d in some regimes, giving quasipolynomial runtime.
- On the hypersphere with positive Ricci curvature, the LSI constant is independent of d and Delta-bar when Delta-bar = o(d), giving polynomial-in-d convergence time.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use MFLA with effective-dimension-adaptive analysis | Two-layer neural network for multi-index models · SubGaussian data with general covariance | sample complexity: n = \tilde{\mathcal{O}}( f) | Helped |
| Use MFLA instead of a fixed-grid method | Learning multi-index models · Anisotropic data with low effective dimension | computational complexity | Helped |
| Constrain weights to a compact manifold with positive Ricci curvature | MFLD · Multi-index models under the Riemannian assumptions | computational complexity | Helped |
| Use the Euclidean weight space rather than a positively curved compact manifold | MFLD · Multi-index models under comparable assumptions | computational complexity | Hurt |
Surprising findings
- In the Euclidean setting the LSI constant scales as exp(beta), so the same assumptions that give polynomial time on the hypersphere yield exponential time there.
Limitations
- Exponential computational complexity in f remains in the general Euclidean setting.
- Polynomial-time guarantee on the hypersphere requires an entropy-bound assumption (Delta-bar = o(d)), which is not verified for all targets; the question of Delta-bar of order f for k-index models in the Riemannian setting is open.
- Analysis focuses on k = O(1) and on the continuous-time or idealized dynamics, with discretization costs only heuristically argued.
Experimental setup
Metrics: excess risk sample complexity LSI constant
Baselines: fixed-grid convex optimization rotationally invariant kernels statistical query learners two-timescale MFLD
Builds on: mean-field Langevin dynamics information exponent generative exponent Bakry-Emery theory
Closest papers by meaning
- Mean-field Underdamped Langevin Dynamics and its Spacetime Discretization (ICML 2024 · similarity 0.88)
- Mean-Field Langevin Dynamics for Signed Measures via a Bilevel Approach (NeurIPS 2024 · similarity 0.88)
- Mean-field Analysis on Two-layer Neural Networks from a Kernel Perspective (ICML 2024 · similarity 0.88)
- Dynamical Decoupling of Generalization and Overfitting in Large Two-Layer Networks (NeurIPS 2025 · similarity 0.87)
- Improved Particle Approximation Error for Mean Field Neural Networks (NeurIPS 2024 · similarity 0.87)
- Learning quadratic neural networks in high dimensions: SGD dynamics and scaling laws (NeurIPS 2025 · similarity 0.86)
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.