Browsing by Author "Yang, Daniel"

Learning-augmented algorithms combine classical online algorithms with predictions supplied by machine learning models. They aim to exploit accurate predictor forecasts while retaining worst-case guarantees when predictions are wrong. Most foundational literature assumes a black-box point prediction model, in which the algorithm receives a single predicted value and its competitive ratio is analyzed as a function of some global error $\eta$. This model is broadly applicable but obscures important structure about the predictor.

This thesis surveys and extends the growing body of work on learning-augmented algorithms with nonstandard prediction models. We organize the literature into various families and trace how each axis changes the algorithmic questions being asked, from what a prediction conveys in the first place to how predictions are interpreted and evaluated.

We then contribute new theoretical and experimental results for $\epsilon$-accurate paging. On the theoretical side, we study an adaptive-request variant and show that the achievable competitive ratio is $\Theta (min\{k,1/\epsilon \})$. Experimentally, we compare two policies BlindOracle and TwoStrikes-LRU across various prediction regimes, illustrating the tradeoffs between immediate trust and strike-based filtering.