Learning Multi-Index Models with Hyper-Kernel Ridge Regression
This work provides theoretical insights into the success of deep learning for researchers, though it is incremental as it builds on existing compositional models and methods.
The paper tackles the problem of understanding when deep neural networks outperform kernel methods in high-dimensional learning by studying multi-index models, and shows that hyper-kernel ridge regression can adaptively learn these models with improved sample complexity, overcoming the curse of dimensionality.
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.