If you have been following the first two posts (post 1, post 2), now is time to reap the rewards! I will show here how to obtain a 
-competitive algorithm for (weighted) paging, i.e., when the metric space corresponds to the leafs of a weighted star. This was viewed as a breakthrough result 10 years ago (with a JACM publication by Bansal, Buchbinder and Naor in 2012), and for good reasons as this simplest instance of 
-server was in fact the one studied in the seminal paper by Sleator and Tarjan in 1985 which introduced the competitive analysis of online algorithms (actually to be precise Sleator and Tarjan considered the unweighted case, for which a
algorithm was known much before).
State space for weighted
-paging
Let 
be the weight of the edge from leaf 
to the root. Recall from the previous post that we want to find a norm and a convex body that can express the Wasserstein-
distance between two fractional
-server configurations.
Consider a fractional move from 
to 
. Then clearly, the amount of mass 
has to transfer through the edge 
, so that the Wasserstein-
distance is at least 
. Furthermore there is trivially a transport plan achieving that much total mass transfer. In other words we just proved that in this case the appropriate norm is a weighted 
norm (namely 
) and one can simply use the basic state space 
(recall from the previous post that we have to work with anticonfiguration, and that the mapping to a configuration is simply given by 
).
Applying the general mirror descent framework
Given a request at location 
and a current anticonfiguration 
, our proposed (fractional) algorithm is to run the mirror descent dynamics with a continuous time linear cost 
from 
(i.e., 
for some 
) and until the first time 
at which 
(i.e., one has a server at location 
in 
). By the lemma at the end of the previous post one has (denote 
for the request being serviced at time
)
- One can think of
- as a “virtual service cost”. In
- -server this quantity has no real meaning, but the above inequality shows that this quantity, which only depends on the algorithm, is tightly related to the value of OPT (provided that
- has a small Lipschitz norm). Thus we see that we have two key desiderata for the choice of the mirror map
- (i) it should have a small Lipschitz norm, (ii) one should be able to relate the movement cost
to this “virtual service cost” 
, say up to a multiplicative factor 
. One would then obtain a 
-competitive algorithm.
Entropy regularization for weighted
-paging
Let us look at (ii), and we shall see that the entropy regularization comes out very naturally. Ignore for a moment the Lagrange multiplier 
and let us search for a separable regularizer of the form 
. We want to relate 
to 
. Making those two quantities equal gives 
and thus the regularizer is a weighted negentropy: 
.
We now need to verify that this relation between the virtual service cost and the movement cost remains true even when the Lagrange mutilplier
is taken into account. Note that because of the form of the state space 
the multiplier contains a term of the form 
(which corresponds to the constraint 
) and for each location a term forcing the derivative to be 
if the value of the missing mass has reached
. In other words we obtain the following dynamics for mirror descent with the weighted negentropy regularization:
Notice that up to a factor 
one can focus on controlling 
(that is only movement into a location is charged). In that view the Lagrange multipliers simply have no effect, since one has 
(indeed recall that 
). Thus we see that the movement cost
is exactly bounded by the virtual service cost
in this case.
Making
Lipschitz
It remains to deal with a non-trivial issue, namely the entropy is not Lipschitz on the simplex! A similar issue is faced in online learning when one tries to prove tracking expert regret bounds, i.e., bounds with respect to a shifting expert. The standard solution (perhaps first used by Herbster and Warmuth in 98, see also Blum and Burch 00) is to shift the variables so that they never get below some 
, in which case the Lipschitz constant would be 
. In the
-server scenario one can stop the dynamics when 
(instead of 
) provided that the mapping from 
to the actual fractional configuration 
is now given by 
. This raises a final issue: the total amount of server mass in such a
is 
. Next we show that if 
is small enough then
can be “rounded” online to a fractional
-server configuration at the expense of a multiplicative 
movement. Precisely we show that 
is sufficient, which in turns gives a final competitive ratio of
for weighted
-paging.
From 
servers to
servers
Consider a fractional server configuration
with total mass
(i.e., 
), which we want to transform into a server configuration 
with total mass
. A natural way to “round down” is at each location to put
if the mass was 
. Furthermore a mass of
should stay
. This suggests the mapping 
, which is 
-Lipschitz. Thus the movement of 
is controlled by the movement of 
up to a multiplicative factor
. Moreover one clearly has 
(in fact the inequality can be strict, in which case one should think of the “lost mass” as being stored at the root, this incurs no additional movement cost).