🤖 machine learning

INO-SGD: Addressing Utility Imbalance under Individualized Differential Privacy

This paper introduces INO-SGD, a novel algorithm designed to address the critical utility imbalance problem in Individualized Differential Privacy by strategically down-weighting data within each batch to ensure better model performance on highly private data without compromising privacy guarantees.

Original authors: Xiao Tian, Jue Fan, Rachael Hwee Ling Sim, Bryan Kian Hsiang Low

Published 2026-05-11

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Xiao Tian, Jue Fan, Rachael Hwee Ling Sim, Bryan Kian Hsiang Low

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 Picture: A Classroom with Different Privacy Rules

Imagine a teacher (the Model Owner) trying to teach a class by gathering homework from many students (the Data Owners). The goal is to build a smart study guide (the AI Model) that helps everyone pass their exams.

However, some students are very private. They are worried that if their specific homework is seen, it could reveal sensitive secrets about them (like a stigmatized disease or a difficult personal situation). So, they ask for stronger privacy protection. Other students are less worried and are okay with weaker protection.

In the past, to protect everyone, the teacher had to treat the whole class the same: either give everyone weak protection (risking the sensitive students) or give everyone super-strong protection (which makes the study guide so blurry and vague that nobody learns anything well).

Recently, a new method called IDP-SGD was invented. It lets each student choose their own privacy level. The private students get strong protection; the others get weaker protection. This sounds perfect, right?

The Problem: The paper discovers a hidden flaw in this new method. Because the private students' data is heavily "blurred" to protect them, the teacher's study guide ends up being bad at helping those specific private students. Meanwhile, the guide works great for the less-private students.

The paper calls this "Utility Imbalance." It's like a doctor's training model that is great at diagnosing common colds but terrible at diagnosing rare, stigmatized diseases because the data for those rare diseases was too "protected" during training.

The Solution: INO-SGD (The Smart Grader)

The authors propose a new algorithm called INO-SGD. Think of it as a Smart Grader who looks at the homework before the teacher tries to learn from it.

Here is how it works, using a metaphor of a Noisy Kitchen:

The Ingredients (Data): Imagine the teacher is making a soup (the model). The ingredients are the homework assignments.
The Noise (Privacy): To protect the students, the teacher adds "privacy noise" (like salt) to the soup. The more private the student, the more salt is added to their specific ingredient.
The Imbalance: If you add too much salt to the private ingredients, they become so salty that the chef ignores them or they ruin the flavor for everyone else. The chef ends up relying mostly on the less-salty (less private) ingredients. The final soup tastes great for people who like the less-salty flavor, but it's useless for the people who need the salty flavor.

How INO-SGD fixes this:
Instead of just throwing all ingredients into the pot equally, the Smart Grader (INO-SGD) looks at the homework and asks: "How hard is this to learn?"

Hard-to-learn data: If a piece of homework is very difficult to understand (which often happens with highly private data because the noise makes it fuzzy), the grader says, "This is important! We need to focus on this." It gives this data a high score.
Easy-to-learn data: If a piece of homework is easy to understand (often from less private students), the grader says, "We already know this. We can ignore a bit of this." It gives this data a lower score.

The Magic Trick:
The algorithm doesn't just throw away the easy data (which would waste privacy budgets). Instead, it down-weights the easy data. It tells the teacher: "Focus 80% of your attention on the hard, private data, and only 20% on the easy data."

By doing this, the teacher learns how to handle the difficult, private data without needing to add even more noise. The result is a study guide that works well for everyone, including the most private students, without sacrificing the overall quality of the guide.

Why Existing Fixes Didn't Work

The paper explains why you can't just use old tricks to fix this:

Oversampling: You can't just "copy-paste" the private students' homework to make them appear more often. That would break their privacy rules.
Undersampling: You can't just throw away the easy homework from the less private students. That wastes their privacy budget and makes the whole soup less flavorful.
Standard Balancing: Old methods assume the problem is that there are fewer private students. But in this case, there might be equal numbers of students; the problem is that the privacy rules make the private data look "smaller" and "fuzzier" to the algorithm.

