Introduction: The Fairness Tax in Differential Privacy
Differential Privacy (DP) has become the gold standard for protecting individual privacy in machine learning. However, this protection often comes with a "fairness tax." Standard DP training techniques, such as DP-SGD, rely on gradient clipping to limit the influence of any single data point. Unfortunately, samples from minority groups or "hard" examples often produce gradients with larger magnitudes because the model has not yet learned them effectively. When these gradients are clipped, the unique signal from these groups is disproportionately suppressed, leading to a significant drop in accuracy for underrepresented populations—a phenomenon known as disparate impact.
The "Vanishing Bound" Problem
Recent advancements in DP training have turned to adaptive clipping, where the clipping threshold ($C$) is dynamically adjusted during training based on the distribution of gradient norms. While this approach aims to find an optimal threshold automatically, it suffers from a critical failure mode identified in this work.
As training progresses and the model begins to fit the majority of the data, the typical gradient norm decreases. In an unbounded adaptive setting, the clipping threshold follows this downward trend. Eventually, the threshold shrinks to near-zero values. While this might be appropriate for well-fitted majority samples, it effectively silences minority groups whose gradients remain relatively large. Their signals are crushed down to the same tiny magnitude as the majority's noise, turning the optimization process into a "majority vote" that ignores the tail of the distribution.
Proposed Method: Bounded Adaptive Clipping
To address this, the authors propose Bounded Adaptive Clipping. The core idea is simple yet effective: introduce a tunable lower bound, $C_{LB}$, to the adaptive clipping threshold. This "floor" ensures that even as the majority of the data becomes well-fitted, the clipping bound remains high enough to preserve the directional signal and relative importance of gradients from minority groups.
The update rule for the clipping threshold $C_t$ is modified as follows: $$C_{t+1} \leftarrow \max(C_{LB}, C_t \cdot \exp(\eta_C(\tilde{b}_t - \gamma)))$$ where $\tilde{b}_t$ is a private estimate of the fraction of gradients clipped, $\gamma$ is the target quantile, and $\eta_C$ is the learning rate for the threshold.
This approach offers several advantages:
- Simplicity: It does not require knowledge of group labels or sensitive attributes during training.
- Privacy-Preserving: It maintains formal DP guarantees using Gaussian DP composition.
- Robustness: By preserving the signal-to-noise ratio for hard samples, it makes the training process more resilient to the noise inherent in DP optimization.
Experimental Evaluation
The researchers evaluated Bounded Adaptive Clipping across various datasets, including image classification (Fashion MNIST, Skewed MNIST) and tabular census data (Adult, Dutch).
Key findings include:
- Skewed MNIST: In a scenario where one class is significantly undersampled, the bounded approach improved minority class accuracy by over 10 percentage points compared to the unbounded baseline.
- Fashion MNIST: The method achieved a 5 percentage point improvement in worst-case accuracy over standard constant clipping.
- Tabular Data: On the Adult and Dutch datasets, the method reached near-optimal fairness and accuracy metrics even at very low privacy budgets (low $\epsilon$).
- Hyperparameter Robustness: The method proved more stable during DP-aware hyperparameter optimization (DPHPO), which is often a bottleneck for deploying DP models.
Conclusion
Bounded Adaptive Clipping provides a practical and effective solution to the disparate impact problem in differentially private learning. By preventing the clipping threshold from vanishing, it ensures that the "voice" of minority groups is preserved throughout the training process. This work highlights that sometimes the most robust solutions in privacy-preserving ML come from simple, well-motivated constraints on existing adaptive mechanisms.
Summary updated