k-server, part 3: entropy regularization for weighted k-paging

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).