AF: Small: Faster Algorithms for High-Dimensional Robust Statistics

AF：小：用于高维稳健统计的更快算法

• 批准号: 2122628
• 负责人: Yu Cheng
• 金额: $ 39.1万
• 依托单位: University of Illinois at Chicago
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-01-01 至 2022-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2122628&HistoricalAwards=false
• 关键词: AF; Small; Faster; Algorithms; Dimensional

As machine learning plays a more prominent role in our society, there is a need for learning algorithms that are reliable and robust. In modern machine learning, one often needs to work with data that are high-dimensional and noisy. Recent work gave the first efficient robust estimators for several basic statistical problems, and since then, there has been a flurry of research that obtained efficient robust algorithms for many machine-learning problems. However, one major drawback of existing algorithms in the literature is that they tend to be much slower when compared to their non-robust counterparts, or they often involve parameters that require careful tuning. To address these issues, this project aims to (i) design faster and provably robust algorithms for a wide range of high-dimensional statistical and learning tasks, and (ii) explore non-convex formulations of robust estimation and analyze their optimization landscape. This project will advance the fields of computer science and statistics, and also potentially lead to useful tools for other areas. The pursuit of faster and simpler algorithms will help accelerate technology transfer into practice, stimulate systematic approaches to robustness, and provide a positive societal impact in the long run. The education plan of this project includes incorporating the materials generated from this project into graduate-level courses at the University of Illinois at Chicago (UIC), as well as training graduate and undergraduate students at UIC, which is an urban university with a diverse student population.Designing robust algorithms in high dimensions is a very challenging task. Even for the basic problem of mean estimation, when a small fraction of the input is adversarially corrupted, no efficient algorithms were known until recently. The first polynomial-time estimators with dimension-independent error guarantees were discovered in 2016. However, given the amount of data available today, polynomial-time no longer translates to scalability in practice. Motivated by the need for faster and more practical algorithms, this project focuses on two main thrusts to expand the area of algorithmic high-dimensional robust statistics. First, the investigator would like to speed up existing algorithms and develop new robust algorithms for a broader range of problems and richer families of distributions, with the ultimate goal of matching the runtime of the fastest non-robust algorithms. Second, the investigator wants to design robust estimators that can be computed via standard first-order optimization methods. The main challenge is to find an objective function whose gradient can be evaluated using basic matrix operations while proving the structural result that this objective has no bad local optima. Concretely, the investigator plans to work on these two thrusts by targeting various aspects of the following problems: (1) robust stochastic optimization, (2) robust sparse mean estimation and sparse PCA, (3) robust covariance estimation, (4) list-decodable learning, and (5) robust learning of Bayesian networks. This project is interdisciplinary and will rely on intuition and techniques from statistics, probability, linear algebra, discrete and continuous optimization, and non-convex optimization.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.

随着机器学习在我们的社会中起着更为突出的作用，需要学习可靠和稳健的算法。在现代机器学习中，通常需要与高维且嘈杂的数据一起工作。最近的工作为几个基本的统计问题提供了第一个有效的稳健估计器，从那时起，一系列研究就为许多机器学习问题提供了有效的鲁棒算法。但是，文献中现有算法的一个主要缺点是，与其非持续的对应物相比，它们往往要慢得多，或者它们通常涉及需要仔细调整的参数。为了解决这些问题，该项目的目的是（i）为广泛的高维统计和学习任务设计更快，更强大的算法，以及（ii）探索可靠估算的非凸式配方，并分析其优化环境。该项目将推进计算机科学和统计的领域，并有可能为其他领域提供有用的工具。追求更快，更简单的算法将有助于加速技术转移，从而刺激系统的鲁棒性方法，并在长远来看提供积极的社会影响。该项目的教育计划包括将该项目产生的材料纳入伊利诺伊大学芝加哥大学（UIC）的研究生水平课程，以及UIC的培训研究生和本科生，UIC是一所城市大学，具有多样化的学生人数。设计高级算法的强大算法是一项非常挑战的任务。即使对于平均估计的基本问题，当一小部分输入是对手损坏时，直到最近才知道有效的算法。 2016年发现了第一个具有无关误差保证的多项式估计器。但是，鉴于当今可用的数据量，多项式时间不再转化为实践中的可伸缩性。由于需要更快，更实用的算法的需要，该项目着重于扩大算法高维鲁棒统计范围的两个主要推力。首先，研究人员希望加快现有算法，并为更广泛的问题和更丰富的分布家庭开发新的强大算法，并最终的目的是匹配最快的非持续算法的运行时。其次，研究者希望设计可通过标准一阶优化方法计算的强大估计器。主要的挑战是找到一个目标函数，可以使用基本矩阵操作来评估其梯度，同时证明该目标没有局部优势不良的结构结果。 具体而言，研究人员计划通过针对以下问题的各个方面来处理这两个推力：（1）强大的随机优化，（2）强大的稀疏平均估计和稀疏的PCA，（3）强大的协方差估计，（4）列表可解码的学习，以及（5）对贝叶斯网络的强大学习。该项目是跨学科的，将依赖于统计，概率，线性代数，离散和连续优化的直觉和技术以及非凸优化的优化。该奖项反映了NSF的法定任务，并被认为是值得通过基金会的智力和更广泛影响的评估来通过评估来获得支持的。

项目成果

Outlier-Robust Sparse Estimation via Non-Convex Optimization

通过非凸优化的异常值稳健稀疏估计

• 发表时间: 2022
• 期刊: Conference on Neural Information Processing Systems
• 作者: Cheng, Yu;Diakonikolas, Ilias;Ge, Rong;Gupta, Shivam;Kane, Daniel M.;Soltanolkotabi, Mahdi
• 通讯作者: Soltanolkotabi, Mahdi

Planning with Participation Constraints

具有参与约束的规划

• DOI: 10.1609/aaai.v36i5.20462
• 发表时间: 2022
• 期刊: Proceedings of the 36th AAAI Conference on Artificial Intelligence
• 作者: Zhang, Hanrui;Cheng, Yu;Conitzer, Vincent
• 通讯作者: Conitzer, Vincent

Efficient Algorithms for Planning with Participation Constraints

具有参与约束的规划的高效算法

• DOI: 10.1145/3490486.3538280
• 发表时间: 2022
• 期刊: Proceedings of the 23rd ACM Conference on Economics and Computation
• 作者: Zhang, Hanrui;Cheng, Yu;Conitzer, Vincent
• 通讯作者: Conitzer, Vincent