Talk title: The Best of Both Worlds: Fast Clustering Algorithms for Simultaneously Optimizing Fairness and Average Welfare
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.