CAREER: Statistics through the Sum of Squares Lens

职业：通过平方和透镜进行统计

• 批准号: 2238080
• 负责人: Samuel Hopkins
• 金额: $ 65万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-02-01 至 2028-01-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2238080&HistoricalAwards=false
• 关键词: CAREER; Statistics; through; Sum; Squares

Statistics with large data sets of high-dimensional observations (e.g., images, videos, genomes) forms the basis for modern machine learning and data science. Despite extraordinary successes in practice and the potential for tremendous further impact, theoretical understanding of the basic algorithmic building blocks for high-dimensional statistics remains limited. Unlike in traditional (low-dimensional) statistics, the key bottleneck is not how much data is available but how much computational power is available to process it. The central aim of this proposal is to advance a theory of algorithmic statistics which can address the core questions: which problems in high-dimensional statistics have computationally efficient algorithms? And, what are the best -- most accurate, most robust, fastest, etc. -- algorithms for such problems? Pursuing answers to these questions is likely to lead both to foundational algorithmic innovations as well as to a deeper understanding of the fundamental limitations of efficient computation in statistical settings, which is a prerequisite for understanding when a given algorithm is the best possible at the task it performs. Furthermore, the curriculum development and mentoring components of this project will disseminate state-of-the-art algorithm design techniques to the broader scientific community via courses, lectures, and videos and train the next generation of algorithm designers for science and industry.This project will develop the Sum of Squares method (SoS) as a powerful tool for algorithm design in statistical settings and as a lens on fundamental limitations. SoS is a problem-independent approach to designing algorithms with strong provable guarantees, generalizing tools such as linear programming, and eigenvalue/eigenvector methods. SoS has already broadly impacted algorithms in numerous areas: combinatorial optimization, quantum information, cryptography, control theory, high-dimensional statistics, and more. Even within high-dimensional statistics, SoS already has many applications in clustering, robust estimation, and tensor decomposition (the inverse problem underlying the method of moments), to name only a few. However, knowledge of SoS remains incomplete: there is tremendous potential to push the frontier of efficient algorithms by studying SoS, including in high-dimensional statistics. The core technical thrust of this project will be developing novel algorithms based on SoS as well as the mathematical tools to understand the guarantees and fundamental limitations of those algorithms. The project will focus on algorithm design in two specific domains, privacy-preserving data analysis and Bayesian inference, where the investigator believes that there are opportunities for new algorithms with strong provable guarantees to offer new insights on algorithm design broadly, as well as to have a near-term impact on practice.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），作为统计设置中算法设计的强大工具，并作为基本限制的镜头。SoS是一种独立于问题的方法，用于设计具有强可证明保证的算法，推广工具如线性规划和特征值/特征向量方法。SoS已经广泛地影响了许多领域的算法：组合优化、量子信息、密码学、控制理论、高维统计等等。甚至在高维统计中，SoS已经在聚类、鲁棒估计和张量分解（矩量方法背后的逆问题）中有许多应用，仅举几例。然而，关于SoS的知识仍然不完整：通过研究SoS，包括在高维统计中，有巨大的潜力来推动高效算法的前沿。该项目的核心技术重点将是开发基于SoS的新算法以及数学工具，以了解这些算法的保证和基本限制。该项目将专注于两个特定领域的算法设计，即保护隐私的数据分析和贝叶斯推理，研究者认为，具有强大可证明保证的新算法有机会为算法设计提供广泛的新见解，并对实践产生近期影响。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Fast, Sample-Efficient, Affine-Invariant Private Mean and Covariance Estimation for Subgaussian Distributions

亚高斯分布的快速、样本效率高、仿射不变的私有均值和协方差估计

• 发表时间: 2023
• 期刊: 36th Annual Conference on Learning Theory (COLT 2023
• 作者: Brown, Gavin;Hopkins, Samuel B.;Smith, Adam
• 通讯作者: Smith, Adam

Robustness Implies Privacy in Statistical Estimation

稳健性意味着统计估计中的隐私

• 发表时间: 2023
• 期刊: 55th Annual ACM Symposium on Theory of Computing (STOC
• 作者: Hopkins, Samuel B.;Kamath, Gautam;Majid, Mahbod;Narayanan, Shyam
• 通讯作者: Narayanan, Shyam

The Full Landscape of Robust Mean Testing: Sharp Separations between Oblivious and Adaptive Contamination

稳健均值检验的全貌：忽视污染和适应性污染之间的鲜明区别

• 发表时间: 2023
• 期刊: 64th Annual IEEE Symposium on Foundations of Computer Science (FOCS
• 作者: Canonne, Clément L.;Hopkins, Samuel B.;Li, Jerry;Liu, Allen;Narayanan, Shyam
• 通讯作者: Narayanan, Shyam