Our numerical experiments indicate that the gap between the regimes in which OGD and \(\mathrm {OMD}_\mathrm {NE}\)  are optimal, w.r.t. the diversity ratio, is narrow; this suggests that our characterization of the two regimes can be further improved. Proving the optimality of \(\mathrm {OMD}_\mathrm {NE}\)  within the \(q\) -norm mirror map class, as opposed to merely its domination over OGD, is also open. Finally, devising strongly polynomial, efficient algorithms for the Bregman projection when \(q\in (1,2)\) , and characterizing update costs in this setting, also remain open problems.


Gradient-based algorithms
Proof of Theorem  REF
Bubeck [1]} provides a general bound on the regret of OMD with \(\rho \) -strongly convex mirror map \(\Phi \)  w.r.t a norm \(\left\Vert .\right\Vert \)  on a convex set \(\mathcal {S}\) . The map \(\Phi (x) = \frac{1}{2}\left\Vert x\right\Vert _q^2, q \in (1, 2]\)  is \(\rho =q-1\)  strongly convex w.r.t \(\left\Vert .\right\Vert _q\)  over \(\mathcal {D} = \mathbb {R}^N\)  a direct result from [2]}, the dual norm of \(\left\Vert .\right\Vert _q\)  is \(\left\Vert .\right\Vert _p\)  (Hölder's inequality). The gradients are bounded in the dual norm \(\left\Vert \nabla f_{r}(\mathbf {x}_t)\right\Vert _p \le L, \forall \mathbf {r} \in \mathcal {R}\) , take \(\mathcal {S} = \mathcal {X}\) , OMD algorithm satisfies:
\(\mathrm {Regret}_T(\mathrm {OMD}_\Phi ) \le \frac{D_{\Phi }(\mathbf {x}_*, \mathbf {x}_1)}{\eta } + \frac{\eta }{2 \rho } \sum ^T_{t=1} \left\Vert \mathbf {g}_t\right\Vert ^2_p\) 
where \(\mathbf {x}_*\)  is the best fixed decision in hindsight.
Bounding \(D_\Phi (\mathbf {x}_*, \mathbf {x}_1)\) : The minimum value of \(\Phi (x)\)  over \(\mathcal {X}\)  is achieved when we spread the capacity mass \(k\)  over the decision variable, giving \(x_i = \frac{k}{N}, i \in \mathcal {N}\) . If we select \(\mathbf {x}_1\)  to be the minimizer of \(\Phi (\mathbf {x})\) , then we have \(\nabla \Phi ^T(\mathbf {x}_1) (\mathbf {x} - \mathbf {x}_1) \ge 0 , \forall \mathbf {x} \in \mathcal {X}\)  [3]}.
\(D_\Phi (\mathbf {x}_*, \mathbf {x}_1) &= \Phi (\mathbf {x}_*) - \Phi (\mathbf {x}_1) - \nabla {\Phi (\mathbf {x}_1)}^T (\mathbf {x}_* - \mathbf {x}_1) \le \Phi (\mathbf {x}_*) - \Phi (\mathbf {x}_1)\) 

We have:
\(\Phi (\mathbf {x}_1) =\frac{1}{2} \left(\left(\frac{k}{N}\right)^q N\right)^{\frac{2}{q}} = \frac{1}{2} k^2 N^{2\left(\frac{1}{q} - 1\right)} = \frac{1}{2} k^2 N^{-\frac{2}{p}}\) 
\(\Phi (\mathbf {x}_*) =\frac{1}{2} k^{\frac{2}{q}} = \frac{1}{2} k^2 k^{-\frac{2}{p}}\) 
Plugging in (REF ), we get:
\(D_\Phi (\mathbf {x}_*, \mathbf {x}_1) \le \frac{1}{2} k^2 \left(k^{-\frac{2}{p}} - N^{-\frac{2}{p}} \right)\) 
Note that the maximum of \(\left\Vert \mathbf {r}\right\Vert _p\)  is achieved when \(\frac{R}{h}\)  components are set to \(h\) , then we take the following bound on the gradients:
\(L &= \underset{r \in \mathcal {R}}{\max } \left\Vert  \nabla f_{\mathbf {r}} (\mathbf {x})\right\Vert _p \le \underset{\mathbf {r} \in \mathcal {R}}{\max } \left\Vert \mathbf {w}\right\Vert _\infty \left\Vert  \mathbf {r}\right\Vert _p = \left\Vert \mathbf {w}\right\Vert _\infty h \left( \frac{R}{h}\right)^\frac{1}{p}.\) 

Plugging (REF ) and (REF ) in (REF ), and we select the learning rate that achieves the tightest bound
\(\eta = \sqrt{\frac{(q-1) k^2 \left(k^{-\frac{2}{p}} - N^{-\frac{2}{p}}\right)}{\left\Vert w\right\Vert ^2_\infty h^2 \left(\frac{R}{h}\right)^{\frac{2}{p}} T}}.\) 
This gives the desired upper bound.

Proof of Corollary  REF
Using the regret bound given in (REF ), set \(q = 2\) , we obtain:
\(\text{Regret}_T(\text{OGD}) \le \left\Vert \mathbf {w}\right\Vert _\infty h k \left(\frac{R}{h}\right)^{\frac{1}{2}} \sqrt{\left(k^{-1} - N^{-1}\right)T} =\left\Vert \mathbf {w}\right\Vert _\infty \sqrt{ hR k \left(1 - \frac{k}{N}\right) T}.\) 
The bound is obtained.

