# Learning Multi-Index Models with Hyper-Kernel Ridge Regression

arXiv: https://arxiv.org/abs/2510.02532 · HTML: https://mlsanity.com/paper/2510.02532/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 76 references that are in the map.
- First posted on arXiv 2 Oct 2025.

## Builds on (most cited first, 21 of 21)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Nonparametric regression using deep neural networks with ReLU activation function](https://mlsanity.com/paper/1708.06633/) (2017)
- [Breaking the Curse of Dimensionality with Convex Neural Networks](https://mlsanity.com/paper/1412.8690/) (2014)
- [Why and When Can Deep -- but Not Shallow -- Networks Avoid the Curse of Dimensionality: a Review](https://mlsanity.com/paper/1611.00740/) (2016)
- [High-dimensional Asymptotics of Feature Learning: How One Gradient Step Improves the Representation](https://mlsanity.com/paper/2205.01445/) (2022)
- [SGD learning on neural networks: leap complexity and saddle-to-saddle dynamics](https://mlsanity.com/paper/2302.11055/) (2023)
- [Online stochastic gradient descent on non-convex losses from high-dimensional inference](https://mlsanity.com/paper/2003.10409/) (2020)
- [Learning with invariances in random features and kernel models](https://mlsanity.com/paper/2102.13219/) (2021)
- [How Two-Layer Neural Networks Learn, One (Giant) Step at a Time](https://mlsanity.com/paper/2305.18270/) (2023)
- [Neural Networks Efficiently Learn Low-Dimensional Representations with SGD](https://mlsanity.com/paper/2209.14863/) (2022)
- [Smoothing the Landscape Boosts the Signal for SGD: Optimal Sample Complexity for Learning Single Index Models](https://mlsanity.com/paper/2305.10633/) (2023)
- [A Theory of Non-Linear Feature Learning with One Gradient Step in Two-Layer Neural Networks](https://mlsanity.com/paper/2310.07891/) (2023)
- [Linear Recursive Feature Machines provably recover low-rank matrices](https://mlsanity.com/paper/2401.04553/) (2024)
- [Survey on Algorithms for multi-index models](https://mlsanity.com/paper/2504.05426/) (2025)
- [Convergence of Alternating Gradient Descent for Matrix Factorization](https://mlsanity.com/paper/2305.06927/) (2023)
- [Smooth over-parameterized solvers for non-smooth structured optimization](https://mlsanity.com/paper/2205.01385/) (2022)
- [Iteratively reweighted kernel machines efficiently learn sparse functions](https://mlsanity.com/paper/2505.08277/) (2025)
- [Backtracking strategies for accelerated descent methods with smooth composite objectives](https://mlsanity.com/paper/1709.09004/) (2017)
- [On Learning the Optimal Regularization Parameter in Inverse Problems](https://mlsanity.com/paper/2311.15845/) (2023)
- [Enhanced Feature Learning via Regularisation: Integrating Neural Networks and Kernel Methods](https://mlsanity.com/paper/2407.17280/) (2024)
- [Generalization Properties of hyper-RKHS and its Applications](https://mlsanity.com/paper/1809.09910/) (2018)

## Built on by (most cited first, 3 of 3)

- [Learning Sparse Compositional Functions with Norm-Constrained Neural Networks](https://mlsanity.com/paper/2605.25608/) (2026)
- [Average Gradient Outer Product in kernel regression provably recovers the central subspace for multi-index models](https://mlsanity.com/paper/2605.15082/) (2026)
- [How does feature learning reshape the function space?](https://mlsanity.com/paper/2605.17718/) (2026)

## Abstract (arXiv)

Deep neural networks excel in high-dimensional problems, outperforming models such as kernel methods, which suffer from the curse of dimensionality. However, the theoretical foundations of this success remain poorly understood. We follow the idea that the compositional structure of the learning task is the key factor determining when deep networks outperform other approaches. Taking a step towards formalizing this idea, we consider a simple compositional model, namely the multi-index model (MIM). In this context, we introduce and study hyper-kernel ridge regression (HKRR), an approach blending neural networks and kernel methods. Our main contribution is a sample complexity result demonstrating that HKRR can adaptively learn MIM, overcoming the curse of dimensionality. Further, we exploit the kernel nature of the estimator to develop ad hoc optimization approaches. Indeed, we contrast alternating minimization and alternating gradient methods both theoretically and numerically. These numerical results complement and reinforce our theoretical findings.