Speaker: Heather Newman (Carnegie Mellon University)

Title: The Best of Both Worlds: Fast Clustering Algorithms for Simultaneously Optimizing Fairness and Average Welfare

The seminar will be available for in-person and Zoom participation. To participate online, please email inquiry-cs@barnard.edu to receive the Zoom link.

In algorithm design and analysis, one measure of the quality of an algorithm is the score, commonly known as the objective function value, that we assign to the algorithm’s decisions. The traditional goal is to obtain algorithms that provably return (near) optimal scores on any input. However, the onus is on the algorithm designer to choose what objective function to optimize for, often among many natural and reasonable choices, each capturing a different notion of quality. For example, in many problems in clustering and resource allocation, the choices for the objective lie on an infinite spectrum, ranging from average welfare on one end, to individual fairness on the other. Importantly, algorithms tailored to one objective may perform arbitrarily poorly for other objectives. The thrust of this talk is the question: do we necessarily need to sacrifice quality in one objective, say average welfare, for quality in another objective, say fairness?

In this talk, I will answer this question for the problem of correlation clustering, a versatile clustering model popular in both the theory and machine learning communities, with applications to social networks, genomics, natural language processing, and image segmentation. I will discuss my work showing that for this problem, there is a so-called universal algorithm that returns near optimal solutions for infinitely many objectives, ranging from average welfare to individual fairness, simultaneously. I will then discuss the positive by-products that can come from the new structural insights gained during the search for universal algorithms. These include the discovery of faster algorithms that scale to today’s large datasets, and of techniques that are more adaptable than traditional techniques to other algorithmic models, such as models that demand robustness to uncertainty.

Heather Newman is a PhD candidate in the interdisciplinary Algorithms, Combinatorics, and Optimization program at Carnegie Mellon University, advised by Benjamin Moseley. She works at the intersection of theoretical computer science and operations research, with a focus on the design and analysis of algorithms that are provably fair, fast, and robust to uncertainty, particularly for problems in clustering and resource allocation. She is also interested in the burgeoning field of beyond worst-case models for decision-making under uncertainty. Her research has been published in top theory, ML, and operations research venues, including ICALP, ICML, and Math Programming B. She holds an A.B. in Mathematics from Princeton University and an M.Sc. in Mathematical Sciences from the University of Oxford.