No-Regret Caching via Online Mirror Descent
  We study an online caching problem in which requests can be served by a local
cache to avoid retrieval costs from a remote server. The cache can update its
state after a batch of requests and store an arbitrarily small fraction of each
file. We study no-regret algorithms based on Online Mirror Descent (OMD)
strategies. We show that the optimal OMD strategy depends on the request
diversity present in a batch. We also prove that, when the cache must store the
entire file, rather than a fraction, OMD strategies can be coupled with a
randomized rounding scheme that preserves regret guarantees.
