Timezone: »

 
Poster
Parsimonious Learning-Augmented Caching
Sungjin Im · Ravi Kumar · Aditya Petety · Manish Purohit

Thu Jul 21 03:00 PM -- 05:00 PM (PDT) @ Hall E #601
in Poster Session 3 »

Learning-augmented algorithms---in which, traditional algorithms are augmented with machine-learned predictions---have emerged as a framework to go beyond worst-case analysis. The overarching goal is to design algorithms that perform near-optimally when the predictions are accurate yet retain certain worst-case guarantees irrespective of the accuracy of the predictions. This framework has been successfully applied to online problems such as caching where the predictions can be used to alleviate uncertainties. In this paper we introduce and study the setting in which the learning-augmented algorithm can utilize the predictions parsimoniously. We consider the caching problem---which has been extensively studied in the learning-augmented setting---and show that one can achieve quantitatively similar results but only using a \emph{sublinear} number of predictions.

Keywords: OPT: Discrete and Combinatorial Optimization · T: Miscellaneous Aspects of Machine Learning

Author Information

Sungjin Im (University of California, Merced)
Ravi Kumar (Google)
Aditya Petety (University of California Merced)
Manish Purohit (Google Research)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors