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

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

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.