Efficient Online Clustering with Moving Costs
Authors: Dimitris Christou
EFSTRATIOS PANTELEIMON SKOULAKIS
Volkan Cevher
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Online Learning
Regret Analysis
Clustering
k-Median

Abstract: In this work we consider an online learning problem, called Online $k$-Clustering with Moving Costs, at which a learner maintains a set of $k$ facilities over $T$ rounds so as to minimize the connection cost of an adversarially selected sequence of clients. The learner is informed on the positions of the clients at each round $t$ only after its facility-selection and can use this information to update its decision in the next round. However, updating the facility positions comes with an additional moving cost based on the moving distance of the facilities. We present the first $\mathcal{O}(\log n)$-regret polynomial-time online learning algorithm guaranteeing that the overall cost (connection $+$ moving) is at most $\mathcal{O}(\log n)$ times the time-averaged connection cost of the best fixed solution. Our work improves on the recent result of (Fotakis et al., 2021) establishing $\mathcal{O}(k)$-regret guarantees only on the connection cost.

Efficient Online Clustering with Moving Costs
Dimitris Christou" UT Austin christou @ cs. us.utexas.edu
Stratis Skoulakis' LIONS, EPFL
Volkan Cevher LIONS, EPFL volkan.cevher@eppl..h
Abstract
In this work consider online learning problem, called Online k- -Cuustering with Moving Costs, at which a learner maintains a set of facilities over T rounds to minimize the connection cost of an adversarially selected sequence of clients. The learner is informed on the positions of the clients at each round / only this information update its decision in
after its facility-selection and the next round. However, updating the facility positions comes with an additional moving cost based on the moving distance of the facilities. We present the first Olog n. -regret polynomial-time online learning algorithm guaranteeing that the overall cost (connection moving) most Oloog n) times the time-averaged connection cost of the best fixed solution. Our work improves on the recent result of Fotakis et al. [3 establishing Ole)-rrrret guarantees only on the connection cost.
Introduction
Due to their various applications in diverse fields (e.g. machine learning, operational research, data science etc.), clustering problems have been extensively studied. In the well-studied ie-median problem, given set of clients, facilities should be placed on a metric with the objective to minimize
the sum of the distance of each client from its closest center [55 13 67
52 65 BS
In many modern applications (e.g., epidemiology, social media, conference, etc.) the positions of the 23
clients not static but rather evolve time [57] 56 64 (59]
5]. For example the geographic distribution of the clients of an online store or the distribution of Covid-19 cases may drastically change from year to year or respectively from day day [II. In such settings it is desirable to update/change the positions of the facilities (e.g., compositions of warehouses or Covid test-units) so better serve the time-evolving trajectory of the clients.
The clients' positions may change in complex and unpredictable ways and thus an a priori knowledge their trajectory is not always available. Motivated by this, recent line of research studies clustering problems under the online learning framework by assuming that the sequence of clients' positions is unknown and adversarially selected 18
16 31). More precisely, learner must place & facilities at each round 2 without knowing the positions of clients at round & which are revealed to the learner only after its facility-sslection The learner
28
this information update its decision in the next round; however, moving a facility comes with an additional moving cost that should be taken into account in the learner's updating decision, e.g. moving Covid-19 19 test-units comes with a cost [8] 28
Building this line of works, consider the following online learning problem:
Problem 1 (Online k- t-Clustering with Moving Costs). Let G(V, E, w) be weighted graph with [V| = n vertices and ls facilities. At each round = I,...,T: T::
1. The learner selects F, V. with F k, at which facilities are placed.
First author contribution.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

2. The adversary selects the clients' positions, R S V.
3. The learner learns the clients' positions Rg and suffers
cost
Σ
min min (.. iEFL
+7 2
JER
moviin cost of fucilities
connection client j
where da(j,i) is the distance between vertices i, E V; Mc(Fi-1, P.) is the minimum overall distance required to move k facilities from Fi-1 to Fú; and y 2 0 is the facility-weight.
An online learning algorithm for Problem ! Itries minimize the overall (connection moving) cost by placing k facilities at each round 7 2 1 based only on the previous positions of clients R.,..., R To the best of our knowledge, Problem was first introduced in [8 If for any sequence of clients, the overall cost of the algorithm is at most times the overall connection cost of the optimal fixed placement of facilities F" then the algorithm is called a-regret, while in the special case of the algorithm is additionally called no-regret.
Problem comes as a special case of the well-studied Metrical Task System by considering each of the possible (f) facility placements as different state. In their seminal work, [1]] guarantee that the famous Multiplicative Weights Update algorithm (MWU) achieves (1 + e) e)-regret in Problem [ for any O. Unfortunately, running the MWU algorithm for Problem i not really an option since it requires (n*)) time and space complexity. As a result, the following question naturally arises:
Q. Can we achieve a-regret for Problem] 7 with polynomial-time online learning algorithms?
Answering the above question is challenging task. Even in the very simple scenario of time-invaan iive-invarannt clients, i.c. R₂ = R for all 2 1, an a-regret online learning algorithm must essentially compute an a-approximate solution of the k-median problem. Unfortunately the k-median problem cannot be approximated with ratio < 1 + 2/e = 1.71 (unless NP S DTIME (n log x] [3 which excludes the existence of an (1+ 2/e) reerrtt polynomial-time online learning algorithm for Problem Despite the fact that many O(1)-approiimation algorithms have been proposed for the k-median problem
(the best current ratio is + v3 [54] ), these algorithms crucially rely on the (offline) knowledge of the whole sequence of clients and most importantly are not designed to handle the moving cost the
facilities [55] 14 13
67
52 65| 51 15
In their recent work, Fotakis al. 31 propose an -regrret polynomial-time online learning algorithm for Problem without moving costs (i.e. the special case of y = 0). Their approach is based on designing a no-regrer polynomial
algorithm for a fractionaal relaxation of Problem [ and then using an online client-oblivions rounding scheme in order to convert fractional solution to an integral one. Their analysis based on the fact that the connection cost of any possible client is at most (k) times its fractional connection cost. However in order to establish the latter guarantee their rounding scheme performs abrupt changes on the facilities leading to huge moving cost.
Our Contribution and Techniques. this work, we provide a positive answer to question (Q), by designing the first polynomial-time online learning algorithm for Online k-Clustering with Moving Costs that achieves O (log n) m)-regret for any 7 2 O. The cornerstone idea of our work was to realize be established with a polynmmial-time online learning algorithm in the special case of G being a Hicrarchical Separation Tree (HST). Then, by using the standard metric embedding result of [25]. we can easily convert such an algorithm to an Ollog rrerett algorithm for general graphs. Our approach for HSTs consists of two main technical steps:
that (())-regret
1. We introduce a fractional relaxation of Problem for HSTs. We then consider a specific regularizer the fractional facility placements, called Dilated Entropic Regularizer (26), that takes into account the specific structure the HST. Our first technical contribution is to establish that the famous Follow the Leader algorithm 35 with dilated entropic regularization admits O11--regret for any 7 2 0.
In [8]. an easier version of Problem 1 with 1-lookahead is considered, meaning that the learner learns the positions of the clients Rd before selecting F.. Moreover, G is considered to be the line graph and 1.

---

2. Our second technical contribution is the design of novel online elient-oblivious rounding scheme, called Cuund, that converts fractional solution for HSTs into an integral one. By exploiting the specific HST structure we establish that Cut Round, despite not knowing the clients' positions R, simultaneously guarantees that (i) the connection cost of each client j E Rg is upper bounded by its fractional connection cost, and (ii) the expected moving cost of the facilities is at most (()) times the fractional moving cost.
Experimental Evaluation. In Section F of the Appendix we experimentally compare our algorithm with the algorithm of Fotakis al. [31] Our experiments verify that our algorithm robust to increases of the facility weight y while the algorithm of [3T] presents a significant cost. increase. We additionally experimentally evaluate our algorithm in the MNIST and CIFAR10 datasets. Our experimental evaluations suggest that the ( -regret bound is pessimistic upper bound and that in practise our algorithm performs significantly better. Finally, we evaluate our algorithm both in the random arrival case (where the requested vertices drawn uniformly random from the graph) as well as in adversarial settings, where the request sequences are constructed through some arbitrary deterministic process.
Related Work.
As already mentioned, our work most closely relates with the work of Fotakis et al.
31 that provides an (kk)-regre algorithm running in polynomial-time for ? 0. [6] also consider Problem I = with the difference that the connection cost of clients is captured through the k-means objective i.e. the sum of the squared distances. They provide (1 c)-regret algorithm with O ((K3 22)) time-complexity that is still exponential in k. [18 28 study the special case [ in which G the line graph and y = while assuming 1-lookahead on the request + coompettti online algorithm meaning that its cost is at most (1 + e) times the cost of the optimal dynamic solution and directly implics (1 + e)-regret. [28) extended the previous result by providing 63-competitive algorithm for h = 2 on line graphs. Our work also relates with the works of [23] and [4] that study offline approximation algorithms for clustering problems with time-evolving metries. Finally our work is closely related with the research line of online learning in combinatorial domains and other settings of online clustering. Due to space limitations, we resume this discussion in Section A of the Appendix.
of Problem
Rs. For k 1, [8] provide
2 Preliminaries and Our Results
Let G(V, E.) be weighted undirected graph where V denotes the set of vertices and E the set of edges among them. The weight we of an edge e (i. E denotes the cost of traversing e. Without loss, we assume that Wie E N and w. 2 for all edges E E. The distance between vertices j is denoted with de (i and equals the cost the minimum cost path from i V to j E V. We use n = [V] to denote the cardinality of G and DG == maxijev di) to denote its diameter.
Given placement of facilities C V. with |F| = a client placed at vertex j E V connects the closest open facility i E F. This is formally captured in Definition] [
Definition 1. The connection cost of a set of clients R S V under the fucility-placement F C V with [F| = k equals
CR(F)= = Σ
min do(j.i) iEF
jER
Next, consider any pair of distance between F' and F² is the minimum overall distance needed to transfer the facilities from F to F", formally defined in Definition 2
F" C V such that [F] |F k. The moving
Definition 2. Fix any facility-placemeen all possible matchings from F F' i.e. each a E E a one-to-one mapping : F +t FO with ai) E F' denoting the mapping of facility i E F. The moving cost between F and F' equals
F, F" C V where [F] =1
k. Let Σ be the set of
Mc(F,F", == min GEE REF
Σ dali,a(i))
At each round 2 1, an online learning algorithm A for Problem ttaes as input all the previous positions of the clients Ri...., Re-1 C V and outputs a facility- F, := A(R1,.... R4-1)
3

---

such that Fi S V and |F:] = k. The performance of an online learning algorithm is measured by the notion of regret, which we formally introduce in Definition Definition 3. An online learning algorithm f Problem is called a-regret with additive regret if and only for any sequence of clients Ri..... Ry SV,
T Σ
T CR. (F) (FO+Y +Y Mo(FF
T (F*) + VT
E
a..
min FF
where Fi A(RI,... Ri-1) and a. 3 are constants independent of
An online learning algorithm A selects the positions of the h: facilities at each round /: 2 1 solely based the positions of the clients in the previous rounds, Ri.... Rt-1. If A is a-regret then Definition 3 implies that its time-averaged overall cost (connection + moving cost) is at most a times the time-averaged cost of the optimal static solution! Furthermore, the dependency on vT known to be optimal [1] and B is typically only required to be polynomially bounded by the size of the input, as for + oo the corresponding term in the time-averaged cost vanishes.
As already mentioned, the seminal work of [1 implies the existence of an (1 + r)-regret algorithm for Problem | the only aalymomiallimmelonniin learning algorithm for Problem was due Fotakis et al. (31, for the special case of 0. Specifically, in their work the authors design an online learning algorithm with the following guarantee:
however, this algorithm requires O(n²) time and space complexity. Prior to this work,
Theorem (Fotakis et al. (31). There exists randomized online learning algorithm for Problem 7 that runs in polynomial time (ward. T, n and log DG) such that
T (Ft) O Vlogn DG) VT |F
(Fi)
E
Σ CR
CR.
OOk)
min
Clearly, the algorithm of [3T] has not been designed to account for charging the moving of facilities, as indicated by the absence of the moving cost in the above regret guarantee. The main contribution of this work is to obtain (for the first time) regret guarantees that also account for the moving cost.
Theorem 1. There exists randomized online learning algorithm for Problem D (Algorithm 2 that runs in polynomial time (w.rt. T, n and log Dc) and admits the following regret guarantee:
T
Σ
CR. (Fi) + Σ Mo (F Ft) s Ologn))
min Σ (F |F
for 3 = O(k . 3/22. DG max(y, 1)) and any 7 222 O.
Remark We remark that while our additive regret is larger than the corresponding term in (31 by a factor of ol vi), our results apply to any
7 2 O while the al algorithm of [31] can generally suffer unbounded moving cost for 7 + co, as our experimental results verify.
2.1 HSTs and Metric Embeddings
In this section we provide some preliminary introduction to Hierarchical Separation Trees (HSTs), as they consist key technical tool towards proving Theorem I A weighted tree T(V, E, w) is weighted graph with no cycles. Equivalently, for any pair of vertices i, E V there exists a unique we establish some basic notation for tree graphs
path that connects them. In Definition 4
Definition& 4. Fix any tree T(V, E, w). For every vertex E V, cld(u) C denotes the set children vertices of u and p(u) denotes its unique parent, i.e. u cld(p(u)). The root V T is the unique node with p(r) = Ø and the set L(T) == {u E V cld(u)- = Ø) denotes the leaves T. We use dpt (u) to denote the depth of a vertex u E V, iee the length of the (unique) froffrom the root maxueL(T) dpt(u) to denote the height T. We use lev(u) == h(T) dpi(u) to denote the level of a vertex E V. Finally, T(u) C V denotes the set of vertices on the sub-tree rooted at u, i.e. the set of vertices that are descendants of
r to u, and T(T)
"Specifically, the time-averaged overall cost A approaches this upper bound with rate 3 T-12/2 "Polynomial-tin time with respect to the input parameters, namely I', and log De.

---

Next, we proceed to define family of well-structured tree graphs that constitute one of the primary technical tools used in our analysis.
Definition 5. A Hierarchical Separation Tree (HST) is weighted tree T(V, E, w) such that (i) for any node u and any of its children E eld(u), the edge (u, v) admits weight We 2lev(1), and (ii) the tree is balanced, namely lev(u) = for all leaves u. E L(T)-
In their seminal works, [10] and later [24] showed that HSTs can approximately preserve the distances of any graph G(V, E, w) within some logarithmic level of distortion.
Theorem 2. For any graph G(V, E, w) with [V n and diameter D, there exists a polynomial-time randomized algorithm that given as input G produces an HST TT with height h(T) [log D1 s.t.
1. I(T) = V, meaning that the leaves T correspond to the vertices of G.
2. For any u, E V, do(u, S du(u, v) and EldT (u, < O(logn) da(u, v).
Theorem 2 states that any weighted graph G(V, E, E,w) can be embedded into HST T with (log n) distortion. This means that the distance dc(u, v) between any pair of vertices u, U E V can be approximated by their respective distance dr(u, v) in within an (expected) factor of Ollog n). required have weights
Remark 2. We note that traditionally HSTs neither balanced that are specifically powers of 2. However, we can transform any general HST into our specific definition, and this has been accounted for in the statement of the above theorem. The details deferred to Section B of the Appendix.
3 Overview of our approach
In this section we present the key steps of our approach towards designing the Ollog n -regret online learning algorithm for Problem I
Our approach can be summarized in the following three pillars:
1. In Section we introduce fractional relaxation of Problem in the special case of HSTs (Problem 2). Problem i an artificial problem at which the learner can place a fractional amount of facility to the leaves of an HST so as to fractionally serve the arrived clients. Since the optimal static solution of Problem 2 lower bounds the optimal static solution Problem
[ in the special case HSTs, the first step of our approach is to design an (1))-regret gorithhmmmm for Problem [
2. In Section 3.2
we present the formal guarantees of novel randomized rounding scheme, called Round that is client-oblivious and converts any fractional solution for Prob- lem into an actual placement of & facilities on the leaves of the HST with just an O(1)- overhead in the connection and the moving cost.
3. In Section
we present how the fractional algorithm for Problem 2 together with the Rout& rounding naturally lead to an -rrgrrtt online learning algorithm for Prob- lem in the special case of HSTs (Algorithm l). Our main algorithm, presented in Algo- rithm 2 then consists of running Algorithm into an Ologgn) HST embedding of input graph.
3.3
3.1 A Fractional Relaxation for HSTs
In this section we introduce a fractional relaxation for Problem called Fractional k-Clustering with Moving Costs HST's (Problem D). Fix any HST T(V, E, w) (in this section, V denotes the nodes of the HST). We begin by presenting a fractional extension of placing k facilities on the leaves T.
Definition 6. The set of fractional facility placements FP(T) consists of all vectors y E RVV such that
1. yv E [0,
for all leaves E L(T).
2. wEcld(v)
Σ
for all non-leaves & L(T).
3. EVELITY Vr k, i.e. the total amount of facility on the leaves equals k.
5

---

For leaf vertex V E L(T), Bo simply denotes the fractional amount of facilities that are placed on it. For all non-leaf vertices & L(T), Yo denotes the total amount facility placed the leaves the sub-tree T(v). Thus, any integral vector E FP(T) n N corresponds to placement of & facilities on the leaves of T
In Definitions 7 and 8 we extend the notion of connection and moving cost for fractional facility
placements. In the special case of integral facility placements, Definitions 7 and 8 respectively collapse to Definitions [ and 2 (a formal proof is given in Claims 1 and 2 of Section C of the Appendix).
Definition 7. The fractional connection cost of a set of clients R C L(T) under E FP((T) is
defined as
fR(U) = Σ 21e0(1)+1 -max (0, - yv)
JERVEP(Úr)
where P(j.r) denotes the set of vertices the (unique) path from the leaf j E L(T) to the root r.
Definition 8. The fractional moving cost between any y.y EF((T) is defined as
Bly VITT== :
Σ
21ee(v)
-lVe V'l
DEV(T)
We are now ready to present our fractional generalization of Problem 1 in the special case of HSTs. Problem 2 (Fractional -CCustering with Moving Costs on HSTs). Fix any HST TT At each round t= ,.....T. TT:
1. The learner selects a vector y' FP(T).
2. The adversary selects set of clients Rd (((T).
3. The learner suffers cost fn, (v') + llvl -y-
In Section 4 we develop and present an Oll)-regret algorithm for Problem (see Algorithm 3 To this end, we present its formal regret guarantee established in Theorem 3
Theorem 3. There exists polynomial time online learning algorithm for Problem 2 [Algorithm 3 such that for any sequence Ri,...; Rr _ L(T), its output y ....,.. yT satisfies
T Σ 11 y "
T (R()')) + VT
3
Σ (V)
min
2
y" EFP(T)
1=
for 3 = ( Dy -maxmmaxyy 1)).
3.2 From Fractional to Integral Placements in HSTs
As already mentioned, the basic idea of our approach is to convert each round t the fractional placement y E (T( produced by Algorithm 3 into an integral facility placement F, S L(T) with |F,1 k on the leaves of the HST. In order to guarantee small regret, rounding scheme should preserve both the connection and the moving cost of the fractional solution within constant factors for any possible set of arriving clients. In order to guarantee the latter, rounding scheme Cut&& (Algorithm 4 uses shared randomness across different rounds. Cut&Round is rather complicated and presented in Section 5 To this end, we present its formal guarantee.
Theorem 4. There exists linear-time deterministic algorithm, called Cut& (Algorithm 4 that takes as imput an HST T, a fractional facility placement y E FP(() and a vector a E [0. and outputs placement of ls facilities F t- Cut& RoundR (T, ,y, a.) the leaves Tf (F C L(T) and F k)) such that
1. (nif(()() (CR(F)) = fR(V) (er for all client requests R C L(T).
2. Unii(i(() by MF 4- 11 v/Ilrr for all other fractional facility placements y FP(T) and F + Cut&&Round a)).

---

Item 1 of Theorem 4 establishes that although Cut& is oblivious to the arrived set of clients R2 S L(T), the expected connection cost of the output equals the fractional connection cost under y' E FP(T). Item 2 of Theorem states that once the same random seed is used into two consecutive time steps, then the expected moving cost between the facility-placemeen Fe and F++1 is at most -ttmme the fractional moving cost between y" and y Both properties crucially rely on the structure of the HST and consist one of the main technical contributions of our work.
3.3 Overall Online Learning Algorithm
We now ready formally introduce main algorithm (Algorithm 2 and prove Theorem [ First, we combine the algorithms from Theorems and 4 to design an --1)-regret algorithm for Problem on HSTs (Algorithm[] D]. Up next present how Algorithm T can be converted into an O (log ni regrett online learning algorithm for general graphs, using the metric embedding technique of Theorem 2 resulting to our final algorithm (Algorithm) 2}
Algorithm 1 r-rggett for HSTs.
Algorithm 2 O(log -rereee for graphs.
Input: sequence R....., RT S (T).
Input: A sequence R....., .......:. Rr S L(T). 2: The learner embeds G(V. E, w) into (ran- dom) HST T with L(T) V via the pro- cedure of Theorem 2
2: The learner samples 0g ~ Unif 1) for all v (T).
3: for each round = 1 to T do
4: The learner places the ie facilities to the leaves of the HST 'T based on the output Cut& Round ,T,2",
3: for each round
to do 4: The learner selects facility-
F. =
F. C.
5: The learner learns R² C L(T).
5: The learner learns R3 V.
6: The learner updates y E (P((T by running Algorithm 3 for Problem with input R1, R Rr.
The learner updates Fe41 by giving as in- put RI. for T.
R. S T(T) to Algorithm
7: end for
end for
Theorem 5. For any sequence of client requests Ri.... Rr S L(T), the sequence of facility- placements Fi,..., Fr S L(T) produced by Algorithm satiifies
E
Σ
CR. (F.
Σ MT Fr-1) <6
min Σ (B F
for 3 O Ok- (LT))/2)) Dy max(7, 1)).
Theorem eestablssses that Algorithm T Tachevess constant regret in the special case of HSTs and its proof easily follows by Theorems 3 and Then, the proof of Theorem easily follows by Theorem and Theorem 5
All the proofs are deferred to Section of the Appendix.
4 Olg--Rereet for Fractional HST Clustering
In this section we present the (())-regret algorithm for Problem 2 described in Algorithm 3 and exhibit the key ideas in establishing Theorem 3 Without loss of generality, we can assume that the weeiltty-weight satisfies 7 1
Algorithm is the well-known online learning algorithm Follow the Regularized Leader (FTRL) with specific regularizer R-(() presented in Definition Our results erucially rely on the properties of this regularizer since it takes into account the HST structure and permits us to bound the fractional moving cost of FTTRL
'If' not, establishing our guarantees for will clearly upper bound the actual moving cost.
7

---

Definition 9. Given an HST T, the dilated entropic regularizer (r( over E FP(T) is defined
as
(y/ + 50) In ( yo òv
(T( = Σ 2lev(1)
Yp(() + 5p(o)
eFr
where 6, = (k/n) ((T) [T)) and n = [L(T)
Algorithm FTTR. with dilated entropic regularization
1: Input: An adversarial sequence RI....,RR Rr L
2: for t = 1 to I do
3: The learner selects y E FP(().
4: The learner suffers cost fR, (v') + 11y - y IT.
5: The learner updates y + arg EEP(T)
ER. (rVnT) Rr(w)]
6:
end for
Algorithm selects at each step the facility placement y' E FP(T) that minimizes convex combination of the total fractional connection cost for the sub-sequence , Rr-1 and Ry (y). The regularization term ensures the stability of the output, which will result in bounded fractional moving cost.
Analysis of Algorithm Due space limitations, all proofs moved Section D) of the Appendix. The primary reason for the specific selection the regularizer at Definition 9 is that (-) strongly convex with respect to the norm -|- of Definition 8 as established Lemma which is the main technical contribution of the section. We use D Dr for the diameter of T.
Lemma 1. For any vectors y, E FPTT).
RT(2') 2 RT( + (VRT()). y)) + (8&D~?) 1ly - y/ 1/
The strong convexity of RTy with respect to || ||T is crucial since it permits us to bound the moving cost of Algorithm by its fractional connection cost.
Lemma 2. For any sequence R1,..., Rr C I(T), the output of Algorithm satisfies
1 T 2 [=1
Σ 1=2
(R. O VT +
We remark that using another regularizer R(-) that is strongly convex with respect to another norm II-Il would still imply Lemma] I with respect to ||. The problem though is that the fractiona moving cost E |1 11-1l can longer be associated with the actual moving cost Σ/= MT F.-1). is for this reason that using a regularizer that strongly convex with respect to || 1lT is crucial.
Next, by adapting the standard analysis of FTRL to our specific setting, we derive Lemma establishing that Algorithm addmts bounded connection cost.
Lemma 3. For any sequence R,...., RT S L(T), the output of Algorithm 3 satisfies
T
T
Σ JR. (v)) < min Σ
Ju + kn 3/2 km2 VT
1=1
The proof of Theorem 3 directly follows by Lemma 2 and We conclude the section by presenting how Step 5 of Algorithm can efficiently implemented, namely
$,(1) = Esn, + (WVnT) RT(y). EEFP(T)
min
Since (y) strongly convex and the set FP(T) a polytope, one could use standard optimization algorithms such the ellipsoid method or projected gradient descent to approximately minimize

---

(x(y) given access to sub- gradgrrdient oracle .y(-). In Claim 11 of Section D of the Appendix, we establish that the sub-gradee gradients of (-)) can computed polynomial time and thus any of the previous methods can be used to approximately minimize ( ). In Lemma we establish the intuitive fact that approximately implementing Step 5 does not affect the guarantees of Theorem 3
Lemma 4. Let y be the minimizer ..(.) (.) in FP(T) and let 2' FF((T be any point such that 2x(2*) S (,yy') + eorrr some (O(T-1/3) Then,
fn, (+'))+++1 -2 ---12=2~---11p 11- S fn, (v") 11 y +
+0 (km3/2 .
TT-1/2
Remark our implementation of the algorithm, we approximately solve Step 5 of Algorithm 3 Mirror Descent based the Bregman divergence RT (-). This admits the same convergence rates as projected gradient descent but the projection step can be computed in linear time with respect to the size of the HST T. We present the details of our implementation in Section C of the Appendix.
5 The Round Rounding
In this section we present our novel rounding scheme (Algorithm Cut&&Roud) as well as the main steps that are required in order to establish Theorem[4] To ease notation, for any real number x 2 0 we denote its decimal part (xx) and updates a distribution over the vertices the HST, and can be thus implemented in polynomial-
[=:. We comment that our rounding scheme simply maintains
time. Similar rounding schemes, like the presented in [9]. typically maintain distribution over all possible sesllity-llacemente which generally cannot be implemented in polynomial -ime..
Algorithm Cut&&oound
Algorithm Alloc.
Input: An HST T, a fractional placement yE FP(T) and thresholds a, E 1] for all vee (T).
Input: Numbers Yas Brem 2 0, Yrem and a, E [0, 1].
N
if Y Yrmm == [trem] then
2: Y, t
if 8(Bu) < 3(yrem) then
3: for levels h(T) do
Yu x Ltne]
4: for all nodes u with lev(u) = l do
else
5: Y Yrem Y
Yu + Lynd + 1 Ou S 1-0(yrem)
5(y-))8((mmm) 8(y
6: Vrem + Dv
end if
7:
for all children E cld(v) do
else
8:
Yu +- Alloc(Bu, Yrem Frem ahu)
5(vu) < 88(rrm) then
9:
Yrem +- Yrem Yu
Yu - Ltned +
On S
olya) 31yram)
10: Vrem + Frem Vu
else
end for
Yu + Lyul +1
12: end for
end if
end for
end if
14:
return F := ((T) 11.
Return Y..
On principle, Roudd (Algorithm assigns to each vertex v an integer number of facilities Y, to be placed at the leaves of its sub-tree. Notice that due to sub-routine Alloc (Algorithm 5). Y, either equals [ye] or [yr] + 1. Ruund initially assigns facilities to the set of leaves that descend from the root r, which is precisely L(T). Then, it moves in decreasing level order to decide Y, for each node u. Once Y, is determined (Step 5), the Y, facilities are allocated the sub-trees of its children cld(v) (Steps 7-10) via sub-routine Alloc using the thresholds Qu, in manner that guarantees that Y, Eweeld(o) Yu, (see Section E. 1 of the Appendix). This implies the feasibility of Cut&Round, as exactly facilities are placed in the leaves T at the end the process.
Assuming that the set of thresholds or is randomly drawn from the uniform distribution in [0. 1]. sub-routine Alloc (Algorithm{3) guarantees that Y, either equals yo or [yo] + while Ex, Y.) = Ve- This is formally captured in Lemma 5l and is crucial in the proof of Theorem

---

Lemma 5. Consider Algorithm 4 given as input a vector y FP(T) and random thresholds
0g Unif(0, 1). Then,
Mv yo
with probability 1- 1-5(yb)
Y
+
with probability 8(y+)
By coupling Lemma 5 with the HST structure we are able to establish Theorem 4 technically involved and thus deferred Section of the Appendix.
The proof is
6 Conclusion
In this work, we designed the first polynomial-time online learning algorithm for Online k- E-Clustering with Moving Costs that achieves Oloo n rregret with respect to the cost of the optimal static facility placement, extending the results of Fotakis et al. [I for the special case of y = 0. The comerrsoon is plausible for HST metrics. This
of our approach was to realize and establish that was achieved through designing a dilated entropic regularizer to capture the structure of the HST and combine it with the FTRL algorithm, as well designing lossless (up constant factors) rounding scheme that simultaneously works for both the connection and the moving cost. Both of these components where central towards acquiring constant regret on HSTs.
interesting future direction is to investigate whether polynomial-time online learning algorithm with O(1)-regret for the problem is theoretically possible or not. Since the Ollog na--oct is inherently lost when using HST embeddings, this would require a significantly different approach to the one presented in this work. Finally, comment that our current optimality guarantees with respect to the optimal static facility placement. Going beyond the notion of regret, an intriguing future direction is establishing guarantees with respect the optimal dynamic facility-placene that moves facilities from round to round by suffering the corresponding moving cost.
Acknowledgements
This work supported by the Swiss National Science Foundation (SNSF) under grant number 200021 200021_200011, by Hasler Foundation Program: Hasler Responsible AI (project number 21043) and Innovation project supported by Innosuisse (contract agreement 100.960 IP-ICT).
References
[1] Alekh Agarwal, Daniel J. Hsu, Satyen Kale, John Langford, Lihong Li, and Robert E. Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. International Conference on Machine Learning, 2014.
[2] Nir Ailon. Improved bounds for online learning over the permutahedron and other ranking polytopes. In Proceedings of the 17th International Conference Artificial Intelligence and Statistics, AISTATS 2014, 2014.
[3] Soroush Alamdari and David B. Shmoys. A bicriteria approximation algorithm for the k-center and k-median problems. In Workshop Approximation and Online Algorithms, 2017.
[4] Hlyug-CCaa An, Ashkan Norouzi-Fard, and Ola Svensson. Dynamic facility location via exponential clocks. ACM Trans. Algorithms,, 13(2):21:122::20 2017.
[5] Tarique Anwar, Surya Nepal, Cecile Paris, Jian Yang, Jia Wu, and Quan Z. Sheng. Tracking the evolution of clusters in social media streams. IEEE Transactions on Big Data, pages 1-15, 2022.
[6] Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, and Vinayaka Pandit. Local search heuristic for k-median and facility location problems. In Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, STOC '01, page 21-29. Association for Computing Machinery, 2001.
[7] Baruch Awerbuch and Robert Kleinberg. Online linear optimization and adaptive routing. Comput. Syst. Sci., 2008
10

---

[8] Maria-Florina Balcan and Avrim Blum. Approximation algorithms and online mechanisms for item pricing. In ACM Conference on Electronic Commerce, 2006.
[9] Nikhil Bansal, Niv Buchbinder, Aleksander Madry, and Joseph Naor. A polylogarithmic- competitive algorithm for the k-server problem. In Rafail Ostrovsky, editor, IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA. USA, October 22-25, 2011, pages 267-276. IEEE Computer Society, 2011.
[10] Yair Bartal. Probabilistic approximation of metric spaces and its algorithmic applications. Proceedings of 37th Conference on Foundations of Computer Science, pages 184-193, 1996.
[11] Avrim Blum and Carl Burch. On-line learning and the metrical task system problem. Mach. Learn., 39(1))35-3)) 2000.
[12] Sébastien Bubeck, Michael B. Cohen, Yin Tat Lee, James R. Lee, and Aleksander Madry. k- server via multiscale entropic regularization. In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, Proceedings of the 50th Anmual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 3-16. ACM, 2018.
[13] Moses Charikar and Sudipto Guha. Improved combinatorial algorithms for the facility location and k-median problems. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science, FOCS '99. IEEE Computer Society, 1999.
[14] Moses Charikar, Sudipto Guha, Éva Tardos, and David B. Shmoys. A constant-factor approxima- tion algorithm for the k-median problem (extended abstract). In Proceedings of the Thirty-Firs Annual ACM Symposium on Theory of Computing, STOC '99, page 1-10. Association for Computing Machinery, 1999.
[15] Moses Charikar and Shi Li. dependent Ip-rounding approach for the k-median problem. In Automata, Languages, and Programming 39th International Colloquium, ICALP 2012, volume 7391 of Lecture Notes Computer Science, pages 194 205. Springer, 2012.
[16] Vincent Cohen-Addad, Benjamin Guedj, Varun Kanade, and Guy Rom. Online k-means cluster- ing. In Arindam Banerjee and Kenji Fukumizu, editors, The 24th International Conference on Artificial Intelligence and Statistics, AISTATS 2021, April 13-15, 2021, Virtual Event, volume 130 of Proceedings of Machine Learning Research, pages 1126 1134. PMLR, 2021.
[17] Aaron Cote, Adam Meyerson, and Laura J. Poplawski. Randomized k-server on hierarchical binary trees. In Cynthia Dwork, editor, Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 1 17-20, 2008, pages 227-234. ACM, 2008
[18] Bart de Keijzer and Dominik Wojtezak. Facility reallocation on the line. In Proceedings of the Eventy-Sevently International Joint Conference on Artificial Intelligence, IJCAI 2018, pages 188-194,70 2018
[19] Sina Dehghani, Soheil Ehsani, MohammadTaghi Hajiaghayi, Vahid Liaghat, and Saeed Sed- dighin. Stochastic keserver: How should uber work? In loannis Chatzigiannakiss Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, 44th International Colloquium on Automata, Lan- guages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, volume 80 of 1.Pllss, pages 126:1-126:1 14. Schloss Dagstuhi Leibniz-Zentruum für Informatik, 2017.
[20] Sina Dehghani, Taghi Hajiaghayi. Hamid Mahini, and Saeed Seddighin. Price of competition and dueling games. arXiv preprint arXiv:1605.0400 2016.
[21] Miroslav Dudík, Nika Haghtalab, Haipeng Luo, Robert E. Schapire, Vasilis Syrgkanis, and Jennifer Wortman Vaughan. Oracle-efficient online learning and auction design. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, 2017.
[22] Miroslav Dudík, Daniel J. Hsu, Satyen Kale, Nikos Karampatziakis, John Langford, Lev Reyzin, and Tong Zhang. Efficient optimal learning for contextual bandits. In Proceedings of the Twenty-Seventh Conference Uncertainty in Artificial Intelligence, UAI 2011, 2011.
11

---

[23] David Eisenstat, Claire Mathieu, and Nicolas Schabanel. Facility location in evolving metrics. In Automata, Languages, and Programming 41st International ColloquiunICALP 2014, volume 8573 of Lecture Notes in Computer Science, pages 459-470. Springer, 2014.
[24] Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar. A tight bound on approximating arbitrary metrics by tree metrics, In Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, STOC '03, page 448-48 455, New York, NY, USA, 2003. Association for Computing Machinery.
[25] 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.
[26] Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Optimistic regret minimization for extensive-form games via dilated distance-generating functions. In Neural Information Processing Systems, 2019.
[27] Hendrík Fichtenberger, Silvio Lattanzi, Ashkan Norouzi-Fard, and Ola Svensson. Consistent k-clustering for general metrics. In Dániel Marx, editor, Proceedings of the 2021 ACCM-IAMM Symposium Discrete Algorithms, SODA 2021, Virtual Conference, January 10 13, 2021, pages 1678- SIAM, 2021.
[28] Dimitris Fotakis, Loukas Kavouras, Panagiotis Kostopanagiotis, Philip Lazos, Stratis Skoulakis, and Nikos Zarifis. Reallocating multiple facilities on the line. In Proceedings of the Twenty- Eighth International Joint Conference on Artificial Intelligence, IJCAI 2019, pages 273-279, 2019.
[29] Dimitris Fotakis, Loukas Kavouras. Grigorios Koumoutsos, Stratis Skoulakis, and Manolis Vardas. The online min-sum set cover problem. In Proc. of the 47th International Colloquium on Automala, Languages and Programming. ICALP 2020.
[30] Dimitris Fotakis, Thanasis Lianeas, Georgios Piliouras, and Stratis Skoulakis. Efficient online learning of optimal rankings: Dimensionality reduction via gradient descent. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, 2020.
[31] Dimitris Fotakis, Georgios Piliouras, and Stratis Skoulakis. Efficient online learning for dynamic k-clustering. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 1396-3406. PMLR, 18-24 Jul 2021.
[32] Takahiro Fujita, Kohei Hatano, and Eiji Takimoto. Combinatorial online prediction via metarounding. In 24th International Conference on Algorithmii Learning Theory, ALT 2013, 2013.
[33] Dan Garber. Efficient online linear optimization with approximation algorithms. In Proceedings of the 30th International Conference on Neural Information Processing Systems, NIPS 2017, 2017.
[34] Xiangyu Guo. Janardhan Kulkarni, Shi Li, and Jiayi Xian. Consistent k-median: Simpler, better and robust. In Arindam Banerjee and Kenji Fukumizu, editors, Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 1135-1112 113--113. PMLR, 13-15 Apr 2021.
[35] Elad Hazan. Introduction to online convex optimization. CoRR, abs/1
[36] Elad Hazan, Wei Hu, Yuanzhi Li, and Zhiyuan Li. Online improper learning with an approxi- mation oracle. In Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018
[37] Elad Hazan and Satyen Kale. Online submodular minimization. J. Mach. Learn. Res., 2012.
[38] Flad Hazan, Satyen Kale, and Shai Shalev-Shwartz. Near-optimal algorithms for online matrix prediction. In 25th Annual Conference on Learning Theory, COLT 2012, 2012.
12

---

[39] Elad Hazan and Tomer Koren. The computational power of optimization in online learning. In Proceedings of the 48th Anmual ACM Symposium on Theory of Computing. STOC 2016, 2016.
[40] David Helmbold, Robert Schapire, and M. Long. Predicting nearly as well as the best pruning of decision tree. In Machine Learning, 1997.
[41] David P. Helmbold and Manfred K. Warmuth. Learning permutations with exponential weights. In Proceedings of the 20th Annual Conference on Learning Theory, COLT 2007, 2007.
[42] Nicole Immorlica, Adam Tauman Kalai, Brendan Lucier, Ankur Moitra, Andrew Postlewaite, and Moshe Tennenholtz. Dueling algorithms. In Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, STOC '11, page 215-224, New York, NY, USA, 2011. Association for Computing Machinery.
[43] Kamal Jain, Mohammad Mahdian, and Amin Saberi. A new greedy approach for facility location problems. In John H. Reif, editor, Proceedings on 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montréal, Québec, Canada, pages 731-740. ACM, 2002.
[44] Kamal Jain and Vijay Vazirani. Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and lagrangian relaxation. J. ACM, 48(2):274-296, 2001.
[45] Stefanie Jegelka and Jeff A. Bilmes. Online submodular minimization for combinatorial structures. In Proceedings of the 28th International Conference Machine Learning, ICML 2011, 2011.
[46] Sham Kakade, Adam Tauman Kalai, and Katrina Ligett. Playing games with approximation algorithms. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing, STOC 2007, 2007.
[47] Adam Kalai and Santosh Vempala. Efficient algorithms for online decision problems. J. Comput. Syst. Sci. Springer, 2003.
[48] Wouter M. Koolen, Manfred K. Warmuth, and Jyrki Kivinen. Hedging structured concepts. In the 23rd Conference on Learning Theory, COLT 2010, 2010.
[49] Elias Koutsoupias. The k-server problem. Comput. Sci. Rev, 3(2):105-118, 2009.
[50] Elias Koutsoupias and Christos Papadimitriou. On the k-server conjecture. conjectuc. ACM, 42(5))971-
983, 1995.
[51] Amit Kumar. Constant factor approximation algorithm for the knapsack median problem. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 12,, page 832. Society for Industrial and Applied Mathematics, 2012.
[52] Amit Kumar, Yogish Sabharwal, and Sandeep Sen. Linear-time approximation schemes for clustering problems in any dimensions. J. ACM, 57,2), 2010.
[53] Silvio Lattanzi and Sergei Vassilvitskii. Consistent k-clustering. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, ICML. 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pages 1975-1984. PMLR, 2017.
[54] Shi Li and Ola Svensson. Approximating k-median via pseudo-approximation. SIAM J. Comput., 45(2):530-547, 2016.
[55] Jyh-Han Lin and Jeffrey Scott Vitter. Approximation algorithms for geometric median problems. Information Processing Letters, 44(5):245 249, 1992.
[56] M.E.J. Newman. The structure and function of complex networks. SIAM review, 45(2):167-256 2003.
[57] Romualdo Pastor-Satorras and Alessandro Vespignani. Epidemic Spreading in Scale-Free Networks. Physical Review Letters, 36(14))3200-3203, 2001.
13

---

[58] Holakou Rahmanian and Manfred K. Warmuth. Online dynamic programming. In NIPS, 2017.
[59] Juliette Stehlé, Nicolas Voirin, Alain Barrat, Ciro Cattuto, Lorenzo Isella, Jean-François Pinton, Marco Quaggiotto, Wouter Van den Broeck, Corinne Régis, Bruno Lina, and Philippe Vanhems. High-resolution measurements of face-to-face contact patterns in primary school. PLOS ONE, 6(8), 2011.
[60] Matthew J. Streeter and Daniel Golovin. An online algorithm for maximizing submodular functions. In 22nd Annual Conference on Neural Information Processing Systems, NIPS 2008, 2008.
[61] Daiki Suchiro, Kohei Hatano, Shuji Kijima, Eiji Takimoto, and Kiyohito Nagano. Online prediction under submodular constraints. Algorithmic Learning Theory, ALT 2012, 2012.
[62] Eiji Takimoto and Manfred K. Warmuth. Predicting nearly as well the best pruning of planar decision graph. In Theoretical Computer Science, 2000.
[63] Eiji Takimoto and Manfred K. Warmuth. Path kernels and multiplicative updates. J. Mach. Learn. Res., 2003.
[64] Chayant Tantipathananaddh, Tanya Berger-Wols and David Kempe. A framework for com- munity identification in dynamic social networks. In Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '07, page 717-726. Association for Computing Machinery, 2007.
[65] David Williamson and David B. Shmoys. The Design of Approximation Algorithms. Cam- bridge University Press, USA, 1st edition, 2011.
[66] Shota Yasutake, Kohei Hatano, Shuji Kijima, Eiji Takimoto, and Masayuki Takeda. Online linear optimization over permutations. Proceedings of the 22nd International Conference on Algorithms and Computation, ISAAC 2011, 2011.
[67] Neal E. Young. K-medians, facility location, and the chernoff-wald bound. In Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '00, page 86-95. Society for Industrial and Applied Mathematics, 2000.
14

---

Appendix
A Further Related Work
In this chapter of the appendix, we continue our discussion on the literature that relates to this work.
Efficient Combinatorial Online Learning. There exists long line of research studying efficient online learning algorithms in various combinatorial domains (e.g.. selection of paths. permutations, binary search trees etc.) 40 62, 63 41 7 60, 45 22 42 66
2 20 30 29). Another related line of work studies black-box reductions converting any a-approximation (offline) algorithm to an (ar)-reret online learning algorithm for specific class of combinatorial optimization problems
38 37
called linear optimization problems [47 g 46 61 32 39 [88 21 33 36] We remark that a key difference of our setting with the aforementioned works is that in the latter case the learner is not penalized for switching actions from round to round with an additional moving/switching cost. In the context of Problem [ this means that y = 0 which is exactly the setting considered by [I]. As a result, apart from the fact that k-median does not belong in the class of linear optimization problems, the aforementioned black-bo, reductions do not apply to Problem T since they do not account for the moving cost.
The k-server Problem.
Our work also relates with the rich line of literature on the k-server problem 19 12]. In this setting there exists only 1 client at each round, while 1-lookahead assumed, i.e. the request Rd is revealed prior to the action of the algorithm at step Moreover in k-server a facility must be placed in the exact position of the request, leading to a simpler combinatorial structure with respect to Problem using the benchmark of regret, the more challenging metric of competitive ratio that measures the sub-optimality with respect to the optimal dynamic solution is used. Mostly related ours is the work of [9] providing the first poly (log r1) -ncomptttee algorithm for k-server by reducing the problem to the special case of HSTs. [9] first design poly n) -competitive algorithm for a fractional version of k-server at which facilities can be fractionally placed into the vertices of the HST. They then use a randomized rounding scheme to convert the fractional solution into an integral one. The basic difference of the randomized rounding scheme of [9] with the one that we introduce in this work (Algorithm Round) that the first provides guarantees only for the moving cost of the facilities while Cut&Round provides guarantees both for the moving cost of the facilities as well as the connection cost of the clients.
550
17
49
9
However, in the k-server problem, instead of
Consistent k-Clustering, Another setting of clustering in the presence of unknown clients is that of Consistent k- k-Clustering [53] 34 27.. In this setting, given an unknown stream of clients, a set of k facilities has to be maintained over time so that at any round t, the selected facilities form an approximately optimal solution of the sub-instance consisting of clients appeared in the time interval {1, A basic difference of Consistent k- k-Clustering with Problem [ is that in the first case the moving cost is not penalized as long as the number of swaps does not exceed a certain threshold (k)).
'Given offline access the sequence of requests, the optimal solution for the k-server can computed in polynomial-timg time while the optimal static solution of Problem cannot be approximated in polynomial-time -immee with ratio less than (1 + 2/e) even under a-priori knowledge of the request sequence (inapproximability of k-median).
15

---

B Proof of Theorem 2
In this chapter of the appendix we briefly discuss the details behind Theorem X and show how the results of 10 and [24] hold even for the specific definition of HSTs we have considered in
Definition 5
Traditionally, HSTs are not required to be balanced nor are required to have weights that are specifically powers of 2. In fact, the seminal work of [10), later improved by [24], states that there exists a randomized procedure such that for every weighted graph G(V, E, w), it constructs (in polynomial-time) tree T such that:
1. There exists a perfect matching ø V L(T) that maps the vertices of G to the leaves of T.
2. For any vertices i,j V, their corresponding distance on T can only increase, i.e.
da j) S dr(o(i),
3. On expectation, distances between vertices are distorted only by a logarithmic factor, i.e. E (ot)) (j))) I (log [V]) da(i.j)
4. The weight of any edge (v, u) between a vertex e E (TT) and its parent vertex is precisely diam(G)) 2-dpt(v),
5. The height of? T satisfies 1(T) S [log (diam(G))]-
The purpose of this section is argue that one can easily transform such tree 'T to match notion of HSTs (Definition 5 while maintaining the same guarantees for the distortion of the distances. Recall that we have already assumed that the minimum edge weight of G Furthermore, we can also assume without loss of generality that the diameter of G is power of 2: if not, simple scaling arguments suffice to transform G into such graph by only distorting distances by a constant factor. Thus, we assume that diam GG) 2d for some d 2 O.
i.e. minee E W.
We start from the tree T that the algorithm of [24] generates. Recall that by definition, the weight of edge (i.j) between some vertex and its parent node j is 2d-dpt(1), In order to balance the tree, we take each leaf vertex u E L(T) at depth dpt(u) and extend it downwards by adding new vertices until it reaches new depth dpt' (u) = d. For every new edge that we add during this process, we maintain that the weight of the edge
(i, from i to its parent j is diam(() 2-dpe(t)
Let T' be used to denote our modified tree. Clearly. the above construction guarantees h(T') Since by definition h(T) S [log (diam(()) (G)) d. we know that all leaves initially lied at depth at most d, and thus by the end of the above process all leaves will lie the same level of the tree and have depth d. Thus, we have indeed constructed a balanced tree. Furthermore, since by definition dpt(e) = (T() lev(w)) we get that the weight of the edge = (i, from i to its parent j is w. diam(G) 21e0(1)- -d) 2lea((), So, the constructed tree indeed satisfies all the requirements of Definition and is valid HST (according to our definition).
We will now argue that T' also satisfies all items of Theorem Fist of all, the height of our tree is precisely d, and thus it is true that h(TT) < [log (diam(G)) Furthermore, since we only added edges to the initial tree T, the distance between any two leaves can only increase. Thus, we get that for any vertices j E V it holds
da(l. & dr(1.)) S (1.j)
Finally, it remains upper bound the expected distortion on T'. Recall that by construction of 24 we know that
E (o(), I Ollog Vi) do(i,j)
Since edge lengths decrease by factor of 2 every time move down the tree, we know that the total length of the path we added in order to move leaf from depth di) to depth d is precisely
1 + 2 + ... 21 < 2dpe(s), This implies that any distance on T can be at most twice the corresponding distance T. i.c.
(T((0(), < (
which completes the proof.
16

---

C Proofs of Section 3
In this chapter of the appendix we present all the omitted proofs from Section concerning the basic algorithmic primitives we use in order to establish our main result in Theorem
Roadmap. section C.1 we establish the connection between Problems and and show that
our notion of fractional connection and moving cost collapses with our initial definitioss in the case of integral facility placements. Then, in section C.2
we present the proof of Theorem [ and in
section C.3
we present the proof of Theorem
C.1
Establishing the relation between Problems and 2
Fix any HST T and let (T) be the corresponding of fractional facility placements. In this section, we will establish that in the case of integral facility placements E FP((T) IN, the notions of fractional connection cost and fractional moving cost (formally stated in Definitions 7 and g collapse to the notions of actual connection and moving costs (formally stated in Definitions and respectively.
Let y E FP(T) N be an integral facility placement. Then, by definition, for each leaf v L(7) have Ve E {0. 1} facilities that are placed it, and the total amount of placed facilities is k; i.e. EVEL(T) Ve = k. Thus, we can associate with any integral facility placement a corresponding set
Fly) {o L(T): yo =
such that [(v) k, meaning that F(y) is valid facility placement of the leaves of the T.
In Claim we will establish that for any set of clients, the connection cost under F(y) is equal to the fractional connection cost under y. Then, in Claim 2
we will establish that the fractional moving cost between y and y gives us precisely the moving cost between facility placements Fly) and F T.
Claim 1. For any integral facility placement y FP((T N and any set of clients R L(T), holds that
fn(y) =Cn(F(y))
Proof. Fix any FP(() n N and any R C L(T. By definition of the connection cost (Defini- tion D. we have
CR(F) = E
min dr(i,) (eF())
JER
Let's fix a particular client that lies on some leaf j L(T) of Let 1 arg min dr (i. be the leaf closest to j that F(y) places a facility into. Since T an HST and distances increase by factor of 2 as move up the tree, it is not hard to see that i is the leaf in F(y) whose lowest common ancestor (Ica) with has the smallest level. Let 1* lea(j, i*). Equivalently, 1" is the minimum-level vertex in P(j.r) such that yr- > 1. Since T is balanced, we have that the connection cost of client j under Fly) is precisely
lev((")
(F)(F())) = -2,77 2.
Σ
2
1=0
and since by integrality have that yo for any E P(j, {1' and yo 1 for all
v E P([", rr), we have
(F) =
Σ
2lev(e) max(0, 1 yo)
rEP(j.)
Summing over all clients j E R we get
CR(F(W)) Σ Σ
2lev(1)-1 max(0, 1 yo) fR())
JERvEP(jrr)
which concludes the proof.
17

---

Claim 2. For any integral facility placements v. E FP((T) n N. it holds that
- 1 - F(y')
Proof. Fix any two integral facility placements y, v/ E FP(T) N. By definition of the moving cost (Definition 2), we have that
Mr(F()),F(()) min
Σ dr((,a(i))
iEF(M)
where E is the set of all possible matchings from the facilities in F(y) to the facilities in F(y)).
In general graphs, the minimum transportation cost can have a very complicated structure and typically requires solving minimum transportation problem in order to compute it. However, in the special case of HSTs, we are actually able to obtain a very simple expression for this quantity.
Recall that in an HST T, edge weights increase by factor of 2 every time we move up level on the tree. Thus, it is always in out interest to move facilities between leaves whose lowest common ancestor is as low as possible. In other words, the matching a that minimizes the transportation cost from F(y) to Fly)) can be obtained by selecting an arbitrary leaf Fly), matching the leaf in F(y') with which it shares the lowest lowest common ancestor and then repeating the process for the rest of the leaves.
Now fix any vertex E ((T). Recall that yo is equal to the number of facilities in F(y) that are placed in the descendant leaves of (respectively for v/). Thus, if we apply the above (optimal) transportation plan, the number of facilities that will end up traversing the edge from to its parent
vertex is going to be precisely lye - 3/ll- Since the weight of this edge is by definition 21ev(v), we get that
MT (F((), F(y')) = Σ
glev(e)
11/. v'l
VEV(T)
and since
1ly 1111= Σ
2lev(e) 1l0 - Vol
VEV(T)
we have proven the claim.
L
C.2 Proof of Theorem
We will now formally present the proof of Theorem 5 bounding the expected total cost of Algorithm Fix any sequence of clients R2,..., Rr. Since the random seed a is selected uniformly at random (Step 3 of Algorithm|] I). by Item 1 of Theorem 4 we get that
[CR, (F)) fR. (v')
Moreover since the same random seed is used at all rounds L. 2 1, Item 2 of Theorem 4 implies that y E [MT F.)] S 4 1ly r+1
y'llr
Thus.
T Cn.
T
T fn, + Σ lly' y² y'-1
T
E
Σ
+7
Σ
My Mf Fr-1)
54.
1=2
1=2
< min
fR. (v' + VT
8* EFP
t=1
where the last inequality follows by Theorem 3 for = O (k: |L(T) 3/2 Dr max(y,1)). The proof is concluded by the fact that
T
min EPP
Σ
fn. (v))
Σ (F") |P
min
t=1
which is established in Claim 1 of Appendix F C T.(T) there exists a corresponding y E FP(T) under any client request.
stating that for any placement of k-facilities
whose fractional connection cost is equal to F's
18

---

C.3 Proof of Theorem 1
We will now formally present the proof of Theorem bounding the regret Algorithm 2
Let T be the HST that we randomly embed our graph G(V, E, w) into. Since V = L(T), we slightly abuse notation and use to refer both to some vertex of G and to the corresponding leaf of T. From we know that the output of Algorithm| satisfies
Theorem
T
T +Y Σ
E
Ch. (F)) (F)
My (F.
<6
min
Ch (F*)
k- [L( 3/2 Dy max(1,7)) vT
where we use T in the connection and moving cost to indicate that all distances are measured on the HST. Here, the expectation is taken over the random choices of Algorithm [
Next, notice that both the connection cost and the moving cost are defined sum of distances. Thus, the results of Theorem 2 about the distance distortion from G to T clearly apply for these quantities as well, namely
Ch. (F.) & Ch, (F)) and [O%, (FA) - O(log C%
and
Mc(Fi,F-1)) S (F, and E [MT K-1)) Ollo [V]) Mc(Fi,Fi-
Thus, taking an expectation over the randomness of TT, we finally get that
E
Σ -=1
ch (Fi)
+ Σ
Mc(Fi, Fr-1) s Olog [V])
GG (F*) min Σ | t=1
1=
+0 (R [L(T) 3/2 Dy max(1.1)) VT
Let n = VV and D = diami(). From the above, we get that Algorithm 2 is indeed a-regret for = O (log m). Furthermore, we have that [L(T) [V] and Dy = 2 (2h(T) 1) < 4D
since h(T)) < [log D1. Thus, setting 3 = O nn D max(1, 7)), we get that Algorithm 2 has 3-additive regret, completing the proof of Theorem D
19

---

D Analysis of FTRL (Proofs of Section 4
In this chapter of the appendix present all the omitted proofs from Section concerning analysis of the Follow the Regularized Leader (FTRL) algorithm (Algorithm B). To avoid repetition, from now on fix an arbitrary HST T and use FP(T) to denote the of all fractional placements of & facilities on the leaves of T. We use = |L(T) to denote the number of leaves of T, h(T) denote its height and D diam (T) to denote its diameter. Since T is HST, we know that its diameter D, i.. the maximum distance between any two leaves, is precisely D 2 (2 1).
To ease notation, let 21ev(1), For convenience, we remind the reader that our regularizer function Ry FP(T) + defined as
Yo + 5p By(y) = ΣEs, wi - (yo + 0o) Up(e) + 5p(r)
wpre
where 6, k [L(T) (()) is the percentage of leaves that lie on the sub-tree rooted vertex v multiplied by k and p(v) is the parent of node v. Also, recall that for any FP(T) we have defined the norm
l = VEV(T)
wolyel
Roadmap. In Section D.I we prove Lemma] I namely the strong convexity of Ry with respect
to I|.. Then, in Section D.2 we bound the moving cost FTRL, proving Lemma] 2 Next, in
Section D.3 we bound the connection cost cost of FTTL, proving Lemma 3 Finally, in Section D.4 we account for approximation errors in the computation of the regularized leader, proving Lemma
D.1 Strong Convexity (Proof of Lemma] 1
The objective of this section is to prove Lemma] ! specifically that for any fractional facility place- ments y, 3/ E FP(T) holds that
RT (1)) 2 RT(y) + (VRT(v), - y) + +olly - y/ 7
where a = (8+D~3)-1.
We begin by computing the gradient of Ry any fractional facility placement y E FP(T).
Claim 3. The partial derivatives of Rt on any point y E FP(T) are given by
We
for t =
2
0R (v)
Wy In
Bp(n) +óp(n)
4o
+ Wr
for v E L(T)
Oy.
Wh In
to
for & L(T)(((U)))
Opte) tete))(pppp)
Proof. Clearly, Ry is well-defined and differentiable FP(T). For any v + compute the partial derivatives (y) to obtain
(R) Oy wy In
Bu + 8, Up(()) + )p(())
ya + 8n Wa
+ ww
Do + 8n
wEeld(u)
Since E FP(T), we know = -Evedd(v)) Vn and by definition, 6, = Ewecid(o) dn. Finally, recall that W., w./2 for any u E cld(v). By plugging everything in get
@R w. In
ye 5 Mp(w) 5p(n)
w. 1/v L(T)
dy.
for any # For the root vertex, using similar arguments we get
dRT
Wr
Oy
20

---

Now that we have calculated the gradient of Ry, we can substitute it into the definition of strong convexity. Specifically, by Claim Lemma states that
v.
Σ wp (3/ + 0.) viger
Veccs +Op(n)
SkD 11 - 2113
(I)
Mp(c)) t.pp())
To ease the presentation, we define quantities
f(8/
Σ 7
wa (16 + 0.) In
Uo 4-
(o(x))
and
Myy 1)
Σ Efr
wr (Up(e) + Ep(u)) .1 1 Vo 8u
Yo + 5y
Vo(1) + +pp() Vp(e) + 5p(u)
We will prove that fly' v) 2 (ORk))>?(y' 3) and that h(y' .) 2 (1/2 yllT in Claims 4 and 5 respectively. Combining these claims, equation (T) clearly holds, completing the proof of Lemma
Claim 4, For any v.y/ FP((), it holds that f(y v) 2 2nD (h(v/, v))²
1
Proof.
We begin by establishing some notation. For any + let
v. + 8, Vm(n) + Sp(r)
1/. = wa (Bp(o) + +p(o))
and
Yo + 8, Mpp()) + Ep(e)
Bv = w. (Bp(c) + op(r))
Then, have that
Hg
/(0',9) = Σ n/
In
Mix
vsr
Σ p/g
In
Ml
Σ Myy
In
My
where = {u * : n4, 2 m and l' tu r plo both of these terms, we obtain
p. By applying the log-sum inequality in
EvErtH He Emer Ho
Ever H/ Hoo
((V'v))
Σ (k)) In
+ ( (4)) In
Ener
NEl'
Next, observe that
Σn.
1/
Σ
w. (v/ 80) 22k (2h 1) k
vste
and also
Ye + 6 3p(1) + 5p(r)
Σ
Mv
Σ v
Wp
(Up(c) +ppo))
v
Σ
Wp
(v/ + +w))
U/ + dn De + 6,
2
(TL(T)
mEnld(())
Σ
Wy
(3/ + 8.)
2
VEL(T)
2 .2k (2 - 2)
k D.
21

---

Let B' = -vel My and B = EvEr Me. Then, we have shown that
B'
kD B' + (kD - B3)-In -Im
f(y' .) B' In
-B)
(2)
B
kD B
Our next step apply Pinsker's inequality the above expression. Pinsker's inequality states that for any p2q E (0, 1), it holds that
p. In ( + +(1 p) in 2 2. (p- (p- 9)²
Since B S kD and B' S kD, we can scale everything in inequality S and apply Pinsker's inequality obtain
fll 2 kD (B B²)²
(3)
To complete the proof, we substitute
B'
B =
Σ
(14
vEl
Vo + 5,
Vv. + 8z
Σ VEI
Wp (Wb(w) + (p(())
(
Up(o) Sp(v)
Vr(1) 6pv))
Σ
We
(y's + +60) Σ
Va + 8n
U/ 8
2
Vo 8,
Ve 8g
vEL(T)
u
Wy
(v', + 8.)
Σ
V/ + 8n
Ya + 8n
2
V 8,
Yo 8
MEL(T)
(Ecld(u))
where the last equality follows from the fact that the ratio in the inner sum always sum to 1, and thus by only summing over the ones with positive difference we get half of the total sum of absolute differences. By swapping the summation order once again, we get
1 Σ We (pr(o) + 5p(w)) . V. + 8.
+ 80 Up(c) 5p(c) Up(c) + 6p(x)
B'-B B
2 hyy .1)
and from inequality (3) we finally get
f(g'.9) 2 2kD
(h(y/.))
as desired.
Claim 5. For any v. FP(T), it holds that [|y' -yll 27 1))/
Proof. To prove the claim, we first need to establish some extra notation. For any E FP((T) and # let
+ &
X- (v)
Bp(r) + 6p(m)
Furthermore, for any vertex and any integer E [0. h - lev())), we use p(u, i) to denote the i-th ancestor of T, for example p(u, 0) v, p(v, 1) p(u) and h-v,h-leu(e
Recall that by definition, y, = 8, k. Thus, if we telescope these terms and let m, = lev(v) - we clearly have that
yo + 6, = 2k 11 Ap (v)
22

---

which implies
V/ yo 2k:
T p(u.)) (v')
2k
2 p(,,00)))
2k:
Ap(r,0)
(pp(,,((0') Apcc,o Ap(r.m)) (v)
i=0
V + 60
(Ppt - (p)),))()) Fp(u.+1) + 8p(v.4+11
2k
Up(u.s)
+ Op(v.))
2k
1=0
Up(u,++1 Sp(u.t11. (Ap(..) - (p)).)(1))
-1/ + 0v)
Vp(O,N) + Sp(u.s)
1=0
and from the triangular inequality
Up(u.i+1) + Sp(e,t1)) my
V/ Vol S (v/ + 6,)
Pp(o,)) (p()))(()
(4)
Up(u.)) Sp(m,))
Plugging inequality (4) into the definition of norm || 11T, we get
ll u|lT Sr.
Σ wo
(1/e + 8,))
mh
Mp(v,e+1) + Op(u.it))
(Ape,,)())) Apcess(uil
Vp(o,) + (p(u.)
and by carefully exchanging the summation order, we obtain
Yp(u) + Sp(o),
11 - ST.
Σ 1ef
(2,(0') - An(1))
wu(K + 6w,
36 + 6
(ET(()
Finally, observe that EvET(H) Withh S 2w.2/. To see this, fix the sub-tree T(v) rooted at vertex v and recall that since y' E FF((), the total amount of facilities at each level v/-- Furthermore, the weights wa decrease by factor of at every level. Using the same arguments, we obtain EmeT(U) wnou+ S 2w,d.. Combining everything, we finally get
II - ullT s 2n Σ we (Un(r) + ((())) 120()') Av(e)l
equivalently, 11 - y s 2n hv)(.v).
D.2 Bounding the Moving Cost (Proof of Lemma
In this section will upper bound the moving of FTRL by its connection cost. Fix any sequence of client requests R₁ R2...., ,..,, Ry C LT). Recall that at each step t, FTRL selects
fractional facility placement y¹ given by
y
arg min Px(y)
PEFP(T)
where (x(1) = Di= Sn, (v) + Ry( is the objective that FTRL minimizes over at step for 7 (y VnTT)- In this section, we prove Lemma 2 by arguing that
Elle' - -' -
1 Σ (n((v')
7 .T
2a
since the proof follows easily by the definitions of n and a.
From Lemma we already know that Ry is a-strongly convex with respect to || l|T for (8k: (8)D)2))- Furthermore, by definition the fractional connection cost
fR(U) Σ Σ
2lcu(1)+1 max (0, - -v))
JER PEP(
23

---

is clearly convex for any client request R S L(T). Thus, it is straight-forwart to argue that at any step the FTRL objective P, 2 -tronggy convex with respect to || 117 Unfortunately, fn(y) is not differentiable on FP(T), but its sub-gradients are well-defined on any E FP(T). Thus, the strong convexity of 4, provides with the following guarantee:
Claim 6. Fix any pair of fructional facility placements y, y' FT((T and any time step E (T].
Let E (3) be any sub- wub-gradient of 4, y. Then, it holds that
De(y') 2 (x( + (gr, V/ y)
a 1l 20-y11 1
77
Furthermore, since by definition y' is the (unique) minimizer of dr, the first order optimality conditions on Dt imply that there exists some oi E @0,(y") such that (9). - v²) 2 0 for any y E FP(T). Claim for y y', y'. = y²= and gi g gives us
2. (14) + -h --1l'' 110''
Thus, we have
11 y²
117
"
(v 1-1 (y- +,(2'))
7 @ (1) 1 + SR. 1 - SR. (v'))
" (Jn. (3'-1) -R. (21))
where for the equality we used the fact that (y = -. (1) fR. (v) and for the second inequality used the fact that y-- is by definition the minimizer of o; - Finally, since fa(y) for any client request R S LT)), we have
11 - 1
11T
S Va (y
7
2 fn (y-11
where the last inequality follows from the Arithmetic Mean Geometric Mean inequality. Summing over completes the proof of Lemma 2
D.3 Bounding the Connection Cost (Proof of Lemma 3
In this section we will upper bound the connection cost of FTRL by the connection cost of the optimal fractional facility placement in hindsight. This is standard analysis found in many textbooks, and we present just for the sake of completeness.
Fix any sequence of client requests R1, R2,..., Rr S L(T). Recall that at each step t, FTRI selects fractional facility placement y given by
y' arg (2()) BEPP(T)
where (v) Ei=l Sn, (v)+ (V( is the objective that FTRL minimizes over step for 77 (y VnTT) Let yn be the optimal facility placement in hindsight, i.c.
y" arg min vEFP(T)
Σ fn. (v)
In this section we prove Lemma by arguing that
T
s (x) KnD
+ 32kn Dn T
and then the proof follows easily by definition of 17-
In the standard analysis of FTRL, the following quantities are of special interest as they appear in the final regret guarantees of the algorithm:
24

---

Let diam((y) == EFF(T) [R) - RR(y')l be the diameter of the regularizer.
Let Gy be an upper bound on the dual norm of the sub-gradient of the fractional connection cost for any client request, i.e. for any R C L(T) and any y FF((), there exists some sub-gradient E Ö5n(y) such that | I Gy- Here, || || denotes the dual norm of ||
We begin by presenting the standard analysis of FTRL and deriving an expression for the regret guarantee that depends on the above quantities. Recall that any step the FTRL objective o doesn't tt include fn, since the client request Rg is not revealed to the algorithm at the time of decision. We begin by bounding the connection cost of a theoretical algorithm that has access this information and thus at time can pick facility placement y'+!.
Claim 7, The output of FTRL satisfies
T
T
Jn (v') + diam(R, R
Σ t=1
Jn, (1*
S Σ t=1
Proof. We have
0e(3') p 1 fR. (s")
21-1 ) + fRI (3²)
where the equality holds by definition of D, and the inequality holds from the optimality of y on - Similarly, we obtain
1 2 2::201-200 Φ1-2(1'~ + f
we keep applying this rule, we finally get that
2e(x²) 2 Σ fR. (1+ 11
Furthermore, we have d1 (1()) = RT(11)/n and 2,())) 2 (b') for all Thus, get
T (+++(1") fm. RT((")) (R(())
or equivalently (by substituting DT+13 's definition) we have
Σ fn. S In( RT(x") (T(22)
T
The claim follows from definition of diam(RT).
Next, proceed by bounding the increase in the connection cost that we suffer by choosing y instead of y at time
Claim 8. For any t 0, it holds that JR. (21') + n/23/a
Proof. For any client request R S L(T), the fractional connection cost function fn(y) clearly convex and its sub-gradee gradients are well-defined on FP(T). By definition of Gy. we know that there
exists some sub-gradient, g E Öfn, (v²) such that I|al|; S Gy. Using this sub-gradient, we get
fn, (v²) < fu, (v + (g.V' - -1
s (1 + +111/177 1lvl l (v (1) + Gy l1le - 11+
25

---

where the first inequality is derived from the convexity of the fractional connection cost, the second inequality is an application Holder's inequality and the third inequality is from Gj definition.
As we have already argued in section D.2 we know that for any step i, the FTRL objective & is a/tn-sronggl convex with respect to T. Using the definition of strong convexity, this implies that
2++1(1)) 2 24+1 + (g.8 - - + -
y + 117
for any sub-gradient E 1 (y () Furthermore, since y is the minimizer of L know from the first order optimality conditions that we can select g E 00 (y++)) such that (g. - y 2 0 for any y E FP(T). Using such a sub-gradient, we get
11 11 !
(fe+1(y") Pet1(x(+))
a
2 (De(y") (R. 11( - FR. (y
a
S (fn.(v") -nn (vtt)))
"
a
where we just expanded P 's definition and used the fact that y is the minimizer of +,. Combining everything, we finally obtain
- fR, (1) S &Gy -
n (fR, - SR. (2)+1))
and the claim follows.
We complete the analysis of FTRL by combining Claims and in order to obtain the following regret guarantce:
Claim 9. The output of FTRL satisfies
T Σ 1=1
Σ Jn. (v*) diam (Rr) + a
n T
(R) S
remains to substitute the specific values of the parameters that appear in the regret guarantee. We have already proven in section D.I that Ry a-strongly convex with respect to || ||7 for a = (8kD>3)-1 Next, we provide an upper bound for the diameter the regularizer.
Claim 10. holds that diam RRy) I knD.
Proof. Fix any E FP(T). Be definition, we know that yo I Up(w) and 6, I 6p(o)) for any + r. Thus, the expressions inside the logarithms of the regularizer always at most 1, which implies that Ri (y) < O. Furthermore, for any a, B >> 0 it holds that a - 3 < a In (a/3). Using this inequality, get that
RT(y) 2 Σ We (yo + 8, Up(v) - 8p(o)
u
Fix any level E [0, h 1] and let Vn FP(T), we know that Evev, yo = k. and by definition of 8's we know
f V(T) f
lev(v) O} denote the set of vertices of the
HST at level I. Since that Erev, 5,, = lo as well. Furthermore, we know that Evev, 3p(n) S n Enevi Bo = n k since any vertex can have at most (i.c. the total number of leaves) children. Using the same argument,
26

---

we have ΣvEni (p(r) n. EveVi V/+ = k. Thus, combining everything we obtain
RT(y) 2
Σ epp
Wy (yo + bo - Alp()) 6p(w))
2' (yo + 8y -ppi)) 6p(v))
DEVi
h-1
2 2 -2k - 2km)
1=0
21:(1 (2
= k(1 D.
which proves our claim.
Finally, we only need to find an upper bound for Gj. We begin by computing a set of sub bub-gradients for the fractional connection cost function.
Claim 11. Fix any client request R S L(T) and any E FP(T), Define the vector g R.y E R(V(T)) such that
yo 2 yo
R.y
9v:
-1e00())+1. (T() R
Then, g.. E dfuly), i.e. RB is a sub-gradient of fn on point y.
Proof. Fix any client request R C L(T). By definition of the fractional connection cost on facility
placement y E FP(T), we have
fR(U) Σ JER P(P
21cv(1)+1 max (0, yv)
where P(j," r) denotes the unique path from leaf L(T) to the root This is clearly convex function on FP(T) and thus the sub-gradients of fn are well-defined. Fix any V(T). We distinguish between two cases.
If < 1. then the partial derivative of fR(Y) is well-defined and given by
Qfu(y) = (1)=(())+ (T()) R
Oy.
where T(v) is the set of vertices on the sub-tree rooted at vertex v.
If yo 2 1, then clearly it doesn't contribute to fn(y)- Using standard calculus, is not hard to argue that in this case there exists sub-gradient of fn(y) whose coordinate corresponding to v is O. Thus, we have argued that that ".y is a valid sub-gradient of fR on point y.
Finally, we provide an upper bound on the dual-norm of the sub-gradients that we computed on Claim [I]
Claim 12. For any y E FP(T) and any R S L(T), it holds that R. < 2n
Proof.
Recall that have defined the moving cost norm
l y
Σ
Wy yv
VEV(T)
27

---

which is basically a weighted fi-norm with weights y Wp. It is well-known that the dual of the -norm is the Lo norm. Similarly, the dual of the weighted I nnorm weighted to norm with inverse weights, i.e. -I" 1o ()) Thus, we have
I
|
max
Wh
Using the calculation of the sub- sub-gradients from Claim and that R S L(T) and thus [R] S n. we immediately get the claim.
Claim 10 provides us with an expression for diam(Ry) and Claim 12 provides us with an expression for G Plugging everything in into Claim we complete the proof of Lemma
D.4
Incorporating approximation errors (Proof of Lemma
Fix any sequence of client requests R1, R2...... Rr S L(T). Recall that at each step FTRL selects fractional facility placement y' given by
arg min (.(y) sEFP(T)
where (v) = Σ JR. (v) + 1. (y) is the objective that FTRL minimizes over step for 77 (y- VnT)--
Now, assume that instead of minimizing P.(y) over FP(T) to compute y', we are only able to compute a fractional facility placement 2f FP(T) such that (2 S 2, + for some >> 0.
Claim 13. For any step t, it holds that
1 - v'I
/
Proof. As we have already argued in section 4 is a/ns-ttooggly convex with respect to condition for b on lt. we get
D.2
we know that for any step t, the FTRL objective Combining this with the first order optimality
2x(2') 2 2,('') + 1| -'
which implies that
1| - 1'1lT v c.a 7
Using Claim FTRL solutions.
easily bound both the connection and the moving cost of the approximated
For the connection cost, recall that the fractional connection cost function fn, at step convex, which implies that
fR, (2') (R. (g.
for some E 05R, (z*). Using Holder's inequality to upper bound the inner-product and using the upper bound of Claim for the dual norm of the sub- gradients of fR. we get that
(2') S fn. (v²) +
|| llT
and finally from Claim 13 we get that
(2') < fR. (v")
2n
?
7
28

---

For the moving cost, recall it suffices to use the triangular inequality that || - I|r (as norm) satisfies:
1| - x² 117 I 11 - y ||T + 11 of 1 + 110001111 2 11T
l1y "17 2 Vc
The proof of Lemma follows easily by plugging n (7 VVT)-1, (8kD)2)-1 and c= O(1VT)
D.5 Implementation of Projected Mirror Descent
We conclude this section by considering the Projected Mirror Descent update step, namely
1/ arg min [n (c, + DD (3" ,y]
y" EFP(T)
that takes as input fractional facility placement that minimizes a linear cost under vector plus the Bregman Divergence between the initial and the new point under regularizer Ry. Here, 7/ 0 is tuning parameter that balances the dynamics between the linear cost and the Bregman Divergence.
FP((T and returns some other y' FP(T)
By letting be the sub gradient of the fractional connection cost over the observed sequence of clients, we can use this update step in order to approximate the FTRL objective; this is, in fact, the implementation we did for experimental evaluation of Algorithm In this section we will argue that the special structure of Ry allows us to compute the update step in linear (to the size of the HST) time.
By definition of the Bregman Divergence, we have DRy (z. v) = Rr(x) Rr(y) - (VRT(V), x-1)) y)
Substituting everything, we get that the update step of Projected Mirror Descent can be written as
y = arg min Fly") y EFP(T)
for
Vr + 8.
F(y") 17 ' co 32 +
Σ Nyt
We (1 + 8v) in
Fp(v) + 6p(w))
U/ + 8n
Σ Wer (No + 55) In
Up(u)) +p((i)
Σ
W. In
Do +
+ We + Wr
1l E L(T)) (ut yo)
Up(()) + 8p(o)
2
ufr
Wr
(y/
yr)
It is always the case that update y/ from some y FP(T), can simplify the above expression to get
+
F(y") = Σ 3o
Σ
W.
(v, + 5,) In
Mocws topen) to
Mo(v) +02(0)
Σ
Wp
(1 + 1ly E L(T))) (V6 - yo)
2
29

---

Recall that by definition, FP(T) is the polytope
Yv Enecld(s) Uu u L(T)
FP(T)
y E RVTI
Vo 00 Dr = K
I(T)
Since our objective is to minimize function F(-) over FP(T), we can write down the KKT optimality conditions to obtain the following conditions about the minimizer y":
M 6, y ()()) 8p(e) Up(c) + 8p(c)
Do + 6,
[ wp
exp
1o0 - v/cw)
where My is the Lagrange multiplier for constraint ye Euseld(e) Yu and juu for E L(T). To complete our computation y", remains to compute the Lagrange multipliers μ..
Since y" E EFP(T). it is not hard to verify that for any & I(T)) it holds
V + 6u
DE + 6.
MEeld(e)
and using the KKT optimality condition, this implies that for any v & L(T)
Yu + 6n
(_(m) - Hu nen.))
exp
+ 8,
W/
@Ecld(v)
or cquivalently, since w. 2w for all cld(v).
We 2
In Σ
Yu + de
(-
Pa + 1eau
exp
Dv + 6,
Wi
uEcld(v)
Thus, starting from pv on the leaves, this expression provides as bottom-up algorithm to compute all the Lagrange multipliers μ. Using these multipliers and the KKT optimality conditions, we can then easily compute the ratios
y 8, Dv + 8, Yp(c) + 8p(r)
exp
(Mpp() 14u - r7co)
( + 6p(n)
uv
for all vertices v # Finally, and cascade these ratios downwards until we reach the leaves and we have compute all entries of y* Clearly, this is all done in linear time to the number of vertices.
start from the root vertex for which know that y k.
Intuitively, this update step can be interpreted as an application of the Multiplicative Weights Update algorithm on every parent vertex that decides how its mass should be split to its children. We repeat this process bottom-up manner, and then we simply start with facilities on the root and begin splitting them based on these ratios while moving downwards.
30

---

E Analysis of Cut& (Proofs of Section
In this chapter the appendix we present all the omitted proofs from Section concerning our online rounding scheme Rut& To avoid repetition, from now fix arbitrary HST T and use FP(T) to denote the set of all fractional placements of facilities on the leaves of T.
Roadmap. In section E. we argue about the correctness Cut&Round; namely, we show that no matter the input, Cut& always returns set of k-leaves of T where the facilities are placed. and prove Lemma Finally, in
Then, in section [..2 we establish the main property of section E.3 analyze the expected connection cost of Cut&Round's output and prove Item 1 of Theorem (Lemma 6) while in section E.4 we analyze the expected moving cost of Cut&Round's output and prove Item of Theorem
(Lemma
E.1 Correctness of Cou&d
We begin by proving the correctness of Cut&Round. Fix any y E FP(T) and any set of thresholds E [0, LII) Let F = Cut&&Round y, a).. In this section, we will prove that |F] = k, i.c. we will argue that Round always returns of leaves which facilities must be placed, as it is expected to. In order to show this, we will need to analyze the Y, variables produced by Cut&&Round.
Claim 14. For any leaf T.TT), it holds that Y, E (0.
Proof. Observe that for any e E VTT), sub-routine Alloc sets Y, to either [vo] or [Vo. 1. By definition of FT( we have yu [0, 1] for each leaf E L(T). We distinguish between two different cases. If yo E [0, 1). then clearly Y, E {0, 1). If yo = 1, then 8(8.) 0 and thus Alloc will always set Y, yo
Thus, the claim holds for all leaves E L(T).
Claim 15. Let u & L(T) any non-leaf vertex. Then, Y, = -Eweod(()) Yu.
Proof. Fix any non-leaf vertex L(T). We will analyze the inner loop of Cut& that iterates over v's children. Initially, Cut&Round sets Yrem = Y, and yrem Vv- Then, we proceed to itteratively call Alloc, once per child vertex of e. Each time Alloc assigns some value Y, to child vertex u E cld(v), we update Yrem to Yrem Y.s thus, to prove our claim suffices to argue that after we update the last child vertex, have Yrom = 0.
Since by definition sub-routine Alloc we know that Y, E [LyoJ, Lyo] + 1}, we know that initially (before any child vertex is assigned value Y,) it holds that Y Yrem E [[yrem]] [yrem] + 1). In fact, a simple case analysis over the decision tree of sub-routine Alloc suffices to see that this invariant holds not only at the beginning, but even after we begin assigning values to the child vertices and update Yrem and frem.
Since E FP(T), we know that = Euecid(e) and thus Yrem Ya at the time we iterate cld(e). Furthermore, from the above discussion we know that
the last child vertex Yrem E [[Bw], [Va] + 1}. Since 6(y,) = 8(yrem), it is easy to verify that in any case Alloc sets Y, Vrem and thus after the last update have Yrem 0, desired.
Li
Proof of Correctness. Recall that by definition, the output of Cut& is F= {u L(T):
Y, = 13. Since from Claim 14 we know that Y, E {0,1) for all v E L(T), this implies that - Y,. We apply Claim t5 to the root vertex r, then again to each E cld(r) and so
on until reach the leaves. This gives us that Y, EvELAT) Y, and thus |A1 Y,. Since by definition Round sets Y, = k we have proven that |F = as desired.
31

---

E.2 Proof of Lemma (Computing the Allocation Probabilities)
In this section, we formally prove the main property of algorithm Cut& as stated in Lemma Fix any fractional facility placement E FP((T and let ag ~ (0, 1) be independent uniformly random thresholds for all o E V(T). Let F Cut (Tund)) y, o)) be the output of algorithm Cou& on this set of inputs. Recall that algorithm Cut&Round sets the variables Y, during its execution, for all & E V(T). As we have already discussed, Y, the total number of facilities in F on the leaves of the sub-tree rooted at v, i.. Y. (T(v) n F1. We will prove that for any (T),, we have
yo yo +1++1111
with probability 1 - 8(vo) with probability 5(y.)
Y
=
We begin by writing down the following property for sub-routine Alloc:
Claim 16. Fix any fractional facility placement y E FP(T) and let Ohp Unif(O,1) 1) for all
E VT)). For any vertex u E VT) Tf let Yu Alloc(yus Yhu yrem, Yrem: a.) be the number of facilities assigned to the sub-tree of u by Line 8 of Algorithm Cut& (Algorithm A Then,
if Yrem Uree
aand 8(ya) < ((yrem)
if rem = Urem aadd 8(ya) > d(yrem)
Pa [Y_ [bull
T
(frrem
0
Yrem F Urom aadd 8(ya) > 6(
By ) 5-5(ga]
if Y + Lreem and 6(yw) S 6(Frem)
[( )
Proof. This claim is a direct consequence of sub-routine Alloc's description (Algorithm 5) and the fact that a (0, 1) for all E V(T).
Using this claim, we are now ready to prove Lemma
5
We prove the lemma via a top-down induction on the vertices of T (decreasing level order). For the root vertex, we know that since y FF((T) we have yr & and also by definition of Cut&Round we have Y, = k. Thus, we get that Y, = 3r- = [y- with probability 1 1- = 1 and the claim holds. Now, fix any non-leaf vertex & L(T) and assume that Y, [yv] with probability 1 5(ye) and Y, = ye + with probability 8(y)). To complete our induction, we will now proceed to prove the claim for all the children vertices of
Proof of Lemma 5
We begin by proving the claim for the first child of vertex v, and then we will show how the same arguments extend for all its children. Let u E cld(v) be the first child vertex of u that Cou& iterates over. Then, by definition of Cut& Round we have that Yrem Y, and Drem = Ve- Using the inductive hypothesis v, this implies that Yrem [yrrm! with probability - 5(yrem) and Yrem Brem] + 1 with probability d(yrem). Conditioning on the value of Y Yrems we get
P. (Y, = [vw.1] P. YY, = [yv.l Yrem = 1/erm 1| (1 5(yrem))
+ P. Yv = [Va Yrem [Urem]] + 1] ((rrm)
We distinguish between two different cases based on whether 6(yw) < 8(yrem) or 5(yu) > 6(grem) In any case, and casily get that
Claim 16 to substitute the conditional probabilities on the above expression
P. [Y.. = LvwJ]
6(yw)
Thus, have already proven the claim for the first child of However, to complete our induction. we need to prove the claim for all children of e and not just the first one. The only property that we used and holds specifically for the first child was that Y frem- [yrem! with probability and Yrem = |rrmm + 1 with probability 6B ). Let Y and yrem be the updated remaining facilities after the value Y. of the first child has been assigned. If we can prove that Y Y I//em. with probability 1 - ø ( and Y = Ly'aml + 1 with probability 5( ), then we can keep applying the same argument and inductively prove the claim for all the children of v.
6(yrem)
By definition, we have that y = Yrem Yu and Frem = Frem - yo- Once again, we distinguish between two different cases.
32

---

Let 6(yu) _ (Brem)) In that case, we get that Vyreml = 1yrem] - [Bul and also that ((yrem) 8(yrem) ((y)). Since we know that Y Yrem { [[rrem] [trem] + 1] and Yu E [LvuJ, [Vn] + 1]. this implies that
PalY Lv = Io (eem = [trem]] n Ya = [va]]
+ IP (Yrem- Lyrrm]] n Yu Lyne + +]
Using conditional probabilities and the inductive hypothesis the distribution of Yrems obtain Pa (Yem [ = Pa Yu = [yn] Yrem = [yrem]] (1 8(yrem))
+ Pa Y 19,, +1 Yrem = [irem! + 1] 5(Urem) Using Claim 16 to substitute the conditional probabilities, we finally get Pa [Xrem [V = 8(Urem) + ō(yw) = 5(v/rm)
desired.
Let (y ). In that case, get that [W'emJ = [Urem Lya - 1 and also that ((rrmm) = (Brem) 8(ya). Since we know that Yrem E [Vrrmm] [Urem] + 11 and Yu [LvuJ, [yv.] + 1}. this implies that
Pa Prem [lm = Pa [Yrem = LBrrm]] n Yu = Lyu] +1]
Using conditional probabilities and the inductive hypothesis on the distribution of Yrems we obtain
Pa [ rem [l = P. Ir [un] 1 Yrem = [yrrem (1 - 5(yrem))
Using Claim 16 substitute the conditional probabilities, we finally get
Pa [Yr W/'mm]] (1y.) ( =1 5(yrem)
desired.
Thus, have concluded the proof of Lemma
E.3
Proof of Item 1 in Theorem 4 (Bounding the Expected Connection Cost)
Lemma 6. Let Cut& Rut&&oundyy, a)) where for all u E V(T), or ~ Unif(0, 1) independently Then,
Fa [C(()) fn(v) for any C I(T)
Proof. Fix any y E FP(T) and let [0, []V(T be set of thresholds such that for each E (TT), Or is drawn independently at random from the uniform distribution, i.e. Unif(O. 1). Let F Cuut&Rund(T, y. ar). We will prove that for any set of clients R I(T),, holds that F., [Cn(F))= = fn(v).
Recall that the Y, variables set by Cut&&Round denote the total number of facilities in that placed on the sub-tree rooted at vertex v, i.e. Y, = F [T(v) As argued in section E. we know that Y FF((T) i.e. Y is valid integral facility placement. Thus, from Claim I of section C.I we know that CR(F) = fY(Y). This implies that by definition of the fractional connection cost under client request R, have that
CR(P) Σ JERnEP(jmn)
2lev(e)+1 max (0, Y,)
Thus, we get
E, [x[CC(())
Σ
2lev(0)+1 [a[max (0, Y.)]
jER
Σ
Σ 2lev(u)+1 P.... 0]
JERvEP(i.M)
33

---

where the first equality holds by linearity of expectation, and the second equality holds by the fact that Y, E If' for all (TT). Since Y, E f.v.l. Ly 1}, we know that for any V(T), can be O only if [0. 1). Furthermore, from Lemma we know that in the case of uniformly random thresholds, this happens with probability precisely Yo- Combining these facts, we get PalY, 0] = max(0,1 Vv) and thus
Ea(CR(F)) = Σ
2lov(1)+1 max(O, 1 ye)
JERnE)(
[R(())
concluding the proof of Lemma
E.4 Proof of Item 2 in Theorem 4 (Bounding the Expected Moving Cost)
Lemma Let F Round&Cutty,, a) and also let F" Round&Cut(T, ./ a) where ay Unif(0, for all E V(T). Then,
7. E. [M((F, S 4 11 1/l1T
Fix any pair of fractional facility placements y, v' FP) and let corresponding outputs of Cut& be denoted as F' = Cutd y, a)) and F' = Cut&&oond(7 aa. Observe that the same set of (uniformly random) thresholds a, is used in both cases, this will play crucial part in our analysis. To prove Lemma 7 we need to prove that
Proof.
7 Ea (FFFF)) s 4- 4-1 1/1-1/117
where the expectation is taken over the value of the uniformly random thresholds Og-
The proof of Lemma iis technically involved, and thus will break down approach into smaller sections to case the presentation. We begin by proving the Lemma in the special case where the transition from y to y has very simple structure, which we now proceed define:
Definition 10. We say that two fractional facility placements J.y E FFP(T) are e-neighboring if there are two leaves 8, L(T) with least common ancestor V(T) such that the following hold:
1. 3/ = Ye for all v E P(s,p) {p).
2. 1. yo for all E Ptt.p) (p).
3. v. yo for all other E VT)..
Furthermore, we say that y, yf are strictly c-neighboring if sufficiently small to satisfy
1. < 8(yo) for all v E P(s,p) \ {p} with 6(y.) > 0.
2. é $ 1 - 8(y:) for all v P(t.p) \ {p) with 6(y.) > 0.
3. 6 6<1.
Basically, if and y are e-neighboring then y is obtained by pushing e-mass on y from to t along the unique path that connects these two leaves. Furthermore, if is sufficiently small that for any V E (T) either yy Ltd or ly, v/ll S 1 and at least one of the two is integral, then we say that the two fractional facility placements strictly e-neighboring. As will shortly argue, Lemmal holds in the special case where y, y' are strictly c-neighboring.
Claim 17. uy. EFP(T) are strictly e-neighboring for some 2 0, then
E., [M, (F,F")) F')] < 4 1-l - y'llT.
Before proving Claim 17 let us first show why it suffices argue about the general case and prove Lemma 7 Let y E FP(T) be any two fractional placements. Recall that |yy - y ||T captures precisely the minimum transportation cost from y to y on T. If we break down this transportation plan into small movements masses between leaves, then we can view it as a sequence of transitions between strictly e-neighboring placements. This is formalized in the following claim:
34

---

Claim 18. For any V.V. E FP(T), there exists finite sequence yo: V1, .i.....: Um E FP(T) of fractional facility placements with y yo and y' yo such that
1. Vj Uj+1 are strictly e-neighboring for some e 2 0 j = 0, 0......... -1
2. 1ly y' IT プド=
11 ----lll.
We will now prove Lemma Let F3 Cut& Mill&Rounn(T,, Mj, a)) be the corresponding output of Cut&Round on yj using the same (uniformly random) thresholds ay. Then,
m
y. Ea [MT
S Ea
Mr (F,
m
En (F;
==
4 1/ys 1011//7
4 11y 1/
In the above calculation, the first inequality holds from the fact that the minimum transportation cost satisfies the triangular inequality. The first equality holds from linearity of expectation. The second inequality holds from Claim and the second equality holds from Claim 18
Thus, we have shown that proving Lemma 7 for the special case strictly e-neighboring fractional facility placements y, y suffices to prove Lemma 7 for the general case of any y. E FP((T) and conclude this section. The rest of this section dedicated to proving Claim 17 which is the main
technical challenge towards proving Lemma] 7
Fix any pair of strictly e-neighboring fractional facility placements y, y FP(T) and let the corresponding outputs of Cut&Round be F Cut&Round( y, a) and F' Round(T, a.) In section E. we have already shown that F, F C L(T) are valid facility placements since [F] [F' L. E FP(T) be used to denote the corresponding integral placements, i.c.
Proof of Claim 17.
Yu [T) n FI number of facilities in F placed the leaves of the sub-tree rooted at
and
Y = ((() number of facilities in F" placed on the leaves of the sub-tree rooted at
Recall that Y and Y' are precisely the values of the Yvariaales that algorithm Cut& sets. As shown in Claim 2 of Section E.4 know that y MT F*) ||l Y'IIT. Thus, in order to prove Claim 17 we need to show that
En [I|Y Y'Il 4 11y y'I
Since y. y' are strictly e-neighboring fractional facility placements, we know that there exist two leaves s,t L(T) with lowest common ancestor V(T) such that 1yv- 3/ is among vertices on the (unique) path from to t (excluding vertex p) and is 0 otherwise. Let L = lev(p). Then, by definition of || we have
L-1
|/ 11g-/lle V
Σ glev(v) 1lo voll 2c
2' Σ 1=0
2c (2t 1)
(5)
DEV(T)
Furthermore, recall that from Lemma Round rounds y, either Y, [yo] + with probability 5(2,) or to [yo] with probability - 5(v.). Since is sufficiently small so that either
[y.] = [v]]] or (yu - v.l S 1 and at lowest one of the two integral (and is thus always rounded
to itself), get that Yy Y.' < for all (T). This implies that
35

---

E - E.,
2lev(1) 18, - Y
TEV(T)
21ev(1). Ea \ Y,
vEV(T)
= Σ
Pa [Y Y, = 1] 2lev(r)
vEV(T)
Let E [0, ((T) be any level the HST 7 and let Cj be used denote the expected number of vertices at level that are rounded to different values, i.e.
Ci = E2, [K E V(T): lev(v) = and Y, * YH
Then, the above imply that
M(T)
Eg I| Y 17
Σ 2 1=0
(6)
It remains to compute Cj for all / [0, (T)) This is done in Claim 19 where prove that C₁ 0 for 2 L (the level of and t's lowest common ancestor) and C I 4e (L otherwise. Combining
this claim with equations 5 and (6) immediately implies that
E. ||| Y'I 4 I1y y'II
which completes the proof of Claim 17
Claim 19. For any 2 L, C
For any < L, Ci 4c (I-1)
Proof. Recall that for fixed thresholds au, the output of Cound is deterministic. Since L, is the level vertex p (the lowest common ancestor of leaves 8, 1) and by definition of strictly e-neighboring placements y, y/ we know Yo 1/ for any vertex such that lev(v) 2 L,, we immediately get that G = for any 1 L.
We will now proceed to analyze Cj for any / < L. We partition the set of vertices v E V(T) with (ev(v) into three sets:
A vertex v called active it lies on the (unique) path between leaves s and
A vertex u called inactive it is not descendant of p (the lowest common ancestor of leaves and t).
A vertex is called affected if it is not active and is descendant of p.
Obviously, each vertex with lev(u) = must lie in exactly one of these sets.
Inactive Vertices. We will prove that for every inactive vertex v, Pa + Y Since the same set of thresholds a is used to round both and y', the output of Cut& is deterministic.. Furthermore, if vertex v inactive, then we know that ye = V/ and also y. = y', for any ancestor vertex of u of v (by Definition of neighboring facility placements). Thus, this immediately implies that Y, Y with probability and thus we do need to account for inactive vertices when computing Ct.
Recall that any active vertex is either an ancestor of leaf or leaf t. We will only prove the claim in the case when formal proof by induction is given in
Active Vertices. We will prove that for every active vertex v PalY. + Y
an ancestor the other case is completely analogous. Claim 20 presented at the end of this section. As a direct corollary, since there are only two active vertices per level, the expected number of active vertices level that are rounded two different values is precisely 2c.
36

---

Affected Vertices. Finally, we will now analyze the affected vertices. By definition, we know that each affected vertex will have unique active ancestor (also counting p). We partition the set of affected vertices on level I into 2 - 1-11 1) + groups, based on their corresponding active ancestor. The main argument we need to establish is that by definition of Cound&Cutt, at most one vertex in each of these groups can be rounded to a different value.
To see this, observe that Round&Cut is monotone, in the sense that if y/ 2 yo and also vl 2 V/u for all ancestors u of v, then (assuming the same set of thresholds is used), we know that Y 2 Y.. Using this fact on the vertices of group, since all of them can either only increase or decrease, in order to maintain balance at most one of them can change, otherwise we would get change of 2 or more on the parent node which cannot happen.
Furthermore, for a specific group, if both the common active ancestor and its child u with yu # yo end up rounded to the same value, we get (from the fact that the same thresholds are used) that all the vertices the group will be rounded to the same value. Thus, in order for a (unique) vertex in any group to change, at least one of two active vertices must change, which happens with probability at most 2e. Since there are 2(L-1- affected vertices level | that get rounded to a different value is at most 2E (2L 21 1).
- -1-1 1) - -1 groups, we get as a corollary that the expected number of
Combining everything, we get that C $ 30+ 2e + 2 (2L - 21 - 1) 4e (L 1).
Claim 20. Let v be any active vertex that is an ancestor of Then, PP Paly, + Yi!
Proof. In fact, we will in fact prove the following stronger claim,
Pa[Y, [yo] and Y = [v-]] = 1 8(yo) c.
Pa [ye] and Y [yo] + 1] c.
Pa(Y, [yee] + and Y [yo1]
Pa(Y, [ye] + 1 and Y |yo| 1| 5(yr)
which clearly implies Claim 20
Once again. we will prove the claim via induction, starting from the highest active ancestor of t at level T, and moving towards the leaf at level 0. We begin by mentioning that for vertex p (s and i's lowest common ancestor at level L.) we know for sure that Y, Yg since Up- V/p and yv. = Jo for any such that lev(u) 2 L; thus, since the same set of thresholds a is used, the execution of &ound will be identical up to this point.
We assume that the first child of any vertex o visited by Alloc is always the active child; this can be done without loss of generality as the order that Alloc visits the vertices hasn't 't played any part on our analysis yet.
Base of the induction. For the base of the induction, let be the (unique) child of p that is an ancestor of t; i.e. let v be the highest active ancestor of t. We have already mentioned that Y, = Y with probability 1. Thus, it can either be the case that Y, Y = Lyp] of Y,- = Y = Lyp] + 1. From L we know that the first happens with probability 1 - 8(y)) and the latter with probability 01)p). We distinguish between the following cases:
* Let o(y,) < 6(y,). Then, if Y, = YY Lyp] we know from the description of Alloc that
Y. Yy -B0e] with probability 1. On the other hand, if Y, = Y 1pp +1, we know that Y. +1 I //y))/ (8pp) and likewise Y² = [vv. +1 if a. I (8().) + e) (ō Thus, by conditioning on the values of Y, and Yd, we get
1. Pa = [ve] and Y = [v-J] = (1 - 8 1)-
5(x.)+e) = 1 - 1-8(1,) -E.
2. Pa(Y, = [vve] and Yy- = =Lve] + 1] = (1 8 -0+ 5(pp)
álu 5lve) = E.
6(w)) 5(1))
3. PPa.Y= [yo] + 1 and Y = [vo]] = (1 6(),)) 8(1)) 0 0.
37

---

4. P.lY, = [un.l + 1 and Y = [th.] + 1] (1 6(y,)) 0 ++ (1))
b(g=] (3%))
= 8(y)).
Let o(ve) 2 8(8p). Then, if Y = Y = 1yp + we know from the description of Alloc
that Y, = Yy = [yb] + 1 with probability 1. On the other hand, if Y Y Lypp we know that Y, = [yo]] + a. < (0(y)) - d(yp))((1 - 8(pp)) and likewise Y - Lyve + 1
if ai (Ó(Ve) + ((up))/(1 0(yp)). Thus, by conditioning the values of Yp and Y we get
1. P. ,Y, [tn_ and Y LVoJ] (1 (((p))) (1
A(y. Alv.)ee-Buup + 5(1p) 0
((2b))
1 6(yb) -E
Pa Y = -[yo] and Y = [[vo]] = (1 - -8(Up)) ) (((x)+e-66 6(yb)
5(y.) (1y-)-6(uo))
6(p))
1 1-8(8p)
1-b(1/)
0 = E.
3. Pa [Y, = -[vo] + 1 and Y = [Vh.]] = (1 8(Up)) 0 {(U))
0 - ((v)) 0.
4. PP Y,, [[vo] and Y [voJ] = 8(Up)) (
+ +d(Up) 16
1-6(wm)
So in both cases, the base of the induction holds.
Inductive Step. Using the exact same approach, we can prove the claim for any active ancestor i, assuming that the claim holds for u's father = p(u). The only difference, that now we can't claim that Y, = Y with probability 1. Instead, there are three different cases that we need to consider; namely
1. Y, = Y [to] with probability c 5yvv)
2. Y, = Y = 1301 + with probability 6(y.).
3. Y, [8e] and Y [yv] + with probability e.
where the probabilities hold from the inductive hypothesis on the parent vertex v. Next, we will need once again consider the case of whether d(yu) < 8(yx) or not (notice that the same relation will hold for Vn and vL)) and use the description of Alloc to get the assignment probabilities. Since this is simple matter arithmetic, the details are omitted.
38

---

Experimental Evaluation
In this section we experimentally evaluate the performance Algorithm fixed facility placement and compare it with the respective performance of the algorithm proposed by [3 In all the following experiments the step-size of Algorithm 3 (subroutine of Algorithm is set to = max I)vT..
with respect to the best
Periodically Moving Clients. We first present a simple setting to indicate the inefficiency of the online learning algorithm of 31 handling moving costs. In this experiment the underlying graph is the 0.01 -ildecrretiztionn of [0, 1 x [0. At each round t 2 1, we periodically select one of four balls of radius selected ball. In Figure 1 ann Table we present the overall cost of Algorithm 2 and the algorithm of [1 for different values facility- y converge to three of the four ball-centers, which is the optimal fixed facility placement. As the experiment reveals, the algorithm of [31] admits significantly larger cost as the facility-weigh increases while Algorithm 2 is robust to the increase.
0.2 depicted
Figure I and then client arrives uniformly at random on the
facilities and T 4000 time-steps. In all cases,
the facilities of
y
10"
10
10-1-
Fotakis et
Fotakis
Our Algorithm
Our Algorithm
10P
10a
10a
10a
10
10
Facility Placement
1.00
101
0.75
0.50
0.25
0.00
10a
-0.25
0.50
Fotakis et Our Algorithm
-0775
-1.00
10a
10
10a
10a
-1.0
-0.5
0.0
0.5
1.0
Figure We plot the evolution of the approximation ratio Algorithm 2 (red curve) and the algorithm from (31 (blue curve) compared to the hindsight optimal facility placement for facility weights 7 7 = and 7 10. Both scales are logarithmic. The bottom-right plot depicts the facilities eventually placed by our Algorithm 2 which coincides with the optimal configuration
Table 1: Ratio of the overall cost of both algorithms with respect to to the hindsight optimal (20 runs).
MovingClients
7 = 0
7
7 10
31
1.297 + 0.045
1.943
0.466
3.388 + 1.335
Algorithm
1.083 = 0.001
1.091
0.001
1.343 + 0.014
39

---

Real-World Datasets. We evaluate the performance of Algorithm on the MNIST and CIFAR10 datasets. We randomly sample sponds to vertex with the edge weights given by the Euclidean distance of the respective images. At each round i, an image is sampled uniformly at random and a client arrives in the corresponding vertex. We then evaluate Algorithm 2 in the latter setting for 7 = 3000 rounds and & = 10 facilities. In 2 we present the ratio of the overall cost Algorithm over the ratio cost of the fractional hindsight optimal" As our experiments indicate, the sub-optimality of Algorithm 2 is way smaller than the theoretical (log n) upper bound on the regret.
100000 images and construct graph where each image corre-
Table 2: The ratio of the cost of Algorithm 2 with respect to the cost of the fractional hindsight optimal facility placement (20 runs).
Algorithm
0
=
10
MNIST
1.118 + 0.01
1.403 = 0.04
1.5631 = 0.03
CIFAR10
1.113 + 0.01 1.189
0.04
1.59 + 0.31
Beyond unit batch sizes and random arrivals. Finally, we once again evaluate the performance of Algorithm 2 on the MNIST and CIFAR10 datasets. This time, the requests arrive in batches of size R 10 for T 3000 rounds. In order go beyond the random arrival model, we first sample the R T requested vertices uniformly at random from [n]] and then we proceed to order them based on their respective categories, using the lexicographical vector order to break ties. Then, we partition these requests into 7 batches of size R and sequentially reveal them to the algorithm as usual. As result, all images/vertices from the first category are requested first, then the second etc.
In Table 3 we present our experimental evaluations on the above constructed sequence. As our experiments indicate, our algorithm admits way better performance than the theoretical (logn) guarantees even in sequences with higher batch sizes and non-random arrivals.
Table 3: The ratio of the cost of our Algorithm with respect to the cost of the fractional hindsight optimal facility placement.
Our Algorithm
7=
0
1
?
10
CIFAR10
1.050
1.048
1.051
MNIST
1.082
1.045
1.12
"The cost of the fractional hindsight optimal can be efficiently computed [3 and lower bounds the cost of
the optimal facility placement. As a result, the presented ratios in Tables 2 and 3 are upper bounds on the actual ratio of Algorithm and the optimal Dacility-placemen
40


Reviews:
[{"review_id": "PrdgfL5CV2", "reviewer": "Reviewer_wiCY", "summary": "The authors study the k-median problem in an online learning setting with incorporated moving costs. In this setting the instance is revealed in batches, and before each batch the algorithm is required to place k centers so that to minimize the assignment costs of the (unseen) points that are then revealed in the batch. The objective function incorporates a cost for each center-placement that is moved between consecutive batches. The cost of the algorithm is the sum of the cost incurred in all batches. The performance of the algorithm is then measured w.r.t. to the best possible *fixed* placement of k-center, and is called the regret of the algorithm. \n\nThe authors present an algorithm that has regret of a O(log n) multiplicative factor, and a O(Poly(k, n, Diameter, \\gamma)*\\sqrt(T)) additive term, where n is the number of all possible points that are revealed, and T the number of batches. The Poly(k, n, Diameter, \\gamma) term in the additive factor becomes insignificant when T grows to infinity.\n\nIn their experiments, the authors compared their algorithm to the previous state-of-the-art algorithm by [Fotakis et al.], which does not consider the moving cost in the objective function. The authors report that their proposed algorithm outperformed [Fotakis et al.] on instances that were adversarial for the competing algorithm. Then, the authors also applied their algorithm to a couple of instances of images, where the images arrived in a random order. They compared the results to the optimum fractional solution on the whole instance. In this second set of experiments, the proposed algorithm performed very close to the optimum. However, the random order arrival seemed to be the easiest arrival order for the algorithm. This is because the distribution of the images did not shift over the batches of updates", "questions": "I find the problem formulation well motivated and natural. The theoretical result and the techniques are quite interesting, and deserve publication. The experimental evaluation is very friendly to the particular setting, and could be further strengthened. ", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "+ Studies a well-motivated formulation that incorporates the moving costs of the center. This models better the discussed applications, overcoming the shortcomings of previous studies.\n\n+ Solid theoretical contributions, and well-structured presentation.", "weaknesses": "\n- The additive term O(k * n^{3/2} * Diameter * \\gamma * \\sqrt{T}) stops being the dominant term (and in fact being less than any arbitrary fixed solution)  when T >> n, which may be unrealistic in some cases (including the motivating applications provided in the introduction). However, this may be an inherent artifact of the online batch-learning model.\n\n- No experiment made it to the main body of the paper (although briefly discussed).\n\n- The experiments consider batches of size 1, and only compare Fotakis et al. on instances adversarial to the competing algorithm. In the second experiment on real instances, the random arrival order is very friendly to the online learning framework. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your work and valuable comments. We commit on addressing them in the revised version of our work.\n\n1. *The additive...model:* As mentioned correctly by the reviewer, the additive term typically vanishes for large values of $T$, and this is indeed a standard convention that is considered in the online learning model. We also comment that in the previous work of Fotakis et al. [30] where the version of the problem without moving costs ($\\gamma=0$) is introduced, their algorithm admits an additive regret of $\\mathcal{O}(k * D * n * \\sqrt{\\log nT})$ that matches our additive regret up to a $\\sqrt{n}$ factor.\n        $$ $$\n  2. *No experiment..(although briefly discussed).* Due to space limitations, we had to move the experimental part of our work to the appendix. We plan to use the extra page that is provided in case of acceptance in order to include the experimental evaluation of our algorithm to the main body of our work.\n   $$ $$     \n   3. *The experiments...learning framework.* $$ $$\nIn our experimental evaluations we compare against the algorithm of Fotakis et al. since to the best of our knowledge it is the only method for online clustering running in polynomial time. \n$$ $$ In the attached pdf we provide additional experimental evaluations of our method for sequences at which the clients do not arrive in random-order while admitting batches of size $10$. As our results indicate, neither the batch size nor the random-arrival order seem to affect the algorithm's performance, and we still observe near optimal performance, showing that the $\\mathcal{O}(\\log n)$-regret guarantee is really pessimistic in real-world data. We will incorporate these additional experimental evaluations in the revised version of the paper.\n$$ $$\nWe would also like to comment that one of the reasons that designing adversarial instances for our algorithm is hard, is the inherent difficulty of designing lower bounds once considering time-efficient online learning algorithms. Deriving improved lower bounds on the regret in case of time-efficient algorithms is a very important and intriguing research direction, however we are not aware of any technique in the literature, and it is for this reason that we chose to consider the random arrival order.\n$$ $$\nFinally, we are more than willing to run additional experiments during the discussion period and incorporate them into the camera-ready version of our work. We welcome any suggestion on settings and/or datasets that would be interesting in evaluating our algorithm.\n"}, {"review_id": "AZWnZGVqNR", "reviewer": "Reviewer_5XPD", "summary": "This paper considers a regret framework for the following online learning problem. As input we are given a weighted graph and a number k of facilities. At each time step, we must select k vertices of the graph to serve as facilities. Afterwards, we learn the clients (also vertices of the graph) that the facilities must serve. The cost of the time step is the connection cost of the clients to the facilities, plus the cost of moving the facilities from the old positions to the new positions. The goal is for the total cost over all rounds to be small compared to the best solution in hindsight, that is, a static set of k facilities that minimizes the connection costs over all rounds. While the multiplicative weights algorithm can be shoehorned to give a (1+\\eps)-regret algorithm, it runs in time O(n^k), hence not polynomial. An O(k)-regret polytime algorithm is known for when there are no moving costs. This paper presents the first polytime algorithm with regret guarantees that accounts for moving costs; it achieves O(log n)-regret (suppressing additive terms). \n\nA key tool in the paper is to first develop an O(1)-regret algorithm for the special case where the input graph is a type of weighted tree called a Hierarchical Separation Tree (HST). Then for the general case, an O(log n)-distortion metric embedding is used to reduce the general graph case to the tree case. To achieve an O(1)-regret algorithm for HSTs, there are two phases. The first phase is to obtain an O(1)-regret algorithm for a fractional relaxation of the problem, in which facilities can be placed fractionally on vertices. The structure of the HST is crucial in both the formulation of the fractional relaxation and in the algorithm used to solve it (which is the well-known Follow the Regularized Leader algorithm, with the choice of regularizer exploiting the structure of the HST). The second phase is to round the fractional solutions to integral solutions, through a novel rounding algorithm the authors call Cut and Round, which preserves the connection and moving costs of the fractional solutions up to constant factors. Here as well, the structure of the HST is crucial.", "questions": "- How crucial is the matching-based formulation of moving costs to the proof? Have you considered other natural ways of defining moving costs and if so, what obstacles arise?\n\n- Can the results be easily adapted to when the connection cost is based on, say, \\ell_p objectives?\n\n- Does the problem become easier for \\gamma = 1?", "limitations": "Limitations are acknowledged.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- This paper gives the first polytime algorithm with regret guarantees for k-clustering with moving costs. Incorporating moving costs gives rise to a more expressive and realistic model than those considered previously. \n\n- This paper solves the problem (up to constant factors) for a certain class of trees, which is interesting in its own right. \n\n- While many of the techniques used (follow the regularized leader, fractional relaxations, and randomized rounding) are somewhat standard, reducing the problem to trees is a key insight that enables the use of these techniques. \n\n- The paper is clear and easy to follow.", "weaknesses": "- Without lower bounds, it is difficult to interpret the regret factor. \n\n- A more detailed comparison to the ideas used in the work of Fotakis et. al. would help contextualize the present work and highlight which ideas are novel. For example, the work of Fotakis et. al. also uses a fractional relaxation. What are the obstacles to extending their work, and in what ways is the present approach similar to theirs?\n\n- While the authors emphasize that the tree structure is exploited in many parts of the algorithm, they do not provide any intuition or motivation for why this case is in some sense easier. \n\n- The paper appears to violate the formatting instructions in terms of font size.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer of all its work and the insightful feedback on our paper. In the revised version of our paper we will incorporate the following discussion, addressing the reviewer's comments.\n\n1. *Without lower bounds...the regret factor:* Our work indeed does not provide lower bounds, however we remark that this is an inherent difficulty once considering time-efficient online learning algorithms. Lower bounds on online learning algorithms are solely based on the lack of knowledge of the future data. Deriving improved lower bounds on the regret in case of time-efficient algorithms is a very important and intriguing research direction however we are not aware of any technique in the literature. \n$$ $$\n2. *A more detailed...approach similar to theirs?:*\n$$ $$\nDespite both our work and Fotakis et al. use the *relax-and-round* pipeline, there are key differences in the two approaches. Namely, the algorithm of Fotakis et al. uses the *original* metric space while our algorithm uses the HST metric space approximating the original metric space.\\\n$$ $$\nThe rounding of Fotakis et al. is based on the so-called filtering technique [1]. More precisely, in order to bound the connection by its fractional counterpart, Fotakis et al. produce a facility-placement such that *the connection cost of any node on the metric (with or without client) is at most $\\mathcal{O}(k)$ times its fractional counterpart*. However, in order to guarantee the latter property, their produced integral solution can be arbitrarily far away from the respective fractional one. This is the reason why their approach is a dead-end once accounting moving cost - two consecutive fractional solutions can be very far away from the respective fractional ones.\\\n$$ $$\nOn the other hand, our algorithm exploits the easier HST structure to simultaneously treat both connection and moving cost. Our rounding scheme (*Cut&Round*) produces a probability distribution over facility placements, the marginal of which coincide with the fractional facility placements (in fact it guarantees a even stronger property, see Lemma 5 and our response to Reviewer d1Rn). By exploiting the HST structure we establish that the expected cost of each client equals its factional connection cost. At the same time *Cut&Round* creates correlations among the probability distributions of different rounds through the *shared randomness* $\\alpha_v$ (see Step $2$ of Algorithm $1$). Again, due to the HST structure we able to approximately upper bound the expected moving cost by the overall fractional moving cost. \n$$ $$\n[1] Approximation algorithms for geometric median problems, Lin et al. 1992\n$$ $$\n\n3. *While the authors emphasize...sense easier:* $$ $$\nThe key reason that HST structure is important is the following: Consider the prob. distribution $x,y$ over the nodes of metric space $G(V,E,w)$. In order to compute the distance of the *optimal transport* from $x $ to $y$ one would need to solve a min-cost flow problem. However in case $G(V,E,w)$ is an HST, then the optimal distance equals $\\sum_{v \\in V} 2^{\\mathrm{Level}(v)} |x_v - y_v|$. The latter closed-form formula provides with *easy to handle description* of both the connection and the moving cost - we refer the reviewer to Definition 7 and 8 for the respective formulas of the connection and moving cost. \n$$ $$\n4. *The paper...terms of font size:* We have used the neurips template. We have also checked with others submissions of ours and we did not find any discrepancy. Could you provide us with further details so that we can correct the formatting for the camera ready version? \n$$ $$\n5. *How crucial...obstacles arise?:* By considering different metric spaces, matching-based formulations capture all natural ways of defining the moving cost . For example the tweak on the problem at which the moving cost is defined as the set-difference of the facilities placements, $(|F_t/F_{t-1}|+|F_{t-1}/F_{t}|)/2$, can be captured with a matching-based formulation on the \\textit{uniform metric}. In this work we have focus on the most \\textit{intuitive formulation} at which the connection cost of the clients and the connection cost lie on the same metric space. The case of two different metric spaces (one for clients and one for facilities) is a very interesting research direction that however remains outside the scope of this work.\n$$ $$\n6. *Can the results be...$\\ell_p$ objectives?:* Extending our results to general $\\ell_p$ metrics is a very interesting direction. We believe that our ideas can be extended to cover general $\\ell_p$ metrics however this question remained outside the scope of this work.\n$$ $$  \n\n7. *Does the problem become easier for $\\gamma = 1$?:* Apart from the obvious fact that $\\gamma \\geq 1$ captures the case $\\gamma = 1$, we do not think that the problem becomes easier in this specific case."}, {"review_id": "LzbZgd7Cwr", "reviewer": "Reviewer_HLbh", "summary": "This paper studies online clustering with moving costs problem. In the problem, the client sets change over time. In each round t, the algorithm has to place k facilities F_t before seeing the set R_t of clients.  Two costs will be involved in each round t: the connection costs and the moving costs. The connection cost is the k-median cost of the solution F_t, with R_t being the client set. The moving cost is gamma times the earth-mover distance between F_{t-1} and F_t. The cost is compared to the cost of the best static solution.  \n\nThe main result of the paper is an algorithm that achieves O(log n)-regret and beta \\sqrt{T} additive error, where beta = O(kn^{3/2} * D_G * max{gamma, 1}.  To achieve this goal, the authors reduced the general metric to a HST metric, by losing an O(log n) factor in the regret. For the HST metric, the authors first solved a fractional version of the problem, and then use an oblivious randomized rounding algorithm to round the fractional solutions to integral ones. The rounding algorithm guarantees that in expectation, the moving cost incurred by the integral solutions is at most that of the fractional solutions. \n\nTo solve the fractional version of the problem, the authors used a dilated entropic regularizer. For every non-leaf u in the tree, they consider the fractional centers in each child-tree of u. After scaling this gives a distribution. They consider the entropy of this distribution. The dilated entropic regularizer is the weighted sum of the entropies over all non-leaves u, where the weight for a vertex u is 2^{lev(u)}; that is, the distance from u to any of its descendent leaf.  With this regularizer defined, the algorithm in every round chooses the fractional solution that minimizes the retrospective connection cost plus the scaled regularizer. The authors then show that the algorithm can achieve a O(k n^{3/2} D \\gamma) * \\sqrt{T} additive regret. \n\n", "questions": "No questions.", "limitations": "No Limitations.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": " -This is the first result that considers moving cost in the online learning model. The model introduced is interesting, and the paper may initiate the study of the model for other problems. Previous results only consider the connection cost. \n\n -The paper achieves an O(log n)-multiplicative regret guarantee, improving the previous O(k) factor. \n", "weaknesses": "The parameter beta is too big. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer of its work and the insightful feedback. In the revised version of our work we will incorporate the following discussion addressing your comments.\n\n*The parameter beta is too big:*  (Similar to  Reviewer wiCY) The additive regret term $\\beta = O(k * n^{3/2} * D * \\gamma * \\sqrt{T})$ is typically only required to vanish for large values of $T$, and this is indeed a standard convention that is considered in the online learning literature. We also comment that in the previous work of Fotakis et al. [30], their algorithm for the $\\gamma=0$ setting admits an additive regret of $\\mathcal{O}(k * D * n * \\sqrt{\\log nT})$ that matches our additive regret up to a $\\sqrt{n}$ factor."}, {"review_id": "SrJRANqpWP", "reviewer": "Reviewer_d1Rn", "summary": "The paper considers the $k$-median clustering problem in the online learning framework. More specifically, at the beginning of each round, the algorithm needs to maintain a set of $k$ centers (or facilities). After this, the actual set of clients is revealed. The algorithm incurs a cost equal to the total assignment cost of each client to the nearest center. At the next round, the algorithm can change the location of the $k$ centers, but then it also has to pay for the movement cost of the centers (by the min-cost matching between the two sets of locations). The total cost of the algorithm is the sum (over all rounds) of the assignment cost and the movement cost. The goal is to minimize the regret. The algorithm is said to have $(\\alpha, \\beta)$ regret, if the total cost is at most $\\alpha$ times the cost of the offline static solution plus an additive term of the form $O(\\beta \\sqrt{T})$ (for $T$ rounds). \n\nOnline learning with movement cost has been well-studied, and an influential result [11] gives an $(1+\\epsilon, \\beta)$ regret for any constant $\\epsilon > 0$ and $\\beta$ depends on size of the metric space. This result uses connections with the metrical task system problem. The running time of this algorithm (in each round) is of the form $O(n^k)$, and so is exponential in $k$. The paper asks if one can give efficient algorithms in this setting. \n\nThe main result of the paper shows that for HSTs (hierarchically separated trees), one can get constant-regret efficient algorithms. Then, using standard ideas, one can get an $O(\\log n, \\beta)$-regret (where $\\beta$ depends on the metric space only). For HST's, the algorithm is obtained in a two phase manner (again, this is standard in the case of online algorithms): frst maintain a fractional solution to this problem, and then maintain a randomized integral solution online (whose marginals are given by the fractional solution). For maintaining the fractional solution, they use the well-known FTRL approach, though the regularizer is non-standard (but was known in prior-work) and requires lots of details. The second part also requires non-trivial analysis, though again some of the ideas seem to be related to [9]. ", "questions": "1. Can we get better results for tree metrics? As stated the reliance on HST's seems crucial. \n2. What are the new ideas in fractional to integral conversion? At a very high level, it seems very related to the result in [9], though the authors do point out that [9] does not consider assignment costs, and only movement costs. Still, it was not clear, if any new ideas are needed here. \n3. The running time is mentioned to polynomial in $n$, but can it be polynomial in $T$ also? For example, is it conceivable that when $T$ gets very large, the running time can also grow with it? I was a bit confused because if we are looking at the aggreagate time after $T$ rounds, then oen can potentially spend time polynomial in $T$. Are we assuming that $T$ is polynomially bounded?", "limitations": "No negative societal impact. ", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The online learning framework for clustering is an interesting problem, and this is the first non-trivial result for this problem. \n2. The analysis, though along standard lines, requires lot of details and so is non-trivial. \n", "weaknesses": "1. As mentioned earlier, most of the ideas follow along standard lines. \n2. The actual regret guarantee is somewhat weak: one would expect constant-regret for general metric spaces. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer of their work and the insightful feedback. In the revised version of our work we will incorporate the following discussion addressing your comments.\n\n*Weaknesses*\n\n1. *As mentioned earlier, most of the ideas follow along standard lines.*\\\nThe cornerstone of our approach was to realize and establish that $O(1)$ regret is plausible for HST metrics. The main technical contribution of this work is (i) coming up with the dilated entropic regularizer to capture the structure of the HST and combine it with the FTRL algorithm and (ii) designing a lossless (up to constant factors) rounding scheme that simultaneously works for both the connection and the moving cost. Both of these components where central towards acquiring constant regret on HSTs.\n\n2. *The actual regret guarantee is somewhat weak: one would expect constant-regret for general metric spaces.*\\\nWhile achieving constant regret for general metric spaces could be theoretically possible, it is unclear whether it can be actually achieved via polynomial-time algorithms. We remark that constructing lower bounds for time-efficient online learning algorithms is inherently difficult, as lower bounds on online learning algorithms are solely based on the lack of knowledge of the future data. Furthermore, achieving constant regret on HSTs (and thus $\\mathcal{O}(\\log n)$-regret on general metric spaces) already required several new ideas, as discussed above. Finally, we comment that constant-regret guarantees are not known even in the simpler setting of $\\gamma=0$ (no moving-costs) considered by Fotakis et. al. [30].\n\n*Questions*\n\n1. Our algorithm is based on the HST structure (tree $+$ exponential decay in the weights). Going beyond our $\\mathcal{O}(\\log n)$ regret guarantees for general tree metrics is a very interesting direction that however requires new ideas and techniques.\n$$ $$\n2. The key idea for bounding the connection cost lies in Lemma 5. More precisely, *Cut&Round* produces a probability distribution over facility placements such that for any node $u$ in the HST,\n* $Y_v = \\lfloor y_v \\rfloor$ with probability $1 - \\delta(y_v) $\n* $Y_v = \\lfloor y_v \\rfloor$ + 1 with probability $\\delta(y_v) $\\\nwith $Y_v$ being the number of facilities in the descendant leaves of $u$. $$ $$\nIn Appendix E3 (at which the respective bound on the connection cost is presented) one can clearly see the importance of the above property - a probability distribution *marginally-respecting* the fractional solution cannot guarantee bounded connection cost. \\\n$$ $$\nBeyond the connection cost, a crucial merit of *Cut&Round* over the rounding of [9] concerns the computational complexity. Specifically, it is not known whether the rounding of [9] can be implemented in polynomial time. The rounding of [9] maintains a prob. distr. $\\mu_t$ (over facility placements) that marginally respects the underlying fractional placement $x_t$. At round $t+1$, $\\mu_{t+1}$ is selected such that $$Earth-mover-distance(\\mu_t,\\mu_{t+1}) \\leq \\mathcal{O}(d(x_t,x_{t+1})).$$ \\\nIn order to guarantee the latter, the rounding of [9] iterates over the facility placements on the positive support of $\\mu_t$ that can be exponentially large.\\\n\\\nOn the other hand, *Cut&Round* runs in linear time wrt to the size of HST. Notice that *Cut&Round* guarantees bounded moving cost through the use of *shared randomness* across all rounds (see $\\alpha_v$ in Algorithm $1$).\n$$ $$\n3.  Notice that since new clients arrive at each round $t \\in [T]$, a linear dependence in $T$ is inevitable. Thus $T$ is essentially considered to be polynomially bounded. Our algorithm  admits linear dependence $T$ and polynomial in the rest of the parameters. In the revised version of our work we will add a formal definition of polynomial-time online learning algorithms so as to avoid confusion; specifically, we are interested in algorithms whose time complexity is polynomial to the size of the input and the horizon $T$. \n"}]

Author rebuttal:
We thank all the reviewers for all their work and insightful comments.

In the attached pdf we present a set of supplementary experiments, addressing some of the reviewers' comments.

Meta-review: All reviews are on the positive side. Reviewers agreed that the problem studied is interesting, and the results are solid. The authors did a good job on addressing reviewers questions and concerns. We hope the authors will add additional experiments with batches of larger size and with non-random arrivals in the next version of this paper.
Decision: Accept (spotlight)