Proof of Corollary  REF
Take \(\alpha = \frac{k}{N}\)  and \(\beta = \frac{N h }{R}\) , we can simplify (REF ) to:
\(\text{Regret}_T(\text{OMD}_{q\text{-norm}}) &\le \left\Vert \mathbf {w}\right\Vert _\infty R \beta ^{\frac{1}{q}} \sqrt{\frac{\alpha ^{2/q} - \alpha ^2}{q-1} T}\) 

We take the limit \(q \rightarrow 1\) , to obtain:
\(\text{Regret}_T(\text{OMD}_{1\text{-norm}}) &\le \underset{q\rightarrow 1}{\text{lim}} \left\Vert \mathbf {w}\right\Vert _\infty R \beta ^{\frac{1}{q}} \sqrt{\frac{\alpha ^{2/q} - \alpha ^2}{q-1} T} \\&= \left\Vert \mathbf {w}\right\Vert _\infty R \beta \sqrt{ \left[ \alpha ^{2/q}\right]^{\prime }_{q=1} T}\\&= \left\Vert \mathbf {w}\right\Vert _\infty R \beta \sqrt{\left[ -2 q^{-2} \alpha ^{2/q}\log (\alpha )\right]_{q=1} T}\\&= \left\Vert \mathbf {w}\right\Vert _\infty R \alpha \beta \sqrt{ 2 \log (\alpha ^{-1}) T}\\&= \left\Vert \mathbf {w}\right\Vert _\infty h k \sqrt{ 2 \log (\frac{N}{k}) T}\) 

Proof of Theorem  REF
We take the simplified version of the regret of the general class of \(q\) -norm mirror maps in (REF ), select \(\alpha = \frac{k}{N}\)  and \(\beta = \frac{N h }{R}\) , we get:
\(\text{Regret}_T(\text{OMD}_{q\text{-norm}}) &\le \left\Vert \mathbf {w}\right\Vert _\infty R \phi (q) \sqrt{T}\) 

where \(\phi (q) := \beta ^{\frac{1}{q}} \sqrt{\frac{\alpha ^{2/q} - \alpha ^2}{q-1}}\) .
The tightest regret bound is achieved with \(q^*\)  that minimizes \(\phi (q)\) .
Computing the first derivative:
\(\phi ^{\prime }(q) = - \alpha ^2 \beta ^{\frac{1}{q}} \frac{q^2 \left(\alpha ^{2/q - 2} - 1\right)+ 2 (q-1) \left( \alpha ^{2/q - 2}\log (\alpha ) + \left(\alpha ^{2/q - 2} - 1\right) \log (\beta )\right) }{2 q^2 (q-1)^2 \sqrt{\frac{\alpha ^{2/q} - \alpha ^2}{q-1}}}\) 

The function \(-J(q)\)  determines the sign of \(\phi ^{\prime }(q)\) , we take:
\(J(q) &= q^2 \left(\alpha ^{2/q - 2} - 1\right)+ 2 (q-1) \left( \alpha ^{2/q - 2}\log (\alpha ) + \left(\alpha ^{2/q - 2} - 1\right) \log (\beta )\right)\\&\ge 2 q (1-q) \log (\alpha ) + 2 (q-1)\left(2\frac{1-q}{q} \log (\alpha ) \log (\alpha \beta ) + \log (\alpha ) \right)\\&\ge 2 q (q-1) \left( \left(1-q\right)\log (\alpha ) + 2\frac{1-q}{q} \log (\alpha ) \log (\alpha \beta ) \right)\) 

We have \(\left(1-q\right)\log (\alpha ) \ge 0\)  and \(\frac{1-q}{q} \log (\alpha ) \ge 0\) . We take \(\frac{R}{h} \le k\) , this gives \(\alpha \beta \ge 1\)  and \(J(q) \ge 0 \Rightarrow \text{sign}(\phi ^{\prime }(q)) = - \text{sign}(J(q)) =-1\) .
\(\phi (q)\)  is a decreasing function of \(q \in (1,2]\)  when \(\frac{R}{h} \le k\) .

Proof of Theorem  REF
We have the following regret upper bound for the \(q\) -norm mirror map, as \(q \rightarrow 1\)  from Corollary REF :
\(\text{Regret}_T(\text{OMD}_{1\text{-norm}}) &\le \left\Vert \mathbf {w}\right\Vert _\infty h k \sqrt{ 2\log \left(\frac{N}{k}\right) T}.\) 

Simplifying the upper bound, we take from [4]}:
\(\text{log}(u + 1) \le \frac{u}{\sqrt{u + 1}}, u \ge 0\) 

Take \(u = \frac{N}{k} - 1\) , note that \(N \ge k>0\) , we get \(u \ge 0\)
\(\text{log}(\frac{N}{k}) &\le \frac{N - k}{\sqrt{Nk}} = \sqrt{\frac{N}{k}} \left( 1 - \frac{k}{N}\right), \forall i \in \mathcal {N}\) 
\(\text{Regret}_T(\text{OMD}_{1\text{-norm}}) &\le \left\Vert \mathbf {w}\right\Vert _\infty k h\sqrt{2 \text{log}(\frac{N}{k}) T}\\&\le \left\Vert \mathbf {w}\right\Vert _\infty \sqrt{2 \sqrt{ N k } h^2 k \left(1 - \frac{k}{N}\right) },\text{Using (\ref {log_upper_bound})}\) 

We can take \(\frac{R}{h} \ge 2 \sqrt{Nk}\)  for this bound to be tighter than the OGD bound obtained in Corollary REF .

