Learning-Augmented Algorithms for $k$-median via Online Learning
Authors: Anish Hebbar
Rong Ge
Amit Kumar
Debmalya Panigrahi
Venue: NeurIPS 2025 poster ()
Keywords: learning-augmented algorithm
k-median
online learning
Primary area: theory
TL;DR: online learning approach to learning-augmented k-median

Abstract: The field of learning-augmented algorithms seeks to use ML techniques on past instances of a problem to inform an algorithm designed for a future instance. In this paper, we introduce a novel model for learning-augmented algorithms inspired by online learning. In this model, we are given a sequence of instances of a problem and the goal of the learning-augmented algorithm is to use prior instances to propose a solution to a future instance of the problem. The performance of the algorithm is measured by its average performance across all the instances, where the performance on a single instance is the ratio between the cost of the algorithm's solution and that of an optimal solution for that instance. We apply this framework to the classic $k$-median clustering problem, and give an efficient learning algorithm that can approximately match the average performance of the best fixed $k$-median solution in hindsight across all the instances. We also experimentally evaluate our algorithm and show that its empirical performance is close to optimal, and also that it automatically adapts the solution to a dynamically changing sequence.

Leamning-Augmented Algorithms for k-median via Online Learning
Anish Hebbar
Rong Ge Duke University
Duke University
anishshripad hebbar@duke.edn edu
rongge@cs. www..uukeeeeeoeoooo
Amit Kumar
Debmalya Panigrahi
IIT Delhi amitk@cse. iit.sseeiii.d.c...... ac.in
Duke University
debmalya@cs.duuke edu
Abstract
The field of corning-augmenten algorithms seeks to use ML techniques on past instances of problem to inform an algorithm designed for a future instance. In this paper, we introduce a novel model for leaming-augmmnted algorithms inspired by online learning. In this model, we are given sequence of instances of a augmented algorithm is to use prior instances
problem and the goal of the to propose solution to a future instance of the problem. The performance of the algorithm measured by its average performance across all the instances, where the performance single instance is the ratio between the cost of the algorithm's 's solution and that of an optimal solution for that instance. We apply this framework the classic k-median clustering problem, and give efficient learning algorithm that can approximately match the average performance the best fixed k-median solution in hindsight across all the instances. We also experimentally evaluate algorithm and show that its empirical performance is close to optimal, and also that it automatically adapts the solution dynamically changing sequence.
Introduction
The field of nessing the ever-improving capabilities of machine learning (ML) solve problems in combinatorial optimization. Qualitatively, the goal in this area can be stated in simple terms: apply ML techniques on prior problem instances to inform algorithmic choices for a future instance. This broad objective has been interpreted in a variety of ways online algorithms with better competitive ratios using ML predictions, faster (offline) algorithms based on ML advice, better approximation factors for (offline) NP-hard problems using ML advice, etc. This breadth of interpretation has led to wealth of interesting research the intersection algorithm design and machine learning.
algorithms has seen rapid growth in recent years, with the aim of har-
In this paper, we take inspiration from the field of online learning to propose a new model for corming-augmmntee algorithms. The stated goal of Seariin--uugmente algorithms of using prior instances to inform the solution of a future instance bears striking similarity with online learning. In its simplest form, online learning comprises sequence of instances in which the learner has to select from set of actions to minimize unknown loss functions. The choice of the learner is based on the performance of these actions on prior instances defined by their respective loss functions. The goal is to optimize the performance of the learner in the long run it aims to match the average performance of the best fixed action in hindsight. Viewing learning-auge aegnnte algorithms through the lens of online learning, we ask:
Can learning-augmenne -agmented algorithm compete average performance over a sequence of problem instances with the best fixed solution in hindsight?
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

