Talk 1:

Coresets for Clustering Problems

by Melanie Schmidt

Abstract: The last two decades have seen a rise of streaming one-pass algorithms for clustering problems. One concept in the core of this success story are so-called coresets: Small summaries of input data which approximately preserve the cost of any solution. For example, for the k-means problem, a coreset is a weighted set of points S which satisfies that for any choice of k centers from the d-dimensional Euclidean space (a k-means solution), the sum of the squared distances of all points to their closest center (which is the k-means objective) is approximately the same for S and the original point set P. Coresets are immensely useful because a) they allow to basically run any algorithm on the coreset instead of huge set, b) they can often be computed in one-pass over the data and c) there exist very small coresets for classical clustering problems like k-means and k-median. In this talk, we review coreset results and point out directions for future research.

Talk 2:

Hardness of Approximation for Metric Clustering.

by Karthik C. S.

Abstract: A lot of attention has been invested over the last three decades by the theory community to understand the efficiency of (even approximately) computing optimal clusters. Despite this focus, our understanding of the approximability of these clustering tasks remains poor, and our understanding of the hardness of approximation of these tasks was even worse.

In this talk, I will survey the recently established conceptual framework to tackle the latter issue of hardness of approximation of clustering in L_p metrics (and in particular Euclidean metric), through which we are now able to significantly improve on the inapproximability bounds established more than twenty years ago.

Talk 3:

On Fair Clustering.

by Sara Ahmadian.

Abstract: From digital assistant, to movie recommendation, and self driving cars, machine learning is behind many day-to-day interactions with technology. While learning algorithms are not inherently biased, they may pick up and amplify the bias already present in the training data. Thus a recent line of work has emerged on revising traditional algorithms or devising new algorithms to factor in fairness. In this talk, I focus on adding fairness to clustering which is a fundamental problem in data mining and unsupervised machine learning. We introduce a notion of fairness that focuses on requiring a bounded representation of various groups of a sensitive feature, e.g. race, gender, etc., in each cluster.

In clustering, the goal is to organize objects into clusters such that elements in the same clusters are “similar”. There are various ways to express the similarity of objects. In metric settings, we are given a distance measure for the objects, and in a non-metric setting, we are given labels in the form of {+,-} for pairs of objects which identify whether two objects are similar (label +) or not (label -). We look at a fair k-center for the metric case and fair correlation clustering for the non-metric case. In addition to flat clusterings which focus on outputting just one set of clusters, I will talk about hierarchical clustering and how the algorithms for this problem can be modified to accommodate fairness constraints.

Talk 4:

Hierarchical Clustering of Graphs.

By Vaggos Chatziafratis.

Abstract: Hierarchical Clustering is a popular tool in unsupervised learning that partitions a dataset in a hierarchical manner. Despite its long history and plethora of heuristics, a principled framework for understanding its optimization properties had been missing. A few years ago, Dasgupta proposed a new objective function for this problem, spurring a flurry of work on designing new algorithms and shedding light on old algorithms for hierarchical clustering. In this talk, I will provide an overview of some of these developments and highlight several open questions in the area.