Detta dokument introducerar en ny caching analys som, i motsats till tidigare arbete, inte gör några modellering antaganden för filen begäran sekvens. Vi kastar caching problemet inom ramen för Online Linear Optimization (OLO), och införa en klass av minsta ånger caching politik, som minimerar förlusterna med avseende på den bästa statiska konfigurationen i efterhand när begäran modellen är okänd. Dessa strategier är mycket viktiga eftersom de är robusta till popularitet avvikelser i den meningen att de lär sig att justera sina caching beslut när popularitet modellen ändras. Vi bevisar först en ny lägre gräns för beklagandet av alla caching politik, förbättra befintliga OLO gränser för vår inställning. Då visar vi att Online Gradient Ascent (OGA) policy garanterar en ånger som matchar den nedre gränsen, därför är det universellt optimal. Slutligen flyttar vi vår uppmärksamhet till ett nätverk av caches arrangerade för att bilda en bipartit graf, och visar att Bipartite Subgradient Algorithm (BSA) har ingen ånger.
Nyligen har Ref föreslagit ett nytt tillvägagångssätt för att utforma samordnade cachepoliser inom ramen för linjär optimering online.
Learning to Cache With No Regrets
{'venue': 'IEEE INFOCOM 2019 - IEEE Conference on Computer Communications', 'journal': 'IEEE INFOCOM 2019 - IEEE Conference on Computer Communications', 'mag_field_of_study': ['Computer Science']}