To instantiate this question, we consider the classic k-median problem in clustering, In this problem. we are given set of n points in a metric space, and the goal find le centers such that the sum of distances of the points to their closest centers is minimized. We note that k-median is among the most well-studied problems in unsupervised learning. In the learning-augmenter framework, consider an online sequence of k-median instances V1, Ve....,V,....... algorithm A has access to the prior instances
VT on some metric space
M. Now, suppose at time t, the V1, V2,,... Vi-1 and has to devise a solution comprising k centers for the next instance V2 (that is unknown to it). Once the algorithm A reveals its solution Y,, the instance V is revealed and the loss of the algorithm is the quality of the solution Y, for Vi, namely the ratio of the cost of Yú and that of an optimal solution for Vi.
We define the loss to be the ratio instead of the absolute cost because the instances that arrive can have very different scales. In particular, if one instance is very large and the rest are small, it suffices to perform well on just the large instance when looking at absolute cost. Thus, taking cost ratios ensures that the algorithm is incentivized do well on every instance, regardless of size. Secondly, it is impossible to obtain regret bounds independent of the number of points n when considering absolute costs. To see this, suppose we get a very large instance with essentially all n points that is far away from all the previous (much smaller) instances which are cumulatively on o(n)) points. Any online learning algorithm would then incur a cost of nA for this single instance, where A is the aspect ratio of the metric space[" On the other hand, the benchmark solution can simply optimize for this large instance and incur small cost for this instance. It suffers a large cost on the previous instances, but these instances being cumulatively small (only o(n) points), the overall cost of the benchmark remains small in terms of absolute cost.
Similar to online learning, A cannot hope to match optimal performance for single instance, but across time, can it match the performance of the best fixed solution in hindsight? In other words, we would like to learn competitive solution from prior instances when such a solution exists. In this paper, we show that this is indeed possible- - for k-median clustering, we design an online learning algorithm that approximately matches the performance of the best fixed solution across any sequence of instances on a metric space.
A natural approach to the above goal would be to employ the tools of online learning directly by encoding each solution as an "expert" and running an experts' learning algorithm (see e.g., (Hazan 2016)) on the problem instances. This does not work for two reasons, and these also reveal the main conceptual challenges in this problem. The first challenge is computational. The space of solutions to a discrete optimization problem such as k-median clustering is exponentially large and non-conver. Therefore, we cannot run experts' algorithms that maintain explicit weights over the entire set of solutions, neither can we use a black-box online convex optimization (OCO) algorithm (see e.g.. [Hazan 2016).. The second challenge is information-theore instances is revealed online, the learning algorithm does not know future instances when it proposes solution. Therefore, the metric space itself, and the corresponding space of solutions, is dynamically growing over time. Indeed, the best solution in hindsight may not even be available option to the algorithm at some intermediate time t. The main technical contribution of this paper is in overcoming this set of fundamental challenges to obtain matches the average performance of the best solution in hindsight.
Since the sequence of
marning-augmentee algorithm for k-median that
Our algorithms have potential applications in clustering evolving data streams, which has been identified as an important open challenge in data stream mining research (Krempl et al., 2014). Some examples include aggregating similar news stories for recommendations downstream GGog jet al. 2017] and maintaining accurate clustering of sensor data that fluctuates due to environmental conditions WWang et al. 20024). Another application lies in clustering network traffic where patterns of network user connections change slowly over time in normal circumstances, but can also undergo
sudden shifts if malicious attack occurs [Gong et al. 2017
Wang al. 2024
Feng 2006
1.1 Our Contributions
Problem Model and Definition, Our first contribution is the new learning- augmented model that we propose in this paper. We define it in the context of the k-median problem, and call it LEARN-
'The aspect ratio of metric space is the ratio of the maximum to minimum pairwise distance between distinct points in the metric space.
2

---

MEDIAN. The problem setting comprises an online sequence of instances of k-median defined on metric space M = (V, d) with set of n points V and distance function V V Rgo. The algorithm does not assume knowledge of the metric space (V,d) its size or the length of the time horizon T upfront. The instance time comprises a set of points V; S V. Using knowledge of prior instances Vo; V1 Vi-1, the Barning-augmentt
algorithm has to produce solution Y
comprising points in Vet == UV U. UU This solution is then applied to the instance Ve and incurs cost
(Yi)
Σ x),,,)), where D(Y, min d(z, v). .VV,
weYi
Correspondingly, the (approximation) loss of the algorithm is given by
Cost;(Y))
ply, vi) = OPT, where OPT, == min Σ D(Y YCVIY TEV
Since the ratio defining p(Y,,Ie) is invariant under scaling, we may assume that min vay d(z,z) y) = 1, and denote the aspect ratio maxz,yEV d(z, v) by A. Also, to avoid degenerate cases where OPT, causing the ratio be infinity, we assume each instance must have at least k + distinct points.
The goal is to match the average performance over time of the best fixed solution y (in hindsight), where y* argminygvyy E p(Y, Vt).
Our Results. We say that Maaming-augmentn algorithm for LEARN- obtains (a, approximation if
T V2) +
Σ p(Y, V1 Σ pY
call a the competitive ratio and / the regret of the algorithm. The goal is to obtain sublinear regret, i.e., 3 = oTT), while minimizing the competitive ratio
Our first result is a deterministic algorithm with a = O(k), = o(T). Precisely, we get
T Σ V)) E0( + (K'A vT log(() log(T))
We also give matching lower bound showing that the competitive ratio of O(k) is necessary, i.e., there is no deterministic algorithm with competitive ratio a = o(k) and sub-linear regret / = o(T).
Next, we use randomization to improve the competitive ratio to O(1). We give randomized algorithm with 0(1), o(T): V.) v0 VTlog(T) log(T)))))))) log(Tk))
Elo(Y, Vi) s 00))
As in the deterministic case, we show that the ((1) factor in the competitive ratio is necessary, i.e., there is algorithm (randomized deterministic) with competitive ratio 1 for arbitrarily small 0 and sub-linear regret 3 = (TT).
Finally, note that the regret bounds in both results depend on k, A. We show that this dependence is necessary, i.e., there is algorithm (randomized or deterministic) with competitive ratio 0(1) and regret 8 o(k2).
We give a sketch of the main techniques in our algorithms. Both the deterministic and randomized algorithm share all the steps, except the last one.
Our Techniques.
Thh set Va initializes the problem. The algorithm does not generate solution for Vo.

---

In the first step, we convert the LEARN-MEDIAN instance to a bounded version of this problem where each instance comprises exactly k points in the metric space, We call this latter problem BEARN-BOUNDED-MEERR
The conversion is done online at every time I.
Next, we relax the k-median problem by allowing fractional solutions, i.e. the centers are allowed to be distributed fractionally across the points of the metric space. Our main technical work is in producing a fractional solution to the k-median instances of LEARN- BOUNDED- BOUNDED-MEDIAN MEDIAN. Note that the feasible fractional solution define a (convex) simplex, but the number of dimensions of the simplex grows over time as more points appear in the k-mediaa instances. The main algorithmic ideas that we develop for this problem outlined in the paragraph below.
Our final step is in rounding the fractional solutions integer k-median solutions. Here, we give two different algorithms, one deterministic and the other randomized, both of which adapt ideas from LP-based rounding of k-median.
We now outline the main ideas in obtaining a fractional solution to the k-median instances. The main challenge is that the convex space of solutions available to the algorithm expands over time, yet the algorithm must compete with a solution that only guaranteed to lie in the final convex set. This means that in applying standard online convex optimization (OCO) tools such as online mirror descent (OMI), we only have partial knowledge of the gradient at any intermediate step corresponding to the dimensions/points that have appeared previously. Unfortunately. this limitation makes standard regularizers ineffective: the squared L2-norm regularizer fails to achieve sub-linear regret since the dimension of the gradient depends on the time horizon, while the negative entropy regularizer unable to handle new dimensions since the gradient is undefined at zero. Instead, we give non-standard changing regularizer parametrized by the number of unique points seen so far. Correspondingly, we depart from standard OCO analysis that compares against a fixed solution in hindsight. Instead, we divide the timeline into phases and compare the performance of our algorithm against a dynamic set of locally optimal solutions. The main advantage is that within a phase, we only compare our algorithm against solution that exists in the current convex set. The phases chosen carefully so that we can use metric properties to show that these locally optimal solutions have total cost comparable the hindsight optimum. Morally, we ensure that if the hindsight optimum is far from the locally optimal solutions, then it performs poorly on the instances in these phases, and therefore, cannot be the best solution in hindsight across all the instances. Putting all these components together in an online learning algorithm is the main technical contribution of this paper.
Experimental Evaluation. We perform experiments validate our theoretical results empirically. We first run our algorithms on synthetic data generated from simple distributions such as uniform distribution on square or on a set of distinct clusters. these cases, we confirm that the algorithms quickly converge to the optimal solution, and the average performance is nearly optimal in long run, thereby significantly outperforming theoretical bounds. In our second set of experiments, we use a sequence of dynamically changing distributions with the goal of understanding the responsiveness of our algorithm to changing data. We observe that as the algorithm discovers new data sets corresponding to new regions of the metric space, it reacts quickly to the changing environment and changes the location of i centers, in some cases even outperforms the static best solution in hindsight.
1.2 Related Work
Our work fits in the burgeoning field of learning-augmentte algorithms, where the goal is to leverage
MI. prediciisss to improve the performance of algorithms for optimization problems. This paradigm
was initially proposed for the online caching problem by [Lykouris and Vassilvitskii 202 and
has since been applied to many problem domains (see [Mitzenmacher and Vassilvitskii 2022 for
survey). In particular, various clustering problems such k-median and k-means clustering Ergun
et al. 2022 Nguyen et al., 2023 Gamlath et al. 2022] and facility location (Tiang et al.) 2022
Fotakis et al. [2025] have been studied in this framework, both in the offline and online settings. Our
work sharply deviates from these existing lines of research in that we consider model comprising a
sequence of problem instances inspired by online learning, while prior work focused on solving a
single instance using MI. predictions. A notable exception is Khodak et al. [0022). where the authors
consider an online learning based model to learn predictions from a sequence of problem instances, and apply it to variety of matching, scheduling, and rent-or-buy problems. In some sense,

---

model is a more direct counterpart of this idea, in that we apply the online learning paradigm to the performance of the algorithm directly instead of using a surrogate learned parameter.
From a technical standpoint, our work is related to the field of combinatorial online learning, where the goal is to develop low-regret algorithms for problems with exponentially large discrete action spaces. Traditional online learning tools like multiplicative weights update (MWU) are typically inapplicable due to computational barriers stemming from the sheer size of the solution space. To address this, several works have adapted online convex optimization and gradient-based techniques for combinatorial problems. Applications include online facility location [Christou et al. 2023 Pasteris et al. 2021]. online k-means clustering SohennAddan et al., [021] online routing (werrbuh and
Kleinberg 2008]. online learning of disjunctions [Helmbold al. [2002]. coalition formation [Cohen
and Agmon (224]] online submodular minimization Hazan and Kale|20112 online matrix prediction
(Hazan al. 2012]] and online ranking [Fotakis et al. 20200. One distinction in our model that we
consider the average approximation ratio across the instances, while these works consider average
cost. More importantly, the novelty in our work lies in designing new online learning algorithm and
analysis for the fractional problem, while most papers focus on reducing the combinatorial problem to an OCO formulation and apply standard OCO tools to the resulting problem.
Our work also bears some similarity with prior work on facility location problems in evolving metric spaces (Eisenstat et al. 2014| An al. [017]. But, in technical terms, this line of research is quite different in that it focuses on metric distances changing over time, while our focus is on new locations being added. Another related line of work is that of universal algorithms for optimization problems. These algorithms aim to compute single solution that performs well across all possible realizations of the input, thus providing robust approximation guarantees. Examples include universal algorithms for Steiner tree and TSP [Tia et al. [2005] (halgat et al. 20011 Gupta et al. [2066) set cover [Grandoni]
jet al.) 2008 Jia et al. 2005], clustering [Ganesh et al. 2023]. Unlike our work which is in the online setting, universal algorithms are offline and thereby use very different set of tools.
Finally, our work is also related to data-driven algorithms (see [Balcan 2021] for survey), where the typical goal is to pick the best algorithm out of a palette of algorithms whose behavior is dictated by a numerical parameter. In this line of work, the typical assumption is that the instances are drawn from an unknown distribution, and the goal is to obtain sample complexity bounds for a given target average performance in comparison to the best parameter choice. In contrast, in our setting, the algorithm is allowed to output any valid solution in each round and the final results are about average performance across an adversarial set of instances. [Balcan et al. 2018 considers the parameterized framework but in an online learning setting, where they pick parameter for each instance that arrives online. The benchmark in this case is the algorithm corresponding to the best fixed parameter in hindsight. Their techniques heavily utilize the parametrization of the algorithms, because of which they are not applicable to our setting.
Outline of the paper. In Section 2. BOUNDED-MEDIAN for which we then give a fractional algorithm in /Scctio and integer algo- rithms via online rounding in Sectionn 4 Details of these technical sections appear in the appendix. We present our experiments and empirical results in /ecctinn 5) again, details are in the appendix. Finally, the lower bounds that complement our algorithmic results are also given in the appendix.
we give the reduction from LEARN-MEDIAN to LEARN-
2 Reduction from LEARN- to
One difficulty in designing an algorithm for LEARN-MEDIAN that the k-median instances V, can have arbitrary size, which would mean that the metric space on which we design the algorithm expands in an arbitrary manner in each online step.
To alleviate this problem. in this section, we give a reduction from LEARN- to a simpler problem we call particular, this reduction eliminates the dependence on the size of instances n in our regret bounds. Otherwise, We will see in the next section that the subgradient that we compute at each step of the fractional algorithm can have a large Lx norm that depends on n, which would then affect the regret term. On the other hand, if we apply our mirror descent algorithm (given the next section) to only k points in each round, then the total number of points under consideration is at most KT. Thus, the regret term is independent of n. A second benefit of the reduction is that reduces the running time of the learning algorithm, and makes it independent of the size of the instances n. (The reduction uses
which has at most k weighted points per instance. In
5

---

k-median algorithm that runs on instances of size n, but this is unavoidable in any case.) We typically expect that n will be much larger than all other parameters in the problem. Using the reduction, we only need to run our learning algorithm on at most k7 points, which is independent of n.
It is important choose exactly h points in the reduction because if we fewer more than k: points, then the weights for the reduced instance are inconsistent with the k-median optimum. For example, if we use k points and there are closely knit clusters, then the resulting cost of the solution (which determines weights) is arbitrarily large in comparison. Similarly, if we use > & points and there are k + closely knit clusters, then the resulting cost of the solution is arbitrarily small.
Bounded Instances of LEARN-MEDIAN, Similar to LEARN- LEARN-MEDIAN a LEARN-BOUNDER BOUNDED- also given sequence of k-median instances. At time t, instance R₂ is specified by a set of at most k weighted points. Each point x E Rg has associated weight w (for simplicity, we often omit the superscript when is clear from context). The instances further satisfy Lign, nt, Wa S (k + 1). All other definitions are the same as before, except that the cost is now defined with respect to the weights:
MEDIAN instance is specified by metric space M (V, d) and
Cost, (Y, R.)
Σ W. D(Y.
DER.
We often just use Costa(Y) when the instance is clear from context.
Reduction to LEARN-BOUNDED--MNN
We show the following reduction:
Theorem 2.1. Given an instance for the LEARN-MEDIA problem. there exists an algorithm A that maps each sub-instance Vg to sub-instance R₂ = A(V)), resulting in LEARN-BOUNDED- MEDIAN instance. If solutions YI, YI.... YT for the new instance of LEARR--OUUNDDDMEDDAN satisfy
Σ Cost, Rτ) a.
(P, Ra) 7
min
where or 2 1 and R Ro U Ri ...U RT, then we have
Σ PY V.) ((a).
Σ V) Y-
min
We now describe the reduction the detailed analysis is deferred to the appendix. The main idea is to replace each set V; by it centers approximating the optimal k-median cost of V, these weighted centers act as proxies for the points in V,. More formally, consider an offline instance of the k-median problem comprising the points in V,, We use a constant factor approximation algorithm A for minogv, [C|=k ErEv. a(C,x:) to obtain set of k centers C. = fcI..... }. Let V. denote the points Ve that are assigned to a in the approximate solution. In the weighted instance Rr, we
miinccv.ICl==
|V(")
choose R, = C., and the weight of a point e; E R₁ is set to E.ev, D(C,, This completes the reduction an instance of LEARN-
3 Fractional Algorithm via Online Mirror Descent with Hyperbolic Entropy Regularizer
To design an online algorithm for SLLARN-BOUNDED-WEE the leader (FTL), where the algorithm outputs the best fixed solution for the prior instances. However, finding the exact FTL solution computationally intractable; moreover, we show (in the appendix) that using approximate FTL solution fails to give competitive algorithm even for A = 1.
perhaps the simplest idea is follow
common approach to address intractability to use a convex relaxation. Indeed, [Fotaiis et al. 2021] introduced a method that could solve LEARN- LEARN-BOUNDED BOUNDED -EDIAAN instances if the entire metric space (V, d) were known upfront. Unfortunately, not knowing the metrie space changes the problem significantly. For example, if the metric space is known, then it is possible to achieve pure (sub-linear) regret using a fractional solution, i.e., a competitive ratio of 1. contrast, we give simple example in the appendix that rules this out even for k 1 in our setting.

---

Our algorithm maintains fractional solution for points in Ret, updated by online mirror descent (OMD) using a hyperbolic entropy regularizer (Dehnition 3.1). New points introduced have fractional value initialized to O. To analyze the performance of the algorithm, we construct a sequence of solutions that only uses points Re and can only change log times. This allows us to show that the fractional solution is constant competitive with sublinear regret. We give further details of these steps in the rest of this section.
Fractional solutions for BEARN-BOUNDEDD MEDIAN. At time I, only points in Rete are revealed.
Let d = Rcal be the number of points available at time t, and A d. denote (2 E R || = k). A fractional solution yv is in the set K which is the intersection of A and [0, 1jd
Given vector Y1 K2-1, for each point the fractional assignment cost is defined by assigning the point æ fractionally to the centers in ye: D(y., x) == a a,=l Eiejd._.) (ed((, x).
The cost for the instance is still the weighted sum as before: Cost; == EzEn, W2 ())
Our algorithm. At each time t, a weighted subset of points RG arrives, At time = O, we initialize yo (which is k-dimensional vector) any k arbitrary points in Rg. At step t, we maintain fractional solution Y/ on the points Reg. To go from y/ to Vt+1, we perform one step of mirror descent based on the B-hyperbolic entropy regularizer defined below:
Definition 3.1 (3-hyperbolic entropy Ghai et al. 2020)). For any x E IRd and 3 > 0, define the 3-hyperbolic entropy of ær denoted (3(2)) as:
Ti
V02 + B2.
Ij aresinh
3
The associated Bregman divergence is given by B (1) (v) = 65(l) - -Øs(U) - (Vos(v), x- y)
d
24 arcsinh
Ti B
aresinh
y1 B
x7 + 82 + Vii + g2
Note that we considered other regularizers such as 1/2||=11 (which recovers online gradient descent) and E; z; log (which recovers exponentiated gradient descent). The problem with the former is that the regret term our analysis is not sublinear in T, while the latter is ill-defined for our setting as the gradient is not defined at 0, which we need for the new points. Before taking one mirror descent step, for points Rs but not in Rec,, we set their fractional values to O. This gives the fractional solution 1 for the next iteration. The detailed algorithm is given in Algorithm 1.
Analysis. To prove Algorithm is constant competitive, we compare its to changing sequence of optimal solutions. To construct such a sequence of optimal solutions, we first partition the sequence of i--median instances into phases. Let y" Kr be integral solution defined by set C of k centers. Let the centers in C' be c()) ..... (k)) The set C' partitions V into & subsets - let V() be the subset of V for which the closest center is c( (we break ties arbitrarily).
Considering each center in this optimal solution separately, we split the solution into different phases at times Ja. which the smallest time t such that the total weight of the points in ((() n Rg (i.e., points in (i) arriving by time t) exceeds k 2/. Define the set P = {je log(w(V(())
[k],
C [1, be the set of times when new phase starts. It's easy to check that
[P| S & log T as the total weight of arriving points is at most k + 1 in each step.
For each phase, we bound the cost of the algorithm using standard tools from the OCO literature:
Lemma 3.2. For any time interval I = [ta, 4s] C [L, T}. let z be an integral vector in K Then,
Σ TET
(Cost, (y:) - Cost (z)) < 3(k + 1)
This lemma shows that up to additive factors, in each phase we can be competitive against any solution. Therefore remains to show that there exists a series solutions that only use available points whose cost is competitive against the offline optimal solution y"
In fact, take Kr-1 A in the experiments for simplicity as the analysis is the same.
7

---

Algorithm 1: Algorithm for an instance of LEARN-BOUNDED-MEDIIN
1.1
Initialize Yo to any k points in Rg. i.e., yo E RR with (yo); = vi [k]]
for f
......,. 2.2..... do
1.3
Let the points in R be U 1
144
for each x E R2 do
let az be the fractional assignment of æ to v, ie.. D(v, x) agdes,,,
Define M max 20 d(v;,
1.6
1.7
Sub-gradient Step: Define V. E R& as follows: for each i E [de],
(V)):=-- Σ
(.(((s) min(M( d(xx, vi))
RE
Learning Rate: Set
GiVt
where G2 = maxyst <t Ve
1.9
Update Step: Define vector T++1 E Rd as follows: for each E [de].
sinh sinh(arcsinh((((v.) no (v))))
(I++1);
de
where we use (y:); = 0 in the above equation for each i E [dk] \ [de-1].
1.10
Projection Step: Define
D++1 argmin Bona (u1l
Lemma 3.3. For each p E P, let the start and end time of phase p be denoted sp and en respectively.
Then, there exist solutions (P) such that
T
ΣΣ pmPt
Cost, (s(P)) -0
2
Σ Coste(v"))
t=1
where y is an arbitrary integral vector in KT.
4 Integral Solutions via Online Rounding
In this section, give online rounding algorithms for the LEARR-BOUNDED-MERI Let y/, the fractional solution computed by Algorithm before the arrival the instance R. Our rounding algorithms will take the fractional solution Y/ as input and return integer solution Y, with exactly i centers. The rounding loss defined as the ratio of the (expected) cost of the integer solution Y, to that of the fractional solution ye-
problem.
We give rounding algorithms. The first algorithm deterministic and has rounding loss of O(k). The second algorithm is randomized and has only O(1) rounding loss. These are adaptations of existing rounding algorithms for k-median CCarrikar al. 1999 Charikar and Li 20022;; the main difference is that we need to bound the rounding loss for points we haven't i seen as well.
Deterministic Rounding Algorithm. The deterministic rounding algorithm based natural greedy strategy: at time f, maintain a set Y, that is initially empty. Consider the points in Rei Ro U... 1 in non-decreasing order of their connection costs D(yr, i). When considering point i, add it to Yú if its connection cost to Y, exceeds its fractional connection cost in ye by an 12(k) factor. This process ensures that |Y| < indeed, the intuition is that each time we add point to Y, we can draw a ball around it which has almost 1 unit of fractional mass (according y.). The criteria for adding a point to Y, ensures that the total connection cost to Y, remains within O(k) factor of that to yt. Thus, get rounding algorithm that rounds ye to integral solution Y, and loses O(k)

---

factor in approximation we give the details in the appendix. Combining this fact with Theorem 2.
and Lemma 3.3
we get the desired result T
Randomized Rounding Algorithm. The randomized rounding algorithm proceeds in two phases: the first phase is similar to the deterministic rounding algorithm described above. However, instead of keeping a threshold of (2(A: for adding a center to Y,, it uses constant threshold. This results in |Y]] being larger than k. Subsequently a randomized strategy is used to prune this set to size We show in the appendix that this algorithm has constant approximation gap. Combining this fact with Theorem 2.1 and Lemma 3.3] we get the desired result (2).
In conclusion, we obtain that the time complexity of our overall algorithm (besides the reduction step) is ( the bottleneck is computing the O x kT) distance matrix in each round.
Experimental Results
In this section, empirically evaluate the performance of our algorithms. In all our experiments, we use a heuristic to improve the performance of the rounding algorithmss where we do a binary search over the best threshold the distance of centers open (this value was (2k D a) for deterministic rounding and 4 (1),,, i) for randomized rounding). We set this threshold to the smallest possible that still gives the desired number of centers kt We report the main experimental findings in this section, and give additional results and experiments in the appendix.
Our first two experiments are for simple i..dd instances. In Uniform Square, each round has a set of points sampled uniformly from the unit square [0, 1] x [0, 1]. In Multiple Clusters, the underlying metric space consists of a set of clusters, and the points are sampled uniformly from these clusters. In both cases, the distances are given by the underlying Euclidean metric. As seen in Fig. both the deterministic and randomized algorithms converge expected solutions for Uniform Square, the centers are distributed (roughly) uniformly over the square and for Multiple Clusters, the centers spread themselves the different clusters. In the adjoining plots, we show the approximation ratio of the algorithms, which approaches once the influence of additive regret declines.
Uniform Square: All Solutions
Multiple Clusters: All Solutions
Uniferm Square: Aporoximation Rasics (k=6)
Multiple Clusters Appraximation Ratios (k=B)
Deterministic Imean)
Deterministi (mean)
Randomiized (mean)
Randomized (mean)
Fractional (mean)
Fractional [meon)
112
Time
Time
Figure 1: For i.i.d. instances (Uniform Square and Multiple Clusters). the optimal (black plus), deterministic (blue cross), and randomized (red diamond) solutions (top figure) and approximation ratios- avg. and std. dev. over 10 random instances (bottom figure).
In the third experiment Oscillating Instances, we have two distinct clusters, and instances comprise alternating batches of geometrically increasing length that draws points from one of the clusters. The optimal solution alternates between the two clusters, switching every time the current batch becomes long enough to dominate all previous instances. In Fig. 2a we show two important properties of our algorithm in this setup. First, for k 1, we plot the ratio over time between Σi=1p(Y, p(Y,, Vú) and

---

Fractional Mass in Clusters (k 2)
20
Mass in Cluster (ALG)
Dynamic Approkimation Ratio (K= tractional)
Mass in Cluster (OPT)
Fractional Mass
ALG/tDynamic OPT)
22
Lo
Time
(b) Fractional mass algorithm and OPT over time in one of the clusters for Oscillating In- stances
112
Time
(a) Approximation ratio for Oscillating Instances
Mass Evolution Hypersphere (d 8)
Mass on Origin
Fractional Clusters 2)
Cluster
Fractional Mass
1.75
ALS mass
ALB mase Cluater
24.
1.50
ALS mass In Cluster
1.25
ALG mass in Cluster 5
Fractional
1.00
0.75
0.75
255
170
112
100
1991
Time
(c) Fractional mass of algorithm over time at the center for Uniform Hypersphere (avg. and std. dev. over runs)
Time
(d) Fractional mass of algorithm in each cluster in Scale Changing
Figure 2: Experimental Results for Dynamic Instances
E'= p V+), where OPT, is the best fixed solution for instances V1,..., V,. Interestingly, our algorithm outperforms the optimal solution by virtue of being adaptive while the optimal solution is fixed. Next, in Fig. 2b we trace the migration of fractional mass between the two clusters for k = 2. We observe the algorithm quickly moves one unit of mass the current cluster, and then slows down since moving more fractional mass does not significantly reduce cost.
In the next set of experiments, explore settings where the metric space changes significantly over time. In Uniform Hypersphere, we choose kt = and every round consists of points chosen at random from the surface of the unit sphere. Around the 100th iteration, we also include the origin in the instance. This changes the space of solutions drastically because the origin is now a much better solution than any of the surface points. As seen in Fig. [c]] the algorithm moves fractional mass the origin once it becomes available, eventually converging entirely to this location.
Our final experiment is called Scale Changing. Here, we have 5 clusters with 10 points each. The clusters grow geometrically far apart in distance. The sequence of instances iterates over these clusters in batches of geometrically increasing length. Fig, 2d shows the fractional mass of the algorithm'ss ' solution in the all clusters. We see that our algorithm adapts to the changing environment by increasing the fractional mass in the cluster being currently presented, and earlier, this process slows after unit fractional mass has been moved to the new cluster.
Closing Remarks
In this paper, we studied the problem of solving a sequence of k-median clustering instances match the best fixed solution in hindsight. One limitation of our techniques is that they are tailored to metric problems. While these techniques might extend to problems similar k-median such as k-means clustering and facility location, they do not apply to other problem domains such as covering for which learning- augmented algorithms have been extensively studied. Nevertheless, our problem formulation bridging online learning and discrete optimization applies to the entire range of problems in combinatorial optimization. We leave the design of algorithms our framework for other problem domains as interesting future work.
10

---

Acknowledgments and Disclosure of Funding
Debmalya Panigrahi and Anish Hebbar supported in part by NSF awards CCF-195570 and CCF-2329230. Rong Ge was supported part by NSF Award DMS-2031844
References
Hyung-Chan An, Ashkan Norouzi-Fard, and Ola Svensson. Dynamic facility location via exponential clocks. ACM Transactions on Algorithms (TALG), 13(2):1-20, 2017.
Baruch Awerbuch and Robert Kleinberg. Online linear optimization and adaptive routing. Journal of Computer and System Sciences, 74(1):97-114, 2008
Maria-Florina Balcan. Data-driven algorithm design. In Tim Roughgarden, editor, Beyond the
Worst-Case Analysis of Algorithms, page 626-645. Cambridge University Press, 2021.
Maria-Florina Balcan, Travis Dick, and Ellen Vitercik. Dispersion for data-driven algorithm design, online learning, and private optimization. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 603-614, IEEE, 2018.
Anand Bhalgat, Deeparnab Chakrabarty, and Sanjeev Khanna. Optimal lower bounds for universal and differentially private steiner trees and tsps. In International Workshop Approximation Algorithms for Combinatorial Optimization, pages 75-86. Springer, 2011.
Moses Charikar and Shi Li. dependent ip-rounding approach for the k-median problem. In International Colloquium on Automata, Languages, and Programming, pages 194-205. Springer, 2012.
Moses Charikar, Sudipto Guha, Êva Tardos, and David B Shmoys. A constant- factor approximation algorithm for the k-median problem. In Proceedings of the thirty-first annual ACM symposium on Theory of computing, pages 1-10, 1999.
Dimitrios Christou, Stratis Skoulakis, and Volkan Cevher. Efficient online clustering with moving costs. Advances Neural Information Processing Systems, 36:25325-25364 2023.
Saar Cohen and Noa Agmon. Online learning of partitions in additively separable hedonic games. In Proceedings of the 33rd International Joint Conference on Artificial Intelligence (IJCAI), pages 2722-2730, 2024.
Vincent Cohen-Addad, Benjamin Guedj, Varun Kanade, and Guy Rom. Online k-means clustering. In International Conference on Artificial Intelligence and Statistics, pages 1126-1134 1134. PMLR, 2021.
David Eisenstat, Claire Mathieu, and Nicolas Schabanel. Facility location in evolving metrics. In International Colloquium on Automata, Languages, and Programming, pages 459-470. Springer, 2014.
Jon Ergun, Zhili Feng, Sandeep Silwal, David Woodruff, and Samson Zhou. Learning augmmented k-means clustering. In Proceedings of the Tenth International Conference on Learning Representa- tions (ICLR), 2022.
Cao Feng. Density-based clustering
evolving data stream with noise. SDM 2006, 2006.
Dimitris Fotakis, Thanasis Lianeas, Georgios Piliouras, and Stratis Skoulakis. Efficient online learning of optimal rankings: Dimensionality reduction via gradient descent. Advances Neural Information Processing Systems, 33:7816-7821 2020.
Dimitris Fotakis, Georgios Piliouras, and Stratis Skoulakis. Efficient online learning for dynamic k-clustering. In International Conference Machine Learning, pages 3396-3406. PMLR, 2021.
Dimitris Fotakis, Evangelia Gergatsouli, Themistoklis Gouleakis. Nikolas Patris, and Thanos Tolias. Improved bounds for online facility location with predictions. In Toby Walsh, Julie Shah, and Zico Kolter, editors, AAAI-25, Sponsored by the Association for the Advancement of Artificial Intelligence, February 25 March 4, 2025, Philadelphia, PA, USA, pages 26973-26981. AAAI Press, 2025.
11

---

Buddhima Gamlath, Silvio Lattanzi, Ashkan Norouzi-Fart and Ola Svensson. Approximate cluster recovery from noisy labels. In Conference on Learning Theory, pages 1463-1509. PMLR, 2022.
Arun Ganesh, Bruce M Maggs, and Debmalya Panigrahi. Universal algorithms for clustering problems. ACM Transactions on Algorithms, 19(2):1-46, 2023.
Udaya Ghai, Elad Hazan, and Yoram Singer. Exponentiated gradient meets gradient descent. In Algorithmic learning theory, pages 386-407. PMLR, 2020.
Shufeng Gong, Yanfeng Zhang, and Ge Yu. Clustering stream data by exploring the evolution of density mountain. Proceedings of the VLDB Endowment, 11(4:3993 405, 2017.
Fabrizio Grandoni, Anupam Gupta, Stefano Leonardi, Pauli Miettinen, Piotr Sankowski, and Mohit Singh. Set covering with our eyes closed. In 2008 49th Anmual IEEE Symposium on Foundations of Computer Science, pages 347-356. IEEE, 2008.
Anupam Gupta, Mohammad T Hajiaghayi, and Harald Räcke. Oblivious network design. In Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pages 970-979, 2006.
Elad Hazan. Introduction to online convex optimization. Found. Trends Optim., 2(3-4):157-325, 2016. doi: 10.1561/4400000133. Uttttttp:://do http:///ooooooo//////// wtt..r.......//0000000000000 1561/2400000013
Elad Hazan and Satyen Kale. Online submodular minimization. The Journal of Machine Learning Research, 13(1)22903-2922, 2012.
Elad Hazan, Satyen Kale, and Shai Shalev-Shwartz. Near-optimal algorithms for online matrix prediction. In Conference on Learning Theory, pages 38-1, JMLR Workshop and Conference Proceedings, 2012.
David P Helmbold, Sandra Panizza, and Manfred K Warmuth. Direct and indirect algorithms for on-line learning of disjunctions. Theoretical Computer Science, 284(1): 109-11442 2002.
Jia, G Lin, G Noubir, R Rajaraman, and R Sundaram. Universal algorithms for tsp, steiner tree, and set cover. In Proceedings of the 36th Annual ACM Symposium Theory of Computing, 2005.
Shaofeng H-C Jiang, Erzhi Liu, You Lyu, Zhihao Gavin Tang, and Yubo Zhang. Online facility location with predictions. In Proceedings of the Tenth International Conference Learning Representations (ICLR), 2022.
Misha Khodak, Maria-Florina Balcan, Ameet Talwalkar, and Sergei Vassilvitskii. Learning pre- dictions for algorithms with predictions. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28- December 2022, 2022.
Georg Krempl, Indre Žliobaite, Dariusz. Brzezinski, Eyke Hüllermeier, Mark Last, Vincent Lemaire, Tino Noack, Ammar Shaker, Sonja Sievi, Myra Spiliopoulou, et al. Open challenges for data stream mining research. ACM SIGKDD explorations newsletter, 16(1):1-10, 2014.
Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. Journal of the ACM (JACM), 68(4):1-25, 2021.
Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. Commun. ACM, 65(7): 33-35, June 2022. ISSN 0001-0782. doi: 10.1145/3528087. URL https: .rg. 10. 1145/ 3528087
Thy Nguyen, Anamay Chaturvedi, and Huy Le Nguyen. Improved learning-augmentted algorithms for k-means and k-medians clustering. In Proceedings of the Eleventh International Conference on Learning Representations (ICLR), 2023.
Stephen Pasteris, Ting He, Fabio Vitale, Shiqiang Wang, and Mark Herbster. Online learning of facility locations. Algorithmic Learning Theory, pages 1002-1050. PMLR, 2021.
Zhengru Wang, Xin Wang, and Shuhao Zhang. Mostream: A modular and self-optimizing data stream clustering algorithm. 2024 IEEE International Conference on Data Mining (ICDM), pages 500-509. IEEE, 2024.
12

---

while preserving the competitive ratio up constant Technical Appendices and Supplementary Material
A
Reduction from LEARN-MEDIAN to
Recall that in Section we first reduce LEARN-MEIE MEDIAN to simpler problem we call LEARN- BOUNDED- MOUNDED-MEDIAN, which has most & weighted points per instance. We do this because the original k-median instances Vi can have arbitrary size, which would mean that the metric space on which we design the algorithm expands in an arbitrary manner in each online step.
We give the details of this reduction step this section.
A.1 Bounded Instances of LEARN-MEDIAN
instance specified by a metric space M = (V, and we are also given sequence of subinstances. At time f, instance R, is specified by set of at most weighted points Rg. Each point x E Rg has an associated weight w (for simplicity, we often omit the superscript i when it is clear from context). The instances further satisfy EnER, ws S (k 1). The cost for round is now given by the weighted k-meddan cost:
Cost, (Y, R.) = Σ
Wg DYY,)
DE R.
We often just use Cost, when the instance is clear from context.
A.2 Reduction
We now show that any instance of LEARN-MEDIAN can be reduced (in an online manner) to an instance of LEARN-BOUNDED--ME factor. More formally, we show
Theorem 2.1 Given an instance for the LEARN-MEDIAN problem, there exists an algorithm A that maps each sub-instance Vz to sub-instance RG = A(Vi), resulting in BEARRN-BUNNDED MEDIAN instance. If solutions Y1, Yi.... Yr for the new instance of LEARR- satisfy
T
Σ
Cost, (Y,, R.) S a
min Σ
(oste(P, RR) +
PgR k t=1
t=1
where or 2 1 and R
Ro U Rí ...U Rr, then have
Σ PYr, V.) S ((a)-
min Y'CK
Σ P(Y + 0(7).
We will first describe the reduction. When the sub-instance Vú arrives time f,, we shall create corresponding sub-instance R₂ as follows: consider an offline instance of the k-median problem where the only points available are V,, We use a constant factor approximation algorithm AA for the k-median problem to obtain a set of & centers. More formally, we find constant factor approximation the following problem:
min CCV.,C/=k ZEV.
Σ D(C.2).
Let C₂ be the subset of k centers returned by the above approximation algorithm. Let the points in C, be fci,..., } and v,(8) denote the points in V, that are assigned to Thus,
Σ D(C,,))=
x) =
Σ Σ d(c,
DEV
In the sub-instance RG, the set of points is just R₁ Cc. and the weight of point e E R2 is equal to
[((()
EvEv, D(C,,z))
13

---

Note that the sum of weights of the above points is
E.
V
V V
S kk+1,
EvEV. D(C,, ExeV. a))
because [V] 2 k ++1 and the minimum distance between any two distinct points in the metric space is 1 due scaling. This completes the description of the instance of LEARN- BOUNDED-MEDAN We now show that a competitive algorithm for the new instance implies the same for the original LEARN-MEDIAN instance, while losing only constant factor in the competitive ratio.
To prove this, we will need the following well-knowe fact about k- k-median.
Claim A.1. Consider weighted instance of the k-median problem where the of clients is given by a subset I of points in the underlying metric space. Let C* be an optimal solution (i.e., optimal set of & centers) to the instance and be an optimal solution where the set of centers is required to be subset of I. Then,
Σ w. I()
S2 Σ WwD(CC DE
ZEI
where wy is the weight of the client x.
Proof. Suppose
the optimal /-median solution for I, with centres y (h),, partitioning I into the corresponding clusters SI,... Sp. Note that ( is the optimal 1-median of the cluster S. For any set of clients X, let wXX) = Σnex wi denote the total weight of the set.
(S)) Σ xx))=
Σ We Σ E'
W (
Σ #'ES, #ES.
Σ
Wy W. ((y + wyy .))
zES;
#ES.
Σ
Σ
Wer ((', (Triangle inequality)
st #'ES, WES,
We then divide both sides by ((S)) to obtain
2 Σ wy .r)
Σ
wyd(x',
((S))
DES.
x'es,
vES,
Since the right hand side is weighted combination of EvEs, w.d(x' x)) for different x' e S, this implies that (() argmin.res, es ExEs, Wyd(æ', x) satisfies
wo 2 Σ
PE
zES,
we denote y/ as the collection of the & centres ( by adding up the above inequality for each i [k]] we obtain the desired result.
k
&
Σ w. (V
w w.d(y' 52
w.d(y = Σ wy,
sES,
xe
We now ready prove the correctness of the reduction.
Proof of Theorem 2.1 For a time f, the subset C₁ is a constant factor approximation to the k-median instance specified by the set of points V,. fact, we have the additional restriction that C, a subset of Vg. Now, Claim A.I implies that if Y is optimal solution to this k-median instance, then
Σ FVV.
D(C = 0(1) Σ D(Y;,))
(3)
zEV.
14

---

) and C. = [ (c.'...,,'') Let v.() be the subset of V that is assigned to ()), i.e. the points in V for which the closest center C₁ is cld) Now we upper bound the competitive ratio of the solution Y, in the instance Vj:
Let Y, - (v.('......e)))
).
p(Y, Vi) ENER. x)
Ener, x)),
2 0(1).
(from 33
Evev, oz)
Σ Evev, D(C,,I)
- Σ j=1 EoEV, d(
Even, D(Cr,
0)( و== Enevchn (d(Y), (3) d(cp ,x))
(triangle inequality)
Enev x(C,,
0(1 Σ Id (()) ((1) ExEv, D(Cr,))
Exer, D(C,,
0(1) Cost, (Y, Rτ) +R))+01) 0(1)
Let Y be the optimal subset of k points that minimizes Σ p(Y", Vt). We now lower bound EX,( V2). We again use the partition of Ve into v, " E [k] and triangle inequality to get: ,(Y", Exev, D(Y"..) Evev. x();
Ever. D(Y*,x)
Σzev D(Ct,
Ej=1 E Ezer(o) d(Y*, xz)
Exev, D(C(,))
Σj=1 E Ezer( (d(Y', -(.1) d(c ,2))
*
(triangle inequality)
Exer, 2(C,,))
== IV. Id(Y', ,(()) - -Erev ((C,,))
Exer. D(C,,
CYs RR))-1. (R), -1
(5)
Consequently, combining 4 and 5 obtain
T
T Cost, (o,tx(P,R,) + O(T +
p(Y,, 1/) S 0(1)
(x), s O(a)
1=1
0(a) Σ (Y" RR) + O +n)
CCaam A.1
s (()a) Σ (p(Y", V2) + O(T +2) O(a) Σ
where in the last step we used that a and p(Y V/) 2 This proves the desired result.
B Detailed Proofs for Fractional Algorithm
In this section, we give a detailed description the online algorithm described in Section 3 for maintaining fractional solution an instance of the LEARN-Bon MEOX--BUNDED--EDDE problem. We also give the missing proofs the analysis of this algorithm.
Problem Setup: Consider an instance M = (V.d) of the LEARN-BOUNDED-MEDAAN problem. There are + rounds in total, and each round I, weighted sub-instance RG arrives. This sub- instance is specified by set of & points RG in metric space M. Note that the points in the metric
15

---

space M are revealed over time, and hence, till time t, only the points in Rgt == UpgeR, in the metric space have been revealed. Let d, denote (Rgel and A denote {z E R ||=||| k} where each coordinate i refers corresponding point in Re.. By ensuring that point in R2 corresponds to the same coordinate in Ary for 1' 2 I, we have Σd, C Ad, for all 6, where 2 L. Finally, let K2 denote the intersection of A di and [0. 1J In an integral solution, we would require that each time f, the algorithm outputs a subset Y, of k points in Rig-ii however, in fractional solution relax this requirement as follows the online algorithm outputs a vector ye E K for each time t. Given a vector yt E K the fractional assignment cost at time is given by:
(ost((v)) =
Σ ZER:
Wr ((),
where (gg,, x) is obtained by fractionally assigning x to an extent of to the closest points in yr- In other words, let o; denote the point corresponding coordinate i in K,-1- Then, D(y., min _[ Eie(d--) o,d(n;,
(rdedd_-)),d((,..00))) where Σ, o; = and 0 S a; S (y));-
B.1 Basic facts about the 1-median problem
In this section, we state some basic facts about the 1-median problem. Given a weighted set X of points in metric space MM, let opt, (X) be the optimal weighted 1-median cost of X. i...
opt, (X) = min Σ wyd(y.v).
yEM
ZEX
where wa is the weight of the point The minimizer y above shall be referred as the optimal 1- median center X. The following result shows that opt, (X) is closely approximated by a weighted sum of the pair-wis wise distances between the points in X.
Fact B.I. Let X be weighted set of points in a metric space. Then,
opt, (X)
Wp
Σ r'EX
ZEX
Proof. Let y be an optimal 1-median center X. Then,
2w(X) wad(y" x) =2 2 Σ
Wey
Wnd(y", x))
Σ
Σ
We W.dly ,x) + uw wedly x')
x
x'
TEX
x'eX FEX
Σ
Σ
Wel Wg
(Triangle inequality)
#'EX xe
Dividing both sides by 2w( X) now gives the desired bound.
The following result states that the weighted distance of X from point be well-appro by the weighted distance between and an optimal I-median of X.
Fact B.2. Let X be weighted set of points in a metric space and y be an optimal 1-median of X. For any point v in the metric space,
d(v. 2
We w(X)
d(v, d(v,.)).
zEX
Proof. We have:
w( w(X)dlv,')) Exex w-dlv,y")
< Erex wxd(v, w(X)
ExEx Wnd(y", .x) w(X)
+
(Triangle inequality)
w(X)
w(X)
w,d(v,
2
(Optimality y))
#EX w(X)
Computing the optimal 1-median center y² can be hard as we don't know the entire metric space- instead the following result shows that replacing yy by the optimal center amongst X retains the property stated above.
16

---

Corollary B.3. Let X be set of points in metric space M and u be an arbitrary point in M. Let x² X be a point that minimizes ExEx wr xx" 2). Then,
d(v, x" S 3
Σ =
w(X) d(v,
Wx
Proof. Let y² be optimal 1-center of X. Using Fact B.1 We have:
Σ wy 22) 2 min sex
Σ
Ward x²)
Σ #EX
Wyd(x' .z)
xEX
x'E
Proceeding as in the proof of Fact B.2 we get
d(v,x*) Exex (()((v
Evex wod(0,2) w(X) + Evex Wod(o" ,2)
w(X)
w(X)
The result now follows from Claim A.I
Σ
w=d("" 5)) 2 2
Σ
w.d(y ()) S Σ wgd(v,
ZEX
zEX
#EX
B.2 Regularizer and its properties
In this section, we define the regularizer that online mirror descent algorithm shall use. We also give useful properties of the regularizer. Definition B.4 (ā-hyperbolic entropy). GGai et al. 2020
For any x E IR and B > 0, define the
3-hyperbolic entropy of x, denoted (1((1) as:
T2 x² + 32.
Φạ(x)= = xs aresinh
3
Note that (1(x)) is convex and twice differentiable, and its gradient is given by
(Vos(<))) arosinh(z:/80) Vi eiel [d]
(6)
Consequently its Hessian is the diagonal matrix,
V2 (0))(()
Diag
32
x + 82
now establish strong convexity properties of the function dg. Definition B.5 (Strongly convex function). A twice differentiable function f: K + IR on a convex set K C Rd is said to a-strongly convex with respect to norm || on K if for all æ, y K
f(x) - f(v) - (Vf(y), x 8)
2
a =11 1 y11
2
or equivalently,
inf
y V f(ry
>EK.ER<::|<||=]
Lemma B.6. The function dg k+Dd -troongy convex over 2 with respect to the & norm.
Proof. We use the second characterization in Definition B.5 such that ||y|| 1. Then
Consider vectors E A and Rd
v
Σ
B2 + x²
82
x
VB+ +
x
82
x
ii
1
E
32
V B
x
Σi (B + +xz))
1: + 3d'
where the first inequality follows from Succay-Schwarz.
17

---

Corollary B.7. The function o; is 1 -srongly conver over A with respect to the { norm. k41
We recall the notion of Bregman divergence and state some well-known properties 2016].
Hazan
Definition B.8 (Bregman Divergence). ge K - R be a convex function defined on a convex set K Rdd Given two points 2; y K, The Bregman divergence (xll)) with respect the function defined as
(x(+)l)) = g(x) - g(v) - (Vg(y), x-
Note that convexity of implies that ( (g) 2 O.
Fact B.9 LLaw of Cosines for Bregman Divergence). Let K - IK be a convex differentiable function. Then
(Vg(y) Vg(2).y Br(x)ly) Bo(Ull2) - By(+112).
Fact B.10 (Generalized Pythagorean Theorem for Bregman Divergences). Let g K R convex, differentiable function and K" C K be convex subser. Given x E K, E K', let y E K' be a minimizer of Bylu][z). Then
(x1ly) + B,(ul22) - (x]1z).
direct application of the definition Bregman divergence and c yields: Claim B.11. Given y, Rd
Ba (Flli))
Σ Ti aaresinh
Zz
aresinh
1/1 Vi )) 3
V
29 + 82
+
Vv 32
3
We now give an upper bound on Bø, (x:ll)). v))
Lemma B.12. Let x. E A assume and | I 1. Then
(xlly) & k log(7/8).
Proof. Consider vectors and y as in the statement of the Lemma. Using Claim B.1l get
))
Bou (x|lg)) =
Σ n3 arcsinh
arcsinh
v
13
+
32
+
u? + 3
B
8
Ty arcsinh
B (y1 + 3)
x B8
1 v2
+
r; log
S k + Σ 2 log
B
/
1 /2
7
S k + & log
< k log
3
where we have used the facts that 4; S and 1.
B.3 Algorithm
Let us now recall the fractional online algorithm that we described in Section At each time f, weighted subset of points R, arrives. At time = 0, we initialize yo (which is k didimensional vector) to any arbitrary points Ro. At step I, we maintain a fractional solution y/ on the points Rec- To go from to It+1, we perform one step of mirror descent based on the 3-hyperbolic entropy regularizer defined earlier. Before taking the mirror descent step, for points in R, not Res, we set their fractional values to 0. This gives the fractional solution Bt+1 for the next iteration.
18

---

Algorithm 1: Algorithm for an instance of LEARN-BOUNDED-MEDIAA
1.1
Initialize Yo to any k points in Rg. i.e, Yo E RR with (yo); = vi [k]]
for f 1, 1.2..... IT' do
1.3
Let the points in R be Up,..., 1
14
for each x E R2 do
let az be the fractional assignment of æ to v, ie.. D(v,, E; af
Define M max 20 d(v;,
1.7
Sub-gradient Step: Define V. E IR as follows: for each i [de],
(V)):=-- :- Σ
(.(((s) min(M( d(x, vi)).
RE
Learning Rate: Set
GiVt
where G2 = maxyst <t Ve
Update Step: Define vector T++1 E Rd as follows: for each E [de].
1.9
sinh (anhharreinh((d(())) no (v))))
(It+1);=
de
where we use (y:); = 0 in the above equation for each i E [dk] \ [de-1].
Projection Step: Define
D++1 argmin Bona (ull
B.4 Analysis
In this section, we analyze the algorithm. Recall that the vector lies in Rd 1. But we shall often consider it to lie in Rd: as well by setting (ye); to for all E [de] \ [de-1].
Claim B.13. For each & [T].
1 Gt
(Vo1,a - Volid, (I(+1))
Proof. Using (6 and the definition of 24+1, have that for any [de),
(V)1) (Vo1)a( (rcs)n)(dd(ee)))) arcsinh(de(xr+)))
arcsinh(d<(wv): (arcsinb(d((21): no (V.))) (V.... M
Using the above claim, we bound the difference between Borya, (Velle (He1) and Borya, (Ve+1 [[(41))-
Claim B.14. For any time t.
Bori (2ollFe+1)) Boraa (21+1l1xe+1) S & v.
19

---

Proof. Using the using the definition of Bregman Divergence, we see that:
B0ria, (vell B (2++1ll24+11
-11/de (We) 01/d, (I++1) 01/4, (v++1) + 01/d. (x++1) ( (V01/a (I(+1)) x141 + It+1 -/++1)
-1//d (Vt) $1/4. (Vt+1) (FL+1), Mt+1)
01/4, (Ve) - 01/4, (Mc+1) (V01/d, (Bt); yot1) + (Vo1/d, (Bt). V1 36+1) (V0l/d, (xc+1), yc++1)
Cor. [...
|1y+ ye+illi (Vo1/d. (y:) Voild, (Feet)) 1/- 91+1)
2(k: + 1)
CI. B.13
2(k 1) 11ye - Me++ 7 ( v,, Ut Be+1)
Holder's ineq.
1
11 - yetilli + mel Velloollue live ye+1ll1.
2(k + 1)
The desired result now follows from the fact that the maximum value of the function f(z) 2(k+1) 2 + V is at most knj V
We now analyze the performance of our algorithm with respect to arbitrary integral solution. Claim B.15. Let y K₁ be an integral vector. Then,
(y) Coste(y:) + (V,, - we)-
Proof. Using the definition of Vt, it suffices to show that for each x E Ry:
D(r v) 2 D(a, We)
Σ(MO min(M(*) d((x,,)))) v:) (ye))))
where ((x) and as defined in Algorithm 1. For ease of notation, relabel the points in Rgg arranged in increasing order of distance from æ, i... d(x; 01) S d(x, 02) I ... I d(x, va,). Let i be the smallest index such that Eise (yr), 2 1. Observe that M()) = d(x, 0.-) and a. (y)); for all i < 1" and O for all > r" Since is an integral vector D x = d(v,, 2) for some in E [d.].
Thus, 7 is equivalent to showing:
d(x, vio) N Σ
af v.) Σ (d(2z, v..) d(x, 2/ v:)) (31)1)
*5
(uo)ddd v1) + af, u.-) - Σ (d(x, uy.) d(z, v4) v4)) - (1r)))
aff. uz.) ) + d(z, vi.) Σ (ue): Σ
(d(z, v4-) d(x, v;))
=dx, Σ (d(x, d(2r, (1)),,
(8)
Two cases arise: (i) in 2 8 or (ii) in i² In the first case, y/4 for all i < and hence, (8) follows easily because d(xx, ) d(x, uy-). ). In the second case, the r.h.s. of ( can be expressed as
d(z, vx) (d(x, v.-) d(z, v4,)) Σ
(d(x, v2-) d(x; v.))y,
d(x, vio)
Σ S
(d(x, uy.) - d(x, 0z))ss I d(x, vto)-
This proves the desired result.
Phases. We shall divide the timeline into phases, and shall bound the cost incurred by the algorithm in phase with respect to an off-line solution that only uses points revealed till the beginning of the phase. The following result bounds the cost incurred during time interval:
20

---

Lemma
3.2. Consider a time interval I = [ta, tol S [1, and let 2 be an integral vector in Kt.-
Then,
Σ
((Cost:(v)) - ( - 3(k + + 1)kAvTlog(7TH))
EEI
Cost, is at Proof. Consider time
Using Claim B.15 we get:
Cost C=st, & (V Yt 2).
Summing this over all i. E I, and using Claim B.13. we see that most
(Vdia, (y:)
V (1241).
7
Fact B.9
1
Bæra (=llya) Bos (Mel (1al)12441) Bas (#11
Fact
B.
(Beraa (ellyt) - Borsa (vel)xe+2))= - Bex (21196+1) Borsa (20+1l1re+11)
T/
:ET
Bare (zllvr) (2
Berydra (zllute)) +
+
T7-
Boria (36ll Borna (16+11122+1)
NET
Using Lemma B.12 and Claim B.14 the above expression is at most (note that de is non-decreasing function of t)
log (dd..) + A log(()d)))
Σ
1b
1
1
Σ EET
Jen
Vell
ne
Te-1
Imta
k
(og((d)rs)
V.ll..
(9)
Meo
NEI
Observe that e/ I + 1)A, and thus G. (k: 1)A. Indeed, by definition of V
I(V.) <
(,( d(r, v:)l S Σ w.A < 1)4
(10)
RER,
zER.
because the total weight of the points in R2 is at most (k + 1). Using this observation and the fact that T7- = G.Vl (9) is at most
(k + 1)A4
(k: + 1)AAV 1)AAVTlog(7d8))
+ Σ
VI
tET
The desired result now follows from the fact that dr S Tk.
We now define the phases. Let y Kr be integral solution defined by a set C' of centers. Let V = Ri U U U Rr denote the set of points that arrive over the last T timesteps. Let the centers in C' be ((1) (()),...,,((}) (k)) The set C' partitions V into subsets let ((() be the subset of V for which the closest center is (i) (we break ties arbitrarily). For a non-negative integer j. let jr be the smallest time such that the total weight of the points in v (R, U... R₂) (i.e., points in V( arriving by time !) exceeds 2/. Let wV(()) denote the total weight the points (()) Define the set P := [j:: 1 E [K].j [[og()(V())]] S [1. Observe that
IP| Σ log(w(((())) //k) I & log
(11)
21

---

because at each time t. the total weight of the arriving points is at most (k + 1). We shall treat the indices in P as subset of [1, T and hence, these partition the timeline into |P] + phases. We shall apply Lemma 3.2 for each of these phases.
In order to apply this lemma, we need to specify a candidate solution 2p for each of these phases p. We need some more definitions to describe this integral solution. For each i E [K] and index j. define ()()) = v(0) n (Rig \ Rggh i.e., the points in V whose corresponding arrival time lies in the range i.] We shall often refer the subset v bucket of V(()
For each of the set of points V2()) let zj denote the optimal 1-median solution where the center is restricted to lie in (1) only, i.c.,
(0) } == argmin sev We
Σ d(z, v).
VEV
For phase p and index E [k:], the time slots in p contained in single bucket V,(0) of V((), Let (6) ((i) denote the index corresponding to 2- in Kr, i.e., the optimal 1-median solution of the last bucket in (i) that does not intersect this phase. We are now ready to define the candidate integral solution (P) for a phase p.
Pp'
Fix phase p and let Sp denote the start time of this phase. Define integral vector g(p) Ke, as follows: for each E [K)]. we set (p) = 1 where j = x all other coordinates of 2(P) are 0 - in case there is no bucket in (+) ending before time Sp. we set (2)) be an arbitrary point. other words, this solution selects i points, namely, the 1-median center of the last bucket in V+(i that ends before Sy. This completes the description of the vector 200) corresponding to a phase p. Lemma 3.2 shows that the total cost incurred by the algorithm during phase is close to that incurred by the fixed solution (P)) Thus, it remains to show that the total cost incurred by (P) during a phase close to that incurred by y².
Lemma B.1 Consider any i [k] and index j 2 1. Then,
Σ
w wyd(a (1))))))) s 42 opt, (V UV
Proof. Consider point x E v, Using Corollary
B.3
we obtain
d(r
3-11 x) < 3
(1)
Wyr
d(x,
x')
< 3
Σ
k. 25-1 d(zx x¹),
Wy'
w(vll
a'EV(0
x' N'EV
where the last inequality follows from the fact that w/ (V(()))
(v)11) ks 20-1 Thus,
Σ
( w. (..
5
Σ
k. 2 ((,,2')
(
V (
a'Ev1o
Since the weight of the points arriving at any particular time is at most l + 1, we have the bound < 7k 2 Consequently, the r.h.s. above is at most 2
w(V (v
(1)
< k.
2i 2 2k
21
Σ
WaWWer
d(x, < 21
Σ
Wr War
d(z,x'),
wo w uv
w uv
2'EV
0 ung d'er
which is at most 42- opt (V u v() (using Fact
B.1
We are now ready bound the total cost incurred by the solution (p)) during phase
22

---

Lemma 3.3
For each P. let the start and end time of phase p be denoted sp and ep respectively.
Then, there exist solutions 2(() such that
T
ΣΣ
Cost,(2!P))
h
+
Σ
(ost(
PEPLESy
t=1
where y" is an arbitrary integral vector in Kr-
Proof. For a point (()))
let Px be the phase containing the arrival time of x. Then,
Σ
Coste
Σ Σ
D(2le), x) S Σ Σ
wad( (0) (0)-
(12)
PEP
sE(R #EV
For E 1/
d(r (1) gog
x)
s A. For 2 and x E v d(x d(rl .t) = d( 2)) Thus, the r.h.s.
of 12 is upper bounded by
Lemma B.16
Σ
A (V( (1) + Σ
Σ
(ed(zf-112)
2k A + 42 ΣΣ opt (1/ u uV
S
RE [4]
521 ZEV())
J2
$ 21 A + 84 Σ Σ wed(cr.))
(E(K] =
T
= =0 A
(ost
where we used opt, (V U UV)")) S Evevs wad(ci,)) x). This proves the lemma.
Combining Lemma 3.2 and Lemma 3.3 since there are at most O log 7) phases, we get:
Theorem B.17. Let y" be arbitrary integral vector in KT. Then,
T
Σ Cost((s')) +0 (A.A vT log(T (og((()))
Cost.
C Details about the Rounding Algorithms
In this section, we give detailed description of the online rounding algorithms described in Sec tion for the
problem. Let be the fractional solution computed by Algorithm 1 before the arrival the ( instannce RG Our rounding algorithms will take the fractional solution Yt as input and return an integer solution Y, with exactly & centers. The rounding loss is defined as the ratio of the (expected) cost of the integer solution Y, to that of the fractional solution V/-
We give rounding algorithms. The first algorithm deterministic and has rounding loss of Okk). The second algorithm is randomized and has only O(1) rounding loss. These are adaptations of existing rounding algorithms for k-median CCariiarr al. 1999 Charikar and Lij [2012); the main difference is that we need to bound the rounding loss for points we haven' I seen as well.
C.1 Deterministic Rounding Algorithm
Initially, there no centers in Y, The algorithm considers each point in Rice Ry U... R2-1 in non-decreasing order of their connection costs D(y, i), and decides whether to open a center at the current point. A center is opened at the current point (call it i) if the connection cost of i to the previously opened centers in Y, exceeds (2k + 2) times its connection cost in the fractional solution Vt- Le.,, Y, Y, (i) if D(Y,, i) > (2k: + 2) D(y,,
We show in the next lemma that the algorithm produces feasible solution, i.e., at most & centers are opened in Yú-
23

---

Lemma C.1. The deterministic algorithm produces a feasiibl solution, i.e., opens at most k centers.
Proof. For j E Yr, let B, fxr E Ret d(j.z) I (I: + 2) D(y be the ball around j of radius k + 2 times the fractional cost of j. We will show that
(a) The fractional mass points in Bj in yr is strictly greater than 1
K+I
(b) The balls B, are disjoint for different j.
Given these properties, if YY| 2 + then the total fractional mass in the balls B3 for j E Y, is strictly greater than k which a contradiction.
We show the two properties. For property (a), the fractional mass yr in By is at most x+ then j must be served at ar least K+I fraction by centers that are outside By. It follows that D) 2 1-1 (k + 2) D(y,, which contradiction. For property (b), suppose By, By overlap where j' j. i.e. J'), 2 D) Then, d(j,j') S 2(k: + 2) D'y,, which means that the algorithm will not open center at j contradiction.
For the rounding loss, note that the algorithm explicitly ensures that for any Ret, we have i) (2k 2 D(u,, i). The next claim bounds the rounding loss for points j Rg.
Lemma C.2. For any point) j E RG we have 5) S (4k: + +3 ()
Proof. Let be the point in Ret that closest to j. Clearly,
D( 2 d(i,j),
since the entire fractional mass of y, is on points in Reg, Moreover,
( i) S (y j) d(i.j).
since the RHS is at most the cost of serving using j's fractional centers. Adding the two inequalities,
we get (y 2 P(gc.), Note that there is a center in Yr that within distance (2k: + 2) D(yc. i)
of since i E R1 U R2 U..0... Ri-1. The distance from this center to is at most
(2k + 2) D(y,, i) + d(i,j) S (4k + 2) () + D(y..)) = (4k + +3 ()...)).
This implies that the rounding loss of the deterministic rounding algorithm is 4 + 3.
C.2 A Randomized Rounding Algorithm
The rounding algorithm has phases. The first phase selects a of centers Y, that might be larger than k. This phase is deterministic. The second phase subselects at most k centers from Y, to form the final solution Y. This phase randomized. The guarantee that most l centers are selected in Y, holds deterministically, but the cost of the solution will be bounded in expectation. We desribe these two phases below.
Phase 1: This phase is similar to the deterministic algorithm in the previous section but with different parameters. Initially, there non-decreasing order of their connection costs D(y, i), and decides whether to open a center at the current point. A new center is opened at the current point (call i) if the connection previously opened centers in Y, exceeds 4 times its connection cost in the fractional solution ye- Le.. Y, + Y, (i) if D(Y.. 4- (yy,
centers in Y. The algorithm considers each point in Re in
of i the
Phase 2: For any center E Yú, let r, be the distance to its closest center in Y, We define the weight of i, denoted wt, the the total fractional mass in ye in the open ball of radius 5/22 centered at i. I.c.,
Σ
yr(i)-
We start by creating matching on the centers in V.. The first matched pair is the closest pair of centers in Y, The matching continues iteratively by pairing the two closest unmatched centers in Y;
24

---

in each step. Eventually, either all centers in Yú are in matched pairs or there is a solitary center that goes unmatched. For any center E Y, that matched pair, we denote the center it got matched to by i'.
Next, we order the matched pairs arbitrarily create induced ordering on the points that satisfies the property that i, i' are adjacent. If there is an unmatched point, it is added at the end of this order. Let us call the ordering i i.......................... Ar11-- We now associate an interval with each point as follows: for point ig its associated interval is I, == ش== Why Ej=1 Way i.e., the points occupy adjacent intervals on the real line in the given order. Next, we generate value A uniformly at random from [0, 1), and add to Y, every point i, E Y, such that + 0 E I, for some non-negative integer a.
First, we establish that the algorithm is correct, i.e., Yil < k. Lemma C.3. The output Y, of the randomized rounding algorithm has at most k centers.
Proof. It sufficient to show that the sum of weights of the centers in Y, is most k. In turn, this follows if we show that the open balls B, == {i ; d(i,j) < r//2) are disjoint for different E Y Suppose not; let d(i1, i2) < Ti for i1, dg E Yg. Then, Tá, I d(i1, i2) and riz S d(d1, (2) by definition of r;- This is contradiction.
Next, we bound the rounding loss of the algorithm. Note that for any point j E Rí R2 R.U.R.U.... U..UU.UUR R,-11. we have the following explicit property from the construction of Y;:
D( 4 ())
(13)
Another important property sets a lower bound on the weight of any point:
Claim C.4. For any point E Y,, we have
2 D i)
1
wi 2 1
Ti
Therefore, for any matched pair i, i' E Y, at least one of i, is in Y..
Proof. For the first inequality, note that D(yr,)) 1) 2 0- wy + (rx/2) (1 wx) since least w; fraction of the service for i in the fractional solution comes from outside the open ball of radius r//2 centered at Re-arranging this inequality gives the first inequality.
For the second inequality, let j be the closest center to i Y, at the time that i was considered in phase 1 of the rounding algorithm. Since was added to Y,, it must be that d(i.j) 4 D i). Moreover, any center e added to Ye later in the algorithm must satisfy d(i, E) > 4 D(v,, E) 2 4 D(y,, i). Therefore, r;
(yy,, i), which implies the second inequality.
Therefore, for any matched pair i, i', their cumulative weight w; + wy > 1. This implies that at least one of i, E' will be added to Y, in phase 2.
O
We use these property to bound the rounding loss for Y:: Lemma C.5. The following properties hold:
1. For any point E Y,, we have E[D(Y,, i)] < 4- D(vr, i).
2. For any point j E Ro U...U Rr-1, 1. we have E[D(Y,, S 8. D(y,,)).
3. For any j E RR, we have E(D(Y,, 5) < 17 D(y...).
Proof. We prove each of these properties separately. Note that Pr(i E Y.) 2 min(w;, 1) in phase of the algorithm. Using Claim C.4 we have
Prli E Y1 21 2- D.y.
Moreover, with probability 1, we have D(Y.i)) < 2r,, This follows from two cases: (a) If is matched to closest point in Ye, then by Claim C.4, least one of i, is in Y. (b) Otherwise, suppose i is unmatched or it is matched to i' which not its closest point in Y,. Let j be closest point
25

---

to in Y,. Then, the fact that j was matched to j' and not to implies that d(j.j') ) - d(i,)) ri. By
triangle inequality, d(i.j") ) S 2r, and at least one of j.J is in Y, by Claim C.4
Combining the two observations above, we get
B 0) 2- ((v,, 2r, = ((y.. 1).
Ti
Next, show the second property. Consider point Rcc \ Yr. since j was not added to Y,, there exists E Y such that DY,, i) I 5) and d(i,j) 5 4 D).. Therefore,
B[D(Y, = d(i.j) + ([D(Y,, s 4 D) + 4 D i) S 8 D(ye.)), where we used the first property in the second to last inequality.
Finally, show the third property. Consider point j R4. Let é be the point in Res that is closest to j. Clearly,
(( 2 d(i,j),
since the entire fractional mass of y, is on points in Rec. Moreover,
D i) S () + d(i.j),
since the RHS is at most the cost of serving using j's fractional centers. Adding the inequalities, we get D i) & 2 (). Therefore,
E[D(Y, < i)) + d(i,)) < 8 D(y.. i) D(y..)) 17 D(y..))
where we used the second property in the second to last inequality.
This implies that the rounding loss of the randomized rounding algorithm is 17.
D
Final Bounds
We now put together reduction, fractional algorithm, and rounding procedure to obtain determin- istic and randomized algorithms for LEARN-MEDIAN. By combining Theorem 2.1 Theorem 1.17 and Lemma C.2] we have the following theorem. Theorem D.1. We give a deterministic algorithm for LEARN-MEDIAL with the following perfor- mance bound:
V.) +0 (K' AA (K vTlog(T) log(Tk))
A=1 where Y* is the best fixed solution in hindsight.
t=1
Similarly, by combining Theorem 2.1
Theorem 1.17 and Lemma C.5 we have the following theorem.
Theorem D.2. We give randomized algorithm for LEARN MEDIINN with the following expected performance bound:
T
Σ Vo) 0(1)
vV +0 +0 +O VT)o log(Tk))
where Y is the best fixed solution in hindsight.
E Detailed Experiments
In this section, we give detailed description of the experiments in Section 5) improve the performance of the rounding algorithms all our experiments, where we binary search over the best threshold on the distance to the already opened centers. For the deterministic rounding algorithm for LENRR-BBUNDDD-MEDAAN we open a new center i its distance the already opened centers exceeds (2k- 2),,, i). We can always slacken this factor of (2k + 2) to
We use heuristic to
26

---

something lower as long as the total number of centers opened does not exceed k, without worsening the theoretical approximation ratio. Similarly in the randomized rounding algorithm for LEARN- COUNDED-MEDIAN we can slacken the threshold of (3t,, 1) in the initial filtration step, long as the fractional mass in the balls we later consider are least 1/2.
We compute optimal-in-hinden under an academic license. Unless mentioned otherwise, experiments were conducted using Google Colab (code available at /ttths://ggitee
solutions for the instances using Gurobi's ILP solver, accessed
httpa///e200--coaaaaaeeerpiippes com cwm/ http///wurii2222---2 colab/ newpbis2u2pp225 using four
Intel Xeon td
CPUs (2.20 GHz) with GB of RAM each, running in parallel over about 24 compute hours. In all our experiments, the underlying metric is the Euclidean metric. Unless mentioned otherwise, we plot the ratio between Σ p(Y,, V-) and E p(Y", V-) in our approximation ratio plots, where y* the fhiimal-in-hindee
solution for the entire input sequence.
this example, the underlying metric space consists of 400 uniformly random points in the unit square [0, 1] x 0, IJ. 10 points arrive each round, chosen uniformly random, and we run the experiment with a time horizon of T' = 1000. We compare the cost of the optimal solution with the deterministic and randomized algorithms, we maintain. We generate 10 random instances in total, and report the standard deviation and mean of the approximation ratio over time. For the randomized algorithm, we first average the approximation ratio for each instance over 5 random runs of the rounding algorithm. We run this experiment with k 2,3, 6.
Uniform Square:
well as the intermediate fractional solution that
As we see in Fig. 3] both the randomized and deterministic algorithms converge to natural solutions, distributed roughly uniformly over the unit square. The approximation ratio also approaches especially after the influence of the initial additive regret declines.
Uniform All Solutions
Uniform Square Approximation ost (k=2)
Determinizzic (mean)
Randomized (mean)
OPT
Fractional [meon)
L.3
Time
Uniform Square: All Salutions (k
Uniform Squere: Approximation (k=3)
Deterministic (meon)
Randomized (mean)
Practional [mean]
X0
1300
Time
Uniform Square: All Solutions (k 6)
Uniform Square: Approximation os (km6)
Deterministic (mean)
Randomized (mean)
Fractional (meen)
Figure 3: (Uniform Square): The optimal (black plus), deterministic (blue cross), and randomized (red diamond) solutions for one of the random instances (left) and approximation ratios avg. and std. dev. over 10 random instances (right) for k = 2.3.6 6.
27

---

Uniform Rectangle: In this example, the underlying metric space consists of 400 uniformly random points in the rectangle [0. 1] x [0, 10). 10 points arrive each round, chosen uniformly random, and we run the experiment with time horizon of 7 = 1000. We compare the cost of the optimal solution with the deterministic and randomized algorithms, as well as the intermediate fractional solution that we maintain. We generate 10 random instances in total, and report the standard deviation and mean of the approximation ratio over time. For the randomized algorithm, we first average the approximation ratio for each instance over 5 random runs of the rounding algorithm. We run this experiment with 2,3,6 6.
As we see in Fig. 4 both the randomized and deterministic algorithms converge to natural solutions, distributed roughly uniformly over the rectangle. The approximation ratio also approaches 1, espe- cially after the influence of the initial additive regret declines.
Uniform Rectangle: All Solutions (k
Uniform Rectangle Approximation Rat (k=2)
Deterministic (mean)
Randomized (mean)
Fractional (meen)
150
Uniform Rectangle: Solutions
Uniform Rectangle Aspreximation Rat (k-3)
Deterministic (mean)
Randomized (mean)
OPTT
Frreciional [meen)
L.3
L33
Time
Uniform Rectangle: All Solutions (k
Rectangle Appreximation Rat (k-6)
Deterministic (mean;
Randomized (mean)
Fractional [meen]
Time
Figure 4: (Uniform Rectangle): The optimal (black plus), deterministic (blue cross), and randomized (red diamond) solutions for one of the random instances (left) and approximation ratios avg. and std. dev. over 10 random instances (right) for 2, 3, 6.
Multiple Clusters: In this example, the underlying metric space consists of k clusters with center in the unit square [0, 1] [0. 1]. The cluster centers are chosen uniformly random from the unit square, and we then generate points in radius of 0.05 around each cluster center, for a total of about 400 points. 20 points arrive each round, chosen uniformly random, and we run the experiment with a time horizon of T = 1000. We compare the cost of the optimal solution with the deterministic and randomized algorithms, as well as the intermediate fractional solution that we maintain. We generate 10 random instances in total, and report the standard deviation and mean of the approximation ratio over time. For the randomized algorithm, we first average the approximation ratio for each instance over 5 random runs of the rounding algorithm. We run this experiment with A 4, 8, 12, 16.
28

---

Multiple Clusters: All Solutions 4)
Multiple Clusters: Approximation Ratios (k=4)
Deterministic (mean)
Randomized (mean)
15.
Fractional (mean)
ALG OPT
24
2.3
400
600
1000
Time
Multiple Clusters: Solutions
Multiple Clusters: Approximation Ratios (k=
18
Deterministic (mean)
12.
Randomized (mean)
Fractional (mean)
ALG OPT
23
14
13-
1000
Time
Multiple Clusters: All Solutions (k 12)
Multiple Clusters: Approximation Ratios (k-12)
20-
Deterministic (mean)
Randomized (mean)
Fractional (mean)
ALG
1.-
14-
Time
Multiple Clusters: Solutions (k 16)
Multiple Clusters: Appraximation Ratios (k-16)
Deterministic (mean)
26.
Randomized (mean)
2.-
Fractional (mean)
ALG OPT
3.9
2.-
188
16
34
202
420
600
800
1000
Time
Figure 5: (Multiple Clusters): the optimal (black plus), deterministic (blue cross), and randomized (red diamond) solutions for one of the random instances (left) and approximation ratios avg. and std. dev. over 10 random instances (right) for = 4, 8, 12, 16.
Once again, as we see in Fig. 5 both the randomized and deterministic algorithms converge to natural solutions, with centers distributed over the different clusters. The approximation ratio also approaches 1, especially after the influence of the initial additive regret declines.
Uniform Hypersphere: In this example, k and the underlying metric space consists of 400 points: one point is the origin and the rest are chosen uniformly at random from the unit hypersphere. We run the experiment with a time horizon of T = 2000. For the first 100 rounds, each instance consists of 10 points chosen random from the boundary the hypersphere. However, in the next round we also include the origin in the instance, thus revealing the origin to our algorithm. We then
29

---

Mass Evolution Hypersphere
10-
Fractional Mass
0.-
0.6-
d 2: Origin
8: Origin
0.4-
530
Time
Figure 6: (Uniform Hypersphere): Fractional mass of algorithm over time at the center (avg. and std. dev. over 10 runs), d = 2,
continue generating instances as before. We do this for for 2 different dimensions of the hypersphere (d 2, 8). We generate 10 random instances in total, and report the standard deviation and mean of the total mass that the fractional algorithm places on the origin.
As we see in Fig. 6 the fractional mass is initially fully on the boundary, but once we introduce the origin the mass slowly shifts to being just on the origin. This happens because the origin is a better solution for the instance sequence compared to any solution solely on the boundary. Moreover, this transition is more rapid for higher dimensions, as typical distance between 2 random points on the hypersphere increases with dimension. On the other hand, the distance from the origin to the hypersphere boundary is always 1.
Oscillating Instances: In this example, the underlying metric space consists of 2 clusters with 10 points each. The 2 clusters are generated by picking points uniformly at random from squares of side length 0.4 centered at (0, 0) and (1, 0) respectively, and we run the experiment with time horizon of T 33. The instance sequence alternates between the first and second cluster, where we give the first cluster for the first 3 rounds, then the second cluster up the 9th round, then the first cluster up to the 27th round, and so on. One difference in this example is that we compare our performance against the dynamically optimal fractional solution as opposed to fixed that is, for each time step we compare against the best fixed solution for the instances so far. That
-iiiddiiihgh integer solution:
is, we plot the ratio between E' P(U+, V+) and Σ ((OPT, V7), where OPT, is the best fixed fractional solution for instances Vi,-.. Vi and y, is the intermediate fractional solution We also study how the fractional mass of the (dynamic) optimal solution and the algorithm in the first cluster changes over time in order to obtain qualitative understanding of how the algorithm shifts its centers towards new points that arrive. We run this experiment with k = 1, 2, 3,
maintain.
As in Fig. ks 1, the algorithm starts shifting fractional mass before the optimal solution. Consequently, our algorithm ends up outperforming the optimal solution in the time horizon that we consider, as seen from the approximation ratio plots. For h 2, 3, 4, we observe that the algorithm quickly moves a unit of mass to the cluster that is currently arriving, and then slows down as the gain in increasing the fractional mass the cluster is minimal.
Scale Changes: In this example, the underlying metric space consists of 5 clusters with 10 points each. The clusters are generated by picking points uniformly at random from squares of side length 0.4 centered at ([10r-1 0) for i = 0, 1, 2, 3, 4, and we run the experiment with time horizon of T= 35. In this example, we have 5 clusters with 10 points each, with time horizon of T = 3 The instance sequence iterates through the clusters, where we give the first cluster for the first 3 rounds, then the second cluster up the 9t round, and on. We study how the fractional mass of the algorithm in the cluster that is currently arriving changes over time in order to obtain a qualitative understanding of how the algorithm shifts its centers toward new far away points that arrive. The approximation ratios plotted are between Σ P(y-, Vz) and Et pOOP,,, V-), where OPT, is the best fixed fractional solution for instances Vi,..., ..., V/ and y, is the intermediate fractional solution we maintain. We run this experiment with k- 3,
As we see in Fig. g we once again see that for k = 1, the fractional algorithm ends up outperforming the optimal solution. For k = 2, 3, we observe that the algorithm quickly moves unit of mass to the
30

---

Fractional Mass in Clusters IK
Dynamic Approslmation Ratio (k- 1, tractional)
ALGitDynamic OPT! 10 6o
Fractional Mass
12
Mass Cluster 1 (ALG)
Cluster (OPT)
Time
Time
Fractional
Dynamic Approximation fractional)
Mass Cluster 1 (ALG)
1.
Mass in Cluster 1 (OPT)
ALGi OPT)
Fractional Masss
25
0.1
Time
Time
Fractional Mass in Clusters
Dynamic Approximation Ratio fractional)
Mass in Cluster 1 (ALG)
Mass in Cluster 1 (OPT)
ALGiliynamiccmm OPT)
Frectional Mass
2:3
223
1.7
1:0
123
1.0
10
23
150
288
100
15c
250
Time
Time
Fractional Mass in Clusters [k 4)
Dynamic Approximation Ratio [k= 4, fractional)
Mass Cluster 1 (ALG)
(OPT)
ALs/(Dynamic OPT)
Fractional Mass
25
10
23
330
250
200
250
200
150
200
250
Time
Time
Figure 7: (Oscillating Instances): Fractional of algorithm and OPT time in one of the
clusters (left) and corresponding dynamic approximation ratios (right), for k = 1,2,3,4.
cluster that is currently arriving, and then slows down rapidly as the gain in increasing the fractional mass on the cluster is very minimal. The change is even more rapid this case compared to previous experiment due to the large scale changes which lead to larger gradient norm, and hence more conservative learning rate.
One question that arises from the approximation ratio plots for k = 2,3 3 is the large approximation factor, but this can be explained by the additive term that is quite large this case. For k > the dynamic optimal solution immediately shifts center from the previous clusters to the new one it a much better solution for the sequence so far, while the algorithm accrues large cost until it shifts a mass of one into the new cluster. To illustrate this, we run the experiment again for k = 2. with 4 clusters and a time horizon of
50000 (we only use 4 clusters this time due to computational reasons, the time required for the additive term to be insignificant grows with A). where we continue giving the th cluster even after the first rounds. We see that approximation ratio eventually approaches 1, see Fig.
31

---

Fractional Mass in Clusters IK
Dynamic Approximation Rabio 1, fractiona))
ALGiDynaamc OPTI
fractional Mass
ALG mass Cluster
ALG mass Cluster
ALG mass Cluster
25
Cluster
Cluster
Time
Time
Fractional
Dynamic Approximation fractional)
4.2
1.7%
Fractional Mess
1.30
mass Cluster
Cluster
1:23
ALG mass Cluster
ALG//Dynamic 8
1.00
0.5
0.3
3.2
Time
Time
Fractional Mass in Clusters Ik
Dynamic Approximation Ratio 3, fractional)
Cluster
ALG/tDynamic OPT)
300
Fractional Mass
23
Cluster
200
500
Time
Time
Figure 8: (Scale Changes): Fractional mass of algorithm over time in one of the clusters (left) and corresponding dynamic approximation ratios (right), for k = 1,2,3.
Dynamic Approximation fractional)
Dynamic Approximation fractional)
ALG//Dyammic OPT)
ALG/(Dynamic OPT)
40
Time
Time
Figure 9: (Seale Changes): Dynamic approximation ratio plots with T = 550000, for = 2, 3.
Small Drifts: In this example, the metric space consists of 2500 points, and we run the experiment with time horizon o' 250. The underlying instances are created by randomly drawing 10 points (out of which 5 random points arrive in round) in disc centered around the origin, but then shifting the center of the disc to the right by 0.02 for each instance. We compare the cost of the optimal solution with the deterministic and randomized algorithms, as well as the intermediate fractional solution that we maintain. We generate 10 random instances in total, and report the standard deviation and mean of the approximation ratio time. For the randomized algorithm, we first average the approximation ratio for each instance over 5 random runs the rounding algorithm. We run this experiment with k 1, 2,
As we see in Fig. TO the final average approximation ratios were less than in all cases. (In contrast, if the algorithm were use the initial solutions throughout, i.c., does not automatically adapt the
32

---

drift, then the cost ratios in each round are around 5-15.) The approximation ratio is small initially as we compare against the optimal-in dedimal-n--iindiieee solution for the entire input sequence.
Small Drffts: All Solutions (k 1
Small Drifts: Approximation Ratios (k=1)
023
Deterministic (mean) Randoriized (mean)
Fractional [mean]
-142
Time
Small Drifts: All Solutions (k 2)
Small Dritts: Approximation Ratios (k=2)
023
Deterministic (mean) Randomized (mean) Fractional [mean)
-539
-185
Time
Small Drifts: All Solutions (k =
Small Drifts: Agpresimation Ratios (k=
Deterministic (mean)
602
Randomized (mean)
635
Fractional (mean)
-03
-380
Time
Figure 10: (Small Drifts): The optimal (black plus), deterministic (blue cross), and randomized (red diamond) solutions for of the random instances (left) and approximation ratios avg. and std. dev. over 10 random instances (right) for A: = 3,
Finally, note that the time complexity of our learning algorithm (besides the reduction step) is O(k273), independent the number of points n. To empirically confirm scalability, we ran experiments with observed that the running time of the learning algorithm (besides the reduction step) was always 2-3 seconds on Google Colab (2.20 GHz Intel@ Xeon@ CPU, 51 GB RAM).
1000, 2000. 6000 while keeping k. T fixed (k 5, T 100) and
33

---

F Lower Bounds
In Theorem 1..1 we gave efficient deterministic algorithm for LEARN-MEDIAL with multiplica- tive O(k) approximation factor and sublinear regret. We now give an information theoretic lower bound that states that any algorithm for LEARN-MEDIAN with sublinear regret must incur (2(k) multiplicative factor loss.
Theorem F.1. Any deserministic algorithm for the LEARN-MEDIAE problem cannot achieve multiplicative o(k) approximation guarantee with an additive regret term that is sublinear T. That is, any bound as below is impossible
T Elo Vi) S o(k)
T
Σ
Σ t=1
(14)
where Y is any fixed solution for LEARN-MEDIAN. Moreover, this holds even when the metric space is known upfront.
Proof. The lower bound result is inspired by the competitive ratio lower bound for deterministic online paging, Suppose for the sake of contradiction that there is an online algorithm A that outputs solution Y, time and satisfies the condition (14). We now describe our hard instance M (V, d). The underlying metric space M consists of = 2(k: + 1) points. It contains & + 1 different clusters of 2 points each, such that the distance between any points belonging to different clusters is A > The distance between any 2 points in the same cluster is 1.
We construct sequence of sub-instances Vo, Vo,...; VT in adversarial fashion: consider round I, and let Y be the set of centers outputted by A in round L. Since there are k + clusters in the metric space, it follows that there is always least 1 cluster which does not overlap with Y,. Thus, clusters. For the round zero, we just
given y, define VE to consist this cluster and any other take Vo to be the entire metric space.
Clearly, AA must suffer a cost of at least 2A for each round after round zero. This is because the &
optimal solution for Vi places exactly 1 point in each of the i clusters with total connection cost of k, while Yú must have a connection cost of at least 2A as it doesn't 't place any center in one of the clusters present in V.
Let us now examine the optimal fixed solution hindsight for this adversarial input sequence. The optimal solution places 1 center each in the & clusters that appear the most frequently. Thus, it suffers a total cost most 2AT Putting it together and using (4). we have
(k+1)K
2AT I o(k)
2AT
(k,
k
(k 1)k:
or equivalently,
2 + 1) < o(k) 2A
k(k
1),
T
which gives a contradiction as 7 - 0o as ks n, are fixed parameters of the underlying metric space.
We now extend the above result the setting where the online algorithm is randomized: again, we show that the result in Theorem D.2 essentially tight, i.e., any randomized algorithm with sublinear additive regret must incur a constant factor multiplicative loss.
Theorem F.2. Any (randomized) algorithm for the LEARN-MEDIAN problem cannot achieve multiplicative (1 + e) approximation guarantee with an additive regret term that sublinear in T. That is, any bound as below is impossible
Σ Elp(Y. Vo) (1++)
(15)
where 0 I is arbitrary constant and Y is any fixed solution LEARN-MEDIAN.
34

---

Proof. Suppose for the sake of contradiction that there is an algorithm A that satisfies (5) for some constant 0 S E 1. We first describe our hard instance M = (V,d). Our metric space M consists of n = mk points, m >> k. It contains k different clusters of m points each, such that the distance between any points belonging to different clusters is A >> k. The clusters themselves are star graphs with m 1 leaves and center point, the distance between any 2 leaves being 2 and the center-leaf distance being
We construct our sequence of sub-instances Vo...., VT in an adversarial fashion. In round zero, we just take Vo to be all the leaves. For = l..... T 1. Vi consists of randomly chosen leaves from each cluster. For the last round, we take V7 to be all the cluster centers and one other leaf.
We claim that the algorithm A must suffer expected loss of at least 4(1 3/m) in each round from 1 to 7-1. Let Y, be the subset of size l selected by A in round f. If Y, does not contain a point from each of the clusters it has connection cost of at least A for round otherwise Y; contains exactly one point from each cluster. For a given cluster, the probability that the point in Y, doesn't 't belong to the two points this cluster in V₂ at least (1-1/m) (11mmm)(1-2) 1-2mm) 2 1 1-3/m. Thus linearity of expectation implies that the expected connection cost of Y2 is at least min A, 4k((1 - 3/m)} 2 4k(1 - 3/m). On the other hand, the optimal connection cost for V,, 1 S T is corresponding to picking 1 of the chosen leaves from each of the clusters.
Let us now examine the optimal fixed solution in hindsight for this adversarial input sequence. We claim that it suffers a total loss of at most 2T. Indeed, consider the fixed solution Y that picks each of the cluster centers, it suffers loss of 2 for each round from to T 1. This because its connection cost
in the last round as it is the optimal solution for Vr, and
suffers a loss of at most is at most 2k, and the optimal connection cost for V,, 1 < ( < T - 1 is k. corresponding to picking I of the chosen leaves from each of the clusters. Putting it together, we obtain
4(T 1)(1 3/m) < (1 + c) 27 (TT) n,
or equivalently,
T
(T)
2 6/m S (1+
/ [kk n,
T-1
2(T - 1)
which gives a contradiction by taking m large enough that 2 - 6/ m > + 6 and then taking T -> oo.
Finally, we show that an additive loss of (kk) is unavoidable if the multiplicative loss a constant.
Theorem F.3. Any (randomized) algorithm for the LEARN-MEDIAN problem must suffer ((kA)
additive loss even when allowing for O(1) multiplicative error. That is, any bound as below is impossible
Blp Vo) S 01) Σ p(Y, V.) + ((k2)
(16)
where Y is any other fixed solution for LEARN-MEDIAN.
Proof. Suppose for the sake of contradiction that there is an algorithm AA satisfying (66). We first describe our hard instance M (V, d). The metric space M consists of n mkk points, >> k. It contains & different clusters of m points each, such that the distance between any points belonging to different clusters is A >> 1. The distance between any 2 points in the same cluster is 1.
Take T 1 and V. to be the (t (1+1) 1)th cluster for 0 < k - 1. The algorithm A must suffer a loss of at least
mA m 2 A/2 for each round t after round zero. This is because it has not seen the (L [++] 1)ahh cluster at time / and hence cannot place any center there, thus suffering a connection cost of at least mA, and the optimal solution for Vú consists of l points from the same cluster, with a total connection cost of m k. Thus, the total loss suffered by the algorithm is at least (k-1)A
On the other hand, the optimal fixed solution in hindsight places center in each of the i clusters. suffering loss of m-1 < 2 each round after round zero. Thus, the total loss suffered by the optimal m-k solution is at most 2 1). Putting it together, we obtain
35

---

1k-1)A 2 S 0(() 2 1) + o(kA)
which gives a contradiction as A + 00, as desired.
Approximate Follow-the-Leaderr So far we have given information theoretic lower bounds on the multiplicative loss and the additive regret term for any online algorithm. Follow The Leader (FTL) another commonly used algorithm - at each time t, output Y, that minimizes the total cost Eneg ci cOst, (Y,). In our setting, computing the optimal cost (i.e., cost of an optimal k-median instance) is NP-hard. Thus, a natural extension of this approach would be Approximate FTL: each time t, output Y, that is a constant factor approximation to the objective function Ei= P(Y, Vv.). We show strong lower bounds for this algorithm even when k = 1:
Theorem F4. Approximate FTL cannot achieve o(log A/ log log A) multiplicative approximation guarantee with sublinear regret even when ho = 1, i.e., any bound as below impossible:
T Σ p(r.V) S ollog A/ log A) Σ
T
(17)
where Y₁ is the set of centers outpuited by Approximate FTL at time t and Y is an arbitrary set of k: centers.
Proof. For case of notation, assume that Approximate FTL uses 4-approximation algorithm for the (off-line) k-median problem the argument remains similar for any constant approximation algorithm. We shall also fix k = 1.
now describe the metric space M. .M consists of star graph with 2 leaves, where À is a parameter that we shall fix later. At each of the leaves, we have two vertices that are at distance 2 from each other (thus, M given by the shortest path metric on a two level tree, where the root has 2λ children and every node at the first level has two children). Let the children of the root be labeled Ui...., 222 The two children of os are labeled ea and v². The edge (r, v;) has length A; = A. where A 2 (assume À >> 1).
At time 1 = O, we give the entire metric space as the instance. The subsequent input sequence is divided into 2 phases. For each time phase h E [2X], the input Vi consists the two points v/ and v Phase h lasts for Ta = XTo timesteps, where To 1. Note that A T,A for all E [2x].
The off-line solution Y places a center at the root of the star. Thus, for any time t in phase h, p(Y, Vi) 2(A++1) Dn + 1. Thus, see that
Σ (Y.V _ Th +1) 2XT 3XT
(18)
because T E, ATo S 2X S ATo and the number of phases is 2X.
Now, we estimate the corresponding quantity for Approximate FTL. Consider a phase h. The median instance at a time t in this phase consists of Tie points at each of u and v7 for h' < and a certain number of points the children of vh. Since T2 To for all h, we claim that this 1 I-median instance has optimal cost at least (h 2.T,A. Indeed, consider a 1-median solution that places a center at the root or at vy or children. Then all points v/. and uf.- where h S h - 1, h & h, incur a cost at least 2T, = T,A. Now, consider the solution that places center at Uh-1 (at any time during phase ft). Again it is easy to see that its total cost at most (/4-2)A444 +2(2) 1)44X)44) < ATA(22) 3 2A), which is at most 4((h - A) when h 2 X + 3,
and hence is a 4-approximation for h E + 3,2X
Thus, we can assume that for any phase 2 + 3. A outputs 8 as the 2-approximate 1-median center. Now consider such phase h: at each time during this phase, optimal cost for V2 is 2, but
36

---

the algorithm incurs at least 2 2 Thus, p(Y,, Vo) 2 AAn. Summing over all times in this phase, we that
Σ
p(Y, 2 ATR = X7.4.
in phase h
Summing over all the phases h 2 + 3 (note that there are such phases), we get
X
Σ
PY,, V4)
2
2 ToA
in phases h 3+3
The result now follows from the above and inequality To parameter independent of n, k, A).
18 (note that À = 0(log A/ log log A) and
37

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: All our claims have corresponding theorems and formal proofs in the main text or appendix.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We discuss that our techniques are tailored for metric problems, and leave extensions to other domains as interesting future work (see SSeciin
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sellsspeciiiationn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
38

---

Answer: [Yes]
Justification:
All our theorems have formal proofs in the main text or the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: The code used for the experiments is available https: com/ neurips2025- colab/ wwwaa/ neurips2025 along with instructions.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
39

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The code used for the experiments is available htttss://github.com neurips2025-com wwwppaawwww..n//0....... along with instructions.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cc.
cablic//uuides/Codeeubbbss wtw.eeeewuumissiiooooooooo for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ wwtps/cccppllggggiiieeeeeec
Saaeee//CoSSSSbisssS.S.. wsw.sssoiccgyyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
All the details of the experiments are described in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We report the standard deviation of the mean across multiple runs when appropriate in our experiments, in particular when running our algorithms on randomly generated instances.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
40

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπτог rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Although our experiments do not require much compute, we describe the resources used to run them in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: All the authors have read and reviewed the Neurips Code of Ethics and have conformed to it.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., s if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This is mostly a theoretical work.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
41

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), faimess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our work is unlikely have significant negative downstream impacts, consid- ering its theoretical nature.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging. and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
We use Gurobi with an academic license to compute optimal integer solutions.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
42

---

If assets are released, the license, copyright information, and terms of use in the thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, datasets.papersstt paperswi
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is available online, the authors encouraged to reach out the asset's s creators.
13. New assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The code used for the experiments is available httts:///itthb:: com/ along with instructions.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
43

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
The authors only use LLMs for minor editing of LaTeX and coding purposes.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy battps://neure http://rrriis.ccooofeeeeeeee//// cc///onnfereeccc//225////.. for what should or should be described.
44


Reviews:
[{"review_id": "ZQWxNUriYe", "reviewer": "Reviewer_vt4Z", "summary": "This paper addresses the k-median clustering problem in an online setting. The input is an online sequence of instances (point sets in a metric space) $V_0, V_1, V_2, \\ldots, V_T$ that arrive one by one. At any time point $t \\leq T$, it is assumed that the algorithm has access to the prior instances $V_0, V_1, V_2, \\ldots, V_{t-1}$. The algorithm uses the knowledge of these prior instances to compute a k-median solution $Y_t$, which is then applied to instance $V_t$ and evaluated for loss. The overall goal is to minimize the total loss over the entire sequence, i.e., to minimize $\\sum_{t} P(Y_t, V_t)$, where $P(Y, V)$ denotes the cost of using center set $Y$ on point set $V$. The main result of the paper is an $(\\alpha, \\beta)$-approximation to the optimal solution, which is defined with respect to the so-called “best fixed solution in hindsight.” Let $Y^*$ be the set of k centers that minimizes $\\sum_{t} P(Y^*, V_t)$. The proposed algorithm computes $Y_t$ for all $t$, such that $\\sum_t P(Y_t, V_t) \\leq \\alpha \\sum_{t} P(Y^*, V_t) + \\beta$, \nwhere $\\alpha = O(1)$ and $\\beta = o(T)$, and $\\beta$ depends polynomially on the spread ratio $\\Delta$ and $k$.", "questions": "Questions:\n\nIs there justification that the method indeed learn from previous instances?\n\nWhat is the justification of several problem settings. For example, what is the justification for evaluating the cost of $Y_t$ on $V_t$ only, rather than over a cumulative set (e.g., $V_0, \\ldots, V_t$)?", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 1, "strengths_and_weaknesses": "Strengths:\n\nThe paper addresses a new variant of the k-median problem in an online setting with theoretical guarantee.\n\n\nWeaknesses:\n\nIt could be misleading to claim the result as learning-augmented. From the perspective of learning-augmented algorithms, I do not believe the result really captures the spirit of \"applying machine learning techniques on prior problem instances to inform algorithmic decisions for a future instance.\" In fact, the proposed algorithm makes no assumptions about the structure or distribution of the prior instances $V_i$. In an extreme case, even if the $V_i$'s are entirely unrelated—so that, in principle, no useful information can be learned from earlier instances to aid future ones—the $(\\alpha, \\beta)$-approximation guarantee still holds (!). This suggests that the theoretical guarantee presented in the paper does not stem from any learning from prior instances.\n\nAs a result, the contribution seems more accurately classified as an analysis of a certain class of online algorithms, rather than as a learning-augmented result. Specifically, it addresses the question: if at each time step $t$, the algorithm is restricted to accessing only the previous instances $V_0, V_1, \\ldots, V_{t-1}$ to compute $Y_t$, how can we minimize the total cost of using $Y_t$ on $V_t$?\n\nHowever, even if we evaluate the work purely as a theoretical result—without the learning-augmented perspective—the problem formulation still seems confusing. It is unclear why the objective focuses on the cost of $Y_t$ with respect to $V_t$, rather than, say, with respect to $V_0, \\ldots, V_t$. Moreover, the definition of the optimal solution $Y^*$ is somewhat puzzling: it does not make sense to me to use a fixed $Y^*$ for all $t$ as the optimal solution. It seems more natural to define an optimal solution $Y^*_t$ for each time $t$, and then compare $Y_t$ to $Y^*_t$.\n\nPresentation can be improved: The algorithm description in Chapter 3 lacks a high-level description of the main idea, making it difficult to follow\n\nExperiment: Relies solely on synthetically data (however, given the aforementioned issues with the algorithm's ability to learn from data, I would suspect the use of real-world data would likely make little difference in the results). The experimental section also lacks a clear summary about the implications of the experiment results.", "was_revised": true, "final_justification": "The authors have addressed all my concerns in their rebuttal and during the communication period. For this reason, I have raised the score from 2 to 4.", "rebuttal": "We thank the reviewer for the detailed review. We address the questions below.\n\n**R:** It could be misleading to claim the result as learning-augmented.... This suggests that the theoretical guarantee presented in the paper does not stem from any learning from prior instances.\n\n**A:** Our framework is based on the well-studied online learning framework; see the standard textbook below (reference [*Hazan 2016*] in our paper):\n\n[*Hazan 2016*] *Elad Hazan. Introduction to online convex optimization. Foundations and Trends in Optimization.*\n\nOnline learning has a vast literature with no distributional assumptions on the inputs across different rounds (chapters 1-5, 7, 10 in [*Hazan 2016*] and references contained therein). As in online learning, our paper makes no distributional assumption either.  In online learning, the algorithm chooses an action for the (unknown) instance in the current round based on the outcome for prior rounds. Similarly, in our paper, the algorithm chooses a $k$-median clustering solution for the (unknown) instance in the current round based on the instances in the prior rounds. Indeed, learning-augmented algorithms in the online learning framework have been considered in prior work (reference [*Khodak et al. 2022*] in our paper):\n\n[*Khodak et al. 2022*] *Misha Khodak, Maria-Florina Balcan, Ameet Talwalkar, and Sergei Vassilvitskii. Learning predictions for algorithms with predictions. NeurIPS 2022.*\n\nThe main difference between this work and ours is that they use prior instances to learn a prediction for the current round, while we use the instances directly to learn a solution for the current round. Moreover, they consider problems such as ski rental, bipartite matching, and scheduling, while we focus on the $k$-median clustering problem. \n\nIn [*Khodak et al. 2022*], as well as in online learning in general, a sequence of instances are presented to the algorithm (with no distributional assumption), and it must produce a solution for the next instance based on the prior instances. The goal is to compete with the best fixed solution in hindsight. This is exactly the setting that we consider in our paper. The intuition in online learning is that if the instances are related, then the benchmark cost (of the best fixed solution) is lower, while if the instances are unrelated, then the benchmark cost is higher. The $(\\alpha, \\beta)$ guarantee holds for any sequence of instances, but in the former case, it leads to a smaller cost bound for the algorithm while in the latter case, it leads to a larger cost bound. Again, this is the same as in the entire literature in online learning.\n\nWe emphasize that our setting is not directly analogous to a prediction-based learning-augmented algorithm (we mention this in the first paragraph of related work in the paper). Indeed, in many papers using explicit predictions, the source of the prediction is vaguely attributed to prior instances, e.g., the survey (reference [Mitzenmacher and Vassilvitskii 2020] in our paper):\n\n[*Mitzenmacher and Vassilvitskii 2020*] *Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. Chapter 30, Beyond the Worst-Case Analysis of Algorithms. Cambridge University Press.*\n\nand other works such as these references from our paper, including for clustering problems such as $k$-means and facility location:\n\n\n[*Ergun et al. 2022*] *Jon C. Ergun, Zhili Feng, Sandeep Silwal, David P. Woodruff, and Samson Zhou. Learning-augmented k-means clustering. ICLR 2022.*\n\n[*Jiang et al. 2022*] *Shaofeng H-C. Jiang, Erzhi Liu, You Lyu, Zhihao Gavin Tang, and Yubo Zhang. Online facility location with predictions. ICLR 2022.*\n\n[*Lykouris and Vassilvitskii 2021*] *Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. Journal of the ACM, 2021.*\n\nIn our paper, we make the source and role of side information (such as predictions) more transparent by showing that we can use online learning on prior instances of the $k$-median problem to inform solutions for future instances of the problem.\n\n**R:** Moreover, the definition of the optimal solution $Y^\\star$ is somewhat puzzling: it does not make sense to use a fixed $Y^*$ for all $t$ as the optimal solution. It seems more natural to define an optimal solution $Y_t^\\star$ for each time $t$, and then compare $Y_t$ to $Y_t^\\star$.\n\n**A:** The benchmark considered is the best fixed solution in hindsight, which is standard in online learning. As in online learning, no algorithm can be competitive with a benchmark that uses a separate solution for each instance. Such a benchmark would have a cost ratio of $1$ for every instance, i.e., would be optimal for every instance. In contrast, an algorithm trained on prior instances can have an arbitrary approximation bound on the next instance. For example, suppose $k=1$ and we receive a concentrated cluster of points in each instance that is far away from all previous instances. An algorithm trained on prior instances cannot predict where the new instance is going to be and hence will have arbitrarily large cost on it, whereas an optimal solution specifically for this instance will have a cost ratio of $1$. This is not specific to our model, but a general feature of any online learning setting, see e.g., Chapter 10 in [*Hazan 2016*].\n\n\n\n**R:** What is the justification for evaluating the cost of  $Y_t$  on $V_t$ only, rather than over a cumulative set (e.g., $V_0, …, V_t$)?\n\n\n**A:** We evaluate the cost of the solution on $V_t$ instead of the historical instances because the algorithm gives the solution $Y_t$ specifically for the next instance $V_t$. This solution is not intended to be used for prior instances $V_0, V_1, \\ldots, V_{t-1}$ that are already in the past at time $t$. This setup is standard in the online learning literature.\n\n\n**R:** Presentation can be improved: The algorithm description in Chapter 3 lacks a high-level description of the main idea, making it difficult to follow. The experimental section also lacks a clear summary about the implications of the experiment results.\n\n\n**A:** We will add details and intuition giving a high-level overview of the algorithm. The main takeaways from the experiments are described at the end of Section 1.1. We will also add a summary of the takeaways from the numerical simulations in the experimental section."}, {"review_id": "IQ5yO1saQA", "reviewer": "Reviewer_v3YS", "summary": "This paper studies an online learning setting of the k-median problem. The setting considers a sequence of instances, each corresponding to a classic k-median problem. Before the realization of each instance, the algorithm must select k centers. Its performance is measured by the cost ratio between the algorithm's solution (i.e., the total distance from points to their nearest centers) and the offline optimal solution that has access to all data in advance. The goal is to achieve an $(\\alpha,\\beta)$-approximation with respect to the cumulative cost ratio, where $\\alpha$ denotes the multiplicative factor and $\\beta$ is the additive term. \nThe paper proposes two algorithms:\n- A deterministic algorithm with $\\alpha = O(k)$ and $\\beta = o(T)$\n- A randomized algorithm with $\\alpha = O(1)$ and $\\beta = o(T)$\n\nThe paper also prove that these results match the lower bounds. \n\nThe proposed approach begins by deriving an online fractional solution to a reduced version of the original problem that involves only k points. The final algorithms (deterministic or randomized) are online rounding schemes applied to this fractional solution. The paper also includes experiments on synthetic data to illustrate performance.", "questions": "- Could you provide a concrete application scenario for the online learning setting over multiple k-median instances? In particular, (i) Why is an online setting necessary? (ii) Why is the cost ratio of each instance more relevant than the absolute cost?\n\n- How does this work compare to the data-driven algorithm design framework in the online setting? What are the key differences, and why wouldn't existing techniques from that literature apply here?\n\n- A key step in the algorithm is to reduce the original problem to one with only k points. Why is exactly k chosen? Would it be possible (or even beneficial) to reduce the problem to fewer or slightly more than k points? How would this affect performance or complexity?", "limitations": "NA", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength\n- The proposed algorithms achieve tight bounds on both multiplicative and additive approximation factors for deterministic and randomized algorithms.\n\n- The paper presents several nice ideas, including: (i) reducing the original problem to a smaller instance with only k points to manage computational complexity, and\n(ii) using a novel regularizer to address the challenge of an expanding solution space in the online setting.\n\n\nWeakness\n- The motivation behind the performance metric could be clearer. The $(\\alpha,\\beta)$-approximation is defined on the cumulative cost ratios, which is less standard compared to bounding the cumulative cost directly. Additionally, the benchmark used is static, which is a bit weak.\n\n- Although the paper refers to learning-augmented algorithms, it more closely aligns with the data-driven algorithm design literature (e.g., M. Balcan, Data-Driven Algorithm Design, 2020). This is essentially an online learning problem over multiple rounds, where each round presents a new k-median instance. The paper lacks a discussion connecting to this line of research.", "was_revised": true, "final_justification": "The authors partially address my concerns about (i) motivating scenarios of the online setting, (ii) choice of performance metrics, and (iii) its connection to data-driven algorithm design. But those will not change my rating of the paper.", "rebuttal": "We thank the reviewer for the detailed review and we address the weaknesses and questions below.\n\n**R:** Could you provide a concrete application scenario for the online learning setting over multiple k-median instances? \n\n**A:** We give several applications that we will add to the paper:\n\n$\\bullet$ Developing accurate methods to cluster evolving data streams has been identified as an open challenge in data stream mining research, e.g.:\n\n*Georg  Krempl, Indre Zliobaite, Dariusz Brzezinski, Eyke Hüllermeier, Mark Last, Vincent Lemaire, Tino Noack, Ammar Shaker, Sonja Sievi, Myra Spiliopoulou, Jerzy Stefanowski. Open challenges for data stream mining research. ACM SIGKDD Explorations Newsletter, 2014.*\n\n$\\bullet$ Aggregating similar news stories based on their similarities can be used for recommendations downstream, e.g.:\n\n*Shufeng Gong, Yanfeng Zhang, Ge Yu. Clustering Stream Data by Exploring the Evolution of Density Mountain. Proceedings of the VLDB Endowment, 2017.*\n\nThis paper studies news articles that are inherently dynamic and evolve over time as fresh stories emerge, and older, less relevant news fades out. To provide timely and accurate recommendations, a clustering algorithm that adapts to evolving data is utilized.\n\n$\\bullet$ Clustering sensor data, e.g.: \n\n\n*Zhengru Wang, Xin Wang, Shuhao Zhan. MOStream: A Modular and Self-Optimizing Data Stream Clustering Algorithm.  IEEE International Conference on Data Mining (ICDM) 2024.*\n\nThis paper studies sensor data in the form of evolving data streams. The data depends on environmental conditions that can change dramatically between day and night or due to localized events such as forest fires, as well as fluctuate significantly across seasons. The goal is to maintain a clustering of such data as it evolves over time.\n\n$\\bullet$ Clustering network traffic, e.g.:\n\n*Feng Cao, Martin Ester, Weining Qian, Aoying Zhou. Density-Based Clustering over an Evolving Data Stream with Noise. SIAM International Conference on Data Mining (SDM) 2006.*\n\nThe last three references also study clustering of network traffic data, where patterns of network user connections change slowly over time in normal circumstances, but can also undergo sudden shifts if a malicious attack occurs. Consequently, network-monitoring methods that use clustering need to be able to adapt to shifts in network traffic and these shifts can be in the form of gradual drifts or adversarial changes.\n\n\n\n**R:** Why is the cost ratio of each instance more relevant than the absolute cost?\n\n**A:** We considered cost ratios instead of the absolute cost as our performance metric for two reasons. \n\nFirst, the instances that arrive can be at very different scales. In particular, if one instance is very large and the rest are small, it suffices to perform well on just the large instance when looking at absolute cost. Thus, taking cost ratios ensures that the algorithm is incentivized to do well on every instance, regardless of size. \n\nSecond, considering cost ratios instead of absolute costs is not only the right choice from a modeling perspective, but is also necessary for obtaining any regret bounds independent of the number of points $n$. To see this, suppose we get a very large instance with essentially all $n$ points that is far away from all the previous (much smaller) instances which are cumulatively on $o(n)$ points. Any online learning algorithm would then incur a cost of $n \\Delta$ for this single instance. On the other hand, the benchmark solution can simply optimize for this large instance and incur small cost for this instance. It suffers a large cost on the previous instances, but these instances being cumulatively small (only $o(n)$ points), the overall cost of the benchmark remains small in terms of absolute cost.\n\n**R:** Additionally, the benchmark used is static, which is a bit weak.\n\n**A:** The benchmark considered is the best fixed solution in hindsight, which is standard in online learning. As in online learning, no algorithm can be competitive with a benchmark that uses a separate solution for each instance. Such a benchmark would have a cost ratio of $1$ for every instance, i.e., would be optimal for every instance. In contrast, an algorithm trained on prior instances can have an arbitrary approximation bound on the next instance. For example, suppose $k=1$ and we receive a concentrated cluster of points in each instance that is far away from all previous instances. An algorithm trained on prior instances cannot predict where the new instance is going to be and hence will have arbitrarily large cost on it, whereas an optimal solution specifically for this instance will have a cost ratio of $1$. This is not specific to our model, but a general feature of any online learning setting, see e.g., Chapter 10 in [Hazan 2016].\n\n**R:** How does this work compare to the data-driven algorithm design framework in the online setting? \n\n**A:** In the data-driven paradigm, the typical goal is to pick the best algorithm out of a palette of algorithms whose behavior is dictated by a numerical parameter, see e.g., the survey:\n\n*Maria-Florina Balcan. Data-driven Algorithm Design. Chapter 29, Beyond the Worst-Case Analysis of Algorithms. Cambridge University Press.*\n\nIn this line of work, the typical assumption is that the instances are drawn from an unknown distribution, and the goal is to obtain sample complexity bounds for a given target average performance in comparison to the best parameter choice. The analysis usually proceeds by obtaining bounds on the pseudo-dimension of the cost functions corresponding to the parametrized algorithms, which are then converted to sample complexity bounds using statistical learning tools. \n\nThis is in contrast to our setting where the algorithm is allowed to output any valid solution in each round (i.e., there is no parameter choice being made, rather an entire solution is being constructed) and there is no distributional assumption on the sequence of instances. Our techniques leverage ideas from online learning (as against statistical learning) and the final results are about average performance across the adversarial set of instances, rather than expected performance on a distribution.\n\nThere are two papers in the data-driven literature that we are aware of which have an online learning flavor. One paper considers an online learning model similar to ours (reference [*Khodak et al. 2022*] in our paper):\n\n[*Khodak et al. 2022*] *Misha Khodak, Maria-Florina Balcan, Ameet Talwalkar, and Sergei Vassilvitskii. Learning predictions for algorithms with predictions. NeurIPS 2022.*\n\nThe main difference between this work and ours is that they use prior instances to learn a prediction for the current round, while we use the instances directly to learn a solution for the current round. Moreover, they consider problems such as ski rental, bipartite matching, and scheduling, while we focus on the $k$-median clustering problem. \n\nA second paper that considers the parameterized framework but in an online learning setting (i.e., not distributional) is:\n\n*Maria-Florina Balcan, Travis Dick, and Ellen Vitercik. Dispersion for Data-Driven Algorithm Design, Online Learning, and Private Optimization. FOCS 2018.*\n\nIn this paper, instances arrive over time and we pick a parameter for each (that corresponds to an algorithm) and see the corresponding cost. The benchmark in this case is the algorithm corresponding to the best fixed parameter in hindsight. The techniques heavily utilize the parametrization of the algorithms, and use properties that dictate the discontinuity of the cost functions such as piecewise Lipschitz-ness and dispersion (a measure of how many discontinuities are present in a bounded region) that are not directly applicable in our setting. \n\nWe will include a detailed comparison with the data-driven literature in our paper.\n\n**R:** A key step in the algorithm is to reduce the original problem to one with only $k$ points. Why is exactly $k$ chosen?\n\n**A:** This reduction eliminates the dependence on the size of instances $n$ in our regret bounds. Otherwise, the subgradient that we compute at each step can then have a large $L_\\infty$ norm that depends on $n$, which would then affect the regret term. On the other hand, if we apply our mirror descent algorithm to only $k$ points in each round, then the total number of points under consideration is at most $kT$. Thus, the regret term is independent of $n$.  \n\nA second benefit of the reduction is that it reduces the running time of the learning algorithm, and makes it independent of the size of the instances $n$. (The $k$-median algorithm has to run on instances of size $n$, but this is unavoidable in any case.) We typically expect that $n$ will be much larger than all other parameters in the problem. Using the reduction, we only need to run our learning algorithm on at most $kT$ points, which is independent of $n$. (The time complexity of the learning algorithm is $O(k^2 T^3)$, which comes from needing to iterate through the entries of a distance matrix of size at most $kT \\times kT$ every round.) To empirically confirm scalability, we ran experiments with $n= 1000, \\ldots, 6000$ and observed that the running time of the learning algorithm was always $2-3$ seconds on Google Colab ($2.20$ GHz  Intel® Xeon® CPU, $51$ GB RAM).\n\nFinally, we comment that it is important to choose exactly $k$ points in our reduction. If we use fewer or more than $k$ points, then the weights for the reduced instance are inconsistent with the $k$-median optimum. E.g., if using $< k$ points and there are $k$ closely knit clusters, then the resulting cost of the solution (which determines weights) is arbitrarily large. Similarly, if we use $> k$ points and there are $k+1$ closely knit clusters, then the resulting cost of the solution is arbitrarily small.\n\nWe will include this discussion in the paper."}, {"review_id": "rgFAATHFh7", "reviewer": "Reviewer_JsQM", "summary": "The paper explores a learning-augmented model of $k$-median clustering where the learner receives the past problem instances up to the current time point in an online manner and the goal is to use the information from past instances to predict a solution for future instances. The paper proposes a deterministic algorithm that achieves a competitive ratio of $O(k)$ and a regret of $O(\\sqrt{T} \\log T \\log (Tk))$ and a randomized algorithm that achieves a competitive ratio of $O(1)$ and a regret of $O(\\sqrt{T} \\log T \\log (Tk))$. The main framework goes by converting the $k$-median problem to a bounded variant and then calculating a fractional solution and then rounding it to get the final solution. The paper also provides empirical evidence in to the performance of the algorithm. They further strengthen their algorithmic results by showing that in the deterministic setting having competitive ratio of $o(k)$ and regret of $o(T)$ at the same time is impossible (and for randomized setting $(1+\\epsilon)$ and $o(T)$ at the same time is impossible).", "questions": "1. How well does the algorithm scale with data in practice? Does the bounded variants help with handling the scaling?  How well would it do against a large dataset with small drifts? Or against a large dataset with infrequent but large drifts? \n\n2. What are the key technical barriers in extending your framework to non-metric problems? \n\n3. How useful might the paradigms such as side-information be in this learning-augmented setting? For instance if there is some information about some optimal centers or some approximate information, would that be useful? What information might be useful in breaking the current lower bounds?\n\n4. How sensitive is your method to noisy or outlier instances? How well would the algorithm do if some $\\alpha$ fraction of the instances are noisy or outliers? Would it still give the same guarantees? Is there any specific steps to take to make it robust against such cases? Or is it inherently robust?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n\n1. The paper explores the $k$-median clustering problem using the notions of learning-augmented algorithms and online learning. Unlike in standard online $k$-clustering with data arriving one by one, we have new instances arriving and past instances giving hints on how the new instances might be solved. This formulation would be useful specially in handling things such as evolving data.\n\n2. The paper provides algorithms with provable cost guarantees and strengthens their work by providing nearly similar lower bounds.\n\n3. The algorithm and the proofs are well structured and easy to follow. The paper is overall well written.\n\n\nWeaknesses\n\n1. The motivation for the specific formulation of the problem is not entirely clear at the start. I can see why the past instances informing on future instances would be an interesting formulation in settings where there is evolving data. It might be nice to clarify why this model is interesting (maybe using some potential applications).\n\n2. The experiments seems to be limited to synthetic data. It would strengthen the empirical claims to include real-world datasets where dynamic clustering is relevant.", "was_revised": true, "final_justification": "The authors clarified the concerns I had on the model, scalability and adaptability. Therefore, I will retain my rating.", "rebuttal": "We thank the reviewer for the detailed review and we address the weaknesses and questions below:\n\n**R:** It might be nice to clarify why this model is interesting (maybe using some potential applications).\n\n**A:** We give several applications that we will add to the paper:\n\n$\\bullet$ Developing accurate methods to cluster evolving data streams has been identified as an open challenge in data stream mining research, e.g.:\n\n*Georg  Krempl, Indre Zliobaite, Dariusz Brzezinski, Eyke Hüllermeier, Mark Last, Vincent Lemaire, Tino Noack, Ammar Shaker, Sonja Sievi, Myra Spiliopoulou, Jerzy Stefanowski. Open challenges for data stream mining research. ACM SIGKDD Explorations Newsletter, 2014.*\n\n$\\bullet$ Aggregating similar news stories based on their similarities can be used for recommendations downstream, e.g.:\n\n*Shufeng Gong, Yanfeng Zhang, Ge Yu. Clustering Stream Data by Exploring the Evolution of Density Mountain. Proceedings of the VLDB Endowment, 2017.*\n\nThis paper studies news articles that are inherently dynamic and evolve over time as fresh stories emerge, and older, less relevant news fades out. To provide timely and accurate recommendations, a clustering algorithm that adapts to evolving data is utilized.\n\n$\\bullet$ Clustering sensor data, e.g.: \n\n\n*Zhengru Wang, Xin Wang, Shuhao Zhan. MOStream: A Modular and Self-Optimizing Data Stream Clustering Algorithm.  IEEE International Conference on Data Mining (ICDM) 2024.*\n\nThis paper studies sensor data in the form of evolving data streams. The data depends on environmental conditions that can change dramatically between day and night or due to localized events such as forest fires, as well as fluctuate significantly across seasons. The goal is to maintain a clustering of such data as it evolves over time.\n\n$\\bullet$ Clustering network traffic, e.g.:\n\n*Feng Cao, Martin Ester, Weining Qian, Aoying Zhou. Density-Based Clustering over an Evolving Data Stream with Noise. SIAM International Conference on Data Mining (SDM) 2006.*\n\nThe last three references also study clustering of network traffic data, where patterns of network user connections change slowly over time in normal circumstances, but can also undergo sudden shifts if a malicious attack occurs. Consequently, network-monitoring methods that use clustering need to be able to adapt to shifts in network traffic and these shifts can be in the form of gradual drifts or adversarial changes.\n\n\n\n**R:** How well does the algorithm scale with data in practice? Does the bounded variants help with handling the scaling? \n\n**A:** Note that our reduction of each instance to $k$ points helps reduce the running time of the learning algorithm, and makes it independent of the size of the instances $n$. (The $k$-median algorithm has to run on instances of size $n$, but this is unavoidable in any case.) We typically expect that $n$ will be much larger than all other parameters in the problem. Using the reduction, we only need to run our learning algorithm on at most $kT$ points, which is independent of $n$. The time complexity of the learning algorithm is $O(k^2 T^3)$, which comes from needing to iterate through the entries of a distance matrix of size at most $kT \\times kT$ every round.\n\nTo empirically confirm scalability, we ran experiments with $n= 1000, \\ldots, 6000$ and observed that the running time of the learning algorithm was always $2-3$ seconds on Google Colab ($2.20$ GHz  Intel® Xeon® CPU, $51$ GB RAM).\n\n\n**R:** How well would it do against a large dataset with small drifts? Or against a large dataset with infrequent but large drifts? \n\n**A:** The experiment named “Scale Changes” in our paper analyzes the performance of our algorithm when the incoming instances have sudden shifts. In this experiment, we have 5 clusters with 10 points each and the clusters grow geometrically far apart in distance. The sequence of instances iterates over these clusters in batches of increasing length. We observed that our algorithm quickly adapts to the changing environment and shifts a center to the new cluster. \n\nAs suggested by the reviewer, we also ran some experiments to analyze the behavior of our algorithm when instances drift slowly over time. In these experiments, we have $n=2500, T= 250$, and we use a range of values for $k = 1,2,3$. The underlying instances are created by randomly drawing $5$ points in a disc around the origin, but then shifting the center to the right by $0.02$ for each instance. The final average approximation ratios were less than $2$ in all cases. (In contrast, if the algorithm were to use the initial solutions throughout, i.e., does not automatically adapt to the drift, then the cost ratios are around $5-15$.)\n\n\n\n**R:** What are the key technical barriers in extending your framework to non-metric problems? \n\n**A:**  Incorporating online learning based techniques to improve the solution for online non-metric clustering problems is an interesting question. However, we note that in the non-metric setting, it is not possible to compete with the optimal solution in hindsight. This is because the last instance can reveal the optimal solution in hindsight, which is close to all previous instances that are mutually far from each other. Since the online learning algorithm only gets to see these optimal centers at the very end, it cannot choose a competitive solution for the prior instances. Therefore, in the non-metric setting, one would need to design a new benchmark against which an online learning algorithm can compete across a sequence of instances.\n\n**R:** How useful might the paradigms such as side-information be in this learning-augmented setting? \n\n**A:** Introducing side information is an interesting direction to consider. For instance, suitable side information may help in reducing the regret (the $\\beta$ in our guarantee) by providing a good starting solution for the mirror descent algorithm. However, this would require a completely new analysis which is beyond the scope of the current work.\n\n**R:** How sensitive is your method to noisy or outlier instances? \n\n**A:** The effect of outliers is another interesting direction. First, we note that our algorithm is inherently robust in the sense that the $(\\alpha,\\beta)$ approximation guarantee holds even in the presence of outliers. That said, the outliers degrade the benchmark since there is no good solution in hindsight that serves all instances including the outliers. If we wanted to compete against the best solution that is allowed to disregard the outlier instances, then we would likely need to redesign our algorithm completely."}, {"review_id": "b6dmtSlLit", "reviewer": "Reviewer_Rx2G", "summary": "This paper introduces LEARN-MEDIAN , a novel framework for learning-augmented algorithms that dynamically adapts to sequences of online instances in metric spaces. Unlike prior work that relies on static predictions, the authors propose an online learning model that iteratively refines a fixed solution to minimize the average approximation ratio over time. The key contributions include:\n\n1.\tA new paradigm where the algorithm learns from historical instances to optimize future performance, achieving sublinear regret against the hindsight-optimal solution by using Hyperbolic Entropy Regularizer \n\n2.\tA deterministic rounding algorithm with $O(k)$-competitive ratio and $ O(k^4 \\Delta\\sqrt{T \\log T})$ regret, a randomized rounding algorithm with improved $O(1)$-competitive ratio and $ O(k^3 \\Delta\\sqrt{T \\log T})$ regret.\n\n3.\tA proof of Lower Bounds for any algorithm for LEARN-MEDIAN with sublinear regret.\n\n4.\tExperiments demonstrate the algorithm’s robustness and convergence to near-optimal performance (approximation ratios close to 1).", "questions": "1.\tThe paper focuses on optimizing the average approximation ratio across instances. However, it does not explicitly analyze the algorithm’s Consistency (performance under accurate predictions) or Robustness (worst-case guarantees under prediction errors). Specifically: When the predictions (e.g., gradient estimates from historical instances) are inaccurate or adversarial, can the approximation ratio still be bounded? How does the algorithm’s performance degrade as the quality of predictions deteriorates? A discussion on these aspects would strengthen the theoretical grounding of the work.\"\n\n2.\tThe paper's experiments evaluate the algorithm on a unit square metric space ([0, 1] × [0, 1]). However, in real-world applications, the metric space may have irregular scales (e.g., a rectangle [0, 1] × [0, 5] or [0, 1] × [0, 10]). What is the approximation ratio of the algorithm when the metric space is not square? Whether the algorithm is effective on real-world datasets? \n\n3.\tIn Fig .3 (for k = 2, 3, 6) and 4 (for k = 4), the average approximation ratio of the randomized rounding algorithm appears higher than that of the deterministic rounding. This seems counterintuitive given the theoretical O(1) approximation for randomized rounding versus the O(k) bound for deterministic rounding. How interpret these empirical results in light of the theoretical guarantees?  For small k, is it possible that the constant hidden in the O(1) bound exceeds k in practice? \n\n4.\tWhat is the scalability of your proposed algorithm for large-scale inputs (e.g., on the order of 100,000 nodes)?", "limitations": "There is no potential negative societal impact of their work.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: The paper introduces a novel framework (LEARN-MEDIAN ) that bridges online learning and learning-augmented algorithms, addressing dynamic metric spaces where instances evolve over time.. The hyperbolic entropy regularizer is an interesting technical enabling dynamic adaptation to expanding metric spaces (e.g., new points appearing online) while maintaining regret guarantees. \n\nWeakness:\n\n1.\tThe paper only analyzes the average ratio.\n\n2.\tThe Consistency and Robustness are the keys of a learning-augmented algorithm. This paper did not discuss consistency and robustness.\n\n3.\tThe paper does not provide the time complexity of the proposed learning-augmented algorithm.\n\n4.\tThe simulation experiment results are unconvincing. For example, the experiments use synthetic data only; real-world validation would strengthen the claims.", "was_revised": true, "final_justification": "Most of the concerns have been addressed during the rebuttal phase. Overall, considering the topic and contributions, this paper is qualified for an acceptance (a weak accept).", "rebuttal": "We thank the reviewer for the detailed review and we address the weaknesses and questions below:\n\n**R:** The paper focuses on optimizing the average approximation ratio across instances. However, it does not explicitly analyze the algorithm’s Consistency (performance under accurate predictions) or Robustness (worst-case guarantees under prediction errors). \n\n**A:** The definitions of consistency and robustness correspond to algorithms that are given explicit predictions. Our setting is not directly analogous to a prediction-based algorithm (see the first paragraph of related work in the paper), rather we are interested in using the source of predictions, i.e., prior instances of the problem, directly in an online learning framework. Having said that, the notions of consistency and robustness, which capture situations where predictions are good and arbitrarily bad, intuitively correspond to the benchmark (cost of the best solution in hindsight) being small or large in our setting. Note that if the instances are related, then the benchmark cost of a fixed solution is smaller, while if the instances are unrelated, then the benchmark cost of any fixed solution is larger. Our algorithm’s $(\\alpha, \\beta)$ guarantees hold irrespective of what the value of the benchmark cost is, i.e., the algorithm automatically adapts to whether the instances provide learnable information or not.\n\n\n**R:** The paper does not provide the time complexity of the proposed learning-augmented algorithm. What is the scalability of your proposed algorithm for large-scale inputs (e.g., on the order of $100,000$ nodes)?\n\n**A:** Note that our reduction of each instance to $k$ points helps reduce the running time of the learning algorithm, and makes it independent of the size of the instances $n$. (The $k$-median algorithm has to run on instances of size $n$, but this is unavoidable in any case.) We typically expect that $n$ will be much larger than all other parameters in the problem. Using the reduction, we only need to run our learning algorithm on at most $kT$ points, which is independent of $n$. The time complexity of the learning algorithm is $O(k^2 T^3)$, which comes from needing to iterate through the entries of a distance matrix of size at most $kT \\times kT$ every round.\n\nTo empirically confirm scalability, we ran experiments with $n= 1000, \\ldots, 6000$ and observed that the running time of the learning algorithm was always $2-3$ seconds on Google Colab ($2.20$ GHz Intel® Xeon® CPU, $51$ GB RAM).\n\n**R:** The paper's experiments evaluate the algorithm on a unit square metric space ($[0, 1] \\times [0, 1]$). However, in real-world applications, the metric space may have irregular scales \n\n**A:** Note that our theoretical $(\\alpha, \\beta)$ guarantee holds regardless of the scale of the metric space. As suggested, we ran experiments on $400$ points drawn uniformly from an $(1 \\times 10)$ rectangle for $k=2,3,6$ and a time horizon of $T=1000$. In all cases we achieved performance close to the optimal fixed solution in hindsight, with a final approximation ratio of less than $1.3$.\n\n**R:** In Fig. $3$ (for $k = 2, 3, 6$) and 4 (for $k = 4$), the average approximation ratio of the randomized rounding algorithm appears higher than that of the deterministic rounding\n\n**A:** While the randomized algorithm does perform slightly worse than the deterministic algorithm in some cases, it is important to note that the approximation ratios are already quite close to $1$ ($<1.4$) and the difference in performance is only about $10\\%$. These results are better interpreted as both algorithms performing very close to the optimal solution, and much better than the worst-case bounds given in the analysis of either algorithm. It is difficult to conjecture on the reasons for the slight differences in performance between the algorithms given they are both so close to the optimum."}]

Author rebuttal:

Meta-review: This paper addresses the k-median clustering problem in an online setting. The input is an online sequence of T instances that arrive one by one. At any point in time, it is assumed that the algorithm has access to the prior instances. The algorithm uses the knowledge of these prior instances to compute a k-median solution, which is then applied to the current instance and evaluated for loss. The overall goal is to minimize the total loss over the entire sequence. The main result of the paper is an (alpha,beta)-approximation of the optimal solution, which is defined with respect to the so-called “best fixed solution in hindsight.” This means that the total loss occurred is at most alpha times the loss of the best fixed solution plus beta. A deterministic algorithm with alpha=O(k) and beta=o(T) is shown and a randomized one with alpha=O(1) and beta=o(T). Also lower bounds are presented showing that these results are tight.

All reviewers think that the results are interesting and non-trivial. The submission is also well-written. Most of the weaknesses mentioned by the reviewers concern the motivation of the model and the connection to other models and results in the literature (e.g. data-driven algorithms). All these questions could be addressed convincingly by the authors, and all reviewers are positive about the submission. I also agree that the submission presents interesting and non-trivial results and that the considered problem is well motivated and important.
Decision: Accept (poster)