Efficient and Robust Learning of Multi-index Models
Abstract
Approved for Public Release.Multi-index models (MIMs) are prevalent across various supervised and unsupervised learning settings, as they effectively capture hidden lower-dimensional structure within high-dimensional datasets. While such models have been studied in isolation by several communities over the last decades, our understanding of the complexity of learning MIMs remains surprisinglypoor. Concretely, in most regimes of interest, no computationally efficient learning algorithms are known. On the other hand, in the few cases where efficient algorithms do exist, they tend to be highly sensitive to corrupted data and utilize their data suboptimally. This project aims to address these limitations by developing a comprehensive algorithmic framework for learning MIMs, emphasizing robustness, computational efficiency, and sample efficiency.The proposed research comprises three interrelated thrusts that will significantly advance our understanding of this area. The first thrust will focus on regression tasks for real-valued MIMs, both under minimal assumptions and for natural classes of neural networks. The second thrust will study classification tasks for discrete-valued MIMs, including multiclass linear classifiers and intersections of halfspaces. The third thrust will study unsupervised MIMs with a focus on latent-variable models. A unifying theme of the research is the development of novel algorithmic techniques that are broadly applicable across all three thrusts. The outcomes of this project have the potential to yield scalable, noise-resistant, and data-efficient algorithms for critical machine learning tasks involving structured data. These advancements could also have future Navy relevance for applications of interest to the Office of Naval Research (ONR), including image and signals intelligence.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Apr 10, 2025
- Source ID
- N000142512268
Entities
People
- Ilias Diakonikolas
Organizations
- Office of Naval Research
- United States Navy
- University of Wisconsin System