Source-linked AI summary
Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms
Alexander Wei, Fred Zhang
TL;DR
Prior work on prediction-augmented online algorithms gave robustness-consistency trade-offs but left open whether they were tight. This paper proves lower bounds for ski-rental and non-clairvoyant scheduling, including optimal trade-offs in several settings and matching bounds for two-job scheduling.
Problem
Earlier prediction-augmented online algorithms offered consistency-robustness trade-offs but did not establish whether those trade-offs were necessary.
Source: §1 · p. 2Method
The paper proves lower bounds for learning-augmented ski-rental and non-clairvoyant scheduling to assess the necessity of their robustness-consistency trade-offs.
Source: §1 · pp. 2–3Results
The paper gives tight ski-rental lower bounds matching and matching upper and lower bounds for the full two-job scheduling trade-off.
Source: §1 · pp. 2–3Takeaways & Limitations
Good performance under perfect predictions can require substantial sacrifices in overall robustness, making the trade-off intrinsic to learning-augmented online algorithms.
Source: §1 · p. 3The results leave tight robustness-consistency trade-offs for other learning-augmented online problems, such as online matching and ski-rental generalizations, as future work.
Source: §4 · p. 11
Abstract
from arXiv · showhide
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.
1 Introduction
Prior work combined predictions with online algorithms to trade performance under accurate predictions for worst-case guarantees, but did not establish whether those trade-offs were necessary. This paper gives lower bounds for ski-rental and non-clairvoyant scheduling, including matching bounds for two-job scheduling.
1 Introduction
- Earlier work introduced consistency and robustness trade-offs for prediction-augmented online algorithms but left their necessity and tightness open.The paper frames its lower bounds as addressing that gap.Source: §1 · p. 2
1.1 Our results
- For n-job non-clairvoyant scheduling, the lower bound is tight at both endpoints, including the classical round-robin guarantee.At λ = 0, the lower bound is n; at λ = 1 − 2/(n + 1), it matches 2 − 2/(n + 1).Source: §1 · p. 3, Non-clairvoyant scheduling · p. 4
- The results show that demanding good performance under perfect predictions can require substantial sacrifices in overall robustness.The paper describes this trade-off as intrinsic to learning-augmented online algorithm design.Source: §1 · p. 3
- For ski-rental, deterministic and randomized lower bounds match the guarantees of.The ski-rental results establish tight robustness-consistency trade-offs in both settings.Source: §1 · p. 2, Figure 1.1 · p. 3, Ski-rental · p. 3
- For two-job non-clairvoyant scheduling, the paper gives a tight trade-off: (1 + λ)-consistency and (1 + 1/(1 + 6λ))-robustness for λ ∈ (0, 1/3).The proposed algorithm also improves on and is 2-competitive across parameter choices.Source: §1 · p. 3, Figure 1.2 · p. 4, Non-clairvoyant scheduling · p. 4
1.2 Related work
- The paper extends classical online ski-rental and scheduling analysis to predictions, while distinguishing its setting from stochastic models because it assumes no input distribution.Related work also situates prediction-augmented online algorithms among other learning-based algorithmic settings.Source: §1.2 · p. 5
1.3 Preliminaries and notations
- The notation defines ALG as the algorithm's cost and OPT as the offline optimum; their ratio gives the competitive ratio, with consistency applying when input equals prediction.Robustness bounds the ratio over all input-prediction pairs.Source: §1.3 · p. 5
2 Ski Rental
The section establishes ski rental with a prediction of season length, then studies lower bounds on the robustness-consistency trade-off. Deterministic and randomized analyses recover trade-offs matching known algorithmic guarantees in the stated regimes.
2 Ski Rental
- Ski rental asks a skier to rent for $1 per day or buy for $B while the season length is unknown; the prediction supplies an estimate y of that length.The cited deterministic and randomized algorithms use a parameter λ ∈ (0, 1) to govern their robustness-consistency trade-off.Source: §2 · pp. 5–6
2.2 Randomized Lower Bound
- For large B and y ≫ B, the randomized lower bound essentially matches the ski-rental guarantee of.The analysis formulates consistency and robustness as linear constraints and reduces the resulting infinite linear program before solving it analytically.Source: §2 · p. 6, §2.2 · pp. 7–8
2.1 Deterministic Lower Bound
- For deterministic algorithms, the lower bound approaches 1 + 1/λ for large B when consistency is at most 1 + λ.The argument forces the purchase day t ≤ λB + 1 under accurate predictions, then considers an adversarial season ending at t.Source: §2.1 · pp. 6–7
3 Non-clairvoyant Scheduling
This section studies prediction-augmented non-clairvoyant scheduling, where job lengths are unknown until completion and the objective is total completion time. It establishes lower bounds on robustness-consistency trade-offs and a matching two-job algorithm.
3 Non-clairvoyant Scheduling
- The problem requires completing jobs of unknown lengths on one processor, minimizing the sum of their completion times, with preemption allowed.The processor learns a job’s length only when that job finishes.Source: §3 · p. 8
3.1 A General Lower Bound
- For n jobs, the lower bound on the robustness-consistency trade-off is tight at the endpoints of the curve.The classic round-robin guarantee makes the trade-off tight at λ = 0 and λ = 1 − 2/(n + 1).Source: §3.1 · p. 8
3.2 A Tight Complete Trade-off for Two Jobs
- For two jobs, any algorithm achieving (1 + λ)-consistency must be at least 1 + 1/(1 + 6λ)-robust for λ ∈ (0, 1/3).The same lower bound extends to n > 2 by adding dummy jobs with zero predicted and actual processing times.Source: §3.2 · p. 10
- The lower-bound construction uses identical unit predictions, then changes actual processing times adversarially while preserving those predictions.The adversarial instance sets x2 just above the amount of processing job 2 receives before job 1 finishes.Source: §3.2 · p. 10
- The two-job algorithm runs round-robin until the consistency constraint is tight, then prioritizes jobs in increasing predicted-time order.If it detects a prediction mismatch, it switches to round-robin permanently.Source: §3.2 · p. 10
- For two jobs, Two-Stage-Schedule achieves (1 + λ)-consistency and (1 + 1/(1 + 6λ))-robustness for λ ∈ (0, 1/3), matching the lower bound.The lower bound applies to any algorithm with (1 + λ)-consistency.Source: §3.2 · p. 10
4 Conclusion
The paper gives lower bounds for learning-augmented ski-rental and non-clairvoyant scheduling, showing that robustness-consistency trade-offs are intrinsic to these algorithms. It points to tight trade-offs for other online problems as future work.
4 Conclusion
- The paper establishes lower bounds for learning-augmented ski-rental and non-clairvoyant scheduling.It characterizes the robustness-consistency trade-off as intrinsic to online algorithms that balance worst-case robustness with performance under accurate predictions.Source: §4 · pp. 10–11
- The authors identify tight trade-offs for online matching and generalizations of ski-rental as directions for future investigation.They propose applying their techniques to those problems.Source: §4 · p. 11
A Proof of Theorem 1.2
The proof models learning-augmented ski-rental as an infinite linear program over probabilities of buying on each day. It simplifies the constraints and derives an asymptotic lower bound on consistency as a function of robustness.
A Proof of Theorem 1.2
- The proof represents the probability of buying on day i with variable p_i and imposes probability-distribution, consistency, and robustness constraints.The LP uses γ for robustness and β for consistency, assuming β < γ because otherwise consistency is redundant.Source: A Proof of Theorem 1.2 · p. 15
- When y ≥ 2B − 1, constraints C(B) through C(y) are redundant because they are dominated by the consistency constraint.The appendix then reduces the LP to B + 1 constraints and y variables.Source: A Proof of Theorem 1.2 · p. 15
- For y ≥ 2B − 1, a feasible solution can set p_i = 0 for all i ≥ y + 1, leaving only robustness constraints C(1) through C(B − 1) as nonredundant.This follows from the redundant-variable lemma and its corollary.Source: A Proof of Theorem 1.2 · pp. 15–16
- A feasible solution can be chosen so that whenever p_k > 0, all preceding robustness constraints are tight.The proof obtains this structure by shifting probability mass while reducing the robustness-slack vector lexicographically.Source: A Proof of Theorem 1.2 · pp. 16–17
- As B → ∞, the lower bound on consistency β approaches γ log(1 + 1/(γ − 1)).Source: A Proof of Theorem 1.2 · p. 19
B Proof of Lemma 3.2
The proof analyzes Two-Stage-Schedule, which combines round-robin processing with a predicted-time greedy stage and reverts to round-robin when it detects a prediction error. For two jobs, it verifies consistency under perfect predictions and bounds robustness under mispredictions.
B Proof of Lemma 3.2
- The algorithm runs round-robin before prioritizing unfinished jobs by predicted time, and switches to round-robin forever if a job’s actual processing time differs from its prediction.The first stage runs for at most λn · OPT_y units of time.Source: B Proof of Lemma 3.2 · p. 19
- With perfect predictions, the two-job schedule achieves (1 + λ)-consistency in both cases: job 1 finishes during stage 1 or remains unfinished at its end.The proof gives ALG = 3y1 + y2 in the first case and ALG = (1 + λ)OPT in the second.Source: B Proof of Lemma 3.2 · p. 20
- If a mismatch is detected or job 1 finishes during stage 1, the schedule is round-robin and has competitive ratio 4/3.The proof notes that 4/3 is below 1 + 1/(1 + 6λ) for λ ∈ (0, 1/3).Source: B Proof of Lemma 3.2 · p. 20
- In the remaining misprediction cases, the competitive ratio is bounded by 1 + 1/(1 + 6λ) when the job completion order and processing times meet the analyzed conditions.The proof also finds a 4/3 bound in cases where OPT = 2x1 + x2.Source: B Proof of Lemma 3.2 · p. 20