AF: RI: Small: Barriers in Adversarially Robust Learning

学习算法正越来越多地承担起以前由人类承担的角色。例子包括人脸识别、恶意软件检测、决定贷款或保释等。然而，学习算法通常对在训练或决策期间发生的对抗性操作很敏感。由于使用这些算法的上下文的敏感性，理解在这种对抗性上下文中可证明的鲁棒方法的功能和局限性至关重要。该项目的目标是从可证明的角度研究对抗性鲁棒性，并确定可能存在的障碍。该项目将建立与其他领域的联系，如计算复杂性和密码学。该项目还包括指导博士生。研究结果将纳入新设计的课程，并将通过讲习班、会议和期刊传播。更具体地说，该项目将侧重于实现上述主要目标的两个部分。第一部分是正式建模对抗鲁棒学习，以实现可证明的方法。事实上，密码学从这种数学上严格的安全方法中受益匪浅，为了达到类似的结果，对抗健壮的学习需要类似的定义方法来模拟攻击的微妙方面，例如：攻击者的计算复杂性，其精确知识和随机性的作用。该项目的第二部分旨在确定对抗学习中存在的可证明的鲁棒性障碍。这个项目将研究信息理论（又名统计）和计算安全的障碍。信息安全理论将攻击者建模为一个强大的实体，而广泛应用于密码学的计算安全模型将攻击者建模为一个多项式时间算法。识别这些障碍是设计最佳稳健学习方法的重要组成部分。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Learning algorithms are increasingly taking on roles that were previously held by humans. Examples include face recognition, malware detection, making decisions about loans or bail, etc. Learning algorithms, however, are usually sensitive to adversarial manipulations happening during training or decision time. Due to the sensitivity of the contexts in which these algorithms are used, it is crucial to understand the power and limitations of provably robust methods in such adversarial contexts. The goal of this project is to study adversarial robustness from a provable perspective and identify the barriers that might exist against it. The project will build connections to other areas such as computational complexity as well as cryptography. The project also involves mentoring PhD students. The findings will be incorporated into newly designed courses and will be disseminated via workshops, conferences, and journals.The project, more specifically, will focus on two parts that enable the main goals outlined above. The first part is to model adversarially robust learning formally to enable a provable approach. Indeed, Cryptography has benefited tremendously from such mathematically rigorous approach to security, and to reach similar results, adversarially robust learning needs a similar definitional approach that models subtle aspects of the attack such as: the computational complexity of the attacker, its precise knowledge, and the role of randomness. The second part of this project aims at identifying barriers that exist against provable robustness for adversarial learning. This project will study barriers against both information theoretic (a.k.a. statistic) as well as computational security. Information theoretic security models the adversary as an all powerful entity, while the more realistic model of computational security, which is widely used in Cryptography, models the attacker as a polynomial-time algorithm. Identifying these barriers is an essential part of designing optimally robust learning methods.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.