Collaborative Research: AF: Medium: Algorithmic High-Dimensional Robust Statistics

从高维和受污染的数据集中做出准确推断的广泛任务是至关重要的，并且已成为许多紧迫的数据分析应用中的关键挑战。其中包括(1)机器学习（ML）中的数据中毒攻击，恶意用户插入的一小部分对抗性数据也会大大降低机器学习系统的质量，以及(2)对科学数据集（例如生物学）的探索性分析，其中系统错误可能会产生结构化的破坏，需要付出艰苦的努力才能检测到。为了应对这些挑战，我们确实需要开发高效的鲁棒学习算法——这些算法的性能在偏离关于输入数据的理想化假设时是稳定的。这些偏差的精确形式是特定于问题的，并产生各种鲁棒性概念。这个项目的总体目标是发展一个高维鲁棒统计和学习的通用算法理论。该项目的一个重要组成部分包括通过组织跨学科研讨会，以及编写关于该主题的新研究生教科书，在不同社区之间建立桥梁。此外，研究人员正在指导本科生，并设计新的以数据为中心的课程，将研究和教学结合起来。该项目的技术核心由两个相互关联的重点组成：(1)列表可解码学习和混合模型：最近大多数关于算法高维鲁棒学习的文献都关注于干净数据占数据集大部分的设置。列表可解码学习是一种轻松的学习概念，在这种学习中，干净的数据只占输入数据集的一小部分，可以用来为重要的数据科学应用程序建模，比如与大多数不可靠的受访者和学习混合模型进行众包。该项目正在开发一个统一的理论，其目标是揭示哪些分布参数可以有效地列表解码，并利用该理论来理解学习混合模型的复杂性。(2)几何概念的鲁棒监督学习：监督学习的目标是从标记观察的集合中推断函数。监督学习传统上关注的是从一组正确标记的示例中进行泛化的问题。在许多现实场景中，一小部分点和/或标签可能会被噪声破坏，例如，由于传感器错误或对抗性数据中毒。因此，重要的是开发有效的算法，在这些条件下产生准确的预测器。该项目正在开发高效的鲁棒学习算法，用于丰富的几何概念族，涉及自然和充分研究的半随机噪声模型。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

The broad task of making accurate inferences from high-dimensional and contaminated datasets is of fundamental importance and has become a key challenge in a number of pressing data-analysis applications. These include (1) data-poisoning attacks in machine learning (ML), where even a small fraction of adversarial data inserted by malicious users can substantially degrade the quality of the ML system, and (2) exploratory analysis of scientific datasets (e.g., in biology), where systematic errors can create structured corruptions that require painstaking effort to detect. To address these challenges, there is a real need to develop efficient robust learning algorithms -- methods whose performance is stable to deviations from the idealized assumptions about the input data. The precise form of these deviations is problem-specific and gives rise to various notions of robustness. The overarching goal of this project is to develop a general algorithmic theory of high-dimensional robust statistics and learning. A crucial component of the project involves building bridges between different communities, by organizing interdisciplinary workshops, and writing a new graduate textbook on the topic. Moreover, the investigators are mentoring undergraduate students and design new data-centric courses integrating research and teaching.The technical core of this project consists of two interrelated thrusts: (1) List-Decodable Learning and Mixture Models: The majority of recent literature in algorithmic high-dimensional robust learning focuses on the setting where the clean data is the majority of the dataset. List-decodable learning is a relaxed notion of learning capturing the regime where the clean data is a minority of the input dataset, and can be used to model important data-science applications, such as crowdsourcing with a majority of unreliable respondents and learning-mixture models. The project is developing a unified theory with the goal of uncovering which distributional parameters can be efficiently list-decoded, and leveraging this theory to understand the complexity of learning mixture models. (2) Robust Supervised Learning of Geometric Concepts: The goal of supervised learning is to infer a function from a collection of labeled observations. Supervised learning has traditionally been concerned with the problem of generalizing from a set of correctly labeled examples. In many realistic scenarios, a fraction of the points and/or labels may be corrupted by noise, e.g., due to sensor errors or adversarial data poisoning. Hence, it is important to develop efficient algorithms that produce accurate predictors under these conditions. The project is developing efficient robust learning algorithms for rich families of geometric concepts with respect to natural and well-studied semi-random noise models.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.