Seminar: From Hierarchical Clustering to Contrastive Embeddings and CSPs over Infinite Domains

Abstract: Hierarchical Clustering (HC) is a widely studied problem in unsupervised learning and exploratory data analysis, usually tackled by simple agglomerative procedures like average-linkage, single-linkage or complete-linkage. Applications of HC include reasoning about text documents, understanding the Evolution of species and the Tree of life, decomposing social networks like Facebook, or even organizing large data centers efficiently. Surprisingly, despite the plethora of heuristics for tackling the problem, until recently there was no optimization objective associated with it; this is in stark contrast with flat clustering objectives like k-means, k-median and k-center.

In this talk, we will give an overview of the optimization objectives for Hierarchical Clustering, we will discuss connections to Phylogenetic and Triplet Reconstruction methods in computational biology, we will see some simple algorithms to find approximate solutions, and finally we will discuss some recent hardness of approximation results and new connections to the notion of approximation resistance of CSPs. We will also draw some connections to problems in contrastive embeddings (also known as ordinal embeddings) where the goal is to preserve qualitative triplet constraints of the form ||i-j|| < ||i-k||, stating that distance between i and j should be smaller than distance i and k. Problems of this nature arise in nearest-neighbor search, recommendation, contrastive learning etc., but they are not well-understood from a theoretical perspective. No prior background is assumed, so feel free to come, as the talk will be self-contained.

Bio: Vaggos Chatziafratis ( https://cstheory.ucsc.edu/vaggos ) is an Assistant Professor of Computer Science & Engineering at the University of California in Santa Cruz. His research lies at the intersection of approximation algorithms and machine learning, focusing on the design and analysis of approximation algorithms and clustering. Vaggos completed his MS and PhD at Stanford University in the Computer Science Department, where he was advised by Tim Roughgarden and Moses Charikar. Before Stanford, he finished with a Diploma from the ECE department of the National Technical University of Athens. Before joining UC Santa Cruz, he did a postdoc at Google Research in New York hosted by Vahab Mirrokni and Mohammad Mahdian, working on hierarchical clustering with the graph mining team. He also did a postdoc at Northwestern working with Konstantin Makarychev, Aravindan Vijayaraghavan and Samir Khuller. Vaggos is the recipient of a FODSI postdoc fellowship at MIT (under Piotr Indyk) and Northeastern (under Paul Hand). His research at UCSC has been supported by a Hellman Fellowship.