Timezone: »

 
Poster
Efficient Online Learning for Dynamic k-Clustering
Dimitris Fotakis · Georgios Piliouras · Stratis Skoulakis

Thu Jul 22 09:00 PM -- 11:00 PM (PDT) @ Virtual
in Poster Session 6 »
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.
Keywords: Online Learning Theory
[ Slides] 

Author Information

Dimitris Fotakis (National Technical University of Athens)
Georgios Piliouras (Singapore University of Technology and Design)
Stratis Skoulakis (Singapore University of Technology and Design)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors