Efficient Online Learning for Dynamic k-clustering

Stratis Skoulakis (Singapore University of Tech and Design)

Monday 18 October at 15:30 Paris time via Teams

Abstract : We study dynamic clustering problems from the perspective of online learning. We consider an online learning problem, called 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 p-norm of the vector consisting of the distance of each client to its closest center at round t, for some p>=1 or p = infty. We present a Theta(min(k,r)-regret polynomial-time online learning algorithm and show that, under some well-established computational complexity conjectures, 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 on combinatorial online learning.