Abstract: In the correlation clustering problem the input is a signed graph where the sign indicates whether each pair of points should be placed in the same cluster or not. The goal of the problem is to compute a clustering which minimizes the number of disagreements with such recommendation. Thanks to its many practical applications, correlation clustering is a fundamental unsupervised learning problem and has been extensively studied in many different settings. In this talk, I will present the problem in the classic online setting with recourse; The vertices of the graphs arrive in an online manner and the goal is to maintain an approximate clustering while minimizing the number of times each vertex changes cluster. In this setting, I will present an algorithm that achieves logarithmic recourse per vertex in the worst case and also complement this result with a tight lower bound.
This is joint work with Vincent Cohen-Addad, Silvio Lattanzi, and Nikos Parotsidis.
Bio: I am a fifth (and final) year Ph.D. student at EPFL, advised by Rudiger Urbanke and Ola Svensson. My interests lie in the intersection of theoretical computer science and machine learning and, more specifically, online algorithms (matchings, clustering, etc.), learning augmented online algorithms (i.e., online algorithms with predictions), and recently active learning. During the last two summers, I was a Research Intern at Google Zurich hosted by Nikos Parotsidis and Ehsan Kazemi, and on May 2022, I co-organized ALPS 2022, a workshop on algorithms with predictions. Before moving to Switzerland, I completed my undergrad studies at the National Technical University of Athens, where I studied Computer and Electrical Engineering, and I was advised by Dimitris Fotakis.
The Data Science Deep Dive is free and open to the public. If you are interested in giving a talk, please email Mohammad Hajiesmaili or Adam Lechowicz. Note that in addition to being a public lecture series, the Data Science Deep Dive is also a seminar (CompSci 692K, Algorithms with Predictions Seminar) that can be taken for credit.