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的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

A Strongly Polynomial Algorithm for Approximate Forster Transforms and Its Application to Halfspace Learning

一种近似福斯特变换的强多项式算法及其在半空间学习中的应用

• DOI: 10.1145/3564246.3585191
• 发表时间: 2023
• 期刊: STOC 2023: Proceedings of the 55th Annual ACM Symposium on Theory of Computing
• 作者: Diakonikolas, Ilias;Tzamos, Christos;Kane, Daniel M.
• 通讯作者: Kane, Daniel M.

Statistical Query Lower Bounds for List-Decodable Linear Regression

• 发表时间: 2021-06
• 期刊: ArXiv
• 作者: Ilias Diakonikolas;D. Kane;Ankit Pensia;Thanasis Pittas;Alistair Stewart

Hardness of Learning a Single Neuron with Adversarial Label Noise

• 发表时间: 2022
• 作者: Ilias Diakonikolas;D. Kane;Pasin Manurangsi;Lisheng Ren

Cryptographic Hardness of Learning Halfspaces with Massart Noise

使用 Massart 噪声学习半空间的密码学硬度

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

Forster Decomposition and Learning Halfspaces with Noise

• 发表时间: 2021-07
• 期刊: ArXiv
• 作者: Ilias Diakonikolas;D. Kane;Christos Tzamos