恶意专家挑战在线预测的乘法权重算法
研究预测问题与专家意见,基于对抗原语构建算法并实现较好的下界,其中 Classic Multiplicative Weights 算法也实现了最小化参数的效果
Jul, 2016
应用聚合策略进行预测时,需要自适应调整学习速率以避免复杂度和当前损失率之间的分析难题;本文基于 Kalai 和 Vempala(2003)的 “Follow the Perturbed Leader”(FPL)算法,在两种不同的专家类别下得出了可调学习速率的损失界限,其中前者的损失界限与迄今为止最佳结果匹配,而后者为新结果。
Apr, 2005
本文研究了一种在线学习算法,该算法将多个专家的预测结果融合为一个预测结果以提高准确性,并利用特定结构的效用函数设计了激励兼容性和无悔策略两个要求的算法,以应对专家可能误导算法的情况。
May, 2023
论文研究了预测问题和多臂老虎机问题两个具有序列决策的基本问题。特别地,我们关注当对手可能篡改损失时的随机机制,并研究能够实现的鲁棒性水平。本文的主要贡献在于表明,最佳鲁棒性可以通过对所涉及的污染量的平方根依赖来表达。此外,我们还提供了下限,表明上述遗憾边界是紧的。最后,对于多臂老虎机问题,我们还提供了一个近似紧密的下限。
Sep, 2021
研究通过设计具有不同能力的裁判来加权专家,以改善二进制投票问题中的正确率,最终展示在从共同分布中 i.i.d. 抽取的已知能力不确定的一组代理的优化划分,可以更好地解决问题。
Nov, 2022
本文研究了在对手设置下采用几何停止时间进行专家建议的预测经典问题。对于 2 个专家的情况,Cover 提出了最优算法。对于三个专家的情况,我们设计了最优算法和对手,并证明了该算法与一个特定的随机对手的概率匹配算法(类似于汤普森抽样)是最优的,该证明显示概率匹配算法不仅针对这个特定的随机对手是最优的,而且是极小化的。同时我们通过主对偶(primal-dual) 方法同时发展了上限和下限,并为任意数量的专家设计了最优算法和对手的通用框架。
Sep, 2014
本文研究带有机构的二元预测问题,提出了一个模型并采用激励兼容算法设计方法,证明了对于绝对损失函数,IC 算法具有很好的性能保证。同时,通过证明 IC 和非 IC 算法的下界,明确了自私专家在线预测性能与诚实专家在线预测性能之间的差异。
Feb, 2017
本文提出了一种基于扰动随从最优策略算法版本,可以将累积损失通过独立的对称随机游动进行扰动,预测者能够实现期望遗憾最优阶 O (sqrt (n log N)), 且预测者的改变在预期下最多为 O (sqrt (n log N)),同时拓展分析在线组合优化,表明即使在更一般的情况下,预测者也很少在专家之间切换,同时达到近乎最优的遗憾级别。
Feb, 2013
设计在线算法,利用机器学习预测,以超越最坏情况范例,解决各种实际相关在线问题(如调度、缓存、聚类、滑雪租赁等)。通过研究设计具备多个专家的在线算法,以超越静态最佳专家的贪心基准。在新的动态基准中提出了具有 O(log K)性能保证的竞争算法,其中 K 是专家数量,适用于 0-1 在线优化问题。此外,我们的多专家方法提供了一种在线组合多个在线算法的新视角,这是在线算法研究社区长期的核心主题。
Dec, 2023