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

合作研究：AF：中：算法高维稳健统计

基本信息

批准号：
2107547
负责人：
Daniel Kane
金额：
$ 60万
依托单位：
University of California-San Diego
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2021
资助国家：
美国
起止时间：
2021-07-01 至 2025-06-30
项目状态：
未结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2107547&HistoricalAwards=false
关键词：
Collaborative Research AF Medium Algorithmic

项目摘要

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.

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