The Results: A Fairer Outcome

The authors tested this on various datasets (like images of handwritten numbers, medical X-rays, and animal photos). They found that:

Better for the Private: The private students (or the groups with strict privacy rules) got much better results. Their "grades" (model accuracy) went up significantly.
No Loss for Others: The less private students didn't lose much. In fact, the overall model often got slightly better because it stopped wasting time on the "easy" stuff and focused on the "hard" stuff.
Privacy is Safe: The new method still strictly follows the privacy rules. The private students are just as protected as before; the algorithm just learned how to listen to them more effectively.

Summary Analogy

Imagine a Team of Hikers trying to reach a summit.

Old Method: Everyone walks at the speed of the slowest hiker. The fast hikers get bored and tired.
IDP-SGD (The Flawed Method): Everyone walks at their own pace, but the slow hikers (private data) are wearing heavy, blurry goggles. The team leader (the model) ends up ignoring the slow hikers because they are hard to see, and the team moves fast but leaves the slow hikers behind.
INO-SGD (The Solution): The team leader realizes the slow hikers are actually carrying the most important map pieces, even though they are hard to see. The leader tells the fast hikers, "Slow down a little and pay extra attention to the slow hikers." The whole team reaches the summit together, and the slow hikers are finally included in the journey.

The paper proves that by strategically paying more attention to the difficult, private data and paying less attention to the easy data, we can build AI models that are fair, accurate, and respectful of everyone's privacy.

Technical Summary: INO-SGD: Addressing Utility Imbalance Under Individualized Differential Privacy

Problem Statement

The paper addresses a critical limitation in Individualized Differential Privacy (IDP), a framework allowing data owners to set distinct privacy budgets ( $\epsilon_n$ ) based on their sensitivity requirements. While existing IDP algorithms (specifically IDP-SGD variants: SAMPLE and SCALE) successfully satisfy individual privacy constraints, they inadvertently induce a severe utility imbalance problem.

In IDP-SGD, data owners with stronger privacy requirements (lower $\epsilon_n$ ) are assigned either lower sampling rates (in SAMPLE) or smaller gradient clipping thresholds (in SCALE). Consequently, during training, gradients from these "more private" owners contribute less to the model update compared to gradients from "less private" owners. The paper identifies two specific negative phenomena resulting from this imbalance:

Minority Initial Drop (MID): An initial phase where the model utility for the more private groups fails to improve or even degrades, while utility for less private groups improves normally.
Biased Optimization Objective (BOO): The final trained model converges to a state that favors the less private groups, resulting in significantly poorer performance on data from the more private owners.

Crucially, the authors argue that existing techniques for correcting data imbalance (e.g., oversampling, loss rescaling) are unsuitable for IDP because they either violate individual privacy budgets, under-utilize available privacy budgets (reducing overall utility), or have their effects nullified by the gradient clipping mechanisms inherent to DP.

Methodology: INO-SGD

To resolve this, the authors propose INO-SGD (Individualized Noisy Ordered SGD). The core intuition is to strategically down-weight less important gradients within each batch without violating IDP constraints.

Key Mechanism

Loss-Based Ordering: Within each sampled batch, gradients are sorted in descending order based on their individual loss values. The authors posit that higher loss gradients represent "harder" or more important data points that the model needs to learn, regardless of the owner's privacy level.
Tail Importance Function (TIF): A predefined function, $f_{tail}$ $f_{t ai l}$ , maps the position of a gradient in the sorted list to an importance score between 0 and 1.
- Gradients in the "head" (high loss) are assigned a score of 1 (fully kept).
- Gradients in the "tail" (low loss) are assigned scores $< 1$ (down-weighted).
Batch Importance Function (BIF): The TIF is transformed into a BIF, $f_t$ , which assigns importance scores to the continuous range of accumulated clipping thresholds within the batch.
Weighted Clipping: Instead of simply clipping gradients to the owner's threshold $C_{o(d)}$ $C_{o (d)}$ , INO-SGD scales the clipped gradient by its calculated importance score $\rho_k$ $ρ_{k}$ .
- If a gradient is deemed unimportant (low loss), its norm is restricted to a value strictly smaller than $C_{o(d)}$ .
- This reduction in the norm of "easy" gradients creates "room" within the total modular sensitivity budget to effectively preserve the contribution of "hard" gradients (often from more private owners) without increasing the total noise scale.
Privacy Preservation: The algorithm ensures that the modular sensitivity of the mechanism with respect to any single datum $d$ remains bounded by its owner's clipping threshold $C_{o(d)}$ . This is achieved because the re-weighting is based on the order of losses (derived from the previous iteration's model, which is already DP-protected) and the total change in the summed gradient upon adding/removing a datum is mathematically bounded by the datum's own clipping threshold.