Proof of Theorem  REF
We have that the strong convexity constant using [5]} is \(\rho = \frac{1}{k}\)  w.r.t the \(\left\Vert .\right\Vert _1\)  over \(\mathcal {X}\) . The dual norm of \(\left\Vert .\right\Vert _1\)  is \(\left\Vert .\right\Vert _\infty \) , take \(p \rightarrow \infty \)  in (REF ) to get \(L = \left\Vert \mathbf {w}\right\Vert _\infty h\) . We use the general regret bound in [1]} for OMD strategies, to obtain:
\(\mathrm {Regret}_T(\mathrm {OMD}_\Phi ) \le \frac{D_{\Phi }(\mathbf {x}_*, \mathbf {x}_1)}{\eta } + \frac{\eta }{2 \rho } \sum ^T_{t=1} \left\Vert \mathbf {g}_t\right\Vert ^2_\infty \) 
\(x_1\)  with \(x_{1,i} =k / N, \forall i \in \mathcal {N}\)  is minimizer of \(\Phi \) , note that the best fixed decision in hindsight \(x_* \in \mathcal {X} \cap \lbrace 0,1\rbrace ^N\)  is an integral point, we have \(\Phi (x) \le 0, \forall x \in X\)  and the equality can be achieved at \(x= x_*\) .
\(D_\Phi (x_*, x_1) \le \Phi (x_*) - \Phi (x_1) = -\Phi (x_1) = -\sum ^N_{i=1} \frac{k}{N} \log \left(\frac{k}{N}\right) = k \log \left(\frac{N}{k}\right)\) 
Plugging the above bounds in (REF ). Similar to the Proof REF , we select the learning rate that gives the tightest upper bound, that is:
\(\eta = \sqrt{\frac{2 \log (\frac{N}{k})}{\left\Vert w\right\Vert ^{2}_\infty h^2 T}} \) 
This gives the desired upper bound of regret.

Proof of Theorem  REF
\(\textstyle \prod _{\mathcal {X} \cap \mathcal {D}}^\Phi (\mathbf {y}) &= \underset{\mathbf {x} \in \mathcal {X}\cap \mathcal {D}}{\mathrm {argmin}} \, D_{\Phi }(\mathbf {x},\mathbf {y}) \\&= \underset{\mathbf {x} \in \mathcal {X} \cap \mathcal {D}}{\mathrm {argmin}} \sum ^N_{i=1} \left(x_i\mathrm {log}\left(\frac{x_i}{y_i}\right) - x_i + y_i \right)\) 

We adapt the Euclidean projection algorithm in [7]}. We have \(x_i > 0\)  is implicitly enforced by the negentropy mirror map \(\Phi \) , because \(\Phi \)  is locally increasing at the boundary of \(\mathcal {D}\) , the minimizer can't lie in a point that has a component \(x_i =0\)  for any \(i\in \mathcal {N}\) . \(D_{\Phi } (\mathbf {x},\mathbf {y})\)  is convex in \(\mathbf {x}\) , \(D_{\Phi } (\mathbf {x},\mathbf {y}) = \Phi (\mathbf {x}) - \Phi (\mathbf {y}) - \Phi (\mathbf {y})^T (\mathbf {x} - \mathbf {y})\) , since \(\Phi (\mathbf {x})\)  is strongly convex [5]} over \(\mathcal {X}\)  and \(-\Phi (\mathbf {y})^T (\mathbf {x} - \mathbf {y})\)  is linear in \(\mathbf {x}\) , then we can find a unique solution to the above optimization problem. The Lagrangian function of the above problem:
\(\mathcal {L} (\mathbf {x}, \mathbf {\beta }, \gamma ) = \sum ^N_{i=1} \left(x_i\mathrm {log}\left(\frac{x_i}{y_i}\right)- x_i + y_i\right) - \sum ^N_{i=1} \beta _i \left(1-x\right) - \gamma \left(\sum ^N_{i=1} x_i - k\right)\) 

At optimal \(x\)  the following KKT conditions hold:
\(\mathrm {log}(x_i) - \mathrm {log}(y_i) + \beta _i - \gamma = 0  \\x_i \le 1  \\\beta _i \ge 0  \\\sum ^N_{i=1} x_i = k  \\\beta _i (1-x_i) =0 \) 



Without loss of generality, the components of \(\mathbf {x}\)  are in non-decreasing order. Let \(b\)  be the index of the largest component of \(\mathbf {x}\)  smaller than 1.
\(x_1 \le ... \le x_b < x_{b+1} = ... = x_N = 1 \,\,\, \text{if} \, b < N \\x_1 \le x_2 \le ... \le x_N < 1 \,\,\, \text{if} \, b = N \) 

For \(i = 1, ..., b\) , () \(\Rightarrow \)  \(\beta _i = 0\) , and then from (REF ), \(\mathrm {log}(y_i) + \gamma = \mathrm {log}(x_i)< 0\)

For \(j = b+1, ..., N\) : as \(\beta _j \ge 0\)  from (), we get \(0 = \mathrm {log}(x_j) = \mathrm {log}(y_j) - \beta _j + \gamma \le \mathrm {log}(y_j) + \gamma \)

We define \(y_{N+1} = +\infty \) , then both conditions(REF ) and () become:
\(y_1 e^\gamma \le ...\le y_{b} e^\gamma < 1 \le y_{b+1} e^\gamma \le ... \le y_{N} e^\gamma \) 
If the components of \(\textbf {y}\)  are ordered in ascending order, so are the components of \(\mathbf {x}\) , then the conditions in (REF ) can be further simplified to:
\(y_{b} e^\gamma < 1 \le y_{b+1} e^\gamma \) 
Therefore, we are required to find a valid \(b \in \mathcal {N}\) . Using the sum constraint ():
\(k = \sum ^N_{i=1}{x_i} = N-b + \sum _{i = 1}^{b} e^{\mathrm {log}(y_i) + \gamma } = N-b +e^\gamma \sum _{i = 1}^{b} y_i\) 
For a given \(b\)  we have:
\(m_b := e^{\gamma } & = \frac{k + b - N }{\sum _{i=1}^{b}{y_i}} = \frac{k+b-N}{\left\Vert y\right\Vert _1 - \sum _{i=b+1}^{N} {y_i}}\) 

