arXiv:1711.01085v1 [] 3 Nov 2017

k-server via multiscale entropic regularization
Sebastien Bubeck

Michael B. Cohen

James R. Lee

Microsoft Research

MIT

University of Washington

Yin Tat Lee

Aleksander Madry
˛

University of Washington

MIT

Abstract
We present an O((log k)2 )-competitive randomized algorithm for the k-server problem on
hierarchically separated trees (HSTs). This is the first o(k)-competitive randomized algorithm
for which the competitive ratio is independent of the size of the underlying HST. Our algorithm
is designed in the framework of online mirror descent where the mirror map is a multiscale
entropy. When combined with Bartal’s static HST embedding reduction, this leads to an
O((log k)2 log n)-competitive algorithm on any n-point metric space. We give a new dynamic
HST embedding that yields an O((log k)3 log ∆)-competitive algorithm on any metric space
where the ratio of the largest to smallest non-zero distance is at most ∆.

Contents
1 Introduction
1.1 Mirror descent and entropic regularization . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2
3
3

2 Traversing a convex body online
2.1 Evolution of the Bregman divergence . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Application: Fractional weighted paging . . . . . . . . . . . . . . . . . . . . . . . . .

4
5
6

3

k-server on trees
3.1 k + ε fractional servers . . . .
3.2 The assignment polytope . . .
3.3 Dynamics . . . . . . . . . . .
3.4 The weighted depth potential

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

8
. 9
. 10
. 11
. 14

4 Dynamic HST embeddings
4.1 Hierarchical partitions and canonical HSTs . . . . . . . . . . . . . . . . . . . . . . . .
4.2 The HST reduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3 A dynamic embedding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19
20
21
21

5 Mirror descent
5.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2 Existence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3 Uniqueness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

24
24
25
26

1

1 Introduction
Perhaps the most widely-studied problem in the field of online algorithms and competitive analysis
is the k-server problem, introduced in [MMS90] to generalize and abstract a number of related
problems arising in the study of paging and caching. The problem has been the object of intensive
study since its inception, motivated largely by two long-standing conjectures about the competitive
ratios that can be achieved by deterministic and randomized algorithms, respectively.
We recall the problem briefly; see Section 1.2 for a formal definition of the model. Fix a metric
space (X, d) and k > 1, as well as an initial placement ρ 0 ∈ X k of k servers in X. An online k-server
algorithm operates as follows. At each time step, a request rt ∈ X comes online, and the algorithm
must respond to this request by moving one of the servers to rt (unless there is already a server
there). The cost of the algorithm is the total distance moved by all the servers over the course of
the request sequence. An oﬄine algorithm operates in the same manner, but is allowed access to
the entire request sequence in advance. An online algorithm has competitive ratio α if, for every
request sequence, its movement cost per unit time step is within an α factor of that achieved by the
optimal offline algorithm.
Randomization. The authors of [MMS90] stated the k-server conjecture: On any metric space with
at least k +1 points, the best competitive ratio achieved by deterministic online algorithms is precisely
k. They showed that the ratio is always at least k. While the conjecture is still open in general,
Koutsoupias and Papadimitriou resolved it within a factor of two: The work function algorithm
obtains a competitive ratio of 2k − 1 on any metric space [KP95]. We refer the reader to the book
[BE98] for further background on online algorithms and the k-server problem.
In the context of the k-paging problem, which is the special case of k-server on a metric space
with all distances in the set {0, 1}, it was observed that randomness can help an online algorithm
dramatically: It is known that the competitive ratio for k-paging is precisely the kth harmonic
number Hk for every k > 1 [FKL+ 91, MS91].
Hierarchically separated trees. There is another class of metric spaces on which one can prove
lower bounds on the competitive ratio even for randomized algorithms. Consider a finite, rooted
tree T  (V, E) with vertex weights w : V → R+ that are non-increasing along every root-leaf path.
Let L ⊆ V denote the set of leaves and define the metric
dw (ℓ, ℓ ′) : w lca(ℓ,ℓ′)

∀ℓ, ℓ ′ ∈ L .

In this case, dw is an ultrametric (in fact, all finite ultrametrics are of this form). If w v 6 w u /τ
whenever v is a child of u, then one says that (T , w) is a τ-hierarchically separated tree (τ-HST) and
the metric space (L, dw ) is referred to as a τ-HST metric. By showing lower bounds on every HST
and additionally demonstrating that all sufficiently large metric spaces contain subsets that are
close to HSTs, the authors of [BBM06] proved a lower bound on the competitive ratio for every
metric space. Using the metric Ramsey bounds
from
[BLMN05], it holds that the competitive ratio


for randomized algorithms is at least Ω

log k
log log k

on every metric space with more than k points.

A lack of further lower bounds motivates the folklore “Randomized k-server conjecture” (see,
e.g., [BBK99]) that the randomized competitive ratio is (log k)O(1) on every metric space, or even
O(log k), matching the lower bound for k-paging. One can also consult the survey [Kou09] (in
particular, Conjecture 2 and the surrounding discussion).
Since the seminal work of Bartal on probabilistic embeddings of finite metric spaces into HSTs
[Bar96, Bar98], it has been understood that obtaining upper bounds on the competitive ratio for
HSTs is of central importance. Indeed, the competitive ratio for n-point metric spaces is at most
an O(log n) factor larger than the competitive ratio for n-point HST metrics. This bound follows
from Bartal’s approach combined with the optimal distortion estimate of [FRT04].
2

The authors of [CMP08] give an O(log D)-competitive randomized algorithm on binary 2HSTs with combinatorial depth at most D, and in [BBMN15], a major breakthrough was achieved
when the authors exhibited an (log n)O(1) -competitive algorithm for general n-vertex HSTs. In the
present work, we obtain a competitive ratio independent of the size of the underlying HST, thereby
verifying a long-held belief.
Theorem 1.1. For every k > 2, there is an O((log k)2 )-competitive randomized algorithm for the k-server
problem on any HST.
As mentioned previously, this yields an O((log k)2 log n)-competitive randomized algorithm for
every n-point metric space, via probabilistic embeddings of finite metric spaces into distributions
over HSTs. The embedding underlying this reduction is oblivious to the request sequence. While
this is a very convenient feature for the analysis, oblivious embeddings cannot avoid losing an
Ω(log n) factor in the competitive ratio. We show that in certain cases, this can be circumvented
via the use of dynamic HST embeddings where the embedding is allowed to depend on the request
sequence.



Theorem 1.2. For every k > 2 and every ﬁnite metric space (X, d), there is an O (log k)3 log(1 + A X ) competitive randomized algorithm for the k-server problem on (X, d), where
AX :

max x,y∈X d(x, y)
min x , y∈X d(x, y)

.

1.1 Mirror descent and entropic regularization
Our algorithm is most naturally stated in the framework of continuous-time mirror descent. This
framework was originally introduced for convex optimization in [NY83] (see also [Bub15]), and
recently it has played a key role in online decision making; see, e.g., [Haz16] for the online
learning setting, and [ABBS14, BCN14] for applications to metrical task systems. Typically an
entropy functional is used as a mirror map, and a key contribution of our work is to propose an
appropriate multiscale entropy functional.
We establish some properties of a general setup in Section 2 and, as a warmup application,
present in Section 2.2 an O(log k)-competitive algorithm for the (fractional) weighted paging problem that is closely related to the algorithm of [BBN12]. This already exhibits a couple key ideas in
a simplified setting, including the natural use of the Bregman divergence as a potential function,
and the utility of using k + ε servers for some ε < 1. In Section 3, we begin transferring these
ideas to the setting of the k-server problem on trees. Notably, the polytope underlying our state
representation is the one derived from the fractional allocation problem as employed in [CMP08]
and [BBMN15]. In Section 3.4.1, we introduce the crucial idea of an auxilliary potential function
that tracks the weighted depth of the underlying fractional server measure, and in Section 3.4.3 we
show how using a time-varying weight can be leveraged to obtain an O((log k)2 ) competitive ratio.

1.2 Preliminaries
We use the notations R+ : [0, ∞) and Z+  Z ∩ R+ . If X and Y are two metric spaces and
F : X → Y is Lipschitz, we use kF klip to denote the Lipschitz constant of F. Consider a bounded,
1
(µ, ν) to
complete metric space (X, d) and two Borel probability measures µ and ν on X. We use WX
1
denote the L -transportation distance between µ and ν (sometimes called the Earthmover metric):

WX1 (µ, ν) : inf

[d(Y, Y ′)] ,

where the infimum is over all jointly distributed random variables (Y, Y ′) such that Y has marginal
µ and Y ′ has marginal ν. The definition is extended in the natural way to any two Borel measures
satisfying µ(X)  ν(X).
3

Online algorithms and the competitive ratio. Let (X, d) be a metric space and fix k > 1. We now
describe the k-server problem more formally. The input is a sequence hσt ∈ X : t > 1i of requests.
At every time t, an online algorithm maintains a state ρ t ∈ X k which can be thought of as the
location of k servers in the space X. At time t, the algorithm is required to have a server at the
requested site rt ∈ X. In other words, a feasible state ρ t is one that services rt :



ρt

dX k (x1 , . . . , x k ), (y1 , . . . , yk ) :

k
Õ

rt ∈



1

, . . . , ρt



k

.

Formally, an online algorithm is a sequence of mappings ρ  hρ 1 , ρ 2 , . . . , i where, for every t > 1,
ρ t : X t → X k maps a request sequence hr1 , . . . , rt i to a k-server state that services rt . In general,
ρ 0 ∈ X k will denote some initial state of the algorithm.
The cost of the algorithm ρ in servicing r  hrt : t > 1i is defined as the sum of the movements of
all the servers:
Õ

costρ (r; k) :
dX k ρ t (r1 , . . . , rt ), ρ t−1 (r1 , . . . , rt−1 ) ,
t >1

where



dX (x i , yi )

∀ x 1 , . . . , x k , y1 , . . . , y k ∈ X ,

i1

and ρ 0 ∈ X k is some fixed initial configuration.
For a given request sequence r  hrt : t > 1i, denote the cost of the oﬄine optimum by
cost∗ (r; k) :

inf

hρ 1 ,ρ 2 ,...i

Õ



dX k ρ t , ρ t−1 ,

t >1

where the infimum is over all sequences hρ 1 , ρ 2 , . . .i such that ρ t services rt for each t > 1.
A randomized online algorithm ρ is a random online algorithm that is feasible with probability
one. Such an algorithm is said to be α-competitive if for every ρ 0 ∈ X k , there is a constant c > 0
such that for all r:


costρ (r; k) 6 α · cost∗ (r; k) + c .

2 Traversing a convex body online
Suppose that K ⊆ Rn is a closed convex set and f : R+ × K → Rn is a time-varying vector field
defined on K. It is very natural to consider the projected dynamical system:
x ′(t)  ΠK x(t), f (t, x(t))
x(0)  x0 ,
where
ΠK (x, v) : lim

ε→0



