Jul, 2020

半空间对抗性鲁棒适当学习的复杂性（不知情噪音）

PDF
TL;DR我们研究了在分布无关的对抗性健壮 PAC 模型中半空间的计算复杂度，重点研究了 L_p 扰动。我们提出了一种计算有效的学习算法和一种几乎匹配的计算难度结果。我们发现的一个有趣的含义是，L_∞扰动的情况被证明比 2≤p<∞的情况更加计算上困难。
computational complexityadversarial robustnessproper learninghalfspacesl_p perturbations
发现论文，激发创造
  • 高效学习带有噪声的对抗稳健超平面

    研究在独立于分布的情况下学习对抗性鲁棒的半空间问题，在可实现的情况下，给出了对抗性扰动集的必要和充分条件，即半空间可以高效地实现鲁棒性学习，并在存在随机标签噪声时提出了一个简单的、计算效率高的算法。

    May, 2020

  • 采用恶意噪声的半空间样本最优 PAC 学习

    本文提出一种能够在存在恶意噪声的条件下有效学习欧氏空间中均匀半空间的 PAC 算法，该算法框架下的样本复杂度接近最优，主要用到了矩阵 Chernoff 型不等式和对错误噪声模型的推广。

    Feb, 2021

  • 关于局部感知机具有优势的半空间对抗噪声最优学习

    本文介绍了一种 Perceptron-like 在线主动学习算法，能够以近乎最优的标签复杂度和样本复杂度下，学习噪声容限在总概率最多为 ν，样本标签误差率 ε 和输入维度 d 给定的 R^d 中同质半空间。该算法的先前版本针对噪声容限存在的情况，不能同时获得标签和样本复杂度多项式级别的优良性能。经过一定的假设前提下，支持 5 罕见的瑕疵。

    Dec, 2020

  • 具有恶意噪声的半空间属性高效学习：近似最优标签复杂度和噪声容错性

    研究如何在噪音下进行有效的学习，在保证计算效率的前提下设计了一种主动学习算法，并根据半空间的结构进行加权和风险最小化等方法的技术优化，解决了恶意噪声等问题并且具有良好的属性效率和样本复杂度。

    Jun, 2020

  • 应对噪声的几何概念学习

    我们研究了在部分数据遭到敌对噪声污染的情况下，几何概念类（特别是低次多项式阈值函数（PTF）和半空间的交集）的高效可学习性，并给出了这些概念类的首个多项式时间 PAC 学习算法，具有不依赖于维度的误差保证。

    Jul, 2017

  • 非凸 SGD 学习带有对抗标签噪声的半空间

    研究学习同质半空间的非说服学派问题，证明对于一类结构化分布，包括对数凹分布，在误分类误差 O（opt）+eps 下，非凸 SGD 有效地收敛到解决方案。相比之下，证明优化任何凸代理本质上会导致 ω（opt）的误分类误差，即使在高斯边际分布下。

    Jun, 2020

  • 学习半空间的复杂性理论限制

    该研究讨论了在固定且未知的分布和自然条件下的半空间学习问题，证明了最坏情况下的性能和效率的复杂性。

    May, 2015

  • 具备 Massart 噪声的半空间分布无关 PAC 学习

    研究分布无关的半空间在 Massart 噪声下的拟准确性学习问题，给出了一个计算复杂度为多项式时间且误分类错误率为 η+ε 的算法。

    Jun, 2019

  • 半空间学习单项式是困难的

    该研究证明了在符合某些要求的示例分布下，多项式的弱会混淆学习几乎不可能，即使在输出更大的概念类的假设的情况下也是如此，这种难度结果从某种程度上包括以前的研究结果，包括最近的对单项式和半空间的适当学习的难度结果。

    Dec, 2010

  • 一种对半空间进行不可知学习的 PTAS 算法

    本文提出了一个以多项式回归和定位技术相结合的算法， 用于在 d - 球上均匀分布的情况下，实现对零时最佳半空间分类器的确定性多项式近似方案（PTAS），误差保证为 opt 的 (1+μ)+ε 倍， 并提供了比以前使用定位技术的算法更加优越的针对全局的误差近似解决方案。

    Oct, 2014