CIF: Small: Precise Computational and Statistical Tradeoffs for Iterative Signal Estimation and Supervised Learning

University Of Southern California, Los Angeles CA

Investigators

Abstract

Due to the proliferation of new sensors and acquisition devices, massive data sets are gathered in many modern applications ranging from medical imaging to online advertisement. Conventional statistical signal estimation and machine learning theory aims to understand how the predictive ability or accuracy of data analysis algorithms scales with data sizes. However, given the sheer size of modern data sets, these classical statistical theories are insufficient as algorithms have to operate effectively under a variety of new constraints such as, limited processing time, fixed computational budget and communication constraints. This project aims to develop the fundamental limits of how statistical accuracy tradeoffs with these resource constraints together with algorithms that nearly achieve such performance limits. The resulting signal estimation and learning algorithms are deployed in novel applications aimed at decreasing the acquisition time in medical imaging devices and speeding up parallelized algorithms in other data processing domains. Parts of this project are integrated into an advanced graduate class and select results will serve to motivate K-12 students to pursue careers in STEM (Science, Technology, Engineering and Math). In this project, the team of researchers study a family of convex optimization algorithms used for signal estimation and unsupervised learning. The main goal of this project is to understand how the statistical performance of iterative convex optimization algorithms tradeoffs with various statistical and computational resources such as run time, data size, communication, etc. The theoretical investigations utilizes techniques from convex analysis, probability, and information theory. The theoretical analysis can be used to establish fundamental performance bounds for popular convex optimization problems and guide the design of new algorithms that achieve optimal trade-offs between competing resource constraints. 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.