We observe that necessarily \(b \in \lbrace  N - k +1, \dots , N\rbrace \) . In fact, we cannot have \(b \le N-k\) . If \(b = N - k\) , we get \(\sum _{i = N-k+1}^{N} x_i = k\) , the capacity constraint implies that \( x_i = 0, \forall i \le b\) , but we must have \(x_i > 0\)  since \(x \in \mathcal {X} \cap \mathcal {D}\)  and \(\mathcal {D} = R_{>0}^N\) , therefore, \(b\)  can only take the values \(b \in \lbrace N-k+1,..., N\rbrace \) . As \(b > N - k\) , then we only require the largest \(k\)  components of \(\mathbf {y}\) .
The Negentropy Bregman divergence projection, sets the components (\(x_i > x_{b}, \forall i \in \mathcal {N}\) ) to 1 and multiplies the rest by \(m_{b}\) , we can avoid updating the components at each projection step. In fact we can only change the components \(x_i, i>b\)  (those that should be set equal to 1) to \(\frac{1}{m_b}\) . At any time \(t\) , we can recover the value of \(x_{t,i}\)  by \(P = \prod _{i=1}^{t}{m_{b,i}}\) , where \(m_{b,t}\)  is the returned \(m_b\)  from the Bregman projection at time step t. Then at any time step, the actual value of the decision variable is \(\mathbf {x} P\) .
When \(\frac{R}{h} = 1\) , Alg. 1 leads to only a single state coordinate update. The projection step takes \(\operatorname{\mathcal {O}}\left(k\right)\) , and an extra \(\operatorname{\mathcal {O}}\left(\log (k)\right)\)  to maintain top-\(k\)  components of \(\mathbf {x}_t\)  sorted online. The norm \(\left\Vert y\right\Vert _1\)  is required to compute \(m_b\) , and this value is computed in \(\operatorname{\mathcal {O}}\left(1\right)\)  steps. Given that \(\left\Vert x_{t}\right\Vert _1 = k\) , and with mirror descent update rule in (REF ), we get \(\left\Vert \mathbf {y}_{t+1}\right\Vert _1 = k + x_{t,i^*} \left(e^{\eta w^{\prime }_{i^*} r_{t, i^*}} - 1\right)\) , where \(i^*\)  is the index of the requested file in \(\mathbf {r}_t\) . This gives the overall time complexity of \(\operatorname{\mathcal {O}}\left(k\right)\)  per iteration of OMD.
In the general setting of \(R,h\) , the projection step takes \(\operatorname{\mathcal {O}}\left(k\right)\)  steps per iteration, a partial sort is required to maintain top-\(k\)  components of \(\mathbf {y}_t\)  sorted; this can be done using partial sorting in \(\operatorname{\mathcal {O}}\left(N + k \log (k)\right)\)  [9]}. The norm \(\left\Vert \mathbf {y}\right\Vert _1\)  can be computed in \(\operatorname{\mathcal {O}}\left(N\right)\) . This gives the overall time complexity of \(\operatorname{\mathcal {O}}\left(N + k \log (k)\right)\)  per iteration of OMD.

Online rounding
Proof of Theorem  REF
Consider a cache with capacity \(k = 1\)  , a catalog of size \(N = 2\)  and the following sequence of requests \(\lbrace 1,2,1,2,\dots \rbrace \) , and the files have equal update costs \(w^{\prime }_1=w^{\prime }_2 = 1\) . We initialize the cache to the state \(\mathbf {x}_1 = \left(\frac{1}{2}, \frac{1}{2}\right)\) . Consider a policy that adds \(\eta = \Theta (\frac{1}{\sqrt{T}})\)  fraction to the component corresponding to the file requested at time \(t\) , and reduces the other component by \(\eta \) , this is similar to the behavior of gradient method, where a fraction in the order of \(\eta \)  is added to the component where we experience the loss, and the projection reduces this fraction from the other component, to satisfy the capacity constraint. The policy generates the following sequence of decisions:
\(\lbrace \mathbf {x}_1, \mathbf {x}_2, \mathbf {x}_3,\mathbf {x}_4,\dots \rbrace  = \left\lbrace \left(\frac{1}{2} , \frac{1}{2}\right), \left(\frac{1}{2} + \eta , \frac{1}{2} - \eta \right), \left(\frac{1}{2}, \frac{1}{2}\right), \left(\frac{1}{2}+\eta , \frac{1}{2} - \eta \right), \dots \right\rbrace \) 
Online independent sampling scheme, decomposes \(\mathbf {x}_1\)  into two integral states \((1,0)\)  w.p. \(\frac{1}{2}\)  and \((0,1)\)  w.p. \(\frac{1}{2}\) , and decomposes \(\mathbf {x}_2\)  into two integral states \((1,0)\)  w.p \(\frac{1}{2} + \eta \)  and \((0,1)\)  w.p. \(\frac{1}{2} - \eta \) , similarly to the fractional setting, the integral movement from \((0,1)\)  to \((1,0)\)  comes for free when the content requested is 1, since this cost is already accounted for in the service cost. The update cost experienced in expectation from \(t=1\)  to \(t=2\)  is:
\(\mathbb {E}\left[\mathrm {UC}_{\mathbf {r}_1}(Z_1, Z_2)\right] = \frac{1}{2} \left(\frac{1}{2} - \eta \right) \) 
The decomposition of \(\mathbf {x}_3\)  is the same as \(\mathbf {x}_1\) , and now the movement \((1,0)\)  to \((0,1)\)  comes for free since content 2 is requested, therefore, the update cost experienced in expectation from \(t=2\)  to \(t=3\)  is:
\(\mathbb {E}\left[\mathrm {UC}_{\mathbf {r}_2}(Z_2, Z_3)\right] = \left(\frac{1}{2} - \eta \right) \frac{1}{2} \) 
The sequence repeats and the same costs are obtained.
The total update cost is:
\(\mathbb {E}\left[\sum ^{T}_{t=1} \mathrm {UC}_{\mathbf {r}_t}(Z_{t}, Z_{t+1})\right] = \sum ^{T}_{t=1} \mathbb {E}\left[\mathrm {UC}_{\mathbf {r}_t}(Z_{t}, Z_{t+1})\right] =\frac{T}{4} - \frac{\eta T }{2}\) 

