AF:Small: Semidefinite Programming for High-dimensional Statistics

AF:Small：高维统计的半定规划

• 批准号: 2007676
• 负责人: Prasad Raghavendra
• 金额: $ 45万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-07-01 至 2024-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2007676&HistoricalAwards=false
• 关键词: AF; Small; Semidefinite; Programming; dimensional

With the deluge of data in almost all areas of human endeavor, there is a growing need for efficient algorithms to uncover underlying patterns and make inferences from the data. The field of statistics has long studied the task of making inferences from data, while largely ignoring issues of computational efficiency, but instead focusing on the quantity of data needed. As data gets increasingly high-dimensional, noisy and corrupted, computational efficiency becomes a vital concern. This project will use the powerful technique of semidefinite programming arising from optimization towards computational tasks in high-dimensional statistics. Specifically, the goal of this research is to develop a systematic approach for using semidefinite programming to design algorithms in high-dimensional statistics. The project will lead to an exchange of problems, definitions and technical tools between the areas of algorithms, statistics and statistical physics. The project includes synergistic educational and outreach activities such as devising a graduate class on complexity of statistics, facilitating undergraduate and graduate research work.There are three central themes to this research work. First, exploiting structure, how can algorithms based on semidefinite programming (SDP) exploit distributional assumptions about the input? More precisely, what is the correct way to encode information about the prior distribution of the input into the SDP-based algorithm? Second, how can algorithms be designed that are robust to noise, outliers or large deviations in the data? In its extreme form, how algorithms be designed with guarantees even in presence of an overwhelming number of outliers? Finally, using techniques inspired by statistical physics, many statistical problems are conjectured to exhibit a sudden change in their computational complexity -- a "computational phase transition". Can the lens of SDP be used to shed more light on these computational phase transitions? The proposed research would not only lead to a flurry of new SDP-based algorithms for this class of problems, but also potentially yield algorithms that provably match the performance of belief-propagation/message-passing algorithms, an algorithmic approach believed to be optimal for Bayesian inference.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.

随着人类奋进的几乎所有领域的数据泛滥，越来越需要有效的算法来发现潜在的模式并从数据中进行推断。 统计学领域长期以来一直在研究从数据中进行推断的任务，而在很大程度上忽略了计算效率的问题，而是专注于所需的数据量。 随着数据变得越来越高维，噪声和损坏，计算效率成为一个至关重要的问题。 这个项目将使用强大的技术，半定规划所产生的优化对计算任务的高维统计。 具体来说，本研究的目标是开发一种使用半定规划来设计高维统计算法的系统方法。 该项目将导致在算法、统计和统计物理学领域之间交流问题、定义和技术工具。 该项目包括协同教育和外展活动，例如设计一个关于统计复杂性的研究生班，促进本科生和研究生的研究工作。 首先，利用结构，基于半定规划（SDP）的算法如何利用关于输入的分布假设？ 更准确地说，将输入的先验分布信息编码到基于SDP的算法中的正确方法是什么？ 其次，如何设计算法，使其对数据中的噪声、离群值或大偏差具有鲁棒性？ 在其极端形式下，如何设计算法，即使在存在大量离群值的情况下也能保证？ 最后，利用受统计物理学启发的技术，许多统计问题被证明在计算复杂性上表现出突然的变化--“计算相变”。SDP的透镜能否用来揭示这些计算相变？ 所提出的研究不仅会为这类问题带来一系列新的基于SDP的算法，而且还可能产生可证明与信念传播/消息传递算法的性能相匹配的算法，该奖项反映了NSF的法定使命，并被认为值得通过使用基金会的智力价值和更广泛的评估来支持。影响审查标准。

项目成果

Local Statistics, Semidefinite Programming, and Community Detection*

局部统计、半定规划和社区检测*

• DOI: 10.1137/1.9781611976465.79
• 发表时间: 2021
• 期刊: Proceedings of the annual ACMSIAM symposium on discrete algorithms
• 作者: Jess Banks, Sidhanth Mohanty

On statistical inference when fixed points of belief propagation are unstable

• DOI: 10.1109/focs52979.2021.00047
• 发表时间: 2021-01
• 期刊: 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)
• 作者: Siqi Liu;Sidhanth Mohanty;P. Raghavendra

Matrix discrepancy from Quantum communication

量子通信的矩阵差异

• DOI: 10.1145/3519935.3519954
• 发表时间: 2022
• 期刊: ACM Symposium on Theory of Computing
• 作者: Hopkins, Samuel B.;Raghavendra, Prasad;Shetty, Abhishek
• 通讯作者: Shetty, Abhishek