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

在信号处理和机器学习的大多数应用程序的核心在于对大型复杂数据集的统计推断问题。然而，今天使用的传统统计理论仅适用于未知数据参数的数量与观测值的数量相比很小的情况。另一方面，大多数现代数据集涉及高维数据，其中未知数据参数的数量如果不是比观测值的数量大的话，也是很大的。示例包括高分辨率计算成像模式、大规模无线通信系统和深度神经网络的训练。该项目开发新的工具和理论，以精确的方式回答有关处理高维数据的流行算法的基本统计推断问题。结果将有助于发展一个完整的理论，性能保证，基本限制，最优性和鲁棒性，直接影响现代信号处理和机器学习的实践，几乎所有的现代计算和通信系统的基础。本研究将指导加州大学圣巴巴拉分校研究生和本科生的跨学科培训。本研究还将为新开发的研究生课程《现代统计信号处理与数据科学的数学原理》提供教材。第一个推力发展了一个统一的理论，尖锐的特征凸风险最小化（ERM）方法在高维广义线性模型下的统计特性。尖锐的性能保证设置这项研究除了大多数现有的作品，只实现松散的界限。 这些明确的保证将使研究人员能够解决有关凸ERM估计量的基本限制，最佳超参数调整以及量化流行算法选择的次优差距的问题。第二个推力通过应用于核心信号处理和机器学习任务来展示理论框架的价值。值得注意的是，研究人员将对高维线性分类器进行全面的研究，重点关注核心学习问题，例如：训练数据何时可分离？在高维中损失函数的选择有多重要？什么样的机制更倾向于流行的做法，如过度参数化和提前停止？研究结果将作为更复杂的学习方法的基准。在技术层面上，该项目将基于高斯过程不等式的方法的范围扩展到压缩感知的原始用途之外，从而将当代信号处理和统计的思想与优化和机器学习联系起来。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.