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 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Matrix discrepancy from Quantum communication

量子通信的矩阵差异

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

Local Statistics, Semidefinite Programming, and Community Detection*

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

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

On statistical inference when fixed points of belief propagation are unstable

置信传播不稳定点时的统计推断

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