We have that \(\eta = \Theta (\frac{1}{\sqrt{T}})\) , then there exists a constant \(a \ge 0\) , such that \(\eta \ge \frac{a}{\sqrt{T}}\) , we obtain:
\(\mathbb {E}\left[\sum ^{T}_{t=1} \mathrm {UC}_{\mathbf {r}_t}(Z_{t}, Z_{t+1})\right] \ge \frac{T}{4} - \frac{a}{2} \sqrt{T}\) 

This is a update cost of \(\Omega (T)\)  paid in expectation by the online independent sampling.

Proof of Theorem  REF
Assume that we can find a coupling satisfying \(\mathbb {E}\left[\left\Vert Z_{t+1} - Z_{t}\right\Vert _{1, \mathbf {\mathbf {w}}^{\prime }}\right] = \operatorname{\mathcal {O}}\left(\left\Vert \mathbf {x}_{t+1} - \mathbf {x}_{t}\right\Vert _{1, \mathbf {w}^{\prime }}\right)\) , where \(\mathbb {E}[Z_t] = \mathbf {x}_t\)  and \(\mathbb {E}[Z_{t+1}] = \mathbf {x}_{t+1}\) . Then there exists a constant \(\gamma > 0\) , such that:
\(\mathbb {E} \left[ \mathrm {UC}_{\mathbf {r}_t} (Z_{t} , Z_{t+1})\right] &= \mathbb {E} \left[ \sum _{i \notin \mathop {\mathrm {supp}}(\mathbf {r}_t)} w_i^{\prime } \max (0, Z_{t+1,i} - Z_{t,i}) \right]\le \mathbb {E}\left[\left\Vert Z_{t+1} - Z_{t}\right\Vert _{1, \mathbf {w}^{\prime }}\right] \\&\le \gamma \left\Vert \mathbf {x}_{t+1} - \mathbf {x}_t\right\Vert _{1, \mathbf {w}^{\prime }}\) 

\( \gamma \left\Vert \mathbf {x}_{t+1} - \mathbf {x}_t\right\Vert _{1, \mathbf {w}^{\prime }}\)  is a norm, then there exists \(M > 0\)  and a norm \(\left\Vert .\right\Vert \) , such that:
\( \gamma \left\Vert \mathbf {x}_{t+1} - \mathbf {x}_t\right\Vert _{1, \mathbf {w}^{\prime }} \le M \left\Vert \mathbf {x}_{t+1} - \mathbf {x}_t\right\Vert \) 
This gives:
\(\mathbb {E} \left[ \mathrm {UC}_{\mathbf {r}_t} (Z_{t} , Z_{t+1})\right] \le M \left\Vert \mathbf {x}_{t+1} - \mathbf {x}_t\right\Vert \) 

Now consider that sequence \(\lbrace \mathbf {x}_t\rbrace ^T_{t=1}\)  is generated by an OMD algorithm, with a \(\rho \) -strongly convex map \(\Phi \)  w.r.t the norm \(\left\Vert .\right\Vert \) .
\(D_\Phi (\mathbf {x}_t, \mathbf {y}_{t+1}) &= \Phi (\mathbf {x}_t) - \Phi (\mathbf {y}_{t+1}) - {\nabla \Phi (\mathbf {y}_{t+1})}^T (\mathbf {x}_t - \mathbf {y}_{t+1}) \nonumber \\&= \Phi (\mathbf {x}_t) - \Phi (\mathbf {y}_{t+1}) + {\nabla \Phi (\mathbf {x}_{t})}^T (\mathbf {y}_{t+1} - \mathbf {x}_t) + {\left(\nabla \Phi (\mathbf {x}_{t}) - \nabla \Phi (\mathbf {y}_{t+1})\right)}^T (\mathbf {x}_t - \mathbf {y}_{t+1} ) \nonumber \\&\le - \frac{\rho }{2} \left\Vert \mathbf {x}_t - \mathbf {y}_{t+1}\right\Vert ^2 + \eta g^T_t (\mathbf {x}_t - \mathbf {y}_{t+1}) , \quad \text{(Strong convexity of $\Phi $ and the update rule.)} \nonumber \\&\le \frac{\eta ^2 L^2}{2 \rho },\quad \text{(Last step in the proof of \cite [Theorem 4.2]{bubeck2015convexbook})}\) 
We can simplify the expression in (REF ) to:
\(\mathbb {E} \left[ \mathrm {UC}_{\mathbf {r}_t} (Z_{t} , Z_{t+1})\right] &\le M \left\Vert \mathbf {x}_{t+1} - \mathbf {x}_t\right\Vert  \\&\le M \sqrt{\frac{2}{\rho } D_\Phi (\mathbf {x}_t, \mathbf {x}_{t+1})} \quad \text{(From the strong convexity of $\Phi $)} \\&\le M \sqrt{\frac{2}{\rho } D_\Phi (\mathbf {x}_t, \mathbf {y}_{t+1})} \quad \text{(Generalized Pythagorean inequality\cite [Lemma 11.3]{Bianchi_Prediction})} \\& \le M \sqrt{2 \eta ^2 \frac{L^2}{2\rho ^2}} ,\quad \text{Using (\ref {eq:bounding_bregman_step}).} \\&\le M \frac{L\eta }{\rho }\) 

