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

优化是现代信号和信息处理的核心。近年来，信息量的激增使得计算和算法问题变得越来越重要。该项目有助于理解各种随机优化算法在处理高维数据时的基本限制。由于这些算法是许多估计，推理和机器学习任务中的主力，因此这项研究很好地对许多应用产生了重大而广泛的影响。例如，实时或低延迟医学图像重建、电网分布式计算以及用于图像理解的人工神经网络训练。在本项目中，PI研究了一系列有效的随机迭代算法，用于解决各种信号估计任务中出现的大规模凸和非凸优化问题。这个项目的主要目标是分析这些随机迭代算法在高维极限下的精确动力学。这种渐近分析提供了一个完整的表征的典型行为的算法。理论研究借鉴了平均场相互作用粒子系统的统计物理学，随机过程的弱收敛理论，信号处理，信息论和优化技术。理论分析可以用来阐明这种随机方法的有效性，为大规模优化，并建立其基本的性能界限。从分析中获得的见解也可以用来指导新的可扩展算法的设计，以实现估计精度，样本复杂性和计算复杂性之间的最佳权衡。

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.