Feb, 2020

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

PDF
TL;DR在特定分布的 PAC 模型下，我们针对学习带有 Massart 噪声的半空间问题进行了研究。我们提出了第一种基于 SGD 的、针对广泛分布（包括对数凹分布）的问题求解的计算机高效算法，并解决了先前研究中的一个悬而未决的问题。
halfspacesmassart noisepac modellog-concave distributionssgd
发现论文，激发创造
  • 具备 Massart 噪声的半空间分布无关 PAC 学习

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

    Jun, 2019

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

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

    Jun, 2020

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

    研究学习理论中使用的统计查询模型在学习含有 Massart 噪声的 Halfspaces 时的有效性，并证明了已知的算法与最优界的差距，解决了一个学习理论中长期存在的难题。

    Dec, 2020

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

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

    Jun, 2020

  • 测试者学习半空间的通用算法

    本研究提出了一种普适性的半空间测试学习算法，它可以在所有满足 Poincaré 不等式的分布上获得较小误差，具体实现是使用 sum-of-squares 算法检查分布的超对称性。

    May, 2023

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

    通过设计基于非凸优化的算法，本文研究了具有 Tsybakov 噪声的计算和标签效率 PAC 主动学习上的 d - 维半空间问题，其标签复杂度较先前已知的高效被动或主动算法与该设置下的信息理论下界之间的差距缩小了。

    Oct, 2023

  • 高效学习带有噪声的对抗稳健超平面

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

    May, 2020

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

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

    May, 2024

  • 学习具有 Tsybakov 噪声的半空间的多项式时间算法

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

    Oct, 2020

  • 基于 S-Concave 分布的样本和计算高效的学习算法

    本文提出了一种新的 $s$-concave 分布类别，基于凸几何工具研究了该分布类别并将其应用于学习算法中，在边缘化算子下提供了有关 $s$-concave 分布的性质和一些学习问题的收敛界限。

    Mar, 2017