在线算法的机器学习预测定制化
本文介绍了在学习增强的在线算法中使用回归技术来预测未来输入参数的方法,并在广义滑雪租赁、装箱问题、最小完成时间调度等一般在线搜索方案的背景下探讨了这种方法。通过在设计回归问题的损失函数中结合在线优化基准,我们显示了这种回归问题样本复杂度的近似上下界,并将我们的结果扩展到了不可知设置。
May, 2022
介绍了一种算法设计范例 —— 基于学习预测器的算法,将在线学习技术应用于预测器学习、调整鲁棒性 - 一致性折中并绑定样本复杂度,在构建优美的预测器的同时,在二分图匹配、滑雪租赁、页面迁移和作业调度等多场景中优化了多个现有结果,且提供了第一批基于学习理论的担保。
Feb, 2022
利用机器学习模型从过去和现在的数据中获得的预测,近期算法设计的先进方法已经显示出提高性能的潜力,并在预测失败时提供最坏情况保证,本文研究在线问题,着重于将学习问题与算法挑战相互整合,并设计了专为所需算法任务而量身定制的在线学习算法,通过细致设计的明确学习算法提出了优化总体性能的新算法,并证明了我们方法的潜力通过改进以前研究中建立的性能界限。
Mar, 2024
如何在设计在线算法中最佳利用不确定性量化预测,以及如何利用更一般形式的不确定性量化,提出了基于在线学习的框架来在多实例场景中学习如何充分利用不确定性量化作出最佳决策。
Oct, 2023
设计在线算法,利用机器学习预测,以超越最坏情况范例,解决各种实际相关在线问题(如调度、缓存、聚类、滑雪租赁等)。通过研究设计具备多个专家的在线算法,以超越静态最佳专家的贪心基准。在新的动态基准中提出了具有 O(log K)性能保证的竞争算法,其中 K 是专家数量,适用于 0-1 在线优化问题。此外,我们的多专家方法提供了一种在线组合多个在线算法的新视角,这是在线算法研究社区长期的核心主题。
Dec, 2023
本文研究了在多个机器学习预测的基础上增强的在线算法。我们提出了一个通用的算法框架,用于多重预测的在线覆盖问题,该算法能够获得与最佳预测器性能相竞争的在线解决方案。该算法还能够同时使竞争性达到最佳预测和最佳在线算法的性能水平,并应用于解决一些经典问题。
May, 2022
通过机器学习预测,本研究提出了算法解决在线有界分配和在线广告拍卖问题,该算法在预测准确时超过了先前的性能界限,而在预测误导时仍能保持标准的最坏情况性能保证。
Feb, 2024
本文提出了适用于任意度量任务系统(MTS)(例如缓存、k-server 和凸体追逐)和在线匹配的预测模型,并利用在线算法理论的结果来展示如何使模型更具鲁棒性,其中特别针对缓存问题,本文提出的算法相对于一般 MTS 问题可使得其性能的预测误差表现成指数级别提升。最后,我们使用实际数据集对所提出的方法进行了实证评估,并得出实用性较好的结论。
Mar, 2020