Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms
Authors: Alexander Wei, Fred Zhang
NeurIPS 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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. ... Our work is on the foundations of learning-augmented online algorithms. In particular, we focus on the fundamental limitations and trade-offs inherent to the approach (as opposed to providing new algorithms). Since our work is primarily theoretical, we believe that the immediate impact of our work will be on the academic design of algorithms within this budding research area. |
| Researcher Affiliation | Academia | Alexander Wei UC Berkeley awei@berkeley.edu Fred Zhang UC Berkeley z0@berkeley.edu |
| Pseudocode | Yes | Deterministic-Ski-Rental(y, B): If y B, Buy at the start of day λB . Otherwise, Buy at the start of day B/λ . Randomized-Ski-Rental(y, B): If y B, Let k = λB . Otherwise, Let k = B/λ . Select day i [k] with probability proportional to (1 1/B)k i. Buy at the start of day i. |
| Open Source Code | No | The paper does not include any statement or link indicating that source code for their contributions is openly available. |
| Open Datasets | No | The paper is theoretical and focuses on mathematical proofs and algorithmic analysis; it does not involve training models on datasets. |
| Dataset Splits | No | The paper is theoretical and does not involve experimental validation with dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not involve empirical experiments. Therefore, no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not involve empirical experiments. Therefore, it does not list any specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not involve empirical experiments. Therefore, no experimental setup details, such as hyperparameters or training configurations, are provided. |