Published on Thu Oct 22 2020

Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms

Alexander Wei, Fred Zhang

We study the problem of improving the performance of online algorithms by incorporating machine-learned predictions. We focus on the classic problems of ski-rental and non-clairvoyant scheduling and provide optimal trade-offs in various settings.

0
0
0
Abstract

We study the problem of improving the performance of online algorithms by incorporating machine-learned predictions. The goal is to design algorithms that are both consistent and robust, meaning that the algorithm performs well when predictions are accurate and maintains worst-case guarantees. Such algorithms have been studied in a recent line of works due to Lykouris and Vassilvitskii (ICML '18) and Purohit et al (NeurIPS '18). They provide robustness-consistency trade-offs for a variety of online problems. However, they leave open the question of whether these trade-offs are tight, i.e., to what extent to such trade-offs are necessary. In this paper, we provide the first set of non-trivial lower bounds for competitive analysis using machine-learned predictions. We focus on the classic problems of ski-rental and non-clairvoyant scheduling and provide optimal trade-offs in various settings.

Mon Jan 26 2015
Machine Learning
Online Optimization : Competing with Dynamic Comparators
The regret bound adapts to the smaller complexity measure in the problem environment. We apply our results to drifting zero-sum, two-player games where both players achieve no regret guarantees against best outcomes in hindsight.
0
0
0
Sat Apr 25 2015
Machine Learning
Online Convex Optimization Using Predictions
Making use of predictions is a crucial, but under-explored, area of online algorithms. This paper studies a class of online optimization problems where we have external noisy predictions available. We propose a stochastic prediction error model that incorporates correlation among prediction errors.
0
0
0
Thu Feb 28 2019
Machine Learning
Optimal Algorithms for Ski Rental with Soft Machine-Learned Predictions
We consider a variant of the classic Ski Rental online algorithm with applications to machine learning. In our variant, we allow the skier access to a black-box machine-learning algorithm that provides an estimate of the likelihood that there will be at most a threshold number of ski-days.
0
0
0
Sun Nov 14 2010
Machine Learning
Online Learning: Beyond Regret
We study online learnability of a wide class of problems. Our framework simultaneously captures such well-known notions as internal and general Phi-regret. We show that learnability in all these situations is due to control of the same quantities.
0
0
0
Mon Aug 09 2021
Machine Learning
Online Multiobjective Minimax Optimization and Applications
We introduce a simple but general online learning framework. At every round, an adaptive adversary introduces a new game. The learner's goal is to minimize the maximum coordinate of the cumulative vector-valued loss. The resulting one-shot game is not convex-concave, so the
2
1
2
Mon Nov 23 2020
Machine Learning
Learnable and Instance-Robust Predictions for Online Matching, Flows and Load Balancing
This paper proposes a new model for augmenting algorithms with useful predictions that go beyond worst-case bounds on the algorithm performance. By refining existing models, our model ensures predictions are formally learnable and instance robust.
0
0
0