CAREER: Efficient Algorithms for Learning and Testing Structured Probabilistic Models

职业：学习和测试结构化概率模型的有效算法

• 批准号: 2011255
• 负责人: Ilias Diakonikolas
• 金额: $ 46.43万
• 依托单位: University of Wisconsin-Madison
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-09-11 至 2023-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2011255&HistoricalAwards=false
• 关键词: CAREER; Efficient; Algorithms; Learning; Testing

In recent years, the amount of available data in science and technology has exploded and is currently expanding at an unprecedented rate. The general task of making accurate inferences on large and complex datasets has become a major bottleneck across various disciplines. A natural formalization of such inference tasks involves viewing the data as random samples drawn from a probabilistic model -- a model that we believe describes the process generating the data. The overarching goal of this project is to obtain a refined understanding of these inference tasks from both statistical and computational perspectives. The questions addressed in this project arise from pressing challenges faced in modern data analysis. A crucial component of the project involves fostering collaboration between different communities. Furthermore, the PI will mentor high-school and undergraduate students, and design several new theory courses integrating research and teaching at the undergraduate and graduate levels.The PI will investigate several fundamental algorithmic questions in unsupervised learning and testing for which there is an alarming gap in our current understanding. These include designing efficient algorithms that are stable in the presence of deviations from the assumed model, circumventing the curse of dimensionality in distribution learning, and testing high-dimensional probabilistic models. This set of directions could lead to new algorithmic and probabilistic techniques, and offer insights into the interplay between structure and efficiency in unsupervised estimation. This research ties into a broader range of work across computer science, probability, statistics, and information theory.

近年来，科学技术领域的可用数据量呈爆炸式增长，目前正以前所未有的速度增长。对大型复杂数据集进行准确推断的一般任务已成为各个学科的主要瓶颈。此类推理任务的自然形式化涉及将数据视为从概率模型中抽取的随机样本——我们认为该模型描述了生成数据的过程。该项目的总体目标是从统计和计算的角度对这些推理任务有更深入的理解。该项目解决的问题源于现代数据分析面临的紧迫挑战。该项目的一个重要组成部分涉及促进不同社区之间的合作。此外，PI还将指导高中生和本科生，并设计一些新的本科生和研究生阶段的研究与教学相结合的理论课程。PI将研究无监督学习和测试中存在惊人差距的几个基本算法问题以我们目前的理解。其中包括设计在存在与假设模型偏差的情况下保持稳定的高效算法、规避分布学习中的维数灾难以及测试高维概率模型。这组方向可能会带来新的算法和概率技术，并提供对无监督估计中结构和效率之间相互作用的见解。这项研究与计算机科学、概率、统计学和信息论等更广泛的工作联系在一起。

项目成果

Non-Gaussian Component Analysis via Lattice Basis Reduction

通过格基约简进行非高斯分量分析

• DOI: 10.1007/bf00184874
• 发表时间: 2021-12-16
• 期刊: ArXiv
• 作者: Ilias Diakonikolas;D. Kane
• 通讯作者: D. Kane

List-Decodable Mean Estimation in Nearly-PCA Time

近 PCA 时间内的列表可解码均值估计

• 发表时间: 2021-01
• 期刊: NeurIPS 2021
• 作者: Ilias Diakonikolas;Daniel Kane;Daniel Kongsgaard;Jerry Li;Kevin Tian
• 通讯作者: Kevin Tian

Robustly learning mixtures of k arbitrary Gaussians

鲁棒地学习 k 个任意高斯的混合

• DOI: 10.1145/3519935.3519953
• 发表时间: 2022-06
• 期刊: Symposium on Theory of Computation
• 作者: Bakshi, Ainesh;Diakonikolas, Ilias;Jia, He;Kane, Daniel M.;Kothari, Pravesh K.;Vempala, Santosh S.
• 通讯作者: Vempala, Santosh S.

Outlier-Robust Learning of Ising Models Under Dobrushin’s Condition

Dobrushin 条件下 Ising 模型的离群稳健学习

• 发表时间: 2021-01
• 期刊: 2021
• 作者: Ilias Diakonikolas;Daniel M. Kane;Alistair Stewart;Yuxin Sun
• 通讯作者: Yuxin Sun

Robust Sparse Mean Estimation via Sum of Squares

通过平方和进行鲁棒稀疏均值估计

• 发表时间: 2022-07
• 期刊: COLT
• 作者: Ilias Diakonikolas;Daniel M. Kane;Sushrut Karmalkar;Ankit Pensia;Thanasis Pittas
• 通讯作者: Thanasis Pittas