Theory for Society: Rigorous Foundations for the Practice of Algorithmic Fairness and Differential Privacy

Abstract

This dissertation comprises a series of works concerning problems at the intersection of computer science theory, computer science practice, and society. Techniques and insights from theoretical computer science can be used to great effect to address societal concerns, but the "last mile" of translating theory to practice is often a significant source of difficulty. Although the topics addressed in each chapter vary, they all follow from the same motivation: addressing the practical barriers between theory and society. In part one of this dissertation, we consider questions of fairness in automated decision-making. There has been an inspiring increase in work concerning the fairness and ethics of automated decision-making systems. However, the vast majority of this work considers evaluation of independent system components. We first consider the question of how fairness composes, i.e., whether two or more fair components can be combined to create a fair system. We demonstrate that fairness under composition is neither guaranteed nor expected and demonstrate the weaknesses of certain group-based fairness definitions under composition. Despite these negative results, we build up a set of fair composition mechanisms, including mechanisms for individually fair pipeline composition, that allow a high degree of autonomy and expressivity in each component, e.g., a resume screening procedure followed by a hiring decision. Finally, we consider the question of how to determine society's view of fairness through the lens of metric learning. In particular, we consider the question of how to learn a metric which captures society's view of who is similar to whom for a particular task. The lack of such a metric is a critical barrier to adoption of Individual Fairness. We propose a generalizable method for learning useful approximations to a metric for Individual Fairness based on limited interaction with a human "arbiter" of fairness. In the second part, we consider the practicalities of implementing privacy preserving data analyses. Although Differential Privacy has emerged as the de facto standard for rigorous privacy protection, practical implementations still face many challenges. We document a series of novel attacks based on vulnerabilities due to inexact arithmetic and propose a new view of Differential Privacy which allows for implementation with exact arithmetic and mitigates these vulnerabilities. We discuss the practicalities of the new implementation strategy, provide a reference implementation of the proposed procedures written in Rust and comment on its properties, and demonstrate that the workflow of proposing mechanisms and proving privacy need not be drastically changed to take advantage of the new implementation strategy.