May, 2024

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

PDF
TL;DR在存在 Massart 噪声的在线学习任务中，我们研究了广义线性分类器的基本类，并提出了一个高效的算法，达到了错误界限，与在线对手对抗。我们还将在线学习模型扩展到 k 臂上下文强盗设置中，通过使用我们的 Massart 在线学习器设计了一个高效的强盗算法，从而达到至少比在每一轮随机选择一个动作大 (1-1/k)~Delta T - o (T) 的期望奖励。
online learningmassart noiselinear classifiersefficient algorithmcontextual bandit setting
发现论文，激发创造
  • 带有 Massart 噪声的学习半空间的近似最优统计查询难度

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

    Dec, 2020

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

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

    Jun, 2019

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

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

    Jun, 2020

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

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

    Feb, 2020

  • 受限噪音下线性分隔器的高效学习

    研究了线性分离器在 Massart 噪声下的可学习性，提供了第一个在此噪声模型下可以多项式时间学习线性分离器的算法，并证明了传统算法不能达到理想误差。我们的算法是基于活动学习的，并且具有对数标签复杂度。

    Mar, 2015

  • 上下文臂针对高效优化学习

    本文介绍了一种在线学习算法，它使用了一种基于代价敏感分类器的方法，并实现了最优遗憾率，与之前的算法相比，具有指数级别的运行速度优势，并且在反馈延迟方面实现了加性遗憾而非乘性遗憾。

    Jun, 2011

  • 带预测内容的在线强盗学习

    我们考虑了上下文强盗问题，在每个时间点上，代理只能访问上下文的嘈杂版本和误差方差（或该方差的估计）。我们提出了第一个在线算法，与适当的基准相比，在此设置中具有亚线性遗憾，其关键思想是将经典统计中的测量误差模型延伸到在线决策情境中，这是一个非常复杂的问题，因为策略依赖于嘈杂的上下文观察。

    Jul, 2023

  • 信息约束在线学习中的适应性

    研究了如何适应信息获取成本昂贵的在线学习问题中平稳变化环境的影响；提出了一种算法用于处理标签有效预测的问题，并扩展到标签有效的赌博反馈和揭示行动部分监测游戏等领域，显著提高了现有算法的性能。

    Oct, 2019

  • 对抗语境强化学习的核化方法

    通过将属于再现核希尔伯特空间的损失函数纳入到对手性线性背景乐队的在线学习问题的研究中，我们提出了一种计算有效的算法，该算法利用一种新的对损失函数进行乐观偏差估计的方法，在对底层内核进行的各种特征值衰减假设下实现接近最佳的后悔保证。

    Oct, 2023

  • 带部分信息的在线学习小损失界

    研究了拥有部分信息反馈的对抗 (非随机) 在线学习问题，在黑盒模型下能够获得如上小损失的概率，而其独特的设计使它在更多应用如半强盗问题和上下文强盗问题中得到有效的应用，并且能够提供一些之前无法获得的最优保证。

    Nov, 2017