CAREER: Optimal High-Dimensional Estimators Using Sum-of-Squares Proof Systems

统计估计问题在现代世界中无处不在。许多重要的机器学习任务都属于估计的范畴，包括回归、主成分分析和聚类。在更广泛的科学领域，从数据中估计参数对追求知识至关重要：在生物学中，估计蛋白质网络结构;在天文学和物理学中，从衍射图案估计恒星物体的空间位置;在生物化学中，从光谱学和成像数据估计蛋白质的三维结构;在高维环境中，待估计的量描述了大型复杂系统，高效计算的作用至关重要。尽管高维统计估计问题的普遍存在，他们的计算景观的理解仍然primitive.The项目的目标是开发和表征最佳估计算法通过平方和（SoS）算法和证明系统的透镜。平方和算法是一类强大的半定编程算法，是已知最强大的算法之一（经验上和精确意义上），而它们与平方和证明系统的关系也允许系统化的算法设计方法。该项目分为三个主要目标：（i）预测统计估计的计算极限与SoS，给出一个统一的理论，自动预测我们最强大的算法的计算极限;（ii）通过SoS的重要问题，如聚类，图形模型和块模型的估计给出最佳算法;（iii）使平方和算法实用化，用轻量级算法取代对体系结构计划的优化。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Statistical estimation problems are ubiquitous in the modern world. A multitude of important machine-learning tasks fall under the umbrella of estimation, including regression, principal components analysis, and clustering. In the sciences more broadly, estimating parameters from data is crucial to the pursuit of knowledge: in Biology, estimating protein network structure; in Astronomy and Physics, estimating the spatial locations of stellar objects from diffraction patters; in Biochemistry, estimating the three-dimensional structure of a protein from spectroscopy and imaging data; and so on. In high-dimensional settings, where the quantities to be estimated describe large, complicated systems, the role of efficient computation is crucial. Despite the ubiquity of high-dimensional statistical estimation problems, understanding of their computational landscape remains primitive.The goal of this project is to develop and characterize optimal estimation algorithms through the lens of the sum-of-squares (SoS) algorithm and proof system. The sum-of-squares algorithm is a powerful class of semidefinite programming algorithms which are among the most powerful known algorithms (empirically and in a precise sense), while their relationship to the sum-of-squares proof system also allows for a systematic approach to algorithm design. The project is organized into three primary thrusts: (i) predicting the computational limits of statistical estimation with SoS, giving a unified theory for automatically predicting the computational limits of our most powerful algorithms; (ii) giving optimal algorithms for estimation via SoS for important problems such as clustering, graphical models, and block models; (iii) making sum-of-squares algorithms practical, replacing optimization over SoS programs with lightweight algorithms.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.