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

统计估计问题在现代世界中无处不在。许多重要的机器学习任务都属于估计的范畴，包括回归、主成分分析和聚类。在更广泛的科学中，从数据中估计参数对于追求知识是至关重要的：在生物学中，估计蛋白质网络结构；在天文学和物理学中，根据衍射图估计恒星物体的空间位置；在生物化学中，根据光谱和成像数据估计蛋白质的三维结构；等等。在高维环境中，待估计的量描述了大型、复杂的系统，有效计算的作用至关重要。尽管高维统计估计问题无处不在，但对其计算前景的理解仍然是原始的。本项目的目标是通过平方和(SOS)算法和证明系统的镜头来开发和表征最优估计算法。平方和算法是一类功能强大的半定规划算法，是(经验上和精确意义上)最强大的已知算法之一，而它们与平方和证明系统的关系也允许系统地进行算法设计。该项目分为三个主要任务：(I)使用SOS预测统计估计的计算极限，为自动预测我们最强大的算法的计算极限提供统一的理论；(Ii)通过SOS为重要问题(如集群、图形模型和块模型)提供估计的最佳算法；(Iii)使平方和算法变得实用，用轻量级算法取代SOS程序的优化。该奖项反映了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.