Mitigating Disparate Impact of Differentially Private Learning through Bounded Adaptive Clipping

Conference: NeurIPS 2025 arXiv: 2506.01396 Code: Expected to be released Area: AI Safety / Privacy-Preserving Machine Learning Keywords: Differential Privacy, Fairness, Gradient Clipping, DP-SGD, Disparate Impact

TL;DR

By introducing a tunable lower bound into adaptive gradient clipping (bounded adaptive clipping), this work prevents the clipping bound from shrinking excessively during training, thereby improving accuracy for minority groups and mitigating algorithmic unfairness under DP constraints.

Background & Motivation

Background: Differential privacy (DP) has been widely adopted in privacy-preserving machine learning and serves as a key technical underpinning for regulations such as the GDPR.

Limitations of Prior Work: Gradient clipping in DP learning suppresses large gradients, disproportionately harming minority groups and difficult classes. Adaptive clipping (Andrew et al., 2021) attempts to alleviate this but still causes the clipping bound to shrink without bound—when majority gradients become small while minority gradients remain large, the bound decays exponentially.

Key Challenge: Privacy and fairness are conflicting objectives: strong privacy requires large noise and low clipping bounds, which in turn intensifies the suppression of minority groups.

Key Insight: Introduce a tunable parameter \(C_{LB}\) (lower bound) to prevent the clipping bound from shrinking excessively while preserving the DP guarantee.

Core Idea: \(C_{t+1} \leftarrow \max(C_{LB}, C_t \cdot \exp(\eta_C(\tilde{b}_t - \gamma)))\)—a minimal modification that prevents exponential decay.

Method

Overall Architecture

A lower bound parameter \(C_{LB}\) is added on top of the standard adaptive clipping in DP-SGD. When the adaptive mechanism attempts to reduce the clipping bound below \(C_{LB}\), the bound is truncated at that value.

Key Designs

1. Problem Diagnosis (Toy Example)

   • Function: Reveals the exponential decay problem of adaptive clipping.
   • Mechanism: A bimodal distribution (60% at 0, 40% at 1, true mean \(\mu=0.4\)) with MSE loss yields gradients \(g_i = x_i - \hat{\mu}_t\). As \(\hat{\mu}_t \to 0\) (the majority center), majority gradients shrink while minority gradients grow → unbounded adaptive clipping continuously reduces \(C\) → minority gradients are fully clipped → \(\hat{\mu}_t\) converges to 0 (incorrectly).
   • Design Motivation: Provides an intuitive illustration of the problem's essence, laying a theoretical foundation for the proposed solution.

2. Bounded Adaptive Clipping

   • Function: \(C_{t+1} \leftarrow \max(C_{LB}, C_t \cdot \exp(\eta_C(\tilde{b}_t - \gamma)))\)
   • Mechanism: \(C_{LB} > 0\) prevents exponential decay, ensuring that the "effective" gradients of minority groups can still contribute to model updates.
   • Design Motivation: In the toy model, the unbounded case yields \(\hat{\mu} \to 0\), while the bounded case yields \(\hat{\mu} \approx 0.4\) (close to the true value).

3. Privacy Guarantee (Theorem 3.2)

   • Function: Proves that introducing \(C_{LB}\) does not alter the privacy composition.
   • Mechanism: Algorithm 2 (for any \(C_{LB} \geq 0\)) satisfies \((ε,δ)\)-DP.
   • Design Motivation: A genuine "free lunch"—fairness is improved without sacrificing the privacy guarantee.

Loss & Training

Standard DP-SGD training is employed, where per-sample gradients are clipped to \(C\) before Gaussian noise is added. \(C_{LB}\) is selected via grid search on a validation set, with the optimal range found to be \(C_{LB} \in [0.5, 1.5]\).

Key Experimental Results

Main Results (Skewed MNIST)

Method	Macro Accuracy	Worst-Class Acc	Disparity
Non-DP Baseline	96.8%	96.2%	0.6
Constant DP-SGD	93.2%	72.4%	20.8
Unbounded Adaptive	93.8%	78.3%	15.5
Bounded Adaptive	94.5%	89.2%	5.3

Ablation Study (\(C_{LB}\) Sensitivity)

\(C_{LB}\)	Skewed MNIST Worst-Acc	Fashion MNIST Worst-Acc
0.0 (Unbounded)	78.3%	82.1%
0.5	86.1%	85.2%
1.0	89.2%	86.7%
2.0	88.9%	85.8%
5.0	87.2%	84.3%

Key Findings

• vs. constant clipping: Worst-Class Acc improves by +16.8pp; disparity reduces from 20.8 to 5.3.
• vs. unbounded adaptive: Worst-Class Acc improves by +10.9pp.
• On tabular datasets (Dutch, Adult), gender disparity narrows from ~10pp to ~3pp.
• The bounded scheme is more stable under DP HPO (lower variance across runs).
• \(C_{LB} \in [0.5, 1.5]\) performs best across most tasks.

Highlights & Insights

• Precise Diagnosis: The exponential decay problem of adaptive clipping is clearly identified and intuitively demonstrated via a toy model. This diagnostic methodology is transferable to the analysis of other adaptive algorithms.
• Minimal Intervention: Only a single lower bound parameter is added, requiring no redesign of the overall algorithm and enabling easy integration into existing DP-SGD implementations.
• No Privacy Cost: Theorem 3.2 proves that \(C_{LB}\) does not affect the privacy guarantee, making this a genuine "free lunch."
• Cross-Domain Generality: The approach is effective on both image and tabular data, demonstrating broad applicability.

Limitations & Future Work

• Selecting \(C_{LB}\) requires HPO, introducing additional tuning cost; data-adaptive automatic selection could be explored.
• Theoretical convergence analysis is lacking—there is no formal characterization of when bounded clipping helps and when it does not.
• Experiments are conducted on relatively small datasets (Skewed MNIST); validation on large-scale real-world data is insufficient.
• Only accuracy parity is considered; other fairness criteria (equalized odds, calibration) are not addressed.

Related Work & Insights

• vs. Andrew et al. 2021 (Adaptive Clipping): The adaptive scheme improves over fixed thresholds but introduces exponential decay; this work fixes it with a lower bound.
• vs. Esipova et al. 2023: Esipova et al. identify the mismatch problem but their solution remains insufficient; this work provides a simpler and more effective remedy.

Rating

• Novelty: ⭐⭐⭐⭐ The lower bound parameter is clean but relatively straightforward.
• Experimental Thoroughness: ⭐⭐⭐⭐ Multiple datasets with comprehensive DP HPO evaluation.
• Writing Quality: ⭐⭐⭐⭐ Diagnosis is clear; theoretical presentation is concise.
• Value: ⭐⭐⭐⭐⭐ Reconciling privacy and fairness is an important open problem.

Related Papers

• [NeurIPS 2025] Enabling Differentially Private Federated Learning for Speech Recognition: Benchmarks, Adaptive Optimizers and Gradient Clipping
• [NeurIPS 2025] Differentially Private High-dimensional Variable Selection via Integer Programming
• [NeurIPS 2025] Differentially Private Bilevel Optimization: Efficient Algorithms with Near-Optimal Rates
• [NeurIPS 2025] FairContrast: Enhancing Fairness through Contrastive Learning and Customized Augmentation
• [NeurIPS 2025] Private Zeroth-Order Optimization with Public Data