Efficient Online Learning for Dynamic k-Clustering

Dimitris Fotakis, Georgios Piliouras, Stratis Skoulakis
Proceedings of the 38th International Conference on Machine Learning, PMLR 139:3396-3406, 2021.

Abstract

In this work, we study dynamic clustering problems from the perspective of online learning. We consider an online learning problem, called \textit{Dynamic k-Clustering}, in which k centers are maintained in a metric space over time (centers may change positions) such as a dynamically changing set of r clients is served in the best possible way. The connection cost at round t is given by the \textit{p-norm} of the vector formed by the distance of each client to its closest center at round t, for some p≥1. We design a \textit{Θ(min-regret} polynomial-time online learning algorithm, while we show that, under some well-established computational complexity conjectures, \textit{constant-regret} cannot be achieved in polynomial-time. In addition to the efficient solution of Dynamic k-Clustering, our work contributes to the long line of research of combinatorial online learning.

Cite this Paper

BibTeX
@InProceedings{pmlr-v139-fotakis21a, title = {Efficient Online Learning for Dynamic k-Clustering}, author = {Fotakis, Dimitris and Piliouras, Georgios and Skoulakis, Stratis}, booktitle = {Proceedings of the 38th International Conference on Machine Learning}, pages = {3396--3406}, year = {2021}, editor = {Meila, Marina and Zhang, Tong}, volume = {139}, series = {Proceedings of Machine Learning Research}, month = {18--24 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v139/fotakis21a/fotakis21a.pdf}, url = {https://proceedings.mlr.press/v139/fotakis21a.html}, abstract = {In this work, we study dynamic clustering problems from the perspective of online learning. We consider an online learning problem, called \textit{Dynamic $k$-Clustering}, in which $k$ centers are maintained in a metric space over time (centers may change positions) such as a dynamically changing set of $r$ clients is served in the best possible way. The connection cost at round $t$ is given by the \textit{$p$-norm} of the vector formed by the distance of each client to its closest center at round $t$, for some $p\geq 1$. We design a \textit{$\Theta\left( \min(k,r) \right)$-regret} polynomial-time online learning algorithm, while we show that, under some well-established computational complexity conjectures, \textit{constant-regret} cannot be achieved in polynomial-time. In addition to the efficient solution of Dynamic $k$-Clustering, our work contributes to the long line of research of combinatorial online learning.} }
Endnote
%0 Conference Paper %T Efficient Online Learning for Dynamic k-Clustering %A Dimitris Fotakis %A Georgios Piliouras %A Stratis Skoulakis %B Proceedings of the 38th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Marina Meila %E Tong Zhang %F pmlr-v139-fotakis21a %I PMLR %P 3396--3406 %U https://proceedings.mlr.press/v139/fotakis21a.html %V 139 %X In this work, we study dynamic clustering problems from the perspective of online learning. We consider an online learning problem, called \textit{Dynamic $k$-Clustering}, in which $k$ centers are maintained in a metric space over time (centers may change positions) such as a dynamically changing set of $r$ clients is served in the best possible way. The connection cost at round $t$ is given by the \textit{$p$-norm} of the vector formed by the distance of each client to its closest center at round $t$, for some $p\geq 1$. We design a \textit{$\Theta\left( \min(k,r) \right)$-regret} polynomial-time online learning algorithm, while we show that, under some well-established computational complexity conjectures, \textit{constant-regret} cannot be achieved in polynomial-time. In addition to the efficient solution of Dynamic $k$-Clustering, our work contributes to the long line of research of combinatorial online learning.
APA
Fotakis, D., Piliouras, G. & Skoulakis, S.. (2021). Efficient Online Learning for Dynamic k-Clustering. Proceedings of the 38th International Conference on Machine Learning, in Proceedings of Machine Learning Research 139:3396-3406 Available from https://proceedings.mlr.press/v139/fotakis21a.html.

Related Material