【牛津大学博士论文】抗规避攻击鲁棒学习的样本复杂度

机器学习模型对抗性攻击的脆弱性的理解日益重要。在对抗性机器学习中，一个基本问题是在存在所谓的规避攻击的情况下量化需要多少训练数据，其中数据在测试时会被损坏。在本论文中，我们采用了“球内精确性”概念，从学习理论的角度研究了对抗性鲁棒学习的可行性，考虑样本复杂性。我们首先得出了两个负面结果。我们证明，在无分布设置下，任何非平凡的概念类都不能在对手能够扰动单个输入位的情况下得到鲁棒学习。然后，我们展示了样本复杂性的下界：单调合取的类以及布尔超立方体上的任何超类，其样本复杂性至少是对手预算（即每个输入上可以扰动的最大位数）的指数函数。特别地，这意味着在均匀分布下，不能对那些可以扰动输入的 ω(log n) 位的对手进行鲁棒学习。

作为获得鲁棒性学习保证的第一条途径，我们考虑限制用于训练和测试数据的分布类别。我们关注概率分布在输入数据上满足Lipschitz条件的学习问题：附近的点具有类似的概率。我们证明，如果对手被限制在扰动 O(log n) 位的情况下，那么可以在对数Lipschitz分布类别的条件下鲁棒地学习单调合取类。然后，我们扩展了这一结果，展示了在相同的分布和对抗环境中学习 1-决策列表、2-决策列表和单调 k-决策列表的可行性。最后，我们展示对于每个固定的 k 值，k-决策列表类在 log(n) 有界对手条件下具有多项式样本复杂性。考虑中间的 k-决策列表子类的优势在于，我们能够为这些情况获得改进的样本复杂性界限。

作为第二条途径，我们研究了学习模型，其中学习者通过使用局部查询获得了更多的能力。我们首先考虑的学习模型使用局部成员查询（LMQ），在该模型中，学习者可以查询接近训练样本的点的标签。我们证明，在均匀分布下，即使在学习者除了随机示例外还可以访问LMQ的情况下，对于扰动预算为 O(log n) 的对手，鲁棒学习合取类和任何超类对于对数Lipschitz分布仍然不可避免地需要对对手的预算呈指数依赖。面对这个负面结果，我们引入了局部等价查询预测器，该预测器返回假设和目标概念在训练样本中的某个点周围区域内是否一致，以及如果存在反例的话也会返回反例。我们证明了一个分离结果：一方面，如果查询半径 λ 严格小于对手的扰动预算 ρ，那么在多种概念类别中是不可能进行无分布鲁棒学习的；另一方面，当 λ = ρ 时，我们能够在无分布环境中开发出鲁棒的经验风险最小化算法。然后，我们基于在线学习保证来限制这些算法的查询复杂性，并在合取式特殊情况下进一步改进这些界限。接着，我们提供了一个在 {0, 1} n 上的半空间鲁棒学习算法。最后，由于在 R n 上的半空间查询复杂性是无界的，我们转而考虑具有有界精度的对手，并在这种情况下给出了查询复杂性的上界。