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.
Figures & tables
(∇t)i:=−∑x∈Rtwx(M(x)−min(M(x),d(x,vi)).
Algorithm 1 Algorithm for an instance of Learn-Bounded-Median
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).
Figure 2: Experimental Results for Dynamic Instances
Appendix figures & tables8 assets
Supplementary material from the paper’s appendix.
Appendix
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 .
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 k=2,3,6 .
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 k=4,8,12,16 .
Figure 6: (Uniform Hypersphere): Fractional mass of algorithm over time at the center (avg. and std. dev. over 10 runs), d=2,8
Figure 7: (Oscillating Instances): Fractional mass of algorithm and OPT over time in one of the clusters (left) and corresponding dynamic approximation ratios (right), for k=1,2,3,4 .
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 .
Figure 9: (Scale Changes): Dynamic approximation ratio plots with T=50000 , for k=2,3.
Figure 10: (Small Drifts): 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=1,2,3 .
In this paper, we investigate the learning-augmented k-median clustering problem, which aims to improve the performance of traditional clustering algorithms by preprocessing the point set with a predictor of error rate α∈[0,1). This preprocessing step assigns potential labels to the points before clustering. We introduce an algorithm for this problem based on a simple yet effective sampling method, which substantially improves upon the time complexities of existing algorithms. Moreover, we mitigate their exponential dependency on the dimensionality of the Euclidean space. Lastly, we conduct experiments to compare our method with several state-of-the-art learning-augmented k-median clustering methods. The experimental results suggest that our proposed approach can significantly reduce the computational complexity in practice, while achieving a lower clustering cost.
Kangke Cheng, Shihong Song, Guanlin Mo +1
University of Science and Technology of China, Hefei, China · School of Informatics, University of Edinburgh, Edinburgh, UK
We present learning-augmented algorithms for two general classes of online minimization problems: metrical task systems and laminar set cover. Both algorithms achieve improved theoretical guarantees using machine-learned predictions of an optimal solution to the dual linear program. Unlike optimal primal solutions, which can change drastically under tiny instance perturbations, these dual solutions are much more stable, which ensures the existence of good (and learnable) predictions for families of similar instances. While previous work has used dual predictions in offline settings and for online maximization problems, our algorithms are, to the best of our knowledge, the first demonstration that such dual predictions can be effective for online minimization. Our theoretical results are complemented by experiments on the k-server problem and the parking permit problem.
Christian Coester, Alexa Tudose, Alexander Turoczy
Learning-augmented algorithms have received significant attention in recent years, particularly in the context of online optimization. Motivated by the high computational cost of generating predictions, a growing line of work studies the tradeoff between performance guarantees and the number of predictions used in learning-augmented algorithms for problems such as caching and metrical task systems. In this paper, we extend this line of research to online metric matching by developing parsimonious learning-augmented algorithms and establishing lower bounds on their performance. Our approach extends the Follow-the-Prediction framework to the parsimonious setting by filling in a virtual prediction in the absence of an actual prediction, using an online metric matching algorithm that maintains good intermediate matchings throughout its execution. We complement our theoretical results with an empirical evaluation, demonstrating the practical effectiveness of our approach.
Yongho Shin, Phanu Vajanopath
Institute of Computer Science, University of Wrocław, Wrocław, Poland.