🤖 machine learning

Adaptive Sampling and Clipping for Private Worst-Case Group Optimization

This paper introduces ASC, a novel algorithm that simultaneously ensures differential privacy and improves worst-case group fairness by adaptively controlling sampling rates and gradient clipping thresholds to prioritize harder-to-learn groups without compromising overall model utility.

Original authors: Max Cairney-Leeming, Amartya Sanyal, Christoph H. Lampert

Published 2026-05-28

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Max Cairney-Leeming, Amartya Sanyal, Christoph H. Lampert

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Problem: The "Privacy vs. Fairness" Dilemma

Imagine you are running a school to train a robot to recognize different types of fruit. You have a huge basket of apples, oranges, and bananas. However, you only have a few rare "star fruits" and a massive pile of apples.

You want two things:

Fairness: The robot must be just as good at recognizing the rare star fruits as it is at recognizing the common apples. If it only learns about apples because there are so many, it fails the "fairness" test.
Privacy: You want to teach the robot using photos of fruit that people sent you, but you must ensure that no one can figure out which specific person sent which photo.

The Conflict:
Usually, when you try to protect privacy (by adding "noise" or static to the data to hide individual contributions), the robot gets confused. It tends to ignore the rare groups (the star fruits) even more than usual because their signals are too weak to cut through the privacy noise. Meanwhile, if you try to force the robot to focus on the rare groups to be fair, you might accidentally reveal private information about the few people who sent those rare photos.

Until now, there wasn't a good way to do both at the same time.

The Solution: ASC (Adaptive Sampling and Clipping)

The authors propose a new method called ASC. Think of ASC as a very smart, fair, and cautious teacher.

1. The "Fairness" Trick: Adaptive Sampling

In a normal class, the teacher picks questions randomly from the whole basket. If there are 1,000 apples and 1 star fruit, the teacher will almost never pick the star fruit.

ASC changes the rules:
Instead of picking randomly, the teacher looks at the "weights" of the groups. If the star fruit group is struggling, the teacher intentionally picks more star fruit questions for that specific round of practice.

The Analogy: Imagine a coach training a team. If the left side of the team is weak, the coach doesn't just practice with the whole team randomly; they make sure the left side gets extra reps in that specific drill. ASC does this by adjusting how many samples it pulls from each group every time it learns.

2. The "Privacy" Trick: Adaptive Clipping

To protect privacy, the teacher has a rule: "No single student can shout too loud, or we'll know who they are." In math terms, this is called clipping. It limits how much any single data point can influence the robot's learning.

The Problem with Old Methods:
If you have a rare group (like the star fruits), you need to give them a "louder" voice to be heard fairly. But if you turn up their volume, you break the privacy rule because their contribution becomes too big.

ASC's Fix:
ASC is dynamic. It changes the "volume limit" (clipping threshold) for every group based on how many samples it just picked.

The Analogy: Imagine a sound mixer. If the teacher picks 50 star fruit questions (a lot), the volume limit for each individual star fruit question is lowered slightly so the total volume stays safe. If they only pick 1 star fruit question, the volume limit is raised so that single question can still be heard clearly.
The Result: The rare groups get the attention they need to learn, but the "loudness" is always adjusted so that no single person's data can be identified.

Why This is Better Than Previous Attempts

The paper compares ASC to other methods:

The "Naive" Approach (DP-SGD): This is like the teacher ignoring the rare groups entirely because they are too hard to protect. The robot becomes great at apples but terrible at star fruits.
The "Reweighting" Approach: This is like the teacher trying to shout "Star Fruit!" louder during the lesson. It helps a bit, but it creates a lot of "static" (variance), making the learning process shaky and slow.
The "Zhou & Bassily" Approach: This is an older method that tries to pick groups randomly based on their importance. The paper argues this is like a teacher who picks one group for the whole hour. If they pick the rare group, they only get 10 minutes of practice; if they pick the common group, they get 50 minutes. It's inefficient and unstable.

ASC's Advantage:
ASC mixes the groups together in every single step. It pulls a few from here, a few from there, adjusting the volume limits on the fly.

The Result: The robot learns much faster and more stably. It achieves high accuracy for the rare groups (the "worst-case" groups) without sacrificing its overall skill or breaking privacy rules.

The Bottom Line

The paper claims that ASC is a practical, working algorithm that solves the "privacy vs. fairness" conflict.

It works: In tests on datasets like handwritten digits (where some numbers are rare) and face recognition (where some demographics are rare), ASC achieved much higher accuracy for the rare groups than any previous private method.
It's stable: It doesn't get confused by the "noise" added for privacy as much as other methods.
It's safe: It mathematically guarantees that user data remains private, even while giving extra attention to underrepresented groups.

In short, ASC is a new way to train AI that says: "We can protect everyone's privacy and make sure the AI is fair to the smallest groups, without having to choose between the two."

Technical Summary: Adaptive Sampling and Clipping for Private Worst-Case Group Optimization

Problem Statement