PK (x + εv) − x
,
ε

and
PK (x) : argmin {kx − z k2 : z ∈ K } .
One can interpret this as trying to “flow” along the vector field in direction f (t, x(t)) while
being confined to remain in the convex body K. But since projection is a discontinuous operation
(imagine hitting the boundary of a polytope, for instance), the classical theory of existence and
uniqueness of ODEs no longer applies. Fortunately, there is now a well-established theory for
projected dynamical systems.
4

Let us denote the normal cone to K at x by



NK (x) : p ∈ Rn : hp, y − xi 6 0 for all y ∈ K .
If K is a polyhedron, then the normal cone to K at x is the cone spanned by the normals of the tight
constraints at x.
Lemma 2.1. Given any matrix A ∈ Rm×n and b ∈ Rm , consider the polyhedron K : {x ∈ Rn : Ax 6 b}.
For any x ∈ K, it holds that



NK (x)  AT y : y > 0 and y T (b − Ax)  0 .
For our applications, we will want to consider a projected dynamical system with respect to
a non-Euclidean geometry on K. Let Φ : K → Rn be a strongly convex function. Then ∇2 Φ is
positive definite and can be thought of as a Riemannian metric on K. One can describe the possible
dynamics in the geometry induced by Φ by the diﬀerential inclusion
∇2 Φ(x(t))x ′(t) ∈ f (t, x(t)) − NK (x(t))

(2.1)

x(0)  x0
x(t) ∈ K

∀t > 0 .

Note that the right-hand side of (2.1) is a set of vectors, and a solution x(t) is one that satisfies
the inclusion. It turns out that, under suitable assumptions, an absolutely continuous solution
exists, and under stronger assumptions, the solution is unique. The following theorem is proved
in Section 5.
Theorem 2.2. Consider a compact convex set K ⊆ Rn , a strongly convex function Φ : K → R, and a
continuous function f : [0, ∞) × K → Rn . Suppose furthermore that ∇2 Φ(x)−1 is continuous. Then for
any x0 ∈ K, there is an absolutely continuous solution x : [0, ∞) → K satisfying



x ′(t) ∈ ∇2 Φ(x(t))−1 f (t, x(t)) − NK (x(t)) ,
x(0)  x0 .

If we further assume that ∇2 Φ(x) is Lipschitz and f is locally Lipschitz, then the solution is unique.

2.1 Evolution of the Bregman divergence
Recall that the Bregman divergence associated to Φ : K → R is given by
DΦ (y; x) : Φ(y) − Φ(x) − h∇Φ(x), y − xi .
We will use DΦ as a potential function to track the “discrepancy” between our algorithm and the
optimal offline algorithm. In fact, it will be slightly easier to work with the function
D̂Φ (y; x) : −Φ(x) − h∇Φ(x), y − xi .
Suppose now that x(t) is an absolutely continuous solution to the differential inclusion (2.1)
and write
∇2 Φ(x(t))∂t x(t)  f (t, x(t)) − λ(t)
with λ(t) ∈ NK (x(t)). One concludes immediately that for y ∈ K:
∂t D̂Φ (y; x(t))  h∇2 Φ(x(t))∂t x(t), x(t) − yi
 f (t, x(t)) − λ(t), x(t) − y

6 f (t, x(t)) , x(t) − y ,
where in the last inequality we have used that hλ(t), y − x(t)i 6 0 since λ(t) ∈ NK (x(t)).
5

(2.2)

2.2 Application: Fractional weighted paging
Fix k > 1. Consider the fractional weighted paging problem on pages in [n] with a cache of size k
and positive weights {w i > 0 : i ∈ [n]}. For z ∈ Rn , define the weighted ℓ 1 norm:
kz kℓ1(w)

:

n
Õ

w i |z i | ,

i1

and the dual norm:
kz kℓ∞ (1/w)





|z i |
: max
: i ∈ [n] .
wi

Note that if z(t) ∈ Rn is an online algorithm for t ∈ [0, T], then the movement cost is precisely

∫

T

k∂t z(t)kℓ1 (w) dt .

0

Moreover, up to a factor of two, we can charge our algorithm only for the cost of moving fractional
mass into a node, i.e.,
∫
T

0

k(∂t z(t))+ k ℓ1 (w) dt ,

(2.3)

where for z ∈ Rn , we denote (z)+ : (max(0, z1 ), . . . , max(0, z n )).
2.2.1

Entropy-regularized dynamics

Define the fractional k-antipaging polytope
P :

(

x ∈ [0, 1]n :

n
Õ

)

xi  n − k .

i1

Here, we think of 1 − x i as the fractional amount of page i that sits in the cache (hence x i is the
amount of fractional “antipage”). Define also the entropic regularizer
Φ(x) :

n
Õ

w i x i log x i .

i1

Suppose the current state of the cache is described by a point x ∈ P such that x i (0) > 0 for all
i ∈ [n]. When a request r ∈ {1, . . . , n} is received, we need to decrease x r to 0. To this end, we use
the (constant) control function:
f (t, x(t)) : −e r

∀t > 0 .

Now the intended trajectory is given by the differential inclusion:
∇2 Φ(x(t))∂t x(t) ∈ −e r − NP (x(t)) .
Let us analyze the dynamics which are described by
∇2 Φ(x(t))∂t x(t)  −e r − λ(t) ,

(2.4)

where λ(t) ∈ NP (x(t)). From Lemma 2.1, it is an exercise to compute that
λ(t) 

n
Õ

λ i (t)e i − µ(t)1

i1

6

(2.5)

for some {λ i (t) > 0} such that λ i (t) > 0 ⇒ x i (t) < 1.
Here, the {λ i } functions are the Lagrangian multipliers for the constraints {x i 6 1} of P, and
Í
µ is the multiplier for ni1 x i  n − k. The fact that x i (t) > 0 for t > 0 is implicitly enforced
by Φ (assuming some boundedness on the control f ). Since k∇Φ(x)k2 → ∞ as x approaches the
boundary of the positive orthant, Φ acts as a barrier preventing the evolution from leaving R+ .
We do not stress this point formally at the moment since we will soon need to maintain a more
restrictive condition.
Let x̂ ∈ {0, 1} n ∩ P denote an integral antipaging point with x̂ r  0 (i.e., a state which has
satisfied the request). Then (2.2) immediately yields
∂t D̂Φ (x̂; x(t)) 6 he r , x̂ − x(t)i  −x r (t) .

(2.6)

Moreover, from (2.4) and (2.5), one easily calculates:
∂t x i (t) 
where


x i (t)
−e r (i) − λ i (t) + µ(t) ,
wi

λ i (t) 
Using ∂t

Ín

i1

x i (t)  0 yields

