PhD Proposal: On Algorithmic Fairness and Stochastic Models for Combinatorial Optimization and Unsupervised Machine Learning

Classical Combinatorial Optimization problems like clustering or finding cuts in graphs, have been extensively studied and are relatively well-understood. My proposed research focuses on two non-disjoint directions, and those are incorporating fairness aspects to such problems and also considering stochastic variants of them.Fairness in algorithm design and machine learning has received a significant amount of attention during the last few years, mainly due to the realization that standard optimization approaches can frequently lead to severely unfair outcomes for the individuals or groups involved in the corresponding application. We will begin the talk by presenting two individually-fair clustering models that we developed, together with algorithms with provable guarantees for them. The first such model exploits randomness in order to provide fair solutions, while the second is purely deterministic. The high-level idea behind each of them is that they try to treat similar individuals similarly. Moving forward, we will demonstrate two novel fair variants of a graph cut problem, which aims to capture situations of disaster containment. The first variant focuses on demographic fairness, while the second considers a probabilistic notion of individual fairness. Again, we provide algorithms with provable guarantees.Furthermore, my research involves a well-known paradigm in Stochastic Optimization, and that is the two-stage stochastic setting with recourse. In that setting, we will present a family of clustering problems that had not yet been studied in the literature, and for this family we will show novel algorithmic techniques that provide constant factor approximation algorithms. The aforementioned problems capture a wide variety of applications revolving around the trade-off of provisioning vs rapid response, with fair variants also considered.Finally, we will talk about open problems and future research directions in the general area of Algorithmic Fairness.Examining Committee:

Chair:Department Representative:Members:

Dr. Aravind Srinivasan Dr. Hal Daume Dr. John Dickerson Dr. Ravi Kumar