Research map / Learning theory and algorithms / Sample complexity
Learning single index models via harmonic decomposition
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.
Proposes spherical harmonics as the natural basis for learning single-index models under spherically symmetric inputs, deriving SQ/LDP lower bounds and matching spectral, tensor-unfolding and online SGD estimators, and recovering Gaussian SIM results.
Problem
Characterizing the sample and runtime complexity of recovering the hidden direction w* in single-index models beyond Gaussian inputs, and explaining why existing Gaussian-specific algorithms (SGD, landscape smoothing, partial trace) reach optimal rates.
Approach
Exploit rotational symmetry: expand the likelihood ratio in spherical harmonics (Gegenbauer coefficients) of the direction z = x/||x||, which decouples SQ/LDP lower bounds across harmonic subspaces V_{d,l}; each subspace is matched by a spectral, harmonic tensor-unfolding, or online SGD estimator, and sample-optimal and runtime-optimal degrees can differ for general spherical SIMs.
Key results
- For Gaussian SIMs with generative exponent sk*, the spectral algorithm achieves sample m = Theta(d^{sk*/2}) and runtime Theta~(d^{sk*/2+1}), matching SQ/LDP lower bounds.
- Without the norm ||x||, harmonic tensor unfolding achieves m = d^{sk*/2} with runtime d^{sk*+1} log d, and online SGD achieves m = d^{sk*-1} with runtime d^{sk*}.
- For a constructed mixture of spherical SIMs, the sample-optimal degree (10 sk) and runtime-optimal degree (4 sk) differ, so no single estimator attains both optimal sample and runtime complexity in that example.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the input norm ‖x‖₂ rather than only the normalized direction (ablation) | Gaussian SIM learning · Gaussian SIM | runtime: d^{{\rm sk}_\star} -> d^{{\rm sk}_\star/2+1} | Helped |
| Normalize inputs and discard ‖x‖₂ (ablation) | Gaussian SIM learning · Gaussian SIM | runtime: d^{{\rm sk}_\star/2+1} to d^{{\rm sk}_\star} | Hurt |
| Use landscape smoothing instead of vanilla SGD | Gaussian SIM learning · Gaussian SIM | sample complexity: \widetilde \Theta_d (d^{{\rm sk}_\star - 1}) -> \widetilde \Theta_d (d^{{\rm sk}_\star/2}) | Helped |
| Use landscape smoothing instead of vanilla SGD | Gaussian SIM learning · Gaussian SIM | runtime: \widetilde \Theta_d (d^{{\rm sk}_\star}) -> \widetilde \Theta_d (d^{{\rm sk}_\star/2 +1}) | Helped |
| Use harmonic tensor unfolding at the sample-optimal degree rather than the runtime-optimal degree | Spherical SIM with the constructed mixture distribution · Constructed mixture example | sample complexity: \widetilde \Theta_d ( d^{6 {\rm sk}_\star}) -> \widetilde \Theta_d ( d^{5 {\rm sk}_\star}) | Helped |
| Use harmonic tensor unfolding at the runtime-optimal degree rather than the sample-optimal degree | Spherical SIM with the constructed mixture distribution · Constructed mixture example | runtime: \widetilde \Theta_d ( d^{10 {\rm sk}_\star}) -> \widetilde \Theta_d ( d^{8 {\rm sk}_\star}) | Helped |
| Use online SGD on the degree-sk⋆ Hermite neuron instead of landscape smoothing | Gaussian SIM learning · Gaussian SIM | runtime: \widetilde \Theta_d (d^{{\rm sk}_\star}) vs. \widetilde \Theta_d (d^{{\rm sk}_\star/2 +1}) | Hurt |
Surprising findings
- Normalizing inputs to unit norm (discarding the radial component) raises the optimal Gaussian SIM runtime from d^{sk*/2+1} to d^{sk*}, while sample complexity is unchanged.
- Optimal Gaussian SIM algorithms always lie in degree-1 or degree-2 harmonic subspaces, even though vanilla SGD is dominated by degree-sk* harmonics.
Limitations
- Lower bounds are for detection and rely on SQ/low-degree heuristics and the low-degree conjecture, not unconditional hardness.
- Assumes the link distribution nu_d is known; the unknown-link case is left to future work.
- Optimality of sample-runtime trade-offs for mixed spherical SIMs is conjectured rather than proven; open whether a single estimator attains both for odd l >= 3.
Experimental setup
Metrics: sample complexity exponent in d runtime exponent in d correlation |<w_hat, w*>| >= 1/4
Baselines: online SGD with Hermite neuron (HeSGD) landscape smoothing (SmLD) partial trace estimator (PrTR)
Builds on: generative exponent framework (Damian et al.) online SGD on Hermite neuron (Ben Arous et al.) tensor unfolding (Montanari and Richard) partial trace estimator
Closest papers by meaning
- Sample and Computationally Efficient Robust Learning of Gaussian Single-Index Models (NeurIPS 2024 · similarity 0.88)
- Robustly Learning Monotone Single-Index Models (NeurIPS 2025 · similarity 0.87)
- The Generative Leap: Tight Sample Complexity for Efficiently Learning Gaussian Multi-Index Models (NeurIPS 2025 · similarity 0.87)
- Robustly Learning Single-Index Models via Alignment Sharpness (ICML 2024 · similarity 0.87)
- Learning Orthogonal Multi-Index Models: A Fine-Grained Information Exponent Analysis (NeurIPS 2025 · similarity 0.87)
- Symmetric Single Index Learning (ICLR 2024 · 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.