(

(2.7)

0
x i (t) < 1
.
µ(t) otherwise.

µ(t)  Í

x r (t)/w r
.
i:x i (t)<1 x i (t)/w i

(2.8)

In particular, if x r (t) < 1 then µ(t) 6 1, hence from (2.7), the instantaneous movement cost (recall
(2.3)) is bounded by
w r |∂t x r (t)| 6 x r (t) .
Thus the potential change (2.6) compensates for the movement cost.
Now we have to address convergence, and here we run into a problem: D̂Φ (x̂; x(t)) could be
infinite! Therefore (2.6) does not show that x r (t) → 0 as t → ∞.
2.2.2

Moving in the interior

Our solution to this problem will be to shift the variables away from the boundary of R+ . For
δ > 0, define
(
)
Pδ : P ∩ [δ, 1]n 

x ∈ [δ, 1]n :

n
Õ

xi  n − k

.

i1

Clearly we cannot remain in this polytope and still service a request r by moving to a point with
x r  0. Instead, we will allow our algorithm to satisfy the weaker constraint x r  δ, and then
afterward show that any such algorithm can be transformed—in an online manner—to a valid
fractional paging algorithm, as long as δ is chosen small enough. Furthermore, we can easily
ensure that our dynamics remain inside Pδ by simplying stopping when x r (T)  δ (if we can
ensure that there is a time T at which this occurs).
Now note that


1
sup k∇Φ(x)kℓ∞ (1/w) 6 O log
.
(2.9)
δ
x∈P δ
Thus if we ensure that x(t) ∈ Pδ , then (2.6) implies that x r (T)  δ occurs after some finite time T.
We are left to analyze how the potential changes when OPT moves. But from the definition
and (2.9), we have
∂t D̂Φ (y(t); x)  h∇Φ(x), −∂t y(t)i 6 O(log 1δ )k∂t y(t)kℓ1 (w) .
7

Thus we obtain an O(log 1δ )-competitive algorithm, where δ is the smallest constant such that we
k
can round (online) a fractional 1−δ
-paging algorithm to a genuine fractional k-paging algorithm.
1
As we will see now, this can be done when δ  2k
.
Transforming to a valid fractional paging algorithm. Consider a request sequence r® 
(r1 , r2 , . . . , rM ), and a differentiable map x : [0, T] → Pδ that services r® in the sense that there
are times t1 < t2 < · · · < t M such that x r i (t i )  δ. We may assume that x(t) is elementary in the
sense that for almost every t ∈ [0, T]:
∂t x(t)  (e i − e j ) dt
for some i , j ∈ [n].
Define

1 − x(t)
∀t ∈ [0, T] .
1−δ
Then z r i (t i )  1, so z represents a trajectory on measures that services r®, but problematically we
k
for t ∈ [0, T].
have kz(t)k1  1−δ
δk
We fix this as follows: Let ε : 1−δ
and define σ : R+ → R+ so that σ|[ℓ,ℓ+ε]  ℓ for every
ℓ ∈ Z+ and σ is extended affinely to the rest of R+ . For z ∈ R+n , define σ(z) : (σ(z1 ), . . . , σ(z n )),
and consider the trajectory σ(z(t)) for t ∈ [0, T]. Observe first that
z(t) :

∫

0

T

k∂t σ(z(t))k ℓ1 (w) dt 6 kσklip

∫

T

0

k∂t z(t)k ℓ1 (w) dt 6

1
1−ε

∫

0

T

k∂t z(t)k ℓ1 (w) dt .

1
Thus for δ  2k
, the movement cost has increased under σ by only an O(1) factor.
Because σ is superadditive, it also holds that for every t ∈ [0, T],
n
Õ
i1

σ(z i (t)) 6 σ

n
Õ

!

z i (t)  σ (k + ε)  k .

i1

Therefore we use at most k fractional server mass at any point in time. We are left to show that, at
no additional movement cost, this can be transformed into an algorithm that maintains fractional
server mass exactly k.
To that end, we may assume that kσ(z(0))k1  k. It will be easiest to think of a weighted star
metric on vertices V  {1, 2, . . . , n} ∪ {0}, where 0 is the center of the star and the edge (0, i) has
length w i . When ∂t σ(z(t))  −e i dt for some i ∈ [n], the instantaneous movement cost of σ(z(t))
is w i e i dt. Instead of deleting this mass, we can move it to 0 for the same cost. Similarly, when
∂t σ(z(t))  e i dt, the instantaneous movement cost is again w i e i dt and instead of creating mass,
we can move dt mass from 0 to i.

3

k-server on trees

Consider a rooted tree T  (V, E) with root r ∈ V and leaves L ⊆ V. Let {w v > 0 : v ∈ V } be a
collection of nonnegative weights on V with w r  0. We will suppose that every leaf ℓ ∈ L is at
the same combinatorial distance from the root.
For v ∈ V, let L(v) ⊆ L denote the set of leaves beneath v. For u ∈ V \ {r }, let p(u) ∈ V denote

the parent of u, and write E®  {®
e : e ∈ E}  (p(u), u) : u ∈ V \ {r } for the set of edges directed
® define lenw (u, v) : w v . Let distw (x, y) denote the weighted
away from the root. For (u, v) ∈ E,
path distance between x, y ∈ V, where an edge e ∈ E is given weight lenw (®
e ). We say that the pair
(T , w) is a τ-adic HST if for every v ∈ V \ {r }, it holds that w v  τ j for some j ∈ Z and, moreover,
if (u, v) ∈ E® then w v  w u /τ.
8

For z ∈ RV and w ∈ RV
+ , denote
kz k ℓ1 (w) :

Õ

w v |z v | .

v∈V

Leaf measures, internal measures, and supermeasures.
A leaf measure is a point z ∈ R+L . The
Í
mass of a leaf measure is defined as the quantity ℓ∈L z ℓ . An internal supermeasure is a point z ∈ RV
+
such that
Õ
zv
∀u ∈ V .
(3.1)
zu >
v:(u,v)∈E®

The mass of an internal supermeasure is the quantity zr . We say that z ∈ RV
+ is an internal measure
if (3.1) is satisfied with equality.
For a leaf measure z ∈ R+L , we define its lifting to an internal measure by

Õ

ẑ v :

∀v ∈ V .

zℓ

ℓ∈L(v)

b denote the set of internal measures on V. It is straightforward to see that this is precisely
Let M
the class of lifted leaf measures.
Lemma 3.1. For leaf measures y, z ∈ R+L with k y k1  kz k1 , it holds that

Ww1 (y, z)  ŷ − ẑ

ℓ1 (w)

.

A fractional k-server algorithm for (L, distw ) is an online sequence z (t) ∈ R+L : t  0, 1, 2, . . . of
(t)

leaf measures of mass k such that for every t > 1: z ℓ t > 1 if ℓ t is the requested leaf at time t. We
also require that z (0) is integral. The cost of such an algorithm is defined by

Õ

Ww1

t >0



(t)

z ,z

(t+1)



.

Lemma 3.2 ([BBMN15, §5.2]). The following holds for all τ > 5. If (X, dX ) is a τ-HST metric and there
is a fractional online k-server algorithm for (X, dX ), then there is a randomized integral online k-server
algorithm whose expected cost is at most O(1) times larger.

3.1

k + ε fractional servers

For the remainder of the proof, we will work with continuous time trajectories z : [0, T] → R+L
whose movement cost is measured by

∫

T

0

k∂t ẑ t k ℓ1 (w) dt ,

in light of Lemma 3.1. Obviously such a trajectory can be mapped to a discrete-time algorithm by
choosing times T1 > T2 > · · · that correspond to discrete times t  1, 2, . . ..
Lemma 3.3. If y : [0, T] → RV
+ is a trajectory taking values in internal supermeasures of mass k, then
there is an (adapted) trajectory z : [0, T] → R+L taking values in leaf measures of mass k such that:
1. For every leaf ℓ ∈ L: z t (ℓ) > yt (ℓ), and
1 (z(0), z(T)) 6
2. Ww

∫T
0

k∂t y(t)kℓ1 (w) dt.
9

Proof. This lemma follows from a more general principle: If (X, d) is a metric space and X ′ ⊆ X,
then an online (fractional) k-server algorithm on (X, d) servicing a sequence of requests in X ′ can
be converted to an online (fractional) k-server algorithm on (X ′ , d|X′×X′ ) without increasing the
movement cost. This is a straightforward consequence of the triangle inequality.
Now observe that we can envision every trajectory on internal supermeasures y(t) ∈ RV
+ with
V
t ∈ [0, T] as a trajectory on genuine measures ỹ(t) ∈ R+ defined by
ỹu (t) : yu (t) −

Õ

yu (t)

∀u ∈ V .

v:(u,v)∈E®

And moreover,

Ww1 ( ỹ(0),

ỹ(T)) 6

∫

T

k∂t y(t)kℓ1 (w) .

0

Since (L, distw ) is a subspace of (V, distw ), this completes the proof by our earlier observation. 
Lemma 3.4. For every 0 6 ε < 1, a fractional online (k + ε)-server algorithm on (L, distw ) can be converted
1
to a fractional online k-server algorithm so that the movement cost increases by a factor of at most 1−ε
.
Proof. The proof is similar to the case for fractional paging. Define σ : R+ → R+ so that σ|[ℓ,ℓ+ε]  ℓ
for every ℓ ∈ Z+ and σ is extended affinely to the rest of R+ . For y ∈ RV
+ , define σ(y) : (σ(y v ))v∈V .
Consider a trajectory z : [0, T] → R+L taking values in leaf measures of mass k + ε. Then since
σ is superadditive, it holds that σ(ẑ(t)) is an internal supermeasure for every t ∈ [0, T]. Moreover,
σ(ẑr (t))  σ(k + ε)  k, so σ(ẑ(t)) is an internal supermeasure of mass k.
Finally, note that

∫

0

T

k∂t σ(ẑ(t))k ℓ1 (w) dt 6 kσklip

∫

T

0

k∂t ẑ(t)k ℓ1 (w)

1
dt 6
1−ε

∫

0

T

k∂t ẑ(t)k ℓ1 (w) dt .

Now applying Lemma 3.3 to the internal supermeasures σ(ẑ(t)) completes the proof.



In light of the preceding lemma, it suffices to construct a competitive fractional (k + ε)-server
algorithm with ε < 1 for any request sequence on (L, distw ).

3.2 The assignment polytope
For u ∈ V, write

n

® j ∈ [Nu ]
χ(u) : (v, j) : (u, v) ∈ E,

o

where Nu is the number of leaves in the subtree rooted at u. Denote

n

o

Λ : (r , i) : i ∈ [Nr ] ∪
With a slight abuse of notation, we sometimes write
assignment polytope on T is defined by



A : x ∈ [0, 1]Λ :

Õ

i 6 |S|

x u,i 6

Õ

(v, j)∈S

xr ,i  1{i>k}

10

Ø

χ(u) .

i >1

f (x u,i ) instead of

u∈V

Í

Í

∀u ∈ V, S ⊆ χ(u) ,

x v, j



∀i > 1 .

i∈[N u ]

f (x u,i ). The

Fix some δ > 0 and define the shifted multiscale entropy by
Φ(x) :

Õ

wu

u∈V

Õ

(x u,i + δ) log(x u,i + δ) .

i >1

For ℓ ∈ L, denote x ℓ : x ℓ,1 . Finally, for u ∈ V and x ∈ A, define the associated server measure z ∈ RV
+
by
1 Õ
(1 − x u,i ) .
z u :
1−δ
i >1

Suppose we receive a request at ℓ ∈ L. Let x : [0, ∞) → A be an absolutely continuous trajectory
satisfying
∂t x(t)  ∇2 Φ(x(t))−1 (−e ℓ,1 − λ(t))
(3.2)
with λ(t) ∈ NA (x(t)) for almost every t > 0. Denote
T  inf {t > 0 : x ℓ (t) < δ} .
By construction, as long as T < ∞ (see Lemma 3.12 below), it holds that {z u (t) : t ∈ [0, T]} is a
1
k
k
-server trajectory that services the request at ℓ. Now set δ : 2k
< k+1
so that 1−δ
fractional 1−δ
for k > 2.

3.3 Dynamics
We now describe in detail the dynamics of x(t) on [0, T]. We allow (momentarily) for the possibility
that T  +∞.
Lemma 3.5. Suppose that x ℓ,1 (0) > δ. The continuous trajectory x(t) deﬁned in (3.2) exists uniquely for
t ∈ [0, T] and satisﬁes x ℓ,1 (t) > δ for all t ∈ [0, T]. Furthermore, x(t) is absolutely continuous and its
derivative is given by

x u,i (t) + δ
−1{(u,i)(ℓ,1)} − λ u,i (t) ,
(3.3)
∂t x u,i (t) 
wu
for all u ∈ V \ {r } and all i > 1, and

λ u,i (t) 

Õ

λ S (t) −

Õ

S⊆χ(p(u)):
(u,i)∈S

S⊆χ(u):
i 6 |S|

λ S (t) ,

Í

where λ S (t) > 0 are the Lagrangian multipliers for the constraints { i 6 |S| x u,i (t) 6
we have that
Õ
Õ
x v, j (t) .
x u,i (t) 
λ S (t) > 0 ⇒

(3.4)

Í

(v, j)∈S

x v, j (t)}. Also,
(3.5)

(v, j)∈S

i 6 |S|

Remark. We will establish that T < ∞ in Lemma 3.12.
Proof. Since the assignment polytope A is compact and convex, Φ is strongly convex and smooth,
the existence and the uniqueness of the path x(t) defined in (3.2) follows from Theorem 5.7 with
f (t, x)  −e ℓ,1 . In particular, using the formula for Φ, we have that
∂t x(t) 

x u,i (t) + δ
(−e ℓ,1 − λ(t))
wu

(3.6)

with λ(t) ∈ NA (x(t)).
To calculate NA (x(t)), we note that the constraints {x u,i (t) > 0} are redundant, as they can be
Í
Í
expressed by the constraints { i 6 |S| x u,i (t) 6 (v, j)∈S x v, j (t)} and xr ,1 (t)  0 using the sequence of
11

singleton sets S  (u, i), (p(u), 1), (p(p(u)), 1), · · ·. Hence, we can ignore the constraints {x u,i (t) > 0}
from the polytope.
Using the definition of the assignment polytope A, Lemma 2.1 asserts that
NA (x(t))







Õ


 u∈V,S⊆χ(u)


©Õ

λ S (t) ­

«i 6 |S|

e u,i −

Õ

ª

e v, j ® +

¬

(v, j)∈S

Õ

µ i (t)er ,i +

i >1

Õ

ηu,i (t)e u,i

u∈V,i >1

where λ S (t), ηu,i (t) > 0, µ i (t) ∈ R , ηu,i (t) · (1 − x u,i (t))  0,



Õ


ª
©Õ
x v, j (t)®  0 .
x u,i (t) −
and λ S (t) · ­


(v, j)∈S
«i 6 |S|
¬


Rearranging the terms in (3.6) and NA (x(t)), and ignoring the terms for the root r , we see that it
only remains to show that one can take ηu,i (t) (the Lagrange multiplier for {x u,i (t) 6 1}) to be 0.
Let e
A be the polytope just as A, except with [0, 1] replaced by [0, 2]. Assume now that x(t)
is defined with A replaced by e
A. We will show that one has x u,i (t) 6 1. This implies that the
Lagrange multipliers for the path defined on e
A are valid Lagrange multipliers for the path on A,
and in particular one can take ηu,i (t)  0.
Toward deriving a contradiction, let us assume that there exists a time t > 0, u ∈ Vh , and i > 1
such that x u,i (t) > 1 and ∂t x u,i (t) > 0. We prove by induction on h that this impossible.
For h  0 this follows from the equality constraints at the root. Now consider h > 1 and
observe that by (3.3) and (3.4), one must have λ S (t) , 0 for some S ⊆ χ(p(u)), which means that
Í
Í
i 6 |S| x p(u),i (t) 
(v, j)∈S x v, j (t). However, the induction hypothesis implies that for any j > 1,
x p(u), j (t) 6 1, and thus the constraint corresponding to S \ {(u, i)} is violated for x(t), yielding a a
contradiction.

We now prove several lemmas giving a more refined understanding of the dynamics (3.3). The
reader is encouraged to skip these arguments upon a first reading. The main technical property
b for all times t ∈ [0, T], i.e., the mass per level remains constant.
we need to establish is that z(t) ∈ M
This is established in Lemma 3.8.
For h > 0, let Vh denote the set of vertices with a simple path to the root using h edges. Define
C(t) ⊇ {S : λ S (t) , 0} to be the set of active constraints:









C(t) : S ⊆ χ(u) : u ∈ V and

Õ

x u,i (t) 

i 6 |S|

Õ









x v, j (t) .

(v, j)∈S

Lemma 3.6. For any t > 0, u ∈ V, and i > j > 1, it holds that x u,i (t) > x u, j (t).

Proof. We will show that x u,i (t) > x u,i+1 (t) implies ∂t x u,i (t) 6 ∂t x u,i+1 (t). Recalling (3.3) and (3.4),
it is enough to show that
Õ
Õ
λ S (t) .
λ S (t) >
S⊆χ(p(u)):
(u,i)∈S

S⊆χ(p(u)):
(u,i+1)∈S

Let us show that if (u, i) ∈ S and (u, i + 1) < S then λ S (t)  0, yielding the desired conclusion.
Using the constraint for S ∪ {(u, i + 1)} \ {(u, i)} gives

Õ

(v, j)∈S

x v, j (t) >

Õ

x v, j (t) >

(v, j)∈S∪{(u,i+1)}\{(u,i)}

12

Õ

i 6 |S|

x p(u),i (t) ,

implying that λ S (t)  0.



Lemma 3.7. Consider u ∈ V and S, S′ ⊆ χ(u) such that S, S′ ∈ C(t). Then S ∪ S′ ∈ C(t) as well.
Proof. First we claim that MS : max(v, j)∈S x v, j (t) and MS′ : max(v, j)∈S′ x v, j (t) are equal. Let
(v∗ , j∗ ) denote some pair for which x v, j (t) is maximal among (v, j) ∈ S. If MS > MS′ , then for any
(v ′ , j ′) ∈ S′, the constraint corresponding to S ∪ {(v ′ , j ′)} \ {(v∗ , j∗ )} is violated because S, S′ ∈ C(t).
Let us denote M : MS  MS′ .
Suppose that |S| > |S′ |. The same argument shows that for any (v, j) ∈ S\S′, one has x v, j (t)  M.
Using the constraint for S \ {(v∗ , j∗ )} and the fact that S ∈ C(t) shows that x u,|S| (t) > M, and thus
by Lemma 3.6, one has x u,|S|+m (t) > M for any m > 0. This implies:

Õ

i 6 |S∪S′ |

x u,i (t) >

Õ

x u,i (t) + M · |S \ S′ | 

i 6 |S|

Õ

x v, j (t) + M · |S \ S′ | 

(v, j)∈S

Furthermore, since x(t) ∈ A it also holds that
that S ∪ S′ ∈ C(t).

Í

i 6 |S∪S′ |

x u,i (t) 6

b Then z(t) ∈ M
b for t > 0.
Lemma 3.8. Suppose that z(0) ∈ M.

Í

(v, j)∈S∪S′

Õ

x v, j (t) .

(v, j)∈S∪S′

x v, j (t), demonstrating



Proof. For u ∈ V, let S u (t) be the maximum (w.r.t. inclusion) active set at time t in χ(u) (cf.
Lemma 3.7). Since ∂t x(t) ∈ NA (x(t))⊥ (Lemma 5.8), one has

Õ

Õ

∂t x u,i (t) 

(v, j)∈S u (t)

i 6 |S u (t)|

which in turns gives, for any h > 1,

Õ

∂t x v, j (t) ,

Õ

∂t x u,i (t) 

u∈Vh ,i 6 |S u (t)|

∂t x v, j (t) .

(3.7)

(v, j)∈∪ u∈Vh S u (t)

Thus to compare the derivatives of the mass at two adjacent levels, it remains to establish that

Õ

Õ

∂t x u,i (t) >

u∈Vh ,i>|S u (t)|

∂t x v, j (t) .

(v, j)<∪ u∈Vh S u (t):v∈Vh+1

We show that every term in the first sum is nonnegative and every term in the second sum is
nonpositive. In particular, since ∂t xr ,i (t)  0 for all i > 1, this will imply by induction that

Í

Õ

v∈Vh+1 , j >1

∂t x v, j (t) 6

Õ

∂t x u,i (t) 6 0 ,

u∈Vh ,i >1

b and z(t) ∈ A for all t > 0.
yielding u∈Vh ∂t z u (t) > 0. Then the proof is concluded using z(0) ∈ M
Thus it remains to show that ∂t x u,i (t) > 0 for all i > |S u | and u < L, and ∂t x v, j (t) 6 0 for all
(v, j) < ∪u∈Vh S u (t). For u  r , one has ∂t x u,i (t)  0, and for u , r we have thanks to (3.3) and
Lemma 3.5:
x u,i (t) + δ
λ u,i (t) .
∂t x u,i (t)  −
wu
Since i > |S u (t)| and S u (t) is the maximum active set in χ(u), it holds that λ S (t)  0 for any S ⊆ χ(u)
with |S| > i. Thus from (3.4), we see that λ u,i (t) 6 0, and in turn ∂t x u,i (t) > 0. On the other hand
for (v, j) ∈ χ(u) one has
x v, j (t) + δ
∂t x v, j (t) 6 −
λ v, j (t) .
wv
Assume (v, j) < S u (t). Then since S u (t) is the maximum active set in χ(u), it holds that λ S (t)  0

for any S with (v, j) ∈ S. Using (3.4), we see that λ v, j (t) > 0, concluding the proof
13

We have established that z(t) is an internal measure for every t > 0, and thus ∂t z(t) is a flow.
We now we show that ∂t z(t) is a flow directed toward the request ℓ.
Lemma 3.9. It holds that ∂t z u (t) > 0 if u is an ancestor of the request ℓ, and ∂t z u (t) 6 0 otherwise.

b (Lemma 3.8), it suffices to show that for any leaf ℓ ′ , ℓ, one has ∂t z ℓ′ (t) 6 0.
Proof. Since z(t) ∈ M
Í
Indeed by preservation of mass at every node (i.e., ∂t z u (t)  v:(u,v)∈E® ∂t z v (t)), this implies that
∂t z u (t) 6 0 for any u which is not an ancestor of ℓ. Furthermore, by preservation of mass per level
Í
(i.e., u∈Vh ∂t z u (t)  0), and the fact that there is a single ancestor of ℓ per level, this also gives
∂t z u (t) > 0 for any ancestor u of Í
ℓ.
1
Notice that ∂t z ℓ′ (t)  − 1−δ
i >1 ∂t x ℓ′ ,i (t), and thus it suffices to show that for any i > 1,
′
∂t x ℓ ,i (t) > 0. The latter inequality is straightforward from (3.3) and (3.4) since χ(ℓ ′ )  ∅.

The next lemma follows immediately from Lemma 3.9 since ∂t x ℓ′ (t) > 0 for all ℓ ′ , ℓ.

Lemma 3.10. If x ℓ′ (0) > δ for all ℓ ′ ∈ L, then x ℓ′ (T) > δ for all ℓ ′ ∈ L.
Let us extend the definition of k · kℓ1 (w) to x ∈ RΛ by
kx kℓ1(w) :

Õ

wu

u∈V

Õ

|x u,i | .

i >1

Observe that
sup k∇Φ(x)kℓ∞ (1/w) 6 O(log 1δ ) .
x∈A

This yields the following.
Lemma 3.11. It holds that for every x ∈ A and { y(t)} ⊆ A diﬀerentiable:
∂t D̂Φ (y(t); x) 6 k∂t y(t)kℓ1 (w) O(log δ1 ) .
The next lemma is an immediate consequence of (2.2).
Lemma 3.12. If y ∈ A satisﬁes yℓ  0, then
∂t D̂Φ (y; x(t)) 6 −x ℓ,1 (t) .
In particular, we have that T < ∞ and hence x ℓ,1 (T)  δ.
Proof. The first conclusion follows from (2.2) using yℓ  0 and f (t, x(t))  −e ℓ,1 . Since the
divergence is nonnegative and it is decreasing with rate at least δ whenever x ℓ,1 (t) > δ, the
trajectory ends in finite time.


3.4 The weighted depth potential
Let us first define an auxiliary potential function Ψt . We relate it to the dynamics, and then
present applications in Section 3.4.1–Section 3.4.3, culminating in the assertion that our algorithm
is O((log k)2 )-competitive.
Consider a differentiable function Ψ(t) such that
∂t Ψ(t) 

Õ

w u ∆u (t) + ∆p(u) (t)

u∈V\{ r }

Õ
i >1

14

∂t x u,i (t)

(3.8)

for some functions {∆u (t) > 0 : u ∈ V } satisfying ∆u (t) 6 ∆v (t) for all (u, v) ∈ E® as well as ∆r (t) ≡ 0.
Note that an important special case is simply when

Õ

Ψ(t) 

w u (∆u + ∆p(u) )

u∈V\{ r }

Õ

x u,i (t)

i >1

® define
where {∆u : u ∈ V } are independent of t. For an edge (u, v) ∈ E,
q t (v) : ∆v (t) − ∆u (t) .

(3.9)

Lemma 3.13. The following holds for almost every t ∈ [0, T]:
k∂t x(t)k ℓ1 (q t w) 6 3∆ℓ (t)(x ℓ (t) + δ) + ∂t Ψ(t) .
Proof. Note that from Lemma 3.5, for every u ∈ V \ {r }, we have:
∂t x u,i (t) 
where


x u,i (t) + δ
−1{(u,i)(ℓ,1)} − λ u,i (t) ,
wu

λ u,i (t) 

Õ

λ S (t) −

Õ

(3.10)

λ S (t) .

(3.11)

S⊆χ(p(u)):
(u,i)∈S

S⊆χ(u):
i 6 |S|

Recalling that ∆r (t)  0 for all t ∈ [0, T], we calculate:


> ∂t Ψ(t) + ∆ℓ (t) + ∆p(ℓ) (t) (x ℓ (t) + δ)
Õ


∂t Ψ(t) + 2∆ℓ (t)(x ℓ (t) + δ)

 ∆ℓ (t) + ∆p(ℓ) (t) (x ℓ (t) + δ) +



Õ

Õ

Õ

u∈V\{ r } S⊆χ(u)

+

λ S (t)

Õ

Õ

Õ

u∈V\{ r } S⊆χ(u)

+

Õ

λ S (t)

Õ

Õ

u∈V\{ r } S⊆χ(u)

+

S⊆χ(r )

∂t x u,i (t)

i >1



∆v (t) + ∆p(v) (t) (x v, j (t) + δ) − ∆u (t) + ∆p(u) (t)

∆v (t)(x v, j (t) + δ)

© Õ 

λ S (t) ­

Õ

i 6 |S|

«(v, j)∈S
Õ

(∆v (t) − ∆u (t)) + ∆p(v) (t) − ∆p(u) (t)

∆v (t)(x v, j (t) + δ)

(v, j)∈S

S⊆χ(r )



«(v, j)∈S
Õ

u∈V\{ r }

Õ

ª

(x u,i (t) + δ)®

¬

(v, j)∈S

S⊆χ(r )



© Õ

λ S (t) ­

w u ∆u (t) + ∆p(u) (t)

© Õ

λ S (t) ­

λ S (t)

«(v, j)∈S
Õ





ª

(x v, j (t) + δ)®

¬

ª

q t (v) + q t (u) (x v, j (t) + δ)®

¬

∆v (t)(x v, j (t) + δ) ,

(v, j)∈S

where in the penultimate equality we have used that for S ⊆ χ(u),
λ S (t) > 0 ⇒

Õ

x u,i (t) 

i 6 |S|

Õ

(v, j)∈S

15

x v, j (t) .

(3.12)

On the other hand, the q t · w-movement cost is equal to

Õ Õ

Õ Õ

q t (u)w u ∂t x u,i (t) 

u∈V\{ r } i >1

u∈V\{ r } i >1

Using (3.10) and (3.11) gives

Õ Õ

w u q t (u) ∂t x u,i (t)

u∈V\{ r } i >1

and
−

q t (u)w u ∂t x u,i (t)

Õ Õ

w u q t (u) ∂t x u,i (t)

u∈V\{ r } i >1



−



+

Õ Õ

6

λ S (t)



Õ

+−

q t (u)w u ∂t x u,i (t)

u∈V\{ r }

Õ

q t (v)(x v, j (t) + δ)

Õ

λ S (t)q t (u)



−

.

(v, j)∈S

u∈V S⊆χ(u)

Õ

6 q t (ℓ)(x ℓ (t) + δ) +

Õ

x u,i (t) + δ

i 6 |S|

u∈V\{ r } S⊆χ(u)



Using q t (ℓ) 6 ∆t (ℓ) and (3.12) again (as well as q t (v)  ∆v (t) for (v, j) ∈ S ⊆ χ(r )), we have

Õ Õ

Õ

q t (u)w u ∂t x u,i (t) 6 ∆t (ℓ)(x ℓ (t) + δ) +

u∈V\{ r } i >1

+

Õ

Õ

Õ

λ S (t)

u∈V\{ r } S⊆χ(u)

λ S (t)

S⊆χ(r )

Õ



q t (u) + q t (v) (x v, j (t) + δ)

(v, j)∈S

∆v (t)(x v, j (t) + δ) ,

(v, j)∈S

yielding the desired result.



Note that k∂t x(t)kℓ1 (q t w)  (1 − δ)k∂t z(t)kℓ1 (q t w) . Thus combining Lemma 3.13 with Lemma 3.12
and using x ℓ (t) > δ for t ∈ [0, T] yields the following.
Corollary 3.14. For almost every t ∈ [0, T], if y ∈ A satisﬁes yℓ  0, then
(1 − δ) k∂t z(t)k ℓ1 (q t w) 6 ∂t Ψ(t) + 6∆ℓ (t)∂t D̂Φ (y; x(t)) .
For a function f : V → R+ , define b
f : V \ L → R+ by

n
o
b
f (u) : min f (v) + f (v ′) : v , v ′ , (u, v), (u, v ′) ∈ E® .

For concreteness, let us define b
f (u) : 0 if u has only one child.

Lemma 3.15. For almost every t ∈ [0, T], the following holds. Suppose that (T , w) is a τ-adic HST for
τ > 2, and there is some c > 0 such that

If y ∈ A satisﬁes yℓ  0, then

b
q t (v) > c

∀v ∈ V \ L .

c(1 − δ)
k∂t z(t)k ℓ1 (w) 6 ∂t Ψ(t) + 6∆ℓ (t)∂t D̂Φ (y; x(t)) .
4
Proof. From Lemma 3.8, it holds that z(t) is an internal measure for all t ∈ [0, T], and moreover
∂t z(t) is a flow towards ℓ (cf. Lemma 3.9). Therefore we can decompose
∂t z(t) 

Õ

ℓ′ ∈L
′

where y (ℓ ) (t) is a flow on the unique ℓ ′-ℓ path in T .
16

′

y (ℓ ) (t) ,

′

Let us use | y (ℓ ) (t)| to denote the magnitude of the corresponding flow. Since ∂t z(t) is a flow
towards ℓ, we have
k∂t z(t)k ℓ1 (q t w) >

>

1
τ
c
τ

Õ

b
q t (lca(ℓ, ℓ ′))w lca(ℓ,ℓ′) y (ℓ ) (t)
′

Õ

ℓ′ ∈L\{ℓ}

′

w lca(ℓ,ℓ′ ) y (ℓ ) (t) >

ℓ′ ∈L\{ℓ}

(3.13)

c
k∂t z(t)k ℓ1 (w) ,
4

where the first and last inequality use the fact that w is τ-adic.
3.4.1



Combinatorial depth for general trees

Let distT denote the unweighted shortest-path metric on T . Define ∆u (t) : ∆u  distT (r , u), and
Ψ(t) :

Õ

w u ∆u (t) + ∆p(u) (t)

u∈V\{ r }

Õ

x u,i (t) ,

i >1

Note that q t (cf. (3.9)) satisfies q t ≡ 1 for all t ∈ [0, T]. Therefore applying Corollary 3.14 yields
(1 − δ) k∂t z(t)k ℓ1 (w) 6 ∂t Ψ(t) + 6 distT (r , ℓ) · ∂t D̂Φ (y; x(t)) ,
which in turn gives the following result (recall also Lemma 3.11).
Corollary 3.16. For any tree metric with combinatorial depth D, there is an O(D log k)-competitive
fractional k-server algorithm.
Note that, as opposed to the situation for HSTs, it is not known how to round online a fractional
k-server algorithm on a tree to a random integral algorithm while losing only an O(1) factor in the
competitive ratio.
3.4.2

Cardinality for an HST

Assume now that (T , w) is a τ-adic HST for some τ >
 2. Recall that Nu is number of leaves in the
subtree rooted at u and define ∆u (t) : ∆u  log Nnu . Define:
Ψ(t) :

Õ

w u ∆u (t) + ∆p(u) (t)

u∈V\{ r }

Õ

x u,i (t) .

i >1

Define q  q t as in (3.9). Then for every u ∈ V:
q(u)  log

Np(u)
Nu

.

In particular, for any two children v, v ′ of u:

b
q (u) > log

Nu
Nu
+ log
> log 2 .
Nv
Nv′

Applying Lemma 3.15 with c : log 2 yields
(1 − δ) log 2
k∂t z(t)kℓ1 (w) 6 ∂t Ψ(t) + 6 log(n) · ∂t D̂Φ (y; x(t)) .
4
Combined with Lemma 3.11, this gives the following consequence.
Corollary 3.17. If (T , w) is a τ-adic HST for some τ > 2, then there is an O(log(k) log(n))-competitive
online fractional k-server algorithm on (L, distw ).
The preceding construction motivates our approach to obtaining an O((log k)2 ) competitive
ratio: Try to replace Nu by the fractional server mass in the subtree beneath u.
17

3.4.3

Fractional server-weighted depth

Finally, let us establish the O((log k)2 ) bound. Suppose now that (T , w) is a τ-adic HST. Define:
Ψ(t) :

Õ

wu

u∈V\{ r }





 

z u (t) + 1 + τ−1 1{u <L} ε log(z u (t) + ε) + z u (t) log(z p(u) (t) + ε) .

Consider some node u ∈ V \ {r }, and the terms in ∂t Ψ(t) corresponding to ∂t z u (t):

©



w u ∂t z u (t) ­1 + log (z u (t) + ε) + log z p(u) (t) + ε +

«



τ−1 ε 1{u <L}
+ τ−1 1{u <L}
z u (t) + ε





Õ

v:(u,v)∈E®

 w u ∂t z u (t) 1 + log (z u (t) + ε) + log z p(u) (t) + ε + 1{u <L} τ−1 ,

z v (t) ª
®
z u (t) + ε

b
where in the last equality we used that z(t) ∈ M.
b and (T , w) is a τ-adic HST, it holds that for every j ∈ Z:
Since z(t) ∈ M
Õ

¬

∂t z u (t)  0 ,

u∈V:
w u τ j

and therefore we conclude that

Õ

∂t Ψ(t) 



w u ∂t z u (t) log (z u (t) + ε) + log z p(u) (t) + ε

u∈V\{ r }

−

Õ

u∈V\{ r }

1

1−δ





k + 2ε
k + 2ε
w u ∂t z u (t) log
+ log
z u (t) + ε
z p(u) (t) + ε

Õ

wu

u∈V\{ r }





Õ
k + 2ε
k + 2ε
log
+ log
∂t x u,i (t) .
z u (t) + ε
z p(u) (t) + ε
i >1

Therefore (3.8) holds with
∆u (t) 
and in this case:
q t (u) 

k + 2ε
1
log
,
1−δ
z u (t) + ε

z p(u) (t) + ε
1
log
.
1−δ
z u (t) + ε

Now we can prove the main technical theorem of this section.
Theorem 3.18. The trajectory σ(z(t)) for t ∈ [0, T] is an internal supermeasure of mass k that services the
request at ℓ ∈ L. Moreover, if y ∈ A satisﬁes yℓ  0, then for almost every t ∈ [0, T]:
1−ε
log 34 k∂t σ(z(t))k ℓ1 (w) 6 (1 − δ)∂t Ψ(t) + 6 log(2 + k/ε) · ∂t D̂Φ (y; x(t)) .
4
Proof. First, note that if u ∈ V \ L and z u (t) > ε, then for any children v, v ′ of u:

and therefore

(1 − δ)b
q t (u) > log

z u (t) + ε
z u (t) + ε
4
+ log
> log ,
z v (t) + ε
z v′ (t) + ε
3

b
q t (u) >

log 34
1−δ
18

1{z u (t)> ε} .

(3.14)

′

Let y (ℓ ) (t) be as in the proof of Lemma 3.15. Partition L \ {ℓ} 
leaves ℓ ′ with v  lca(ℓ, ℓ ′), and define
y (v) (t) :

Õ

Ð

v∈V\L

L v , where L v is the set of

′

y (ℓ ) (t) .

ℓ′ ∈L v

Note that by Lemma 3.9, ∂t z(t) is a flow towards ℓ, and thus there are no cancellations in the
preceding sum.
Now use inequality (3.13) and (3.14) to write
k∂t z(t)k ℓ1 (q t w) >



>

Õ

log 43
(1 − δ)τ

ℓ′ ∈L\{ℓ}

Õ

log 34
(1 − δ)τ

′

w lca(ℓ,ℓ′) 1{ zlca(ℓ,ℓ′) (t)> ε } y (ℓ ) (t)
w v 1{z v (t)> ε} y (v) (t)

v∈V\L

1−ε
log 43 k∂t σ(z(t))k ℓ1 (w) ,
1−δ

1
where in the final line we have used the fact that σ is 1−ε
-Lipschitz and σ(z v (t))  0 when z v (t) < ε.
Combined with Corollary 3.14, this yields the desired result, noting that for any leaf ℓ ∈ L:

∆ℓ (t) 6

k + 2ε
1
log
.
1−δ
ε



Using Lemma 3.11 and Lemma 3.3, this yields an O((log k)2 )-competitive online fractional kserver algorithm for any HST metric. (It is not difficult to see that every HST metric embeds with
O(1) distortion into the metric of a 2-adic HST.)

4 Dynamic HST embeddings
Consider a discrete metric space (X, d). Denote the aspect ratio of (X, d) by
AX :

max x,y∈X d(x, y)
min x , y∈X d(x, y)

.

Theorem 4.1. If there is an α-competitive algorithm for k-server on HSTs, then there is an
O(α log(A X ) log k)-competitive algorithm on any metric space (X, d).
We use R(X) : X  to denote the space of request sequences. For σ ∈ R(X) and s 6 t, denote
σ[s,t] : hσs , σs+1 , . . . , σt i. We will consider sequences of random variables that are implicitly
functions of σ ∈ R(X). Say that such a sequence Z  hZ t : t > 0i is adapted if Z t is a function of
σ[1,t] for every t > 1.
This allows one to encode state that depends on the underlying request sequence σ in a timedependent way. For instance, to count the number of requests that fall into a subset X ′ ⊆ X, one
would set Z  0. Then given that σt arrives at time t, we would update Z : Z + 1X′ (σt ). The
meaning is: Z0  0 and Z t : Z t−1 + 1X′ (σt ) for all t > 1.
An online algorithm for k-server on X is an adapted sequence A  hA1 , A2 , . . .i where for every
t > 1: A t ∈ X k and σt ∈ {(A t )1 , . . . , (A t )k }. For a function f with domain X, write f ⊗k for the
function with domain X k given by f ⊗k (x1 , . . . , x k ) : ( f (x1 ), . . . , f (x k )).
For an algorithm A and a request sequence σ, we write costX (A(σ)) for the total movement
cost incurred in servicing σ. We denote by optX : R(X) → (X k ) an optimal oﬄine algorithm and
cost∗X (σ) : costX (optX (σ)) the optimal offline movement cost.
19

4.1 Hierarchical partitions and canonical HSTs
Let us suppose that diam(X, d)  1 and AX < ∞. Let τ : 4 be a scale parameter, and let M ∈ 
denote the smallest number for which τ−M < d(x, y) for all x , y ∈ X.
A sequence of subsets ξ  (ξ0 , ξ1 , . . . , ξ ℓ ) of X for 0 6 ℓ 6 M is a chain if ξ0  X and
ξ0 ⊇ ξ1 ⊇ · · · ⊇ ξ ℓ .
Define the length of such a chain by len(ξ) : ℓ. Denote min(ξ) : ξlen(ξ) . A chain is complete if
it has length M and |ξ M |  1. Let CX denote the set of chains in X and let C̄X denote the set of
complete chains.
Define a rooted tree structure on CX as follows. The root of CX is X. For two chains ξ, ξ ′ ∈ CX :
ξ ′ is a child of ξ if and only if ξ is a prefix of ξ ′ and len(ξ ′)  len(ξ) + 1. For ξ, ξ ′ ∈ CX , let
lca(ξ, ξ ′) ∈ CX denote their least common ancestor. Define a τ-HST metric on C̄X by
′

dτ (ξ, ξ ′) : τ−len(lca(ξ,ξ ))

ξ , ξ′ .

Embedding into complete chains. For a partition P of X we write P(x) for the unique set S ∈ P
containing x. A τ-stack P of X is a sequence P  (P 0 , P 1 , . . . , P M ) of partitions of X such that:
P 0  {X} and for all j  1, 2, . . . , M, it holds that
S ∈ P j ⇒ diam(S) 6 τ−j .
Note that P M (x)  {x} because diam(S) 6 τ−M implies |S| 6 1. Every τ-stack P induces a
canonical mapping FP : X → C̄X into
chains on X as
First define the
 follows.
 the set of complete
′
0
j
0
1
M
0
:
:
S ∩ S : S ∈ P j , S′ ∈ P j−1
P and P̂
forced reﬁnement P̂  P̂ , P̂ , . . . , P̂ inductively by P̂
for j  1, 2, . . . , M. Next define FP by



FP (x) : P̂ 0 (x), P̂ 1 (x), . . . , P̂ M (x) .
The following two lemmas will help to estimate the distortion of the embedding FP .
Lemma 4.2. For any τ-stack P, the map FP : X → (C̄X , dτ ) is non-contracting.
Proof. Consider x, y ∈ X. If dτ (FP (x), FP (y))  τ−ℓ , then FP (x) and FP (y) share a common
prefix of length ℓ, and therefore P ℓ (x)  P ℓ (y). Now property (ii) of a τ-stack guarantees that
d(x, y) 6 diam(P ℓ (x)) 6 τ−ℓ .




Lemma 4.3. For any τ-stack P  P 0 , P 1 , . . . , P M , it holds that

Õ

dτ FP (x), FP (y) 6 τ
τ−j 1P j (x),P j (y)
j >1

∀x, y ∈ X .



Proof. Consider x, y ∈ X and suppose that dτ FP (x), FP (y)  τ−ℓ for some ℓ < M. It is straightforward to check that ℓ + 1  min{ j : P j (x) , P j (y)}.

Next we observe that there is a universal inverse to those embeddings. Define the mapping
Fin : C̄X → X by Fin (ξ) : min(ξ). One has for any τ-stack P:
Fin ◦ FP  idX .

20

(4.1)

4.2 The HST reduction
Let A C denote an α-competitive k-server algorithm for the metric space (C̄X , dτ ) over some probability space ΩC . Suppose that σ  hσ1 , σ2 , . . .i is a request sequence for X, and we have an adapted
sequence P  hP1 , P2 , . . .i of τ-stacks of X over an independent probability space ΩX .
This yields a mapping FP : R(X) → R(CX ) given by
FP (σ) : FP1 (σ1 ), FP2 (σ2 ), . . . .
From this one derives a k-server algorithm for X:
A X : Fin⊗k ◦ A C ◦ FP ,
Note that A X is a valid k-server algorithm precisely because of (4.1).
Moreover, because of Lemma 4.2, the inverse map Fin is non-expanding, and thus:
costX (A X (σ)) 6

ΩC

h



costdτ (A C ◦ FP )(σ)

i

6 OX,k (1) + α cost∗dτ (FP (σ)) .

(4.2)

Thus our goal becomes clear: We would like to choose P so that
ΩX

h



⊗k
◦ optX )(σ)
costdτ (FP

i

6 OX,k (1) + β cost∗X (σ)

∀σ ∈ R(X) .

(4.3)

⊗k
Indeed since FP
◦ optX services the request sequence FP (σ), one has cost∗dτ (FP (σ)) 6





⊗k
◦ optX )(σ) , and thus (4.3) in conjunction with (4.2) show that A X is an αβ-competitive
costdτ (FP

algorithm for X.
In essence, (4.3) asks that the embedding FP has β-distortion on the subset of X that currently
matters. Focusing on such a subset is the reason why one could hope to the usual Ω(log n) lower
bound by something depending on k and AX .

4.3 A dynamic embedding
The algorithm will produce an adapted sequence P  hP1 , P2 , . . .i of τ-stacks verifying (4.3) with
j
β 6 O(M log k). In fact it is slightly easier for the algorithm’s description to allow Pt to be a partial
partition, i.e., simply a collection of pairwise disjoint subsets of X. In the case it is understood that
the embeddings FP use the completion of any such partial partition P, that is all the elements from
X \ [P] (we denote [P] : ∪S∈P S) are added as singletons to form a complete partition.
The embedding algorithm. For j  1, . . . , M, we will maintain an adapted set N j ⊆ X of level-j
centers as well as an adapted mapping R j : N j → R+ of radii. These will be used to construct our
adapted τ-stack P  P 0 , P 1 , . . . , P M .
For every j ∈ Z, consider the probability distribution µ j with density:
dµ j (r) :



kτ j log k
exp −rτ j log k 1[0,τ− j ] (r) .
k−1

This is simply a truncated exponential distribution, as employed by Bartal [Bar96].
j

j

Initially, N0  P0  ∅ for j  1, . . . , M. Upon receiving request σt ∈ X, we proceed as follows:
For j  1, 2, . . . , M:
1. If |N j | > 2k, then
[level- j reset]:
For i  j, j + 1, . . . , M, set N j : ∅ and P j : ∅.
21

2. If d(σt , N j ) > τ−j−1 , then
[level- j insertion]:
(a) N j : N j ∪ {σt }
j

j

(b) R j (σt ) : τ−j−1 + R̂ t , where R̂ t is sampled independently according to the
distribution µ j+1 .

(c) P j : P j ∪ B(σt , R j (σt )) \ [P j ] .

Analysis. Let us now prove that for the stack P generated in this way, (4.3) holds for β 6
O(M log k). We need a few preliminary results.
Lemma 4.4. Pt is a τ-stack for every t > 1.
Proof. This follows from the fact that the distribution µ j+1 is supported on the interval [0, τ−j−1 ]
j

and thus every set in Pt is contained in a ball of radius 2τ−j−1 , which is a set of diameter at most
4τ−j−1 6 τ−j for τ > 4.

We defer the proof of the next lemma to the end of this section.
Lemma 4.5. For all x ∈ X and t > 1, it holds that
ΩX




dτ (FP t (x), FP t (σt )) 6 O(M log k) d(x, σt ) .

Lemma 4.6. For all t > 1 and j  1, 2, . . . , M: If K j,t denotes the number of level-j resets up to time t,
then
cost∗X (σ[1,t] ) > kτ−j−1 · K j,t .
Proof. Suppose that between time t1 +1 and t2 there are requests made at points x1, x2 , . . . , x k+k′ ∈ X
that satisfy d(x i , x j ) > D for all i , j. Then clearly:
cost∗X (σ[1,t2 ] ) > cost∗X (σ[1,t1 ] ) + k ′ D .

Theorem 4.7. For every time t > 1:
ΩX

h



⊗k
◦ optX )(σ[1,t] )
costdτ (FP

i



6 O(M log k) cost∗X (σ[1,t] ) + OX,k (1) .

⊗k
◦ optX into three parts: First the stack P is possibly
Proof. We can split the movement of FP
updated by the algorithm, either with a reset or an insertion (each induce movement), and then
we mirror the move of optX .
Let us first consider the case of a level-j reset at time t. The key observation is that the mapping
j−1
j−1
0
FP t remains identical to FP t on the (j −1)-prefix, that is (Pt0 (x), . . . , Pt (x))  (Pt−1
(x), . . . , Pt−1 (x)),
∀x ∈ X. Thus the movement cost induced by a level-j reset is at most kτ1−j . In particular the total
cost of resets up to time t is upper bounded by
M
Õ

K j,t · kτ1−j 6 τ2 M · cost∗X (σ[1,t] ) ,

j1

where the last inequality is Lemma 4.6.
For the cost resulting from a level-j insertion at time t, we use the following argument. Assume
that j is the smallest index in [M] with a level-j insertion. Note that, by construction of the
22

j

radii, one has Pth (σt ) ⊆ Pt (σt ) for h > j. In particular, the movement comes from the set of
j

servers I t  {i ∈ [k] : (optX
t−1 )i ∈ Pt (σt )}, for which the mapping F P t will change the j-suffix
j

(i.e., (Pt , . . . , PtM )) compared to FP t−1 . However, importantly the (j − 1)-prefix remains identical
(this is because there is no insertion at level j − 1 and thus these servers remain part of the same
non-singleton cluster at level j − 1).
In other words, the total movement is O(τ−j |I t |). Now we argue that we can match this
movement with either reset movement or movement coming from optX as follows. First we
ignore the set of servers in Jt ⊆ I t such that their (j − 1)-prefix remain the same forever, indeed
Í
one has t >1 | Jt |  OX,k (1). Now for a server i ∈ I t \ Jt consider the first time s > t such that the
X
(j − 1)-prefix of FP t−1 ((optX
s )i ) is different from F P t ((opt t−1 )i ). The corresponding movement at
time s comes either from a reset or from a movement of optX , and moreover its cost is larger than
τ−j . Thus we just showed that at the expense of an additive term of OX,k (1) and a multiplicative
factor 2 for movement cost induced by resets and the movement of optX , one can ignore the
movement cost induced by insertions.
Finally, we deal with the cost coming from movement of optX . We may assume that optX is
X
X
X
X
conservative: If σt ∈ optX
t−1 , then optt  optt−1 and otherwise optt−1 \ optt  {x t } for some x t ∈ X,
X
and opt pays d(σt , x t ). From Lemma 4.5, the expected cost of mirroring this move in dτ is at most
O(M log k) d(σt , x t ).

j

Thus we are left only to analyze the stretch. Note that since d(σt , Nt ) 6 τ−j−1 by construction,
the next lemma yields Lemma 4.5 when combined with Lemma 4.3.
j

Lemma 4.8. For every y ∈ X satisfying d(y, Nt ) 6 τ−j−1 and every x ∈ X:

h
i
j
j
 Pt (x) , Pt (y) 6 (2 + 4e)d(x, y)τ j+1 log k .

j

Proof. Note that |Nt | 6 2k by construction. Let us arrange the centers in the order which they were
j
j
added: Nt  {x1 , x2 , . . . , x N }. Let R̂ 1 , . . . , R̂ N denote the corresponding random radii R̂ i : R̂ t (x i )
and let R i : R̂ i + τ−j−1 .
Denote the event



E i : d(x i , {x, y}) 6 R i ∧ max{d(x i , x), d(x i , y)} > R i ,
and let i ∗ : min{i : d(x i , {x, y}) 6 R i }. Define c : (1 −



h

j
Pt (x)

,

j
Pt (y)

i



6

N
Õ

i1
N
Õ

1
−j−1 .
log k )τ

Then:

[i  i∗ ] · [E i | i  i∗ ]
[E i ∧ { R̂ i > c}] +

i1

N
Õ
i1

For any i  1, . . . , N, we have

[E i ∧ { R̂ i > c}] 6 sup
∫

R>c

6

(∫



[i  i∗ ] ·  E i ∧ { R̂ i < c} | i  i∗ .

R+d(x,y)

dµ j+1 (r)

R

c+d(x,y)

dµ j+1 (r)

c

23

)



k 
j+1
1 − exp −d(x, y)τ j+1 log k e −cτ log k
k−1
2e
6 d(x, y)τ j+1 log k ,
k



where the final line uses 1 − e −u 6 u and k > 2.
4e d(x, y)τ j+1 log k since N 6 2k.
Now analyze:

This yields

∫ R+d(x,y)





 R

dµ j+1 (r) 
[E i ∧ { R̂ i < c} | i  i∗ ] 6 sup
∫
−
j−1
06 R<c 

 τ dµ j+1 (r) 

 R
∫ c+d(x,y)
6 c∫ − j−1
τ
c



ÍN

i1

[E i ∧ { R̂ i > c}] 6

dµ j+1 (r)

dµ j+1 (r)

1 − exp −d(x, y)τ j+1 log k
1 − exp(cτ j+1 log k)/k



6 2d(x, y)τ j+1 log k ,

where in the last line we have used again 1 − e −u 6 u and the value of c.



5 Mirror descent
We now prove Theorem 2.2.

5.1 Preliminaries
Consider an Rn -set-valued map F with domain X ⊆ Rn . We will be interested in the following
viability problem (i.e., a differential inclusion with a constraint set for the solution): Given a constraint
set K ⊆ X and initial point x0 ∈ K, find an absolutely continuous solution x : [0, ∞) → K such that
∂t x(t) ∈ F(x(t)) ,
x(0)  x0 .
The upshot is that, under appropriate continuity condition on F, this problem has a solution
provided that F always contain admissible directions, that is F(x) ∩ TK (x) , ∅ where TK (x) is the
tangent cone to K at x (see definition below). We now recall the needed definitions with some
basic results, and state the general existence theorem from [AC84].
Definition 5.1. The polar N ◦ of a set N ⊆ Rn is
N ◦ : {z ∈ Rn : hz, yi 6 0 for all y ∈ N } .
The normal cone to K at x is
and the tangent cone to K at x is

NK (x)  (K − x)◦ ,
TK (x) : NK (x)◦ .

Lemma 5.2 (Moreau’s decomposition [HUL93, Thm III.3.2.5]). Let N be a cone. Then for any x ∈ Rn
there is a unique pair (u, v) ∈ N × N ◦ such that hu, vi  0 and x  u + v. Furthermore u (resp., v) is the
projection of x onto N (resp., N ◦ ).

24

Definition 5.3. F is upper semicontinuous (u.s.c.) if for any x ∈ X and any open neighborhood
N ⊃ F(x) there exists a neighborhood M of x such that F(M) ⊆ N. F is upper hemicontinuous (u.h.c.)
if, for any θ ∈ Rn , the support function x 7→ sup y∈F(x) hθ, yi is upper semicontinuous.
Lemma 5.4 ([AC84, Prop. 1, pg. 60; Cor. 2, pg. 63]). For any F as above, u.s.c. implies u.h.c., and
moreover if F takes compact, convex values then the two notions are equivalent.
Lemma 5.5 ([AC84, Thm. 1, pg. 41]). Let F and G be two set valued maps such that F is u.s.c., F takes
compact values, and the graph of G is closed. Then the set-valued mapping x 7→ F(x) ∩ G(x) is u.s.c.
Theorem 5.6 ([AC84, Thm. 1, pg. 180]). Assume that F is u.h.c. and takes compact, convex values, and
that K is compact. Furthermore assume the tangential condition: For any x ∈ X,
F(x) ∩ TK (x) , ∅ .
Then the viability problem admits an absolutely continuous solution.

5.2 Existence
We prove the following theorem which can be viewed as a non-Euclidean extension of [AC84, pg.
217].
Theorem 5.7. Let K ⊆ Rn be a compact convex set, let H : K → {A ∈ Rn×n : A ≻ 0} be continuous, and
let f : [0, ∞) × K → Rn be continuous. Then, for any x0 ∈ K, there is an absolutely continuous solution
x : [0, ∞) → K K satisfying



∂t x(t) ∈ H(x) f (t, x(t)) − NK (x(t)) ,
x(0)  x0 .

(5.1)

Furthermore, any solution to the viability problem satisﬁes
2
∂t x(t)  argmin kv − H(x) f (t, x(t))kx,∗
: v ∈ TK (x(t)) .



(5.2)

k∂t x(t)kx,∗ 6 k f (t, x)kx .

(5.3)

In particular, one has

Proof. It suffices to prove the existence on any time interval [T, T + 1]. We denote h·, ·ix for the
inner product induced by H(x) (i.e., hα, βix : hα, H(x)βi), k · kx for the corresponding norm, and
k · kx,∗ for its dual norm. To apply Theorem 5.6, consider the following differential inclusion, with
K  [T, T + 1] × K,
e
x ′(t) ∈ F(e
x (t)) ,

where F : K → 2R

n+1

defined by



F(t, x) : 1, H(x) f (t, x) − NK (x)) ∩ {v ∈ Rn : kv kx,∗ 6 k f (t, x)kx }



