SYNTOLOGY HomeExplorerAtlasCodeMethodologyAboutDevelopersFeedPricing
Paper · 2009.08228 · NeurIPS · 2020

LeadCache: Regret-Optimal Caching in Networks

Abhishek Sinha, Debjit Paria

arXiv · PDF · Open in the Atlas

Code that ran

We have not lifted any functions out of this paper's repositories yet, so there is nothing we have run. The repositories linked to it are listed below.

Repositories linked to this paper

Some links come from the archived Papers with Code dataset (CC BY-SA 4.0): attribution and licence.

Abstract

We consider an online prediction problem in the context of network caching. Assume that multiple users are connected to several caches via a bipartite network. At any time slot, each user may request an arbitrary file chosen from a large catalog. A user's request at a slot is met if the requested file is cached in at least one of the caches connected to the user. Our objective is to predict, prefetch, and optimally distribute the files on the caches at each slot to maximize the total number of cache hits. The problem is non-trivial due to the non-convex and non-smooth nature of the objective function. In this paper, we propose LeadCache -an efficient online caching policy based on the Follow-the-Perturbed-Leader paradigm. We show that LeadCache is regret-optimal up to a factor of Õ(n 3 8 ), where n is the number of users. We design two efficient implementations of the LeadCache policy, one based on Pipage rounding and the other based on Madow's sampling, each of which makes precisely one call to an LP-solver per iteration. Furthermore, with a Strong-Law-type assumption, we show that the total number of file fetches under LeadCache remains almost surely finite over an infinite horizon. Finally, we derive an approximately tight regret lower bound using results from graph coloring. We conclude that the learning-based LeadCache policy decisively outperforms the state-of-the-art caching policies both theoretically and empirically.

For agents

The same record, over MCP at https://syntology.ai/mcp:

get_harvested_code_for_paper("2009.08228")
get_code_for_paper("2009.08228")
have("2009.08228")

The run record, dated, one paper per request, free:

curl https://syntology.ai/api/ran/2009.08228.json

A badge for a README (the split and the date, never a ratio):

[![Syntology run record](https://syntology.ai/api/ran/2009.08228.svg)](https://syntology.ai/paper/2009.08228)

Connect an agent — have() is free.