PhD Defense: On Algorithmic Fairness and Stochastic Models for Combinatorial Optimization and Unsupervised Machine Learning
Leonidas Tsepenekas
Monday, October 17, 2022, 2:30-4:30 pm 
Abstract
Combinatorial optimization and unsupervised machine learning problems have been extensively studied
and are relatively well-understood. Examples of such problems that play a central role in our work are
clustering problems and problems of finding cuts in graphs. The goal of the research to be presented
was to introduce novel variants of the aforementioned problems, by generalizing their classic variants
into two, not necessarily disjoint, directions. The first direction involves incorporating fairness aspects to
a problem's specifications, and the second involves the introduction of some form of randomness in the
problem definition.
Fairness in the design of algorithms and in 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, that can potentially hurt the individuals or the groups
involved in the corresponding application. As far as considerations of fairness are concerned, we will
begin by presenting two novel individually-fair clustering models, 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 motivation behind both of them is
trying to treat similar individuals similarly. Moving forward, we focus on a graph cut problem that
captures situations of disaster containment in a network. For this problem we introduce two novel fair
variants. The first variant focuses on demographic fairness, while the second considers a probabilistic
notion of individual fairness. Again, we will demonstrate algorithms with provable guarantees for the
newly introduced variants.
In the next part of the presentation, we turn our attention to generalizing problems through the
introduction of stochasticity. At first, we present algorithmic results for a computational epidemiology
problem, whose goal is to control the stochastic diffusion of a disease in a contact network. This
problem can be interpreted as a stochastic generalization of a static graph cut problem. Finally, we will
discuss a well-known paradigm in stochastic optimization, namely the two-stage stochastic setting with
recourse. Two-stage problems capture a wide variety of applications revolving around the trade-off
between provisioning and rapid response. In this setting, we present a family of clustering problems that
had not yet been studied in the literature, and for this family we show novel algorithmic techniques that
provide constant factor approximation algorithms.
We conclude with a discussion on open problems and future research directions in the general area of
algorithmic fairness.
and are relatively well-understood. Examples of such problems that play a central role in our work are
clustering problems and problems of finding cuts in graphs. The goal of the research to be presented
was to introduce novel variants of the aforementioned problems, by generalizing their classic variants
into two, not necessarily disjoint, directions. The first direction involves incorporating fairness aspects to
a problem's specifications, and the second involves the introduction of some form of randomness in the
problem definition.
Fairness in the design of algorithms and in 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, that can potentially hurt the individuals or the groups
involved in the corresponding application. As far as considerations of fairness are concerned, we will
begin by presenting two novel individually-fair clustering models, 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 motivation behind both of them is
trying to treat similar individuals similarly. Moving forward, we focus on a graph cut problem that
captures situations of disaster containment in a network. For this problem we introduce two novel fair
variants. The first variant focuses on demographic fairness, while the second considers a probabilistic
notion of individual fairness. Again, we will demonstrate algorithms with provable guarantees for the
newly introduced variants.
In the next part of the presentation, we turn our attention to generalizing problems through the
introduction of stochasticity. At first, we present algorithmic results for a computational epidemiology
problem, whose goal is to control the stochastic diffusion of a disease in a contact network. This
problem can be interpreted as a stochastic generalization of a static graph cut problem. Finally, we will
discuss a well-known paradigm in stochastic optimization, namely the two-stage stochastic setting with
recourse. Two-stage problems capture a wide variety of applications revolving around the trade-off
between provisioning and rapid response. In this setting, we present a family of clustering problems that
had not yet been studied in the literature, and for this family we show novel algorithmic techniques that
provide constant factor approximation algorithms.
We conclude with a discussion on open problems and future research directions in the general area of
algorithmic fairness.
Examining Committee
Bio
Leonidas Tsepenekas is a PhD student at the Computer Science Department of the University of Maryland, College Park. He is co-advised by professors Aravind Srinivasan and John P. Dickerson. His research interests revolve around Algorithmic Fairness and Stochastic Models for Combinatorial Optimization. Specifically, he is interested in identifying meaningful notions of fairness, translating them into rigorous mathematical objects, and incorporating them in classical algorithmic problems. For instance, his work includes fairness in Clustering and Graph Cut problems. Furthermore, he studies the interplay of fairness and stochasticity, with emphasis on how the latter can ensure socially fair algorithmic solutions.
This talk is organized by Tom Hurst