Jul, 2023

在线学习和使用 ERM 预测子解决无限博弈

PDF
TL;DR本文提出了一种基于 ERM 孤注一掷算法的在线二元分类方法，证明了它在真实问题上的收益有限，且在迷惑问题上的收益不断增长。同时，本文还探讨了 ERM 算法在非参数博弈中的应用，提出了一种不依赖于最优反应的学习算法，并将其应用到两人和多人博弈中，证明了算法的有效性和可靠性。
ermonline learningbinary classificationregretlittlestone dimension
发现论文，激发创造
  • 有效的 PAC 学习与回应是 "是" 或者 "否" 的 Oracle 可能吗？

    在本文中，我们探讨了在二分类的 PAC 学习中，是否有比经验风险最小化（ERM）更弱的预测力量仍然能够实现学习，结果表明只需多项式代价就可以使用我们的更弱预测力量来学习概念类，同时也满足了 Alon 等人提出的对于有效性学习的算法原则的要求。

    Jun, 2024

  • 未知分布的高效混合在线学习

    我们提出了一种适用于未知特征生成过程的混合在线学习的、高效的预测方法，证明了该方法可在有限的 VC 类中实现具有次线性的遗憾上限，并在具有 α fat-shattering 维度的类中实现具有次线性的遗憾上限。此外，我们拓展了我们的结果到具有 K 个变化的分布转移场景，并为具有有限策略集合 H 和未知分布的 i.i.d. 生成的上下文以及敌对生成的成本的情境 K 臂赌博机建立了遗憾上限。

    Jan, 2024

  • 正规化与最优多类学习

    这项研究的目的是在多类学习中表征正则化的作用，并使用一种最优学习算法来控制模型容量，该算法与结构风险最小化、最大熵原理和贝叶斯推理相结合。同时引入一种新的学习者，通过在无监督学习阶段学习正则化器，实现结构风险最小化的放松，以及推导学习问题的归纳错误率。最后，引入了对偶误差的泛化和不可知情况的哈明图最优学习算法，通过最大熵程序实现最优学习。

    Sep, 2023

  • 多类学习能力与点最小风险原则

    研究多类预测中的样本复杂度，并提出了设计 ERM 学习器的原则以及使用这些原则来证明对称的多类假说类的样本复杂度的紧束缚定理。此外，通过对 Littlestone 维度的新概括，提供了在线背景和强盗问题中多类学习的错误和遗憾界限的描述。

    Aug, 2013

  • 高效在线学习和拍卖设计

    本文研究了对手环境下的在线学习算法的设计，提出了广义随机扰动跟随者算法，且证明了在一定条件下它是牛逼优而且可以实现消失的后悔；同时，本文也提出了另一个基于拍卖设计的框架，用于帮助拍卖师在选举获得最佳的拍卖方式方面做出决策，并且得到相应的应用。

    Nov, 2016

  • 适用于超出最坏情况对手的 Oracle 高效在线学习

    本文探讨了在线学习的超出最坏情况分析的 Oracle 高效算法，着重于平滑分析设置和 K 提示移项学习。

    Feb, 2022

  • 多类问题的最优学习器

    本文证明了多分类问题的效率最优解必须是不正确的，并提出了一种基于 generalized linear classifiers 的效率最优解的算法。

    May, 2014

  • 未知约束的在线学习

    在线学习中最小化后悔，满足安全约束的广义元算法，估计未知的安全约束，并将在线学习预测转化为满足未知安全约束的预测，同时使用预测误差、各类模型的复杂度和新的复杂度度量来界定算法的后悔上限，同时提供了线性约束情况下的具体算法，使用比例变换平衡乐观探索和悲观约束满足，最小化根号 T 的后悔。

    Mar, 2024

  • 使用优化预言机在非凸博弈中学习

    本文着重考虑在线学习在对抗性，非凸设置下，通过使用离线优化模型，得到了相对应的在线学习模型和统计学习模型之间的计算等价关系，同时提出了一种应用，将该方法应用于求解包括 GAN（生成对称网络）在内的非凸博弈的均衡解。

    Oct, 2018

  • 在线到 PAC 转换：通过遗憾分析获得泛化界

    本文提出了从在线学习的角度推导统计学习算法的泛化界限的新框架，建立在线学习算法与统计学习算法之间的联系，通过构造一种在线学习游戏来实现该框架并得到多种泛化保证。

    May, 2023