The total update cost experienced is:
\(\sum ^{T-1}_{t=1} \mathbb {E} \left[ \mathrm {UC}_{\mathbf {r}_t} (Z_{t} , Z_{t+1})\right] \le \left(M \frac{L\eta }{\rho }\right) T\) 

The OMD Algorithm takes a fixed learning rate \(\eta = \Theta (\frac{1}{\sqrt{T}})\) , then we get:
\(\sum ^{T-1}_{t=1} \mathbb {E} \left[ \mathrm {UC}_{\mathbf {r}_t} (Z_{t} , Z_{t+1})\right] = \operatorname{\mathcal {O}}\left(\sqrt{T}\right)\) 
[h!]
[1]
Elementary \(\delta \) -movement\(\delta , u, v, \mathbf {x}, \zeta , p, \) 
Decompose \(\mathbf {x}\)  into \((\mathbf {C}, \pi )\) , such that there exists \( i \in \mathcal {N}\)  giving \(\zeta = C_i\)  with probability mass \(p = \pi _i\) 
Duplicate \((\mathbf {C},\pi )\)  as \((\mathbf {C}^*, \pi ^*)\) 
.5cm// The original values of the decomposition \((C,\pi )\)  are stored in \((C^*, \pi ^*)\)  
\(I_u \leftarrow \emptyset ; I_v \leftarrow \emptyset ;\mathbf {M}\leftarrow []\) 
.5cm// M summarizes the transportation plan from \((C^*, \pi ^*)\)  to \((C, \pi )\) .
.5cm// The plan is list of 3-tuples \((i,j, \delta )\) . The tuple indicates that \(\delta \)  mass is transported from \(C^*_i\)  to \(C_j\) .
\(\delta _u < \delta \) 
Add \(i \in \mathcal {N}\)  to \(I_u\)  if \( C_{i,u} = 1\)  and \(i \notin I_u;\delta _u \leftarrow \delta _u + \pi _i;i_{(u)} \leftarrow i\) 
\(\delta _v < \delta \) 
Add \(i \in \mathcal {N}\)  to \(I_v\)  if \( C_{i,v} = 0\)  and \(i \notin I_v;\delta _v \leftarrow \delta _v+ \pi _i;i_{(v)} \leftarrow i\) 
Split \(\pi _{i_{(u)}}\)  into \((\pi _{i_{(u)}} - (\delta _u - \delta ),(\delta _u - \delta ))\) , and \(\pi _{i_{(v)}}\)  into \((\pi _{i_{(v)}} - (\delta _v - \delta ),(\delta _v - \delta ))\) 
.5cm// The corresponding states are duplicated. Exactly \(\delta \)  probability mass is now covered by \(I_u\)  and \(I_v\) .
\(C_{i,u} \leftarrow 0, \forall i \in I_u\) ; \(C_{i,v} \leftarrow 1, \forall i \in I_v\) 
.5cm// We have at this point \(\sum ^{|\pi |}_{i=1} C_i \pi _i = \mathbf {x} - \delta \mathbf {e}_u + \delta \mathbf {e}_v \)  
.5cm// The generated configuration are valid for \(i \in I_u\cap I_v\) , where \(\left\Vert C_i\right\Vert _1 = k\) \(\delta _{u,v} \leftarrow \sum _{i \in I_u \cap I_v} \pi _i\) 
\(i \in (I_u \cap I_v) \cup (\mathcal {N} \setminus (I_u \cap I_v))\) 
\(\mathbf {M}\mathrm {.append}\left((i, i, \pi _i)\right)\) 
\(I_u \leftarrow I_u \setminus (I_u \cap I_v)\) ; \(I_v \leftarrow I_v \setminus (I_u \cap I_v);\delta \leftarrow \delta - \delta _{u,v}\) 
Find a flow \(\mathbf {F} = [f_{i,j}]\)  that transports \( \delta \)  probability mass from the states \(i \in I_v\)  to \(j \in I_u\) 
 \(f_{i,j} \in \mathbf {F}\) 
