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.
