关于强鲁棒分类的困难程度
从学习理论的角度研究鲁棒学习的可行性,考虑样本复杂性,研究了鲁棒学习在拥有随机样本、满足 Lipschitz 条件的数据分布和更强学习能力的情况下的对抗性攻击的脆弱性,提出了基于经验风险最小化的鲁棒算法,并给出了查询复杂性的上下界。
Aug, 2023
高维度分类器为何易受到 “对抗性” 扰动?本文中将阐述这种现象可能不是由于信息论的限制,而是由于计算约束所引起的。同时探讨了分类任务的一种特殊情况,即在高维空间中对于对抗扰动较大的学习是容易的,但是具有计算难度的。这种例子带来了对于经典学习和鲁棒性学习之间的计算复杂度的差异的新见解,并建议这种现象可能是学习算法计算能力所限制的必然副产品。
May, 2018
本文研究了在学习稳健分类器时统计 / 计算权衡的问题,证明了 对于一些分类任务,即使存在计算不受限制的稳健分类器,也不可能得到高效的稳健分类器,而这与计算数论中一些重要的开放问题密切相关。
Feb, 2019
该研究探讨在对抗鲁棒性的背景下,证明攻击 ReLU 分类器是 NP 难题,而在训练期间确保它们的稳健性则是 Σ2_P 难题,同时提出一种名为 Counter-Attack 的方法来证明抵御攻击的有效性。
Jun, 2023
研究了均匀分布在 {0,1}^n 上的实例中的敌对扰动,提出了不同于通常定义的错误区域的保真度定义,并根据该定义研究了任何分类问题的任何分类器的风险和稳健性的内在限制。使用布尔超立方体的等周不等式和中心极限定理,对单个和大规模的问题提出了与数学相关的结果。
Oct, 2018
本文研究在简单自然数据模型中,对抗鲁棒学习的样本复杂度可以显著大于标准学习,这个差距是信息理论的,且与训练算法或模型家族无关。作者做了一些实验来证实这个结果。我们可以假设训练鲁棒分类器的困难,至少部分来自这种固有的更大的样本复杂度。
Apr, 2018
我们在最近的工作中(Bubeck,Price,Razenshteyn, arXiv:1805.10204)指出,机器学习中的对抗性例子可能是由于问题固有的计算难度造成的。更确切地说,我们构建了一个二元分类任务,其中(i)存在强大的鲁棒分类器;但在(ii)统计查询模型中无法使用有效算法获得任何非平凡的准确性。在本文中,我们显着加强了(i)和(ii):我们现在构建了一个任务,该任务允许(i')最大限度地鲁棒的分类器(即它可以容忍与示例本身大小相当的扰动);此外,我们证明了在(ii')标准加密假设下学习此任务的计算困难性。
Nov, 2018
通过优化多项式优化问题的技术,我们设计了具有计算效率和可证明保证的鲁棒性算法,能够抵御测试时的对抗性干扰,特别地,针对线性分类器和二次多项式阈值函数(PTF)分类器,我们给出了其计算鲁棒性的代价的精确刻画,同时,我们还证明了用环境所提供的函数信息可以在有效时间内帮助生成对抗攻击样本,并证明这些攻击样本在实际数据上是有效的。
Nov, 2019
对于分布学习问题,我们研究了可学习性和鲁棒(或不可知)可学习性之间的关系,发现与其他学习设置(例如函数类的 PAC 学习)相反,概率分布类的可实现学习性并不意味着其不可知可学习性。我们进一步研究了什么样的数据损坏可以破坏分布类的可学习性以及该可学习性对于怎样的损坏是鲁棒的。结果表明,概率分布类的可实现学习性仅对加性损坏具有鲁棒性,而不具备对减性损坏的鲁棒性。我们还探索了与压缩方案和差分隐私可学习性相关的含义。
Jun, 2024