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

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

发现论文，激发创造

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

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

Oct, 2020

学习增广算法的原始-对偶方法

通过对原始双重算法的扩展，将预测信息加入在线算法中，并在多种特定领域采用新算法，与真实及预测的方案相比，当预测准确时优于任何在线算法，但同时可保持当预测误导时的良好保证。

Oct, 2020

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

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

Jun, 2021

带有预测的算法学习

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

Feb, 2022

在学习优化器中，内存、计算和性能之间的实际权衡

本文主要研究了利用学习优化器代替手动设计的优化器来优化机器学习系统，重点探讨了如何平衡模型训练的内存、计算和性能三方面的权衡，并构建了一个更快捷、更高效的学习优化器。

Mar, 2022

多预测在线算法

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

May, 2022

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

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

May, 2022

在线度量算法的混合预测

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

Apr, 2023

通过动态学习器跟踪变化的概率

考虑一个预测器，一个学习者，其输入是一系列离散项目。预测器的任务是在每个时间点进行概率多类别预测，即通过输出一个或多个候选项目，每个项目附加一定概率，从中推测可能出现的下一个项目，然后实际项目被揭示，预测器从这次观察中学习。

Feb, 2024

在线分类与预测

在线分类研究中，研究者利用对未来示例的预测来改进在线学习算法，以减小期望遗憾并提高分类准确性。该研究还证明了当未来示例可准确预测时，在线学习可以与转导式在线学习相媲美，从而对近期基于预测和分布假设的在线算法的研究提供了补充。

May, 2024