Recently, Paschos et al. [1]} proposed studying caching as an online convex optimization (OCO) problem [2]}. OCO considers again an adversarial setting, but the metric of interest is the regret, i.e., the difference between the costs incurred over a time horizon \(T\)  by the algorithm and by the optimal offline static solution. Online algorithms whose regret grows sublinearly with \(T\)  are called no-regret algorithms, as their time-average regret becomes negligible for large \(T\) .
Paschos et al. propose a no-regret caching policy based on the classic online gradient descent method (\(\mathrm {OGD}\) ),
under the assumption that (a) the cache can store arbitrarily small fractions of each content (the so-called fractional setting), and (b) the cache state is updated after each request.
