Dec, 2020

带有 Massart 噪声的学习半空间的近似最优统计查询难度

PDF
TL;DR研究学习理论中使用的统计查询模型在学习含有 Massart 噪声的 Halfspaces 时的有效性，并证明了已知的算法与最优界的差距，解决了一个学习理论中长期存在的难题。
pac learningmassart noisehalfspacesstatistical query modelerror bounds
发现论文，激发创造
  • 具备 Massart 噪声的半空间分布无关 PAC 学习

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

    Jun, 2019

  • 分类任务中的模型偏差：半空间、广义线性模型和与可演进性的关联

    本文研究半空间分类问题，在给出令人困扰的常规算法的同时，提出了更简单优雅的算法以及进一步解决了多个未解决的问题，并通过实验证明了该算法具有公平性。

    Jun, 2020

  • 学习高斯半空间问题中随机分类噪声的近最优界

    研究使用高斯分布下随机分类噪声学习半空间的问题，证明算法和统计查询下限，在此基本问题中，存在令人惊讶的信息计算差距，给出了正面的结果和近乎匹配的复杂度，并展示了算法的复杂度下界

    Jul, 2023

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

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

    Feb, 2020

  • 带 Massart 噪声的半空间在线学习

    在存在 Massart 噪声的在线学习任务中，我们研究了广义线性分类器的基本类，并提出了一个高效的算法，达到了错误界限，与在线对手对抗。我们还将在线学习模型扩展到 k 臂上下文强盗设置中，通过使用我们的 Massart 在线学习器设计了一个高效的强盗算法，从而达到至少比在每一轮随机选择一个动作大 (1-1/k)~Delta T - o (T) 的期望奖励。

    May, 2024

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

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

    Feb, 2021

  • 学习带有随机分类噪声的边缘半空间的信息计算权衡

    本文研究 PAC 学习半空间问题中的分类噪声并建立信息计算交换模型，给出了算法复杂度和样本复杂度之间存在固有差距，最终得到了关于统计查询算法和低次多项式测试的下限，证明了计算效率算法的样本复杂度存在基本平方依赖关系。

    Jun, 2023

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

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

    Jun, 2020

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

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

    Oct, 2014

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

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

    May, 2015