.

Thanks to the restriction to velocities satisfying kv kx,∗ 6 k f (t, x)kx , it holds that F(t, x) is compact
(it is also clearly convex). Moreover, K is compact. Thus, besides the tangential condition, it remains
to show that F is u.h.c. Since F is compact and convex valued, by Lemma 5.4 it suffices to show
that F is u.s.c. For this we apply Lemma 5.5. Note that {(1, H(x)( f (t, x) − y)) : x ∈ K, y ∈ NK (x)}
is closed (using again continuity of H and f ), and thus it suffices to show that the mapping
x 7→ {v ∈ Rn : kv kx,∗ 6 k f (t, x)kx } is u.s.c., which is clearly true since its support function in
direction θ is x 7→ k f (t, x)kx kθkx which is continuous by continuity of H and f .
25

It remains to check the tangential condition. We note that
NK (t, x) 
TK (t, x) 

(
(

(−∞, 0] × NK (x) t  0 ,
{0} × NK (x)
otherwise.
[0, ∞) × TK (x)
R × TK (x)

t  0,
otherwise.

Thus it suffices to show that there exists u ∈ NK (x) such that kH(x)( f (t, x) − u)kx,∗ 6 k f (t, x)kx
and H(x)( f (t, x) − u) ∈ TK (x).
We apply Moreau’s decomposition (Lemma 5.2) in Rn equipped with the inner product h·, ·ix to
the cone NK (x) and write f (t, x)  u + v where u ∈ NK (x) and v is in the polar (w.r.t. h·, ·ix ) of NK (x).
Since hu, vix  0, we have k f (t, x) − u kx 6 k f (t, x)kx . This gives kH(x)( f (t, x) − u)kx,∗ 6 k f (t, x)kx .
Furthermore since v is in the polar, we have for all y ∈ NK (x), h f (t, x) − u, yix 6 0 which means
that H(x)( f (t, x) − u) ∈ TK (x). This concludes the existence proof.
Since the objective function in (5.2) is strongly convex, the optimality condition of (5.2) shows
that any v ∈ TK (x(t)) satisfying H(x)−1 (v − H(x) f (t, x(t))) ∈ −TK (x(t))◦ is the unique solution.
Now, we note that ∂t x(t) ∈ TK (x(t)) because x(t) ∈ K and
H(x)−1 (∂t x(t) − H(x) f (t, x(t))) ∈ −NK (x(t))  −TK (x(t))◦ ,
where we used that TK (x(t))◦  NK (x(t))◦◦  NK (x(t)) (since NK (x(t)) is a closed and convex cone).
This establishes (5.2).
Since we exhibited a solution satisfying (5.3), the almost everywhere uniqueness of ∂t x(t) shows
that (5.3) holds for any solution.


5.3 Uniqueness
We prove here that the solution to the viability problem is in fact unique under slightly more
restrictive assumptions than those in Theorem 5.7. In what follows, we denote, as in the proof of
Theorem 5.7, h·, ·ix for the inner product induced by H(x), k · kx for its corresponding norm and
k · kx,∗ for its dual norm.
Lemma 5.8. Let x(t) be an absolutely continuous path with values in a convex set K ⊆ Rn . Then,
∂t x(t) ∈ NK (x(t))⊥ almost everywhere.
Proof. For any t such that ∂t x(t) exists, one has
x(t + h)  x(t) + h∂t x(t) + o(h) .
In particular for any y ∈ NK (x(t)), since x(t + h) ∈ K, one has
y, x(t + h) − x(t) 6 0.
Taking h → 0+ , we obtain y, ∂t x(t) 6 0. Taking h → 0− , we obtain y, ∂t x(t) > 0. Therefore,
∂t x(t) ∈ NK (x(t))⊥ .

Lemma 5.9. The solution x(t) in Theorem 5.7 is unique provided that H is Lipschitz, and f is locally
Lipschitz.
Proof. Let x(t) and x̃(t) be two solutions to the viability problem. We show that for any T > 0 there
are some constants C, ε > 0 such that for all t ∈ [T, T + ε],
2
2
,
6 C kx(t) − x̃(t)kx(t),∗
∂t kx(t) − x̃(t)kx(t),∗

26

(5.4)

which concludes the proof by a simple application of Gronwall’s inequality (notice that since H is
continuous and K is compact, there is some constant ε′ such that H −1 (x)  ε′In , ∀ x ∈ K).
Recall that we have ∂t x(t)  H(x(t))( f (t, x(t)) − u(t)) for some u(t) ∈ NK (x(t)) (and similarly
for x̃ there is some path ũ in the normal cones). In particular we get:
1
2
∂t kx(t) − x̃(t)kx(t),∗
 hx(t) − x̃(t), H(x(t))( f (t, x(t)) − u(t)) − H(x̃(t))( f (t, x̃(t)) − ũ(t))ix(t),∗
2
(5.5)
1
(5.6)
+ (x(t) − x̃(t))⊤ (∂t H(x(t))−1 )(x(t) − x̃(t)) .
2
Denote k · kop for the spectral norm, and observe that by continuity of H and compactness of K,
there exists M > 0 such that for all t, kH(x(t))kop , kH(x(t))−1 kop 6 M. Thus we can bound the
term (5.6) as follows:
2
kH(x(t))1/2 (∂t H(x(t))−1 )H(x(t))1/2 kop
(x(t) − x̃(t))⊤ (∂t H(x(t))−1 )(x(t) − x̃(t)) 6 kx(t) − x̃(t)kx(t),∗
2
6 M kx(t) − x̃(t)kx(t),∗
k(∂t H(x(t))−1 )kop .

Now since H is Lipschitz, there exists a constant M ′ such that for all t ∈ [T, T + ε],
k(∂t H(x(t))−1 )kop  kH(x(t))−1 (∂t H(x(t)))H(x(t))−1 kop

6 M 2 M ′ k∂t x(t)k2 6 M 3 M ′ k∂t x(t)kx(t),∗ 6 M 3 M ′ k f (t, x(t))kx(t) ,
where the last inequality follows from (5.3). Since f (t, x) is uniformly bounded on [T, T + ε], we
2
finally get that for some C > 0, the term (5.6) is bounded from above by C kx(t) − x̃(t)kx(t),∗
for all
t ∈ [T + ε].
Next we consider the term (5.5) and decompose it into two terms:



(i) (x(t) − x̃(t))⊤ f (t, x(t)) − u(t) − ( f (t, x̃(t)) − ũ(t)) , and
(ii)

x(t) − x̃(t), (H(x(t)) − H(x̃(t))) f (t, x̃(t)) − ũ(t)

We further decompose (i) into



x(t),∗

.

(iii) (x(t) − x̃(t))⊤ ( f (t, x(t)) − f (t, x̃(t))), and
(iv) (x(t) − x̃(t))⊤ (ũ(t) − u(t)).
To bound (iii), we now use that f is locally Lipschitz, which shows that this term is bounded from
above by C kx(t) − x̃(t)kx(t),∗ for any t ∈ [T, T + ε].
The term (iv) is nonpositive since u(t) ∈ NK (x(t)) and ũ(t) ∈ NK (x̃(t)). Finally, for (ii) one can
combine Lipschitzness of H and (5.3) as above to obtain that it is bounded by C kx(t) − x̃(t)kx(t),∗
for all t ∈ [T, T + ε], thus concluding the proof.


Acknowledgements
Part of this work was carried out while M. B. Cohen, Y. T. Lee, and J. R. Lee were at Microsoft
Research in Redmond. We thank Microsoft for their hospitality. M. B. Cohen and A. Madry
˛
are
supported by NSF grant CCF-1553428 and an Alfred P. Sloan Fellowship. J. R. Lee is supported by
NSF grants CCF-1616297 and CCF-1407779 and a Simons Investigator Award.

27

References
[ABBS14] Jacob Abernethy, Peter Bartlett, Niv Buchbinder, and Isabelle Stanton. A regularization
approach to metrical task systems. In Algorithmic Learning Theory, ALT 2010. Springer,
2014. 3
[AC84]

Jean Pierre Aubin and A. Cellina. Diﬀerential Inclusions: Set-Valued Maps and Viability
Theory. Springer-Verlag New York, Inc., Secaucus, NJ, USA, 1984. 24, 25

[Bar96]

Yair Bartal. Probabilistic approximations of metric spaces and its algorithmic applications. In 37th Annual Symposium on Foundations of Computer Science, FOCS ’96, Burlington,
Vermont, USA, 14-16 October, 1996, pages 184–193, 1996. 2, 21

[Bar98]

Yair Bartal. On approximating arbitrary metrices by tree metrics. In STOC ’98 (Dallas,
TX), pages 161–168. ACM, New York, 1998. 2

[BBK99]

Avrim Blum, Carl Burch, and Adam Kalai. Finely-competitive paging. In 40th Annual
Symposium on Foundations of Computer Science (New York, 1999), pages 450–457. IEEE
Computer Soc., Los Alamitos, CA, 1999. 2

[BBM06]

Yair Bartal, Béla Bollobás, and Manor Mendel. Ramsey-type theorems for metric spaces
with applications to online problems. J. Comput. System Sci., 72(5):890–921, 2006. 2

[BBMN15] Nikhil Bansal, Niv Buchbinder, Aleksander Madry, and Joseph Naor.
A
polylogarithmic-competitive algorithm for the k-server problem. J. ACM, 62(5):Art.
40, 49, 2015. 3, 9
[BBN12]

Nikhil Bansal, Niv Buchbinder, and Joseph Naor. A primal-dual randomized algorithm
for weighted paging. J. ACM, 59(4):Art. 19, 24, 2012. 3

[BCN14]

Niv Buchbinder, Shahar Chen, and Joseph (Seffi) Naor. Competitive analysis via regularization. In Proceedings of the Twenty-ﬁfth Annual ACM-SIAM Symposium on Discrete
Algorithms, SODA ’14, pages 436–444, Philadelphia, PA, USA, 2014. Society for Industrial and Applied Mathematics. 3

[BE98]

Allan Borodin and Ran El-Yaniv. Online computation and competitive analysis. Cambridge
University Press, New York, 1998. 2

[BLMN05] Yair Bartal, Nathan Linial, Manor Mendel, and Assaf Naor. On metric Ramsey-type
phenomena. Ann. of Math. (2), 162(2):643–709, 2005. 2
[Bub15]

Sébastien Bubeck. Convex optimization: Algorithms and complexity. Foundations and
Trends in Machine Learning, 8(3-4):231–357, 2015. 3

[CMP08]

Aaron Coté, Adam Meyerson, and Laura Poplawski. Randomized k-server on hierarchical binary trees. In STOC’08, pages 227–233. ACM, New York, 2008. 3

[FKL+ 91]

A. Fiat, R. M. Karp, M. Luby, L. A. McGeoch, D. D. Sleator, and Young N. E. Competitive
paging algorithms. J. Algorithms, 12(4):685–699, 1991. 2

[FRT04]

Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar. A tight bound on approximating
arbitrary metrics by tree metrics. J. Comput. Syst. Sci., 69(3):485–497, 2004. 2

[Haz16]

Elad Hazan. Introduction to online convex optimization. Foundations and TrendsÂő in
Optimization, 2(3-4):157–325, 2016. 3
28

[HUL93]

Jean-Baptiste Hiriart-Urruty and Claude Lemaréchal. Convex analysis and minimization
algorithms, Volume I: Fundamentals. Springer-Verlag, 1993. 24

[Kou09]

Elias Koutsoupias. The k-server problem. Computer Science Review, 3(2):105–118, 2009.
2

[KP95]

Elias Koutsoupias and Christos H. Papadimitriou. On the k-server conjecture. J. Assoc.
Comput. Mach., 42(5):971–983, 1995. 2

[MMS90]

Mark S. Manasse, Lyle A. McGeoch, and Daniel D. Sleator. Competitive algorithms for
server problems. J. Algorithms, 11(2):208–230, 1990. 2

[MS91]

Lyle A. McGeoch and Daniel D. Sleator. A strongly competitive randomized paging
algorithm. Algorithmica, 6(6):816–825, 1991. 2

[NY83]

A. Nemirovski and D. Yudin. Problem Complexity and Method Eﬃciency in Optimization.
Wiley Interscience, 1983. 3

29

