Research map / Optimization / Implicit bias and generalization
Learning Orthogonal Multi-Index Models: A Fine-Grained Information Exponent Analysis
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 for orthogonal multi-index models with a second-order plus higher-order (order L) link function, online spherical SGD with symmetric initialization and ridge regression recovers all directions with Õ(d P^{L-1}) samples, improving on the Õ(P d^{L-1}) of vanilla information-exponent analysis.
Problem
Information-exponent-based analyses of online SGD for multi-index models fail when the lowest Hermite degree is 2, since second-order terms only identify the subspace, and when higher-order terms are used alone the sample complexity scales as d^{L-1}.
Approach
Exploit both second-order and L-th order Hermite terms: the second-order term first drives neurons into the relevant subspace (norm ratio grows from Θ(P/d) to Θ(1)), then the L-th order term, started from Ω(1/P) coordinates rather than Õ(1/d), converges neurons to exact ground-truth directions, with a stochastic Gronwall-type lemma converting gradient-flow analysis to online SGD.
Key results
- Online spherical SGD with symmetric initialization and width m = Θ̃(P) recovers all P directions with Õ(d P^{L-1}) samples, versus Õ(P d^{L-1}) for vanilla information-exponent analysis.
- Gradient-flow stage 1.2 needs O(P^{L/2-1}) time to grow v_1^2 from Ω(1/P) to 3/4, versus O(d^{L-1}) if starting from Õ(1/d).
- Stage 1.1 norm ratio grows from Θ(P/d) to Θ(1) in Θ(log(d/P)) gradient-flow time, using only second-order terms.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use second-order terms to learn the relevant subspace before using higher-order terms to learn directions | Online SGD for orthogonal multi-index models · Orthogonal multi-index models | sample complexity: \tilde{O}(P d^{L-1}) -> \tilde{O}( d P^{L-1} ) | Helped |
| Include second-order terms alongside higher-order terms | Online SGD for orthogonal multi-index models · Orthogonal multi-index models | sample complexity: \tilde{O}( 1 / (P d^{L/2}) ) -> O(1) / (P d P^{L/2-1}) | Helped |
Surprising findings
- Second-order terms alone cannot recover directions: the relative ratios v_p^2/v_q^2 evolve only under the higher-order term, so the second-order term only identifies the subspace.
Limitations
- Requires orthonormal (isotropic) teacher directions; extension to near-orthogonal or non-isotropic signal strengths left open.
- Assumes isotropic signal strengths; non-isotropic case may collapse neurons to the largest direction.
Experimental setup
Datasets: synthetic Gaussian inputs with planted multi-index target
Metrics: sample complexity population MSE loss
Baselines: vanilla information exponent online SGD analysis Õ(P d^{L-1}) bound for near-orthogonal multi-index models
Builds on: information exponent (Ben Arous et al. 2021) generative exponent correlation loss online SGD analysis
Closest papers by meaning
- Online Learning and Information Exponents: The Importance of Batch size & Time/Complexity Tradeoffs (ICML 2024 · similarity 0.90)
- Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit (NeurIPS 2024 · similarity 0.90)
- From Information to Generative Exponent: Learning Rate Induces Phase Transitions in SGD (NeurIPS 2025 · similarity 0.90)
- Symmetric Single Index Learning (ICLR 2024 · similarity 0.89)
- The Generative Leap: Tight Sample Complexity for Efficiently Learning Gaussian Multi-Index Models (NeurIPS 2025 · similarity 0.89)
- Learning single index models via harmonic decomposition (NeurIPS 2025 · similarity 0.87)
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.