带有预测的算法学习

Feb, 2022

Learning Predictions for Algorithms with Predictions

Mikhail Khodak, Maria-Florina Balcan, Ameet Talwalkar, Sergei Vassilvitskii

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

Abstract

A burgeoning paradigm in algorithm design is the field of algorithms with predictions, in which algorithms can take advantage of a possibly-imperfect prediction of some aspect of the problem. While much work has

algorithm prediction online learning sample complexity performance measure

发现论文，激发创造

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

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

Mar, 2024

具有预测功能的算法

介绍应用机器学习预测的算法，旨在实现在预测准确时表现最佳，但当预测出现大误差时仍能恢复到最坏情况下的算法。

Jun, 2020

在线图算法预测

本文研究具有预测的在线图形问题，提出了一个新的度量误差的定义 (metric error)，并给出了一个通用框架，用于在线预测算法。采用这个框架，我们能够获得关于竞争比率的紧密限制，并将其作为度量误差的函数来描述。

Dec, 2021

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

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

Oct, 2023

多预测在线算法

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

May, 2022

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

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

May, 2022

在线度量算法的混合预测

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

Apr, 2023

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

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

May, 2022

在线匹配、流量和负载均衡的可学习和实例鲁棒性预测

本文提出了一种新的模型来增强算法的预测能力，该模型要求算法具有形式上可学性和实例鲁棒性；通过构造在线可学习算法，为网络流量分配问题和受限指派最小化问题提供高质量的预测性能，并证明了这些预测对少量训练实例的数据具有鲁棒性。

Nov, 2020

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

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

Oct, 2020