在线图算法预测
本文研究了在多个机器学习预测的基础上增强的在线算法。我们提出了一个通用的算法框架,用于多重预测的在线覆盖问题,该算法能够获得与最佳预测器性能相竞争的在线解决方案。该算法还能够同时使竞争性达到最佳预测和最佳在线算法的性能水平,并应用于解决一些经典问题。
May, 2022
介绍了一种算法设计范例 —— 基于学习预测器的算法,将在线学习技术应用于预测器学习、调整鲁棒性 - 一致性折中并绑定样本复杂度,在构建优美的预测器的同时,在二分图匹配、滑雪租赁、页面迁移和作业调度等多场景中优化了多个现有结果,且提供了第一批基于学习理论的担保。
Feb, 2022
本文提出了适用于任意度量任务系统(MTS)(例如缓存、k-server 和凸体追逐)和在线匹配的预测模型,并利用在线算法理论的结果来展示如何使模型更具鲁棒性,其中特别针对缓存问题,本文提出的算法相对于一般 MTS 问题可使得其性能的预测误差表现成指数级别提升。最后,我们使用实际数据集对所提出的方法进行了实证评估,并得出实用性较好的结论。
Mar, 2020
如何在设计在线算法中最佳利用不确定性量化预测,以及如何利用更一般形式的不确定性量化,提出了基于在线学习的框架来在多实例场景中学习如何充分利用不确定性量化作出最佳决策。
Oct, 2023
利用机器学习预测作为辅助,通过引入预测算法结合最近邻算法,探索未知环境的学习增加变种基于线上图探索问题的研究,证明当预测精度高时算法显著优于其他线上算法,并在预测较差时保持良好保证,提供了与预测误差平稳退化的理论最坏情况下的绑定,并通过计算实验证实了结果,同时还扩展了该概念到鲁棒算法的一般框架,通过在给定算法与最近邻算法之间进行谨慎插值,证明了新的性能边界,既利用特定输入的良好性能,又确立了对任意输入的鲁棒性。
Dec, 2021
本文考虑了将机器学习与在线算法设计相结合的新型 “超越最坏情况” 算法分析模型在在线 Steiner 树问题上的应用,其中预测的终端节点可能不正确,算法性能取决于错误预测的数量,可以通过正确预测来突破在线下界并且具有良好的竞争比,同时实验证明该理论具有预测性。
Dec, 2021
在线分类研究中,研究者利用对未来示例的预测来改进在线学习算法,以减小期望遗憾并提高分类准确性。该研究还证明了当未来示例可准确预测时,在线学习可以与转导式在线学习相媲美,从而对近期基于预测和分布假设的在线算法的研究提供了补充。
May, 2024