CIF: Small: Exploring and Exploiting the Universality Phenomenon in High-Dimensional Estimation

理解在实践中使用的各种算法的性能是信息处理和机器学习的核心问题。这样的性能保证对从业者来说非常重要。例如，数据分析人员需要知道为给定的推理算法收集多少数据样本才能达到具有足够统计准确性和置信度的预测。尽管在精确表征各种估计和推理算法的性能方面取得了重大进展，但理论与实践之间存在很大差距。大多数关于绩效分析的现有理论工作都依赖于对基础统计模型的强大且往往不切实际的假设。这种理想主义模型虽然对数学证明有用且方便，但往往不适合实际情况。本项目旨在利用普遍性现象，缩小绩效分析理论与实践的差距。简而言之，普遍性是一种观察，即普遍规律支配着许多高维系统的宏观行为，而不管它们在微观结构上有多么不同。通过利用普遍性现象，该项目有助于了解在更现实的模型下各种估计和推理方法的基本局限性。此外，该项目通过数据集的传播、研讨会/教程的组织以及对来自不同背景的学生的指导和支持，产生了广泛的影响。该项目的具体目标分为三个主要部分。在第一篇文章中，研究者分析了一类谱方法的精确渐近性能，这些方法在最近的信号估计的非凸优化方法中被广泛使用。特别是，该项目将当前的分析从独立集成扩展到更通用的集成，并探索了包括多路复用成像和多层神经网络训练在内的新应用。在第二个推力中，该项目研究了当感知矩阵从一般非独立集成中提取时正则化m估计器的性能界限。该项目的第三个重点是使用广泛的数值模拟来探索高维估计中普遍性现象的强度，鲁棒性以及局限性。数值实验是在前两个推力的理论和见解的指导下进行的。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Understanding the performance of various algorithms used in practice is a central question in information processing and machine learning. Such performance guarantees are very important to practitioners. For example, data analysts need to know how many data samples to collect for a given inference algorithm to reach a prediction with sufficient statistical accuracy and confidence. Although significant progress has been made in precisely characterizing the performance of various estimation and inference algorithms, a big gap exists between theory and practice. Most of existing theoretical work on performance analysis relies upon strong and often unrealistic assumptions on the underlying statistical models. Such idealistic models, while useful and convenient for mathematical proofs, often do not fit the situations encountered in practice. This project aims to narrow the gap between theory and practice in performance analysis by leveraging the universality phenomenon. In short, universality is the observation that universal laws govern the macroscopic behavior of many high-dimensional systems, irrespectively of how different they might be in their microscopic constructions. By exploiting the universality phenomenon, this project contributes to an understanding of the fundamental limits of various estimation and inference methods under more realistic models. In addition, this project makes broad impacts through the dissemination of datasets, the organization of workshops/tutorials, and the mentoring and supporting of students from diverse backgrounds.The specific goals of this project are organized into three main thrusts. In the first thrust, the investigator analyzes the exact asymptotic performance of a class of spectral methods that have been widely used in recent work on nonconvex optimization approaches for signal estimation. In particular, the project extends the current analysis from independent ensembles to more general ensembles, and explores new applications including multiplexed imaging and the training of multilayer neural networks. In the second thrust, the project investigates the performance bounds for regularized M-estimators when the sensing matrices are drawn from general non-independent ensembles. The third thrust of the project uses extensive numerical simulations to explore the strength, robustness, as well as the limitations of the universality phenomenon in high-dimensional estimation. The numerical experiments are guided by the theory and insights developed in the first two thrusts.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.