We develop a framework for augmenting online algorithms with a machine learned oracle to achieve competitive ratios that provably improve upon unconditional worst case lower bounds when the oracle has low error. Our approach treats the oracle as a complete black box, and is not dependent on its inner workings, or the exact distribution of its errors. We apply this framework to the traditional caching problem ‚Äî creating an eviction strategy for a cache of size k. We demonstrate that naively following the oracle‚Äôs recommendations may lead to very poor performance, even when the average error is quite low. Instead we show how to modify the Marker algorithm to take into account the oracle‚Äôs predictions, and prove that this combined approach achieves a competitive ratio that both (i) decreases as the oracle‚Äôs error decreases, and (ii) is always capped by O(log k), which can beachieved without any oracle input. We complement our results with an empirical evaluation of our algorithm on real world datasets, and show that it performs well empirically even using simple off the shelf predictions.
( events) Timezone: »
Fri Jul 13 02:00 AM -- 02:20 AM (PDT) @ K11
Competitive Caching with Machine Learned Advice