Near-Optimal Learning of Joint Alignments and Clusters with a Faulty Oracle

Tuesday, July 23, 2019

2.30 p.m.

ISI seminar room 1st floor

Prof. Charalampos Tsourakakis Boston University, Massachusetts, USA Harvard University, Massachusetts, USA ISI Foundation

In this talk we will discuss state-of-the-art results on two important problems, clustering and learning joint alignments (e.g., of images and shapes) using noisy queries. For the clustering problem, we consider the following model for two clusters: we are allowed to query any pair of nodes whether they belong to the same cluster or not, but the answer to the query is corrupted with some probability $0<q<\frac{1}{2}$. Let $\delta=1-2q$ be the bias. We provide an algorithm that recovers all signs correctly with high probability in the presence of noise  with $O(\frac{n\log n}{\delta^2}+\frac{\log^2 n}{\delta^6})$ queries. This is the best known result for this problem  for all but tiny $\delta$. We also provide another algorithm that performs $O(\frac{n\log n}{\delta^4})$ queries, and  uses breadth first search as its main algorithmic primitive.  Then we will present our results for the problem of learning joint alignments.  The goal is to recover $n$ discrete variables $x_i \in \{0, \ldots, k-1\}$ (up to some global offset) given noisy observations of a set of their pairwise differences {x_i - x_j mod k}; specifically, with probability $1/k+\delta$ for some $\delta > 0$ one obtains the correct answer, and with the remaining probability one obtains a uniformly random incorrect answer.  We provide an efficient algorithm that learns the joint alignment with high probability. We will conclude with some open problems.

Charalampos Tsourakakis is an assistant professor in computer science at Boston University and a research associate at Harvard. Dr. Tsourakakis obtained his PhD in Algorithms, Combinatorics and Optimization at Carnegie Mellon under the supervision of Alan Frieze, was a postdoctoral fellow at Brown University and Harvard under the supervision of Eli Upfal and Michael Mitzenmacher respectively. Before joining Boston University, he worked as a researcher in the Google Brain team. He has received the 10-year highest impact paper award from IEEE, has won a best paper award in IEEE Data Mining, has delivered three tutorials in the ACM SIGKDD Conference on Knowledge Discovery and Data Mining, and has designed two graph mining libraries for large-scale graph mining, one of which has been officially included in Windows Azure. His research focuses on large-scale graph mining, and machine learning.

Joint work with Michael Mitzenmacher (Harvard), Kasper Green Larsen (Aarhus), Jarosaw Basiok (Harvard), Ben Lawson (BU), Preetum Nakkiran (Harvard), Vasileios Nakos (Harvard).