CIF: Small: Fundamental Limits of Empirical Risk Minimization in High Dimensions: A Unifying Gaussian Processes Approach

University Of California-Santa Barbara, Santa Barbara CA

Investigators

Abstract

At the core of most applications in signal processing and machine learning lie questions about statistical inference over large and complex data-sets. Conventional statistical theories used today, however, apply only when the number of unknown data parameters is small compared to the number of observations. Most modern data-sets, on the other hand, involve high-dimensional data, in which the number of unknown data parameters is large, if not larger, than the number of observations. Examples include high-resolution computational imaging modalities, large-scale wireless communication systems, and training of deep neural networks. This project develops new tools and theories that answer, in a precise way, fundamental statistical inference questions about popular algorithms for processing high-dimensional data. The results will contribute to the development of a complete theory about performance guarantees, fundamental limits, optimality, and robustness properties, with direct implications for modern signal-processing and machine-learning practice that underlie nearly all modern computing and communication systems. This research will instruct the cross-disciplinary training of graduate and undergraduate students at the University of California, Santa Barbara. The investigation will also shape the course material of a newly-developed graduate-level course about the mathematical principles of modern statistical signal-processing and data science. This project has two thrusts. The first thrust develops a unifying theory that sharply characterizes the statistical properties of convex empirical-risk minimization (ERM) methods in high-dimensions under generalized linear models. Sharp performance guarantees set this research apart from the majority of existing works, which only achieve loose bounds. These sharp guarantees will allow the investigators to address questions regarding fundamental limits of convex ERM estimators, optimal hyperparameter tuning, as well as quantifying the suboptimality gap of popular algorithmic choices. The second thrust demonstrates the value of the theoretical framework via applications to core signal-processing and machine-learning tasks. Notably, the investigators will develop a comprehensive study of high-dimensional linear classifiers, with a focus on core learning questions, such as: When are training data separable? How important is the choice of the loss function in high-dimensions? What regimes favor popular practices such as overparameterization and early-stopping? The results will serve as a benchmark for more sophisticated learning methods. At a technical level, this project advances the scope of methods based on Gaussian process inequalities beyond their original use in compressed sensing, thus bridging ideas from contemporary signal-processing and statistics with optimization and machine learning. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.