The paper addresses the challenge of training machine learning models that simultaneously satisfy two critical requirements: fairness and privacy. Specifically, the authors focus on worst-case group optimization (WGO), which aims to maximize the accuracy of the worst-performing demographic group (Rawls's max-min criterion), while adhering to differential privacy (DP) to protect user data.

Existing literature indicates a fundamental conflict between these goals. Standard differentially private stochastic gradient descent (DP-SGD) often exacerbates fairness issues, leading to significantly lower accuracy for minority groups compared to standard SGD. While prior works have attempted to mitigate DP-induced unfairness or proposed private WGO algorithms (e.g., Zhou and Bassily [2024]), these approaches suffer from practical limitations:

Unfairness Mitigation: Methods that only adjust DP-SGD's internal mechanics fail to address scenarios where standard SGD itself is unfair.
Prior Private WGO: Existing private WGO algorithms often rely on assumptions (e.g., balanced group sizes) that do not hold in real-world datasets, or they exhibit poor experimental performance due to high variance and inefficient sampling strategies.

Methodology

The authors propose ASC (Adaptively Sampled and Clipped Worst-case Group Optimization), a practical algorithm designed to optimize worst-group accuracy under differential privacy constraints. The core innovation lies in moving beyond simple loss reweighting to fundamentally altering the sampling and clipping mechanisms of DP-SGD.

1. The ASC Algorithm

ASC operates by adaptively controlling two parameters for each group $g$ at every training step:

Adaptive Sampling: Instead of sampling a uniform batch from the entire dataset and reweighting gradients (which introduces high variance for minority groups), ASC samples a specific number of points $m_g$ from each group $g$ within a single batch. The batch size for each group is proportional to the current group weight $\lambda_g$ (i.e., $m_g \approx \lambda_g M$ ). This ensures the expected update matches the WGO objective directly.
Balanced Clipping: To maintain a consistent privacy guarantee despite varying sampling rates ( $m_g/n_g$ ), ASC adaptively sets the gradient clipping threshold $\xi_g$ for each group. The threshold is calculated such that the Rényi Differential Privacy (RDP) guarantee for the step remains fixed at a predefined budget $(\alpha, \epsilon_s)$ , regardless of the group size or sampling rate. This allows the algorithm to add noise to the sum of group updates rather than individual updates, reducing total noise.

2. Baselines and Comparisons

The paper evaluates ASC against several baselines:

DP-SGD: Standard private training.
DP Loss Reweighting (DP-LRW): A new baseline that applies standard DP-SGD but reweights gradients based on group importance. The authors note this introduces significant variance due to the rescaling of gradients.
aZB (Zhou and Bassily [2024]): A prior private WGO method that samples batches from groups based on categorical probabilities. The authors identify that this method suffers from high variance and poor privacy guarantees when group sizes are imbalanced, as the privacy cost is dictated by the smallest group.
aZB-prop: A variant of aZB using proportional sampling to equalize privacy guarantees, though it still suffers from high sampling variance.

3. Theoretical Analysis

The authors provide a convergence analysis for noisy WGO algorithms, decomposing the error into terms related to the optimization landscape and sampling variance.

Theorem 3 demonstrates that ASC has a significantly lower sampling variance compared to aZB and aZB-prop.
Unlike aZB, which includes a term for inter-group discrepancy that does not shrink with batch size, ASC's variance is solely a weighted combination of within-group variances because it samples from all groups in every step.
The paper proves that ASC satisfies $(\alpha, \epsilon)$ -RDP by composing the guarantees of the adaptive model update steps and the periodic group reweighting steps.

Key Contributions

A New Baseline: Introduction of DP-LRW, a simple, easy-to-implement baseline that privatizes loss reweighting, showing improvements over standard DP-SGD but highlighting variance issues.
The ASC Algorithm: A practical algorithm for private WGO that uses adaptive stratified sampling and adaptive clipping thresholds. This design allows the model to prioritize harder-to-learn groups without compromising privacy guarantees or model utility.
Convergence Analysis: A theoretical study establishing that the sampling variance is a primary differentiator between WGO algorithms, proving ASC's superior stability compared to prior methods.
Experimental Validation: The first comprehensive experimental comparison of private WGO algorithms, demonstrating that ASC achieves state-of-the-art worst-case group accuracy without sacrificing overall average accuracy.

Experimental Results

The authors evaluated ASC on three datasets: Unbalanced MNIST (digit classification with downsampled classes), CelebA (face attributes with demographic imbalances), and Bank Account Fraud (tabular data with fraud/age groups).

Performance: ASC consistently outperformed all baselines. On the CelebA dataset, ASC achieved a worst-case group accuracy (WGA) 30% higher than the next best method. On Unbalanced MNIST, ASC reached 75.2% WGA compared to 20.4% for standard DP-SGD.
Variance: Empirical measurements confirmed the theoretical analysis, showing ASC exhibits approximately a 100-fold reduction in sampling variance compared to aZB and aZB-prop.
Privacy Budgets: ASC maintained robust performance across a range of privacy budgets ( $\epsilon \in [0.1, 5]$ ), whereas other methods (like DP-SGD-F) only showed significant improvements at higher, less private $\epsilon$ values.

Significance and Claims

The paper claims to provide the first practical method for enforcing both worst-case group fairness and differential privacy simultaneously. The authors argue that previous approaches were either theoretically sound but practically ill-suited (e.g., failing on imbalanced data) or failed to address the root causes of unfairness in private learning.

By decoupling the sampling strategy from the privacy mechanism through adaptive clipping, ASC resolves the tension between the need to upweight minority groups (for fairness) and the need to bound sensitivity (for privacy). The authors conclude that their work offers a positive societal impact by enabling the training of fair and private machine learning models, a prerequisite for trustworthy AI in human-centric applications. They acknowledge fundamental privacy limitations regarding extremely small groups but note that their method significantly improves upon existing baselines even in these challenging settings.