Multi-Index Models

Follow this topic Ask about this topic

Multi-index models represent a high-dimensional input through a small set of directions, then apply a nonlinear function to those projections; learning these directions can make prediction more sample-efficient and reveal useful features. Approaches include hyper-kernel ridge regression and gradient-based subspace recovery, neural-network SGD and gradient-flow analyses, and approximate message passing in high-dimensional Gaussian settings. Results study when methods recover the hidden subspace before achieving accurate prediction, and how symmetry, incremental feature learning, and flatness affect recovery and generalization. A central tension is that models may be statistically learnable yet computationally difficult: statistical-query limits do not always predict vanilla SGD, and success can depend on activation functions, initialization, noise, and model structure.

Latest papers

11 papers1 paper in the last four weeks, against 1 the four weeks before. 0.0% of all new papers.

Symmetry-Aware Feature Learning: A Polynomial Separation for Multi-Index Models
Oct 6, 2026Jivan Waber, Vanessa Piccolo, Yatin Dandi +1Representation Learning Data Augmentation
Information, Learning and Physics Laboratory École Polytechnique Fédérale de Lausanne (EPFL) · Statistical Physics of Computation Laboratory École Polytechnique Fédérale de Lausanne (EPFL)
Learning Orthogonal Multi-Index Models Beyond Small Initialization: Incremental Learning, Competitive Dynamics and Symmetry
Sep 9, 2026Mo Zhou, Weihang Xu, Simon S. Du +1Shallow Neural Networks Orthogonal Representation Learning
University of Washington · Amazon, Inc.
Replica Symmetry Breaking and Algorithmic Thresholds in Empirical Risk Minimization under Multi-Index Model
Jun 26, 2026Andrea Montanari, Kangjie ZhouApproximate Message Passing Statistical Learning Theory
Department of Mathematics and Department of Statistics, Stanford University · Department of Statistics, Columbia University
CAMI: Cost-Aware Agent-Guided Multi-Indexing for Semantic Retrieval
Jun 14, 2026Adnan Qidwai, Anand Eswaran, Sonam Mishra +2Semantic Search Information Retrieval
IBM Software Innovation Lab India
Flatness and Generalization: Learning Multi-Index Models with Homogeneous Neural Networks
Jun 3, 2026Harsh Vardhan, Hossein Taheri, Arya MazumdarNeural Network Generalization Flat Minima
Average Gradient Outer Product in kernel regression provably recovers the central subspace for multi-index models
May 14, 2026Libin Zhu, Damek Davis, Dmitriy Drusvyatskiy +1Kernel Ridge Regression Representation Learning
Department of Mathematics, University of Washington, Seattle, WA 98195 · Wharton Department of Statistics and Data Science, University of Pennsylvania, Philadelphia, PA 19104, USA · Department of Mathematics, U. Washington, Seattle, WA 98195 +1
A Noise Sensitivity Exponent Controls Large Statistical-to-Computational Gaps in Single- and Multi-Index Models
Mar 18, 2026Leonardo Defilippis, Florent Krzakala, Bruno Loureiro +1Statistical Learning Theory Multi-Index Models
Departement d’Informatique, École Normale Supérieure, PSL & CNRS · Information, Learning and Physics Laboratory, École Polytechnique Fédérale de Lausanne (EPFL) · INRIA Paris
Dataset Distillation Efficiently Encodes Low-Dimensional Representations from Gradient-Based Learning of Non-Linear Tasks
Mar 16, 2026Yuri Kinoshita, Naoki Nishikawa, Taro ToyoizumiTwo-Layer Neural Networks Dataset Distillation
The University of Tokyo, Tokyo, Japan · Laboratory for Neural Computation and Adaptation, RIKEN Center for Brain Science, Wako, Japan · RIKEN Center for Advanced Intelligence Project, Nihonbashi, Japan
Limitations of SGD for Multi-Index Models Beyond Statistical Queries
Feb 5, 2026Daniel Barzilai, Ohad ShamirSingle-Index Models Statistical Learning Theory
Weizmann Institute of Science · University of Toronto
Learning Multi-Index Models with Hyper-Kernel Ridge Regression
Oct 2, 2025Shuo Huang, Hippolyte Labarrière, Ernesto De Vito +2Kernel Ridge Regression Kernel Regression
Istituto Italiano di Tecnologia, Genoa, Italy · MaLGa - DIBRIS - Universit`a di Genova, Genoa, Italy · MaLGa - DIMA - Universit`a di Genova, Genoa, Italy +2
Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension
Jul 1, 2024Gautam Chandrasekaran, Adam Klivans, Vasilis Kontonis +2Agnostic Learning Margin-Based Learning
a University of Texas at Austin · b University of California, Los Angeles

Oct 6, 2026J/K move · Enter open · S save

Symmetry-Aware Feature Learning: A Polynomial Separation for Multi-Index Models

Jivan Waber, Vanessa Piccolo, Yatin Dandi, Florent Krzakala

Information, Learning and Physics Laboratory École Polytechnique Fédérale de Lausanne (EPFL) · Statistical Physics of Computation Laboratory École Polytechnique Fédérale de Lausanne (EPFL)

Representation Learning Data Augmentation Equivariant Representation Learning Statistical Learning Theory Multi-Index Models

Open paper AskPDF arXiv

We establish a polynomial sample complexity separation between symmetry-aware and symmetry-agnostic feature learning. We study growing-rank multi-index models with high-dimensional Gaussian covariates in

\mathbb{R}^d

and

r=Θ(d^δ)

teacher directions forming a cyclic symmetry orbit, where

0<δ<1/2

. We compare three ways of exploiting this structure: architectural weight sharing, data augmentation over the full symmetry group, and learning without access to the symmetry. In particular, we analyze a symmetry-tied convolutional network, an untied network, and the same untied network trained with full-group data augmentation, using spherical online SGD with correlation loss. For a class of polynomial links with information exponent

p\ge3

, we prove matching sample complexity bounds up to logarithmic factors: the tied and augmented learners achieve weak directional recovery in

\widetildeΘ(d^{p-1})

samples, whereas the symmetry-agnostic learner requires

\widetildeΘ(rd^{p-1})

. For the pure quadratic Hermite link, the same separation holds for weak recovery of the teacher subspace, with sample complexities

\widetildeΘ(d)

and

\widetildeΘ(rd)

, respectively. Thus, full-group data augmentation matches the sample efficiency of architectural weight sharing, and both provide a polynomial advantage over training without symmetry. For

p\ge3

, the proof reveals a two-stage mechanism: fluctuations at initialization select one direction in the teacher orbit, after which localized growth amplifies its overlap to the weak recovery scale while competing overlaps remain near their initialization scale.