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的算法针对这类问题，而且还产生了可能产生算法，这些算法与证明是与信念促进/消息传播算法的性能相匹配的算法，这是一种算法的方法，该方法被认为是对贝耶斯的最佳奖励，这是对贝耶斯的最佳选择。和更广泛的影响审查标准。

项目成果

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