Find \(k^*\) , such that, \(C_{i,k^*} = 1\)  and \(C_{j,k^*} = 0\) .
1cm// \(k^*\)  always exists, \(C_i \ne C_j, \forall (i,j) \in \mathcal {N}^2\) . The decomposition in Line 2 generates distinct integral cache states
Duplicate the states \(C_i\)  and \(C_j\) , each with probability mass \(f_{i,j}\) 
1cm// \(C_{i^*}\)  and \(C_{j^*}\)  are duplicates of \(C_{i}\)  and \(C_{j}\) . The mass \(f_{i,j}\)  is reduced from \(\pi _i\)  and \(\pi _j\)  
\(C_{i^*,k^*} \leftarrow 0\) ; \(C_{j^*,k^*} \leftarrow 1\) 
\(\mathbf {M}\mathrm {.append}((i, i^*, f_{i,j}))\) 
\(\mathbf {M}\mathrm {.append}((j, j^*, f_{i,j}))\) 
.5cm// Construct the transport flow matrix \(\mathbf {M}_\text{flow}\) .
\(m \in \mathbf {M}\) 
\(i \leftarrow m_1; j \leftarrow m_2; f \leftarrow m_3\) 
\(\mathbf {M}_{\text{flow}(i,j)} \leftarrow f\) 
Jump to the random state \(C_j, j \in \lbrace 1,2,\dots , |\pi |\rbrace \) , with the conditional probability
\(\mathbb {P} ( Z^{\prime } = C_j | Z = \zeta ) = \frac{\mathbf {M}_{\text{flow}(i,j)}}{p}\) 
.5cm//The index \(i\in \mathcal {N}\) , is the index of \(\zeta \)  in \(\mathbf {C}^*\) , such that \(\zeta = \mathbf {C}^*_i\) .
\(C_j\) , \(\pi _j\)  
Elementary \(\delta \) -movement

Bounding Elementary Movements
Lemma 1 
Algorithm REF  outputs a random integral cache configuration \(Z^{\prime }\)  with \(\mathbb {E}[Z^{\prime }] = \mathbf {x} - \delta e_u + \delta e_v\) .
If its input is sampled from a random variable \(Z\)  with \(\mathbb {E}[Z] = \mathbf {x}\) , then \(\mathbb {E}_{Z}\left[\mathbb {E}_{Z^{\prime }| Z}\left[\left\Vert Z^{\prime }- Z\right\Vert _{1, w^{\prime }}\right]\right] \le \delta (w^{\prime }_u + w^{\prime }_v + 2 \left\Vert \mathbf {w}^{\prime }\right\Vert _\infty )\) .

Consider the elementary fractional movement of the cache state from \(\mathbf {x} \in \mathcal {X}\)  to \(\mathbf {x}^{\prime } \in \mathcal {X}\) , where we have a \(\delta \)  mass movement from node \(u\in \mathcal {N}\)  to \(v \in \mathcal {N}\)  and \( u \ne v\) , this gives:
\( \mathbf {x}^{\prime } = \mathbf {x} - \delta e_u + \delta e_v\) 
The rounding algorithm moves from a random state \(Z\)  to \(Z^{\prime }\) , and \(Z\)  is described with the set of possible cache states \(\mathbf {C} \in \mathcal {Z}^N\)  and the probability distribution over the configurations \(\pi \) . The cache states \(\mathbf {C}\)  and the probability distribution \(\pi \) , satisfy the following:
\(\mathbf {x} = \mathbb {E}\left[Z^{\prime }\right] = \sum _{i=1}^{N} \pi _{i} C_{i}\) 
We define the operator split(\(i, p\) ), where the probability mass of \(\pi _{i}\)  is split to \(p\)  and \(\pi _{t,i} - p\) , this is done by adding a configuration \(C_{L+1} \leftarrow C_i\)  with probability \(\pi _{L+1} = p\) , where \(L =|\pi |\) , and update \(\pi _i \leftarrow \pi _i - p\) .

We define the set \(I_u\) , initially \(I_u = \emptyset \) , add \(i\)  to \(I_u\)  if \( C_{i,u} = 1\)  and \(i \notin I_u\) , we stop when \( \sum _{i \in I_u} \pi _{i} \ge \delta \)  and let \(i^*\)  be the last added index. If \(\sum _{i \in I_u} \pi _{i} > \delta \) , we split the mass of state \(C_{i^*}\)  to using split(\(i^*, p\) ) with \(p := \left(\sum _{i \in I_u} \pi _{i} \right) - \delta \) , we now have exactly \(\delta \)  of probability mass over configurations indexed by \(I_u\) .
\(\sum _{i \in I_u} \pi _{i} = \delta \text{ and } C_{i,u} = 1, \forall i \in I_u \) 

We define the set \(I_v:=\emptyset \)  initially, add \(i\)  to \(I_v\)  if \(C_{i,v} = 0\)  and \(i \notin I_v\) , we stop when \( \sum _{i \in I_v} \pi _{i} \ge \delta \) . If \(\sum _{i \in I_v} \pi _{i} > \delta \) , we remove the extra probability mass using the split operator, the same as above. We obtain:
\(\sum _{i \in I_v} \pi _{i} = \delta \text{ and } C_{i,v} = 0, \forall i \in I_v \) 

we perform the following operations: \(C_{i,v} \leftarrow 1, \forall i \in I_v\)  and \(C_{i,u} \leftarrow 0, \forall i \in I_u\) , giving:
\(x^{\prime } = \sum _{i=1}^{N} \pi _i C_i\) 
Although we can obtain \(x^{\prime }\)  in expectation, \(C\)  is no longer valid as we have:
\(\left\Vert C_i\right\Vert _1= \left\lbrace \begin{array}{ll}k+1 & \mbox{if } i \in I_u \setminus (I_v \cap Iv) \\k-1 & \mbox{if } i \in I_v \setminus (I_v \cap Iv) \\k & \mbox{if } i \in I_v \cap Iv \\k & \mbox{otherwise}\end{array}\right., \forall i \in \mathcal {N}\) 

