BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1243
DTSTAMP:20230914T125956Z
SUMMARY:Universal Caching
DESCRIPTION:Speaker: Ativ Joshi (CMI)\n\nAbstract: \nIn the learning litera
 ture\, the performance of an online policy is commonly measured in terms o
 f the static regret metric\, which compares the cumulative loss of an onli
 ne policy to that of an optimal benchmark in hindsight. In the definition 
 of static regret\, the benchmark policy remains fixed throughout the time 
 horizon. Naturally\, the resulting regret bounds become loose in non-stati
 onary settings\, where fixed benchmarks often suffer from poor performance
 . In this paper\, we investigate a stronger notion of regret minimization 
 in the context of an online caching problem. In particular\, we allow the 
 action of the offline benchmark at any round to be decided by a finite sta
 te predictor possessing arbitrarily many states. Using ideas from the univ
 ersal prediction literature in information theory\, we propose an efficien
 t online caching policy with an adaptive sublinear regret bound. To the be
 st of our knowledge\, this is the first data-dependent regret bound known 
 for the universal caching problem. We establish this result by combining a
  recently-proposed online caching policy with an incremental parsing algor
 ithm\, e.g. Lempel-Ziv '78. Our methods also yield a simpler learning-theo
 retic proof of the improved regret bound\, as opposed to the more involved
  and problem-specific combinatorial arguments used in the earlier works.\n
URL:https://www.tcs.tifr.res.in/web/events/1243
DTSTART;TZID=Asia/Kolkata:20221007T160000
DTEND;TZID=Asia/Kolkata:20221007T170000
LOCATION:A201
END:VEVENT
END:VCALENDAR