Research map / Optimization / Implicit bias and generalization

Symmetric Single Index Learning

ICLR 2024 · Optimization › Implicit bias and generalization · approach: Low-rank and single-index recovery · 0 citations (OpenAlex)

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 gradient flow on a correlational loss with a DeepSets student recovers a planted symmetric single-index direction under the Vandermonde measure, with rates governed by a symmetric analogue of the information exponent.

Problem

Provable feature learning with gradient methods is well understood for two-layer single-index models, but not for permutation-invariant architectures such as DeepSets, which are three-layer by construction. The paper asks whether gradient descent can provably recover a symmetric single-index target.

Approach

Model the teacher as a single-index function in the feature space of normalized power-sum polynomials, and use complex-valued inputs on the unit circle with the squared Vandermonde measure, where power-sum monomials are orthogonal in a Hermite-like way. Train a DeepSets student (only second layer trained) with a regularized correlational loss using a single monomial student link, and reduce gradie

Key results

• Under gradient flow, the paper proves convergence to epsilon accuracy in O(log 1/epsilon) time for information exponent s=1 and O(2^{s^2} r_0^{-4s} + log 1/epsilon) for s>1.
• With the specific activation sigma(z)=arctan(xi z)+xi z arctan(xi z), the corollary gives r_0 >= O(N^{-7/4}) with probability 1/3 - 2exp(-O(N)), yielding time O(2^{s^2} N^{7s} + log 1/epsilon) for s>1.
• Experiments with N=25, M=100 and link coefficients alpha_3=alpha_4=alpha_5=1/sqrt(3) show very high strong-recovery rates with the correlational loss L, while the loss L-hat often gets stuck with r below 1.

Measured effects reported in the paper

Surprising findings

• The correlation r and orthogonal component v initially decrease, so the analysis needs a delicate argument to avoid the saddle at r=0.
• The regularized correlational loss L-hat often gets stuck at local minima, while the simpler monomial-student loss L recovers reliably.

Limitations

• Analysis is for gradient flow on the population loss; discretization to SGD/GD is left open.
• Restricted to complex scalar inputs on the unit circle with the Vandermonde measure, analytic activations, and link functions supported on degree up to sqrt(N).
• Recovers the hidden direction only up to an s-th root of unity; the analysis is pessimistic relative to experiments.

Experimental setup

Datasets: synthetic Vandermonde-distributed samples on the unit circle (N=25)

Benchmarks: synthetic student-teacher single-index setup (N=25, M=100)

Metrics: summary statistic r (correlation magnitude) cos(s*theta) v probability of strong recovery over runs

Baselines: correlational loss with projection (Arous et al.-style) unregularized loss L-tilde regularized loss L-hat with full link

Builds on: single-index model information exponent analysis DeepSets Hermite polynomial orthogonality for Gaussian single-index models

Closest papers by meaning

• Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit (NeurIPS 2024 · similarity 0.91)
• Learning Orthogonal Multi-Index Models: A Fine-Grained Information Exponent Analysis (NeurIPS 2025 · similarity 0.89)
• From Information to Generative Exponent: Learning Rate Induces Phase Transitions in SGD (NeurIPS 2025 · similarity 0.87)
• Sample and Computationally Efficient Robust Learning of Gaussian Single-Index Models (NeurIPS 2024 · similarity 0.86)
• Learning single index models via harmonic decomposition (NeurIPS 2025 · similarity 0.86)
• Can Neural Networks Achieve Optimal Computational-statistical Tradeoff? An Analysis on Single-Index Model (ICLR 2025 · similarity 0.86)