Key Contributions

Identification of IDP-Induced Utility Imbalance: The paper theoretically demonstrates that even on balanced datasets, IDP-SGD induces utility imbalance (MID and BOO) due to the disparity in sampling rates and clipping thresholds required to satisfy individual privacy budgets.
The INO-SGD Algorithm: A novel optimization algorithm that satisfies IDP while mitigating utility imbalance. It achieves this by down-weighting low-loss gradients (often from less private owners) to prioritize high-loss gradients (often from more private owners), effectively optimizing a different objective function.
Theoretical Guarantees:
- Privacy: Proven to satisfy $(\alpha, \bar{\epsilon})$ -Rényi Individualized Differential Privacy (IRDP) with the same privacy consumption rate as standard IDP-SGD.
- Objective: The algorithm is shown to effectively minimize a Mixed Conditional Value-at-Risk (CVaR) objective (or an Ordered Weighted Average with non-increasing weights). This objective prioritizes reducing the losses of the worst-off groups (more private owners) rather than minimizing the average loss.
Generalization (INO-SGM): The authors generalize the mechanism to INO-SGM (Individualized Noisy Ordered Gaussian Mechanism), applicable to any function where data ordering is important, not just gradient descent.

Experimental Results

The authors evaluated INO-SGD against IDP-SGD across various datasets (MNIST, CIFAR-10, CIFAR-100, Pneumonia, Cardiotocography) and models (CNNs, ResNet-18, LSTMs).

Utility Balance: INO-SGD consistently improved the performance (recall/accuracy) of the more private data owners. In several experiments, the performance gap between private and less private groups was significantly reduced.
Overall Utility: Contrary to the typical privacy-utility tradeoff, INO-SGD did not sacrifice overall model utility. In many cases, it achieved equal or slightly higher overall accuracy compared to IDP-SGD. The authors attribute this to the removal of "noisy" or less informative gradients that distract the model.
Robustness: The algorithm demonstrated robustness to hyperparameter choices (tail length $\gamma$ , Beta distribution parameters $\alpha, \beta$ ) and remained effective under label noise and adaptive clipping settings.
Privacy Verification: Membership Inference Attacks (LiRA) confirmed that INO-SGD provides privacy protection comparable to IDP-SGD, with no significant leakage.

Significance and Claims

The paper claims to be the first work to identify and address the specific problem of IDP-induced utility imbalance. Its significance lies in:

Ethical AI: It ensures that the deployment of privacy-preserving models does not inadvertently discriminate against users with sensitive data (e.g., patients with stigmatized diseases) by providing them with a model that performs poorly on their specific data.
Efficiency: It resolves the tradeoff where satisfying individual privacy requirements previously led to suboptimal model performance for specific groups. INO-SGD allows model owners to utilize the full privacy budgets of all owners while maintaining balanced performance.
Pareto Superiority: The authors demonstrate that INO-SGD Pareto-dominates naive approaches (like uniformly reducing privacy budgets or random undersampling), offering a superior tradeoff curve between overall utility and utility balance.

The authors modestly acknowledge that while INO-SGD improves balance, a fundamental IDP-balance-utility tradeoff still exists; pushing too aggressively for balance (via extreme down-weighting) can eventually degrade overall utility. However, INO-SGD pushes the Pareto frontier closer to the ideal than existing methods.