Adaptive Sampling for Private Worst-Case Group Optimization
This work addresses a critical issue in fair and private machine learning by ensuring consistent privacy across groups, which is important for applications involving sensitive data, though it is incremental as it builds on existing worst-case group optimization methods.
The paper tackles the problem of ensuring consistent privacy guarantees across all groups in differentially private worst-case group optimization, where unequal data weighting can weaken privacy for minority groups. The proposed ASC algorithm adaptively controls sampling and clipping, resulting in lower-variance gradients, tighter privacy guarantees, and substantially higher worst-case group accuracy without sacrificing average accuracy.
Models trained by minimizing the average loss often fail to be accurate on small or hard-to-learn groups of the data. Various methods address this issue by optimizing a weighted objective that focuses on the worst-performing groups. However, this approach becomes problematic when learning with differential privacy, as unequal data weighting can result in inhomogeneous privacy guarantees, in particular weaker privacy for minority groups. In this work, we introduce a new algorithm for differentially private worst-case group optimization called ASC (Adaptively Sampled and Clipped Worst-case Group Optimization). It adaptively controls both the sampling rate and the clipping threshold of each group. Thereby, it allows for harder-to-learn groups to be sampled more often while ensuring consistent privacy guarantees across all groups. Comparing ASC to prior work, we show that it results in lower-variance gradients, tighter privacy guarantees, and substantially higher worst-case group accuracy without sacrificing overall average accuracy.