The above transformation has a update cost of \(\delta (w^{\prime }_u +w^{\prime }_v)\) . We need to apply an extra transformation on \(C\)  to make it a set of valid cache configuration, we must then find a feasible flow \(f_{i,j} \in [0,\pi _i], \forall (i,j) \in I_u \times I_v\) , satisfying the following constraints:
\( \sum _{j\in \mathcal {N}} f_{i,j} = \pi _i, \forall i \in I_u \) 
\( \sum _{i\in \mathcal {N}} f_{i,j} = \pi _j, \forall j \in I_v \) 
\( \sum _{i\in I_u} \sum _{j \in I_v} f_{i,j} = \delta \) 
Let \(\mathbf {F} = [f_{i,j}]\)  be a flow satisfying the above constraints, for every pair \((i,j) \in I_u \times I_v\)  we can find a \(j^*\) , such that, \(j^* \in C_i \text{ and } j^* \notin C_j\) , implied by the fact \(C_i \ne C_j, \forall (i,j) \in \mathcal {N} \times \mathcal {N}\) , We swap \(j^*\)  from \(C_i\)  to \(C_j\)  creating two configurations \(C_i^{\prime }\)  and \(C_j^{\prime }\)  with probability mass both equal to \(f_{i,j}\) , we can obtain at most \(2 N - 1\)  modified configurations. The update cost per pair is \( 2 f_{i,j} w^{\prime }_{j^*}\)  for the pair defined by \(f_{i,j}\) , with \(w^{\prime }_{j^*} \le \left\Vert \mathbf {w}^{\prime }\right\Vert _\infty \) , the total update cost of this modification is at most:
\( \sum _{(i,j) \in I_u \times I_v}2 f_{i,j} \left\Vert \mathbf {w}^{\prime }\right\Vert _\infty = 2\delta \left\Vert \mathbf {w}^{\prime }\right\Vert _\infty \) 
The update cost of an elementary movement of probability mass \(\delta \)  from component \(u\)  to \(v\)  is at most \(\delta \left(w^{\prime }_u + w^{\prime }_v + 2\left\Vert \mathbf {w}^{\prime }\right\Vert _\infty \right)\)  in expectation.

Proof of Theorem REF  
The general fractional movement caused by a policy \(\mathcal {A}\) , changes the cache state from fractional state \(\mathbf {x}_t \in \mathcal {X}\)  to \(\mathbf {x}_{t+1} \in \mathcal {X}\) , we denote by \(I = \left\lbrace  i \in \mathcal {N}: x_{t+1,i} - x_{t,i} > 0 \right\rbrace \)  the set of components that have a fractional increase, then we get:
\(\mathbf {x}_{t+1} = \mathbf {x}_{t} + \sum _{j \in I} m_j e_j - \sum _{i \in \mathcal {N} \setminus I } m_i e_i\) 

where \(m_i, i \in \mathcal {N}\)  is the absolute fractional change in component \(i\)  of the cache. The fractional update cost is:
\(\left\Vert \mathbf {x}_{t+1} - \mathbf {x}_{t}\right\Vert _{1, w^{\prime }} = \sum _{i\in \mathcal {N}} w^{\prime }_i m_i\) 

From the capacity constraint we know that \(\sum _{i \in \mathcal {N} \setminus I } m_i = \sum _{j \in I} m_j\) . If we want to split this general fractional change to elementary operations, then we need to find a flow \(\left[\delta _{i,j} \in [0,m_i] \right], (i,j) \in (\mathcal {N}\setminus I) \times I\)  that moves \(\sum _{j \in I } m_j e_j\)  mass from the components \(i \in \mathcal {N} \setminus I\)  to \(j \in I\) . This requires at most \(N-1\)  elementary operations. For each of these elementary operations we pay in expectation at most a update cost of \(\delta _{i,j} \left(w^{\prime }_i + w^{\prime }_j + 2\left\Vert \mathbf {w}^{\prime }\right\Vert _\infty \right)\)  from Lemma REF . Then the total movement is at most:
\(\sum _{i \in \mathcal {N} \setminus I } \sum _{j \in I } \delta _{i,j} \left(w^{\prime }_i + w^{\prime }_j + 2\left\Vert \mathbf {w}^{\prime }\right\Vert _\infty \right) &= \sum _{i \in \mathcal {N} \setminus I} m_i w^{\prime }_i + \sum _{j \in I} m_j w^{\prime }_j + 2 \sum _{j\in I} m_j \left\Vert \mathbf {w}^{\prime }\right\Vert _\infty \\&= \left\Vert \mathbf {x}_{t+1} - \mathbf {x}_{t}\right\Vert _{1, w^{\prime }} + 2 \sum _{j\in I} m_j \left\Vert \mathbf {w}^{\prime }\right\Vert _\infty \\&=\left\Vert \mathbf {x}_{t+1} - \mathbf {x}_{t}\right\Vert _{1, w^{\prime }} + 2 \frac{\left\Vert \mathbf {w}^{\prime }\right\Vert _\infty }{w^{\prime }_*}\sum _{j\in I} w^{\prime }_*m_j \\&\le \frac{w^{\prime }_* + 2\left\Vert \mathbf {w}^{\prime }\right\Vert _\infty }{w^{\prime }_*} \left\Vert \mathbf {x}_{t+1} - \mathbf {x}_{t}\right\Vert _{1, w^{\prime }}\) 

where \(w^{\prime }_*:= \underset{i \in \mathcal {N}}{ \min }\, w^{\prime }_i\) , and we pay a update cost that is \(\operatorname{\mathcal {O}}\left(\left\Vert \mathbf {x}_{t+1} - \mathbf {x}_{t}\right\Vert _{1, w^{\prime }}\right)\)  in expectation, therefore we preserve the sub linearity of regret from Theorem REF . 