CIF: Small: High-Dimensional Analysis of Stochastic Iterative Algorithms for Signal Estimation

Harvard University, Cambridge MA

Investigators

Abstract

Optimization lies at the heart of modern signal and information processing. In recent years, the soaring quantity of information that is being acquired and becoming available makes computational and algorithmic issues increasingly important. This project contributes to an understanding of the fundamental limits of various stochastic optimization algorithms when dealing with high-dimensional data. Since such algorithms are the workhorse in many estimation, inference, and machine learning tasks, this research is well-posed to make significant and broad impact on many applications. Examples include real-time or low-latency medical image reconstructions, distributed computation on power grids, and the training of artificial neural networks for image understanding. In this project, the PI studies a family of efficient stochastic iterative algorithms for solving large-scale convex and nonconvex optimization problems that arise in various signal estimation tasks. The broad goal in this project is to analyze the exact dynamics of these stochastic iterative algorithms in the high-dimensional limit. This asymptotic analysis provides a complete characterization of the typical behavior of the algorithms. The theoretical investigation draws upon techniques from the statistical physics of mean-field interactive particle systems, the weak convergence theory of stochastic processes, signal processing, information theory, and optimization. The theoretical analysis can be used to clarify the effectiveness of such stochastic methods for large-scale optimization and to establish their fundamental performance bounds. The insights obtained from the analysis can also be used to guide the design of new scalable algorithms to achieve optimal trade-offs between estimation accuracy, sample complexity, and computational complexity.