Research map / Bandits and online learning / Online convex optimization and games
Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Require deterministic ski-rental consistency of (1+λ) | Ski-rental algorithms with machine-learned prediction · Ski rental | robustness: (1+1/λ) robustness is necessary | Hurt |
| Require randomized ski-rental robustness γ | Ski-rental algorithms with machine-learned prediction · Ski rental | consistency: \beta\ge\gamma\log\left(1 + \frac{1}{\gamma - 1}\right) | Hurt |
| Require consistency of (1+λ) | Non-clairvoyant scheduling algorithms · Non-clairvoyant scheduling with n jobs | robustness: \gamma \geq \frac{n + n(n+1)\lambda}{1 + \lambda{(n+1)(n+2)}/{2}} | Hurt |
| Use Two-Stage-Schedule: round-robin until the consistency allowance is tight, then process in predicted order | Non-clairvoyant scheduling · Non-clairvoyant scheduling with 2 jobs | robustness: 4/(3-3\lambda) -> (1+1/(1+6\lambda)) | Helped |
| Set consistency to (1+λ) using Two-Stage-Schedule | Non-clairvoyant scheduling · Non-clairvoyant scheduling with 2 jobs | consistency: (1+\lambda) | Helped |
Closest papers by meaning
- Augmenting Online Algorithms with $\varepsilon$-Accurate Predictions (NeurIPS 2022 · similarity 0.92)
- Near-Optimal Consistency-Robustness Trade-Offs for Learning-Augmented Online Knapsack Problems (ICML 2025 · similarity 0.88)
- Online Algorithms with Uncertainty-Quantified Predictions (ICML 2024 · similarity 0.88)
- Overcoming Brittleness in Pareto-Optimal Learning Augmented Algorithms (NeurIPS 2024 · similarity 0.87)
- Non-clairvoyant Scheduling with Partial Predictions (ICML 2024 · similarity 0.87)
- Algorithms with Calibrated Machine Learning Predictions (ICML 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.