Our contributions are summarized as follows.
First, we show that caching policies based on \(\mathrm {OMD}\)  enjoy \(\operatorname{\mathcal {O}}\left(\sqrt{T}\right)\)  regret in the fractional setting. Most importantly, we show that bounds for the regret crucially depend on the diversity of the request process. In particular, the regret depends on the diversity ratio \(R/h\) , where \(R\)  is the size of the batch, and \(h\)  is the maximum multiplicity of a request in a given batch.
Second, we characterize the optimality of OMD caching policies w.r.t. regret under different diversity regimes. We observe that, for a large region of possible values of the diversity ratio, the optimum is either \(\mathrm {OGD}\)  or \(\mathrm {OMD}\)  with a neg-entropy mirror map (\(\mathrm {OMD}_{\mathrm {NE}}\) ). In particular, \(\mathrm {OGD}\)  is optimal in the low diversity regime, while \(\mathrm {OMD}_{\mathrm {NE}}\)  is optimal in the high diversity regime.
Third, \(\mathrm {OMD}\)  algorithms include a gradient update followed by a projection to guarantee that the new solution is in the feasible set (e.g., it does not violate the cache capacity constraints). The projection is often the most computationally expensive step of the algorithm. We show that efficient polynomial algorithms exist both for \(\mathrm {OGD}\)  (slightly improving the algorithm in [1]}) and for \(\mathrm {OMD}_{\mathrm {NE}}\) .
Finally, \(\mathrm {OMD}\)  algorithms work in a continuous space, and are therefore well-suited for the fractional setting originally studied by Paschos et al. Still, we show that, if coupled with opportune rounding techniques, they can also be used when the cache can only store a content in its entirety, while preserving their regret guarantees.
