Jul, 2024

战略Littlestone维度: 改进的在线战略分类界限

HTML
PDF
TL;DR在线二分类问题中，我们研究了策略性代理可以修改可观测特征以实现积极分类的问题。我们通过特征空间上的有向图模拟可行的操纵集，并假设学习者仅观察到修改的特征而非原始特征。我们引入了战略Littlestone维度，一种新的组合测量方法，捕捉了假设类和操纵图的联合复杂性。我们证明它刻画了可实现设置中确定性学习算法的实例最优错误界限。通过一种精细的从不观察代理的原始特征带来的额外挑战的可知设置到可实现设置的减少，我们在可知设置中实现了改进的遗憾。最后，我们放宽了学习者知道操纵图的假设，而是假设他们的知识由图族来表示。我们得出了在所有代理按照图族中的同一图进行操纵的可实现设置和选择性地建模为图系的对抗选择性设置中的遗憾界限。
发现论文，激发创造
  • 反馈图的在线学习：超越赌博机

    研究在线学习问题中的反馈问题，证明反馈图的结构控制引起的学习难度，并给出了三个类别的反馈图的理论极限表现和影响。

    Feb, 2015

  • 来自显式偏好的战略分类

    研究在线线性分类问题，应对操纵特征的策略代理的对抗性选择和他们操纵向量的揭示偏好，提供一个计算有效的学习算法，获得减小的 Stackelberg 后悔以近似于最佳分类器。

    Oct, 2017

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

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

    Nov, 2017

  • 战略分类的学习损失

    本文研究了利用学习理论来生成具有鲁棒性的决策规则，以及针对机器学习领域中存在的潜在的策略操纵问题，提出了一种新的损失函数，称为策略操纵损失，分析了在已知操纵网络结构和未知操纵网络结构下的学习样本复杂度，并且基于迁移学习技术，定义了一种相似度度量，用于度量操纵网络结构的相似度，得到了具有鲁棒性的学习结果。

    Mar, 2022

  • 关于具备反馈图的在线学习的最小化后悔算法

    本文针对具有强可观测无向反馈图的在线学习问题，在回报上下界方面进行了改进，并使用 FTRL 与 q-Tsallis 熵对结果进行了证明；同时扩展了该技术应用于时间变化图的情形，并提供了适用于所有 alpha>1 的改良下界。

    May, 2023

  • 未知个性化操纵下的战略分类

    本研究研究了战略分类中的基本错误界限和样品复杂性，其中代理可以在一定程度上战术地操纵其特征向量，以便被预测为积极，我们考虑个性化的操纵，并提供在线错误界限和PAC样品复杂性。

    May, 2023

  • 有界损失在线学习游戏的组合特征化

    我们研究了关于任意但有界损失函数的假设类的在线可学习性。我们给出了一种新的与规模敏感的组合维数相关的步进最小二维，并证明它对在线可学习性提供了紧密的定量刻画。作为应用，我们首次对两种自然学习设置进行了在线可学习性的定量刻画：向量值回归和多标签分类。

    Jul, 2023

  • 迁移式在线学习的三分论

    我们对Ben-David、Kushilevitz和Mansour (1997)的可逆在线学习设置中学习者错误的数量提出新的上界和下界。定性地，我们证明了一个三分法，即随着n的增长，学习者所犯错误的最小数量只能取三个明确定义的值之一：n，Θ(log(n))或Θ(1)。此外，这种行为是由VC维度和Littlestone维度的组合确定的。定量地，我们展示了各种将错误数量与众所周知的组合维度相关联的界限。特别地，我们将Θ(1)情况下的常数的已知下界从Ω(√log(d))改进为Ω(log(d))，其中d是Littlestone维度。最后，我们将我们的结果扩展到多类分类和不可知设置。

    Nov, 2023

  • 策略分类的学习差距

    对比标准分类任务，战略分类涉及代理人在修改其特征以获得有利预测的过程中的策略性行为，重点关注战略分类与标准学习之间的可学习差距，并通过提供几乎紧密的样本复杂性和后悔界限来解释这一问题，同时引入两种自然的不确定性情况，以实现一定程度的放松的完全信息设置。

    Feb, 2024

  • 在线策略分类中的错误、操控和保证金

    在一个在线的战略分类问题中，每个到达的代理可以操纵其真实特征向量以获得正面的预测标签，同时付出依赖于操纵量的成本。学习者在仅能访问操纵后的特征的情况下，试图预测代理的真实标签。之后学习者公布其预测，代理的真实标签被揭示。我们提供两种新算法，旨在在战略代理行为的情况下恢复最大边界分类器。我们证明了各种代理成本结构的收敛性、有限错误和有限操纵保证。我们还提供了针对不同成本的具有错误保证的战略感知器的广义版本。我们对真实数据和人工合成数据进行的数值研究表明，新算法在边界、操纵数量和错误数量方面优于以前的算法。

    Mar, 2024