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

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

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.