CAREER: Efficient Algorithms for Learning and Testing Structured Probabilistic Models

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

基本信息

批准号：
1652862
负责人：
Ilias Diakonikolas
金额：
$ 54万
依托单位：
University of Southern California
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2017
资助国家：
美国
起止时间：
2017-02-01 至 2020-03-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1652862&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将在我们当前的理解中研究一些无监督的学习和测试中的几个基本算法问题。这些包括设计有效的算法，这些算法在与假定模型的偏差存在下稳定，规避分布学习中维度的诅咒，并测试高维概率模型。这组方向可能导致新的算法和概率技术，并在无监督的估计中提供有关结构与效率之间相互作用的见解。这项研究与计算机科学，概率，统计和信息理论的更广泛的工作有关。

项目成果

期刊论文数量（18）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

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

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

DOI：
发表时间：
2021
期刊：
2021
影响因子：
0
作者：
Ilias Diakonikolas;Daniel M. Kane;Alistair Stewart;Yuxin Sun
通讯作者：
Yuxin Sun

Robustly learning mixtures of k arbitrary Gaussians

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

DOI：
10.1145/3519935.3519953
发表时间：
2022
期刊：
Symposium on Theory of Computation
影响因子：
0
作者：
Bakshi, Ainesh;Diakonikolas, Ilias;Jia, He;Kane, Daniel M.;Kothari, Pravesh K.;Vempala, Santosh S.
通讯作者：
Vempala, Santosh S.

Testing Shape Restrictions of Discrete Distributions

测试离散分布的形状限制