Learning-Augmented Algorithms for $k$-median via Online Learning

We thank the reviewer for the detailed review and we address the weaknesses and questions below:

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

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.

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

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.

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

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

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

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

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.

We thank the reviewer for the detailed review and we address the weaknesses and questions below:

R: It might be nice to clarify why this model is interesting (maybe using some potential applications).

A: We give several applications that we will add to the paper:

$\bullet$ Developing accurate methods to cluster evolving data streams has been identified as an open challenge in data stream mining research, e.g.:

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.

$\bullet$ Aggregating similar news stories based on their similarities can be used for recommendations downstream, e.g.:

Shufeng Gong, Yanfeng Zhang, Ge Yu. Clustering Stream Data by Exploring the Evolution of Density Mountain. Proceedings of the VLDB Endowment, 2017.

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

$\bullet$ Clustering sensor data, e.g.:

Zhengru Wang, Xin Wang, Shuhao Zhan. MOStream: A Modular and Self-Optimizing Data Stream Clustering Algorithm. IEEE International Conference on Data Mining (ICDM) 2024.

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

$\bullet$ Clustering network traffic, e.g.:

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.

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

R: How well does the algorithm scale with data in practice? Does the bounded variants help with handling the scaling?

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.

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

R: How well would it do against a large dataset with small drifts? Or against a large dataset with infrequent but large drifts?

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.

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

R: What are the key technical barriers in extending your framework to non-metric problems?

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.

R: How useful might the paradigms such as side-information be in this learning-augmented setting?

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.

R: How sensitive is your method to noisy or outlier instances?

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.

We thank the reviewer for the detailed review and we address the weaknesses and questions below.

R: Could you provide a concrete application scenario for the online learning setting over multiple k-median instances?

A: We give several applications that we will add to the paper:

$\bullet$ Developing accurate methods to cluster evolving data streams has been identified as an open challenge in data stream mining research, e.g.:

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.

$\bullet$ Aggregating similar news stories based on their similarities can be used for recommendations downstream, e.g.:

Shufeng Gong, Yanfeng Zhang, Ge Yu. Clustering Stream Data by Exploring the Evolution of Density Mountain. Proceedings of the VLDB Endowment, 2017.

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

$\bullet$ Clustering sensor data, e.g.:

Zhengru Wang, Xin Wang, Shuhao Zhan. MOStream: A Modular and Self-Optimizing Data Stream Clustering Algorithm. IEEE International Conference on Data Mining (ICDM) 2024.

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

$\bullet$ Clustering network traffic, e.g.:

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.

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

R: Why is the cost ratio of each instance more relevant than the absolute cost?

A: We considered cost ratios instead of the absolute cost as our performance metric for two reasons.

First, 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.

Second, 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.

R: Additionally, the benchmark used is static, which is a bit weak.

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

R: How does this work compare to the data-driven algorithm design framework in the online setting?

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:

Maria-Florina Balcan. Data-driven Algorithm Design. Chapter 29, Beyond the Worst-Case Analysis of Algorithms. Cambridge University Press.

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

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

There 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):

[Khodak et al. 2022] Misha Khodak, Maria-Florina Balcan, Ameet Talwalkar, and Sergei Vassilvitskii. Learning predictions for algorithms with predictions. NeurIPS 2022.

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

A second paper that considers the parameterized framework but in an online learning setting (i.e., not distributional) is:

Maria-Florina Balcan, Travis Dick, and Ellen Vitercik. Dispersion for Data-Driven Algorithm Design, Online Learning, and Private Optimization. FOCS 2018.

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

We will include a detailed comparison with the data-driven literature in our paper.

R: A key step in the algorithm is to reduce the original problem to one with only $k$ points. Why is exactly $k$ chosen?

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

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

Finally, 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.

We will include this discussion in the paper.

We thank the reviewer for the detailed review. We address the questions below.

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.

A: Our framework is based on the well-studied online learning framework; see the standard textbook below (reference [Hazan 2016] in our paper):

[Hazan 2016] Elad Hazan. Introduction to online convex optimization. Foundations and Trends in Optimization.

Online 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):

[Khodak et al. 2022] Misha Khodak, Maria-Florina Balcan, Ameet Talwalkar, and Sergei Vassilvitskii. Learning predictions for algorithms with predictions. NeurIPS 2022.

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

In [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.

We 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):

[Mitzenmacher and Vassilvitskii 2020] Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. Chapter 30, Beyond the Worst-Case Analysis of Algorithms. Cambridge University Press.

and other works such as these references from our paper, including for clustering problems such as $k$-means and facility location:

[Ergun et al. 2022] Jon C. Ergun, Zhili Feng, Sandeep Silwal, David P. Woodruff, and Samson Zhou. Learning-augmented k-means clustering. ICLR 2022.

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

[Lykouris and Vassilvitskii 2021] Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. Journal of the ACM, 2021.

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

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

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

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$)?

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.

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.

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.