[Talks@IDSIA] PIDSIA Seminar by Silvio Lattanzi, 22nd February

Speaker: Silvio Lattanzi, Research Scientist, Google Research Europe, Zurich Title: Consistent k-Clustering Abstract: The study of online algorithms and competitive analysis provide a solid foundation for studying the quality of irrevocable decision making when the data arrives in an online manner. While in some scenarios the decisions are indeed irrevocable, there are many practical situations when changing a previous decision is not impossible, but simply expensive. In this work we formalize this notion and introduce the consistent k-clustering problem. With points arriving online, the goal is to maintain a constant approximate solution, while minimizing the number of reclusterings necessary. We prove a lower bound, showing that Ω(k log n) changes are necessary in the worst case, for a wide range of objective functions. On the positive side, we give an algorithm that needs only O(k^2 log^4 n) changes to maintain a constant competitive solution. This is an exponential improvement on the naive solution of reclustering at every time step. Finally, we show experimentally that our approach performs much better than the theoretical bound, with the number of changes growing approximately as O(log n). Joint work with Sergei Vassilvitskii. Bio: Silvio is a Research Scientist at Google Research Europe since April 2017. Before he was in the NY Algorithm group at Google New York from January 2011 to March 2017. He received his PhD from Sapienza University of Rome under the supervision of Alessandro Panconesi. During his PhD he interned twice at Google and once at Yahoo! Research. His research interests are in the areas of algorithms, machine learning and information retrieval. When: 22nd of February 2018, 12:00-13:00 Location: Manno, Galleria 1, 2nd floor, room G1-204 Registration: Pizza (or alternative food) and drinks will be offered at the end of the talk. If you plan to attend, please register in a timely fashion at the following link so that we will have no shortage of food: https://doodle.com/poll/uxnyzybwp7e5yyyy