Adaptive Sampling and Clipping for Private Worst-Case Group Optimization

A central requirement for the acceptance of machine learning methods for human-centric tasks is that they should be fair, in the sense that they should work comparably well for individuals from different societal groups. A second, equally important, requirement is that they should respect the privacy of user data. While techniques exist to address each aspect in isolation, such as worst-case group optimization for the former and differentially private SGD for the latter, these are often at odds with with each other, and no practical method currently exists to enforce both requirements simultaneously. In this work, we overcome this problem and propose an algorithm for optimizing the worst-case group accuracy in a differentially private way. Our main contribution is ASC (Adaptively Sampled and Clipped Worst-case Group Optimization), which adaptively controls both the sampling rate and the clipping threshold of each group's gradient contributions. Thereby, it is able to reweight the training objective in favor of harder-to-learn groups, while keeping the noise required to enforce privacy low enough to preserve model utility. Our experiments show that ASC achieves substantially higher worst-case group accuracy than prior work, without sacrificing overall average accuracy.