AF:Small: Semidefinite Programming for High-dimensional Statistics

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

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.