权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

职业：使用平方和证明系统的最优高维估计器

基本信息

批准号：
2143246
负责人：
Tselil Schramm
金额：
$ 64.95万
依托单位：
Stanford University
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2022
资助国家：
美国
起止时间：
2022-02-01 至 2027-01-31
项目状态：
未结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2143246&HistoricalAwards=false
关键词：
CAREER Optimal Dimensional Estimators Using

项目摘要

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.

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