鲁棒聚合中基本率忽视的惊人益处
我们研究了一个关于二元决策聚合问题,其中既有真实可信的专家,又有对抗性的专家;我们的目标是设计一个稳健的聚合器来预测真实世界的状态,同时最小化与基准决策之间的预期损失差距。我们证明了在一些条件下,截断均值是最优的聚合器选择,并且很多情况下最优聚合器属于分段线性函数类;我们的结果表明,遗憾值与专家总数无关,只取决于对抗性专家的比例。
Mar, 2024
通过建立一个算法框架,我们提供了一种高效的逼近方案,用于在具有有限信息结构的情况下进行预测聚合,同时考虑了 Lipschitz 条件和离散条件。数值实验表明,我们的方法在所考虑的情景中能够提供几乎最优的聚合器。
Jan, 2024
我们研究了一个二元决策聚合问题,两位专家根据观测到的关于未知二元世界状态的私人信号提出二元推荐。在专家的推荐观测情况下,一个不知道信号和状态之间联合信息结构的代理人试图将行动与真实状态匹配。我们在该情景下研究了是否能通过二阶信息进一步提高聚合效果,采用最小化后悔的框架来评估聚合器的性能,与一个知道联合信息结构的全知基准进行比较。我们发现通用的信息结构情况下,二阶信息并没有提供任何好处,没有聚合器能够比一个始终遵循第一个专家推荐的平凡聚合器更好。然而,当我们假设专家信号在给定世界状态的条件下相互独立时,积极的结果出现了。对于确定性聚合器,我们提出了一种利用二阶信息的鲁棒聚合器,可以明显优于没有二阶信息的对手。此外,在两个专家是同质的情况下,并在信号上添加一个非退化假设,我们证明使用二阶信息的随机聚合器可以超越没有二阶信息的最优聚合器。在其他情境中,二阶信息没有益处。我们还将上述结果推广到聚合器的效用函数更一般的情况。
Nov, 2023
本论文探讨了一种统计方法,利用专家的意见而无需真实的事实来推断每位专家的能力,并利用众人之智的原理测量每位专家的能力,进而提出一种完全无监督的朴素贝叶斯分类器的技术,并证明该技术在大类问题中是渐进最优的。同时,将该方法应用于大规模意见聚合、基于有限意见的决策制定。
Aug, 2023
本研究采用贝叶斯方法研究了具有放弃反馈的基于池的主动学习问题,提出了两种新的贪心算法,同时学习分类问题和未知的放弃率,证明了这两种算法均具有近似最优保证,并在各种实际情况下进行了实验验证。
Jun, 2019
本文提出了一种利用基本算法 A 设计跟踪算法的方法,对于二进制序列预测在对数损失下,时间复杂度仅为 O(n^(1+γ)ln n),达到了最优的 O(ln n)的遗憾率。
Oct, 2011
本文研究了聚合理论中的统计学设置,并通过用较小的局部复杂度替换全局复杂度来加强经典聚合理论的结果,包括基于 Leung 和 Barron 的指数权重估计器的局部经典简单限制,并针对 Q - 聚合估计器提出了偏差最优限制。
Jun, 2023
采用指数权重的综合方法,在边际假设下,对于铰链风险(hinge risk),获得了凸聚合的最优速率。 此外,在边际假设下,对于超额贝叶斯风险,获得了模型选择聚合的最优速率。
Mar, 2006
我们研究了专家意见下具有预测的经典问题,假设学习者选择不参与游戏的行动在每次试验中既没有奖励也没有损失,我们提出了 CBA 算法,利用这个假设获得了可以显著改善经典 Exp4 算法的奖励界限。我们将问题视为对置信度评估预测器进行合并,当学习者有选择不参与游戏的选项时。重要的是,我们是首次在普通置信度评估预测器上实现了累积期望奖励的界限。在专家预测器的特殊情况下,我们实现了一种新的奖励界限,显著改善了以前在特殊专家(将不参与视为另一种行动)上的界限。作为一个示例应用,我们讨论了在有限度量空间中学习球的并集。在这个背景设置中,我们设计了 CBA 的高效实现,将运行时间从二次降低到几乎线性与上下文数量相当。初步实验表明 CBA 在现有的 bandit 算法上有所改进。
Feb, 2024