CRII: CIF: Approximate Message Passing Algorithms for High-Dimensional Estimation

由于过去几十年来计算能力的显著提高，在生物学、天文学和金融等领域收集的数据量大大增加。由于新数据的爆炸式增长，许多现代科学和工程应用需要分析和学习更大的数据集和比该领域以前考虑过的更复杂的问题。研究人员面临的一个主要挑战是了解需要多少数据或信息来解决如此复杂的统计问题，以及如何最有效地利用这些数据来了解手头的实际应用。本项目通过为这些设置开发和分析计算效率高的算法和统计程序的性能来探索这些问题。该研究将汇集信息理论、统计物理和应用概率的工具和思想，作为理解现代高维统计问题和复杂机器学习任务的框架，这些问题是工程和数据科学的核心挑战。正如该项目的研究是跨学科的，所追求的教育活动也是跨学科的，其重点是使非专家能够获得研究成果，为来自计算和数据科学中代表性不足的社区的学生增加机会，并培养具有多学科技能和研究兴趣的新一代数据科学家。该项目研究了一类计算效率高的算法，称为近似消息传递或AMP，用于高维统计推断和估计任务，这些任务是许多实际应用的基础，例如医疗保健和安全成像或使用人工智能构建自动驾驶汽车。此外，由于AMP允许对其渐近性能进行精确表征，因此此类算法已被用于为机器学习和统计学中的估计问题建立理论。在许多此类应用中，AMP在准确性和运行时间方面都优于最佳竞争算法。利用信息理论、信号处理、机器学习、概率和统计物理等技术，该项目的目标是显著扩展和改进AMP算法的理论基础，以便(i)大大扩展算法在高维估计中的能力，（ii）表征现有AMP算法的理论特性，以解决更一般的问题设置。（iii）为AMP算法及其支持理论创造新的应用领域。这项工作将导致AMP在机器学习和人工智能等新兴领域的引入或更多使用。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Due a remarkable increase in computational power over the last few decades, the amount of data collected in fields such as biology, astronomy, and finance has expanded considerably. Because of this explosion of new data, many modern scientific and engineering applications require analysis of and learning on larger datasets and more complex problems than the field has ever considered before. A major challenge for researchers is to understand how much data, or information, is necessary to solve such complex statistical problems, and given that data, how to most effectively use it to gain insight about the real-world application at hand. This project explores these questions by developing and analyzing the performance of computationally-efficient algorithms and statistical procedures for these settings. The research will bring together tools and ideas from information theory, statistical physics, and applied probability to use as a framework for understanding modern, high-dimensional statistics problems and complex machine learning tasks that are core challenges in engineering and data science. Just as the research in this project is interdisciplinary, so are the educational activities pursued, which focus on making research outcomes accessible to non-experts, increasing opportunities for students from underrepresented communities in computing and data science, and training a new generation of data scientists with multi-disciplinary skillsets and research interests.This project studies a class of computationally-efficient algorithms, referred to as approximate message passing or AMP, that are used for high-dimensional statistical inference and estimation tasks that underlie many practical applications such as imaging in healthcare and security or building autonomous vehicles using artificial intelligence. Moreover, because AMP allows for exact characterization of its asymptotic performance, such algorithms have been used to establish theory for estimation problems in machine learning and statistics. In many of these applications, AMP outperforms the best competing algorithms in both accuracy and runtime. Drawing on techniques from information theory, signal processing, machine learning, probability, and statistical physics, the goal of the project is to significantly expand and improve the theoretical foundations of AMP algorithms in order to (i) greatly extend the algorithm's capabilities in high-dimensional estimation, (ii) characterize the theoretical properties of the existing AMP algorithms for more general problem settings, and (iii) create new application areas for AMP algorithms and their supporting theory. The work will lead to the introduction or greater use of AMP in burgeoning fields like machine learning and artificial intelligence.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.