Adaptive Sampling for Minimax Fair Classification
This addresses fairness issues in machine learning for underrepresented groups, presenting a novel method with theoretical and empirical validation.
The paper tackles the problem of machine learning models adversely affecting underrepresented groups by proposing an adaptive sampling algorithm to construct training sets for minimax fair classification, achieving theoretical performance bounds and validating benefits on synthetic and real-world tasks.
Machine learning models trained on uncurated datasets can often end up adversely affecting inputs belonging to underrepresented groups. To address this issue, we consider the problem of adaptively constructing training sets which allow us to learn classifiers that are fair in a minimax sense. We first propose an adaptive sampling algorithm based on the principle of optimism, and derive theoretical bounds on its performance. We also propose heuristic extensions of this algorithm suitable for application to large scale, practical problems. Next, by deriving algorithm independent lower-bounds for a specific class of problems, we show that the performance achieved by our adaptive scheme cannot be improved in general. We then validate the benefits of adaptively constructing training sets via experiments on synthetic tasks with logistic regression classifiers, as well as on several real-world tasks using convolutional neural networks (CNNs).