Oct, 2023

具有 Tsybakov 噪声的高效主动学习半空间问题的非凸优化方法

PDF
TL;DR通过设计基于非凸优化的算法，本文研究了具有 Tsybakov 噪声的计算和标签效率 PAC 主动学习上的 d - 维半空间问题，其标签复杂度较先前已知的高效被动或主动算法与该设置下的信息理论下界之间的差距缩小了。
pac active learningtsybakov noisenonconvex optimizationlabel complexityinformation-theoretic lower bound
发现论文，激发创造
  • 学习具有 Tsybakov 噪声的半空间的多项式时间算法

    本文首次提出了针对在 Tsybakov 噪声情况下 PAC 学习均匀半空间的可行的多项式时间算法，并且证明了该算法对于如对称型对数凹分布之类的广泛应用的分布成功率显著

    Oct, 2020

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

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

    Feb, 2021

  • 高效稀疏半空间的主动学习

    本文提供了一个计算有效的算法，用于解决高维空间中的 PAC 主动学习问题，其中数据遵循某些分布假设，该算法在少量的标记查询下使用稀疏的半空间学习，能够达到 O（t polylog（d，1/ϵ））的标记复杂度。

    May, 2018

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

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

    Dec, 2020

  • 基于 Margin 的噪声自适应主动学习及在 Tsybakov 噪声条件下的下界

    提出了一个简单的噪声 - 鲁棒性基于边缘的主动学习算法来查找同质 (通过原点) 的线性分离器，并分析了标签受噪声干扰时的误差收敛性。我们证明了当所施加的噪声满足 Tsybakov 低噪声条件时，算法能够适应未知的噪声水平，并在多对数因子上实现最优统计速率。同时，我们为基于边缘的主动学习算法在会员查询合成场景下的 Tsybakov 噪音条件 (TNC) 导出了下限。我们的分析可能为其他形式的下限提供了见解。

    Jun, 2014

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

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

    Jun, 2020

  • 在结构化分布下学习带有 Massart 噪声的半空间

    在特定分布的 PAC 模型下，我们针对学习带有 Massart 噪声的半空间问题进行了研究。我们提出了第一种基于 SGD 的、针对广泛分布（包括对数凹分布）的问题求解的计算机高效算法，并解决了先前研究中的一个悬而未决的问题。

    Feb, 2020

  • 重温感知机：半空间高效与标签最优学习

    本文提出了一种半空间主动学习算法，能够在存在噪声和尽可能少的标签情况下，有效地学习均匀分布在单位球上的均匀半空间，并证明其在两种噪声情况下均达到了近似最优标签复杂度。

    Feb, 2017

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

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

    Jun, 2020

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

    我们研究了在分布无关的对抗性健壮 PAC 模型中半空间的计算复杂度，重点研究了 L_p 扰动。我们提出了一种计算有效的学习算法和一种几乎匹配的计算难度结果。我们发现的一个有趣的含义是，L_∞扰动的情况被证明比 2≤p<∞的情况更加计算上困难。

    Jul, 2020