具有显式预测器的增强学习算法

Mar, 2024

Learning-Augmented Algorithms with Explicit Predictors

Marek Elias, Haim Kaplan, Yishay Mansour, Shay Moran

TL;DR利用机器学习模型从过去和现在的数据中获得的预测，近期算法设计的先进方法已经显示出提高性能的潜力，并在预测失败时提供最坏情况保证，本文研究在线问题，着重于将学习问题与算法挑战相互整合，并设计了专为所需算法任务而量身定制的在线学习算法，通过细致设计的明确学习算法提出了优化总体性能的新算法，并证明了我们方法的潜力通过改进以前研究中建立的性能界限。

Abstract

Recent advances in algorithmic design show how to utilize predictions obtained by machine learning models from past and present data. These approaches have demonstrated an enhancement in performance when the pred

algorithmic design machine learning models online problems learning algorithms performance bounds

发现论文，激发创造

带有预测的算法学习

介绍了一种算法设计范例 —— 基于学习预测器的算法，将在线学习技术应用于预测器学习、调整鲁棒性 - 一致性折中并绑定样本复杂度，在构建优美的预测器的同时，在二分图匹配、滑雪租赁、页面迁移和作业调度等多场景中优化了多个现有结果，且提供了第一批基于学习理论的担保。

Feb, 2022

强化学习增强的缓存：实验研究

使用机器学习和加强式算法提高缓存置换的性能

Jun, 2021

在线算法的机器学习预测定制化

本研究探讨在机器学习算法中加入优化基准以提高在线算法的预测性能，以租赁或购买问题为例，并通过理论边界和数值模拟能够支持此发现。

May, 2022

具有不确定性量化预测的在线算法

如何在设计在线算法中最佳利用不确定性量化预测，以及如何利用更一般形式的不确定性量化，提出了基于在线学习的框架来在多实例场景中学习如何充分利用不确定性量化作出最佳决策。

Oct, 2023

基于回归的增强学习在线算法

本文介绍了在学习增强的在线算法中使用回归技术来预测未来输入参数的方法，并在广义滑雪租赁、装箱问题、最小完成时间调度等一般在线搜索方案的背景下探讨了这种方法。通过在设计回归问题的损失函数中结合在线优化基准，我们显示了这种回归问题样本复杂度的近似上下界，并将我们的结果扩展到了不可知设置。

May, 2022

多预测在线算法

本文研究了在多个机器学习预测的基础上增强的在线算法。我们提出了一个通用的算法框架，用于多重预测的在线覆盖问题，该算法能够获得与最佳预测器性能相竞争的在线解决方案。该算法还能够同时使竞争性达到最佳预测和最佳在线算法的性能水平，并应用于解决一些经典问题。

May, 2022

学习增强在线算法的最优韧性 - 一致性平衡

研究如何将机器学习预测融入在线算法以提高性能，并提供非平凡的下界来衡量竞争分析的最优权衡.

Oct, 2020

有效学习预测人类能力的辅助模型

这篇论文介绍了在专家推迟决策的场景下，利用学习算法提高决策准确性的方法，通过分析一系列代理损失函数的理论性质，设计并使用最小量的数据训练出高效准确的决策系统。

Jul, 2022

在线度量算法的混合预测

本文阐述了一种基于多种算法或预测器的学习增强在线算法技术，通过针对在线问题的分析，设计出与动态组合相竞争的算法，能够在多种预测器之间切换，具有灵活性和实用性。

Apr, 2023

多专家在线覆盖

设计在线算法，利用机器学习预测，以超越最坏情况范例，解决各种实际相关在线问题（如调度、缓存、聚类、滑雪租赁等）。通过研究设计具备多个专家的在线算法，以超越静态最佳专家的贪心基准。在新的动态基准中提出了具有 O（log K）性能保证的竞争算法，其中 K 是专家数量，适用于 0-1 在线优化问题。此外，我们的多专家方法提供了一种在线组合多个在线算法的新视角，这是在线算法研究社区长期的核心主题。

Dec, 2023