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

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

• 批准号: 2107079
• 负责人: Ilias Diakonikolas
• 金额: $ 60万
• 依托单位: University of Wisconsin-Madison
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2021
• 资助国家: 美国
• 起止时间: 2021-07-01 至 2025-06-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2107079&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 的法定使命，并通过使用基金会的智力优势和更广泛的评估进行评估，被认为值得支持。影响审查标准。

项目成果

SQ Lower Bounds for Learning Single Neurons with Massart Noise

使用 Massart 噪声学习单个神经元的 SQ 下界

• 发表时间: 2022-12
• 期刊: Advances in Neural Information Processing Systems (NeurIPS
• 作者: Diakonikolas, I;Kane, D;Ren, L;Sun, Y.
• 通讯作者: Sun, Y.

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

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

• 发表时间: 2021-01
• 期刊: 2021
• 作者: Ilias Diakonikolas;Daniel M. Kane;Alistair Stewart;Yuxin Sun
• 通讯作者: Yuxin Sun

Learning General Halfspaces with Adversarial Label Noise via Online Gradient Descent

通过在线梯度下降学习具有对抗性标签噪声的一般半空间

• 发表时间: 2022-07
• 期刊: ICML
• 作者: Ilias Diakonikolas;Vasilis Kontonis;Christos Tzamos;Nikos Zarifis
• 通讯作者: Nikos Zarifis

Statistical Query Lower Bounds for List-Decodable Linear Regression

列表可解码线性回归的统计查询下界

• 发表时间: 2021-12
• 期刊: Advances in neural information processing systems
• 作者: Ilias Diakonikolas;Daniel Kane;Ankit Pensia;Thanasis Pittas;Alistair Stewart
• 通讯作者: Alistair Stewart

Non-Gaussian Component Analysis via Lattice Basis Reduction

通过格基约简进行非高斯分量分析

• 发表时间: 2022-07
• 期刊: COLT
• 作者: Ilias Diakonikolas;Daniel Kane
• 通讯作者: Daniel Kane