📊 statistics

Integrating Feature Correlation in Differential Privacy with Applications in DP-ERM

This paper introduces **CorrDP**, a relaxed differential privacy framework that leverages total variation distance to account for correlations between sensitive and insensitive features, enabling more utility-efficient differentially private empirical risk minimization (DP-ERM) algorithms that outperform standard approaches when insensitive features are present.

Original authors: Tianyu Wang, Luhao Zhang, Rachel Cummings

Published 2026-05-06

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Tianyu Wang, Luhao Zhang, Rachel Cummings

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

Imagine you are a librarian trying to protect the privacy of your patrons. In the world of Differential Privacy (DP), the standard rule is: "If you want to keep a secret, you must add a little bit of 'static' or 'noise' to the information you release, so no one can tell exactly what any single person's data looks like."

For a long time, librarians (data scientists) treated every piece of information as if it were a top-secret state secret. Whether it was a person's medical history (very sensitive) or their favorite color (not very sensitive), the librarian added the same amount of static to both.

The Problem:
This "one-size-fits-all" approach is like putting a heavy steel lock on a diary and on a grocery list.

The Diaries (Sensitive Data): Need the heavy lock.
The Grocery Lists (Insensitive Data): Don't really need it.
The Catch: Sometimes, the grocery list hints at what's in the diary. For example, if your grocery list says "insulin," it reveals you have diabetes. If you only lock the diary but leave the grocery list open, someone can still guess the secret. But if you lock the grocery list too heavily, you ruin the usefulness of the list for everyone else.

The old methods either ignored the connection (leaking secrets) or locked everything too tightly (ruining the data's usefulness).

The New Solution: "CorrDP" (Correlation-Aware Differential Privacy)
The authors of this paper, Wang, Zhang, and Cummings, propose a smarter way to lock things up. They call it CorrDP.

Think of it like a smart security system that understands relationships.

It knows who is who: It identifies which features are "Sensitive" (like health status) and which are "Insensitive" (like age group).
It measures the "Gossip Factor": It calculates how much the insensitive feature "gossips" about the sensitive one. In math terms, they use something called Total Variation Distance.
- Analogy: If knowing someone's "Age Group" tells you almost nothing about their "Blood Pressure," the gossip factor is low. If knowing their "Zip Code" tells you exactly what their "Income" is, the gossip factor is high.
It adjusts the noise accordingly:
- If the gossip factor is low, the system adds very little noise to the insensitive feature. This keeps the data useful.
- If the gossip factor is high, the system adds more noise to the insensitive feature to protect the sensitive secret.

How They Tested It (The "Training" Analogy)
The paper focuses on a specific task called Empirical Risk Minimization (ERM). Imagine you are training a robot to predict house prices.

Standard DP: You teach the robot by showing it data, but you add a lot of static to every number (square footage, neighborhood, owner's name, owner's medical history). The robot gets confused and learns poorly.
CorrDP: You tell the robot, "The owner's medical history is a secret, so add heavy static there. The neighborhood is public, but it's slightly related to the medical history, so add a tiny bit of static there. The square footage is totally unrelated, so add no static."
The Result: The robot learns much better because the data is clearer, but the secrets are still safe.

Key Findings from the Paper

Better Accuracy: When they tested this on fake data and real-world datasets (like predicting income, credit card defaults, or medical costs), the CorrDP method produced much more accurate results than the standard method, while keeping the same level of privacy.
Handling the Unknown: Sometimes, you don't know exactly how much two features are related (the "gossip factor"). The paper shows a way to estimate this from the data itself without breaking the privacy rules.
Neural Networks: They showed this works even for complex AI models (Neural Networks), not just simple math problems.

In a Nutshell
The paper argues that we don't need to treat all data as equally dangerous. By understanding how different pieces of data are connected, we can be smarter about how we protect them. This allows us to keep secrets safe without throwing away the useful information that helps us make good decisions. It's the difference between locking the whole house in a vault versus just locking the safe, while keeping the windows open for the light to come in.

Technical Summary: Integrating Feature Correlation in Differential Privacy with Applications in DP-ERM

Problem Statement

Standard Differential Privacy (DP) imposes uniform privacy constraints across all features of a dataset, treating every feature as equally sensitive. This assumption often leads to overly conservative privacy-utility trade-offs in real-world applications where feature sensitivity is heterogeneous. For instance, in healthcare data, blood pressure readings may be highly sensitive, while age groups are less sensitive. However, these features are frequently correlated; revealing age can inadvertently leak information about blood pressure distributions.

Existing "semi-sensitive" DP approaches attempt to address this by treating some features as public and others as private. However, these methods often assume independence between sensitive and insensitive features. When correlations exist, treating a feature as public can still compromise the privacy of the sensitive feature it correlates with, leading to potential privacy violations. Conversely, applying uniform noise to all features (standard DP) distorts the dataset unnecessarily, degrading utility. The paper identifies a gap in existing literature: a lack of frameworks that rigorously account for correlations between sensitive and insensitive features to improve utility without sacrificing privacy guarantees.

Methodology: CorrDP Framework

The authors propose CorrDP (Correlation-aware Differential Privacy), a relaxed definition of DP that incorporates feature correlations into the privacy constraint.

1. Definition of CorrDP

CorrDP modifies the standard DP definition by introducing a distance metric $d(D, D')$ between neighboring databases $D$ and $D'$ .

Neighboring Databases: Defined as differing in at most one entry, where the difference occurs either in sensitive features ( $S$ ) or insensitive features ( $U$ ), but not both simultaneously.
Distance Metric: The privacy constraint is relaxed based on the correlation between the changed feature and the sensitive features.
$P(A(D) \in R) \leq e^{\frac{\epsilon}{d(D, D')}} P(A(D') \in R) + \delta$
Metric Choice: The paper utilizes Total Variation (TV) Distance to quantify the correlation. Specifically, $d(D, D')$ $d (D, D^{'})$ is defined as the maximum TV distance between the conditional distributions of sensitive features given the insensitive features before and after the change.
- If the change is in a sensitive feature, $d(D, D') = 1$ (standard DP).
- If the change is in an insensitive feature that is independent of sensitive features, $d(D, D') = 0$ (no privacy cost).
- If the change is in an insensitive feature correlated with sensitive features, $d(D, D') \in (0, 1)$ , relaxing the privacy budget to $\epsilon / d(D, D')$ .

2. Mechanisms and Algorithms

The authors adapt standard mechanisms to the CorrDP framework:

CorrDP Laplace Mechanism: Introduces a "correlated sensitivity" $\Delta_C f$ which weights the sensitivity of insensitive features by their TV distance to sensitive features. This allows for reduced noise injection on insensitive features.
CorrDP-SGD (Stochastic Gradient Descent): Applied to Empirical Risk Minimization (DP-ERM).
- Noise Calibration: The noise variance $\sigma_i^2$ for the $i$ -th feature is adjusted. For sensitive features ( $i \in S$ ), standard noise is used. For insensitive features ( $i \in U$ ), the noise scale is reduced by a factor dependent on $\max\{TV(i), m_s^2/m^2\}$ , where $m_s$ is the number of sensitive features and $m$ is the total dimension.
- Handling Unknown Correlations: When the TV distance is unknown, the authors propose an estimation procedure using an upper confidence bound of the empirical TV distance. They prove that this estimation step, when properly bounded, maintains the privacy and utility guarantees.

3. Theoretical Guarantees

Privacy: The proposed algorithms satisfy $(\epsilon, \delta)$ -CorrDP.
Utility: For convex loss functions (including Generalized Linear Models like OLS and Logistic Regression), the utility gap (excess empirical risk) is bounded by:
$R(\theta_{priv}) = \tilde{O}\left( \frac{\sqrt{m_s + \min\{\sum_{i \in U} TV(i), m_s/4\}}}{n\epsilon} \right)$
This represents an improvement over the standard DP-ERM bound of $\tilde{O}(\sqrt{m}/(n\epsilon))$ when the number of sensitive features $m_s$ is small relative to the total features $m$ , and the insensitive features are weakly correlated with sensitive ones.
Lower Bound: The paper establishes a near-matching lower bound, confirming that the utility improvement is theoretically tight.

Key Contributions

New Framework (CorrDP): Introduction of a DP notion that explicitly incorporates feature correlations via a distance metric (TV distance), collapsing to standard DP when all features are sensitive.
Improved Utility in DP-ERM: Design of CorrDP-SGD algorithms that incorporate distance-dependent noise. Theoretical results show a utility improvement by a factor of $\sqrt{m/m_s}$ under mild conditions.
Distance Estimation: A procedure to estimate the unknown TV distance from the dataset using upper confidence bounds, ensuring that the estimation error does not compromise privacy or utility guarantees.
Extension to Neural Networks: Adaptation of the framework to neural networks, specifically reducing noise in the first layer where insensitive features are processed, yielding improved performance over standard DP-SGD.
Empirical Validation: Experiments on synthetic and real-world datasets (Adult, Sepsis, Credit Card, Medical Cost) demonstrating that CorrDP consistently outperforms standard DP and "Partial" (discarding sensitive features) baselines, achieving accuracy comparable to "Semi" (ignoring correlations) but with stronger privacy guarantees.

Results

Synthetic Data: In ridge regression tasks, CorrDP achieved lower utility gaps (better accuracy) than standard DP across various privacy budgets ( $\epsilon$ ), particularly in high-privacy regimes. It performed comparably to the "Semi" baseline (which ignores correlations) but with rigorous privacy protection.
Real-World Datasets:
- Adult (Income Prediction): CorrDP outperformed the Semi baseline and suffered less than a 4% accuracy drop compared to non-private models in high-privacy regimes.
- Sepsis (Survival Prediction): Using a 2-layer neural network, CorrDP matched the performance of Semi and consistently outperformed Standard DP.
- Credit Card & Medical Cost: Similar trends were observed, with CorrDP achieving near-Semi utility while maintaining strict privacy guarantees.
TV Distance Estimation: The proposed estimation method successfully handled unknown correlations, with the noise scales adjusted dynamically based on the estimated correlation strength (e.g., in the Adult dataset, the "workclass" feature required higher noise due to high correlation with sensitive features).

Significance and Claims

The paper claims that CorrDP offers a principled way to relax privacy constraints in the presence of feature correlations without compromising rigorous privacy guarantees. By quantifying the "leakage" from insensitive to sensitive features via TV distance, the framework allows for distance-dependent noise injection.

The authors emphasize that their approach:

Does not rely on public data or specific gradient geometry assumptions (unlike some other utility improvement methods).
Provides a natural generalization of standard DP and semi-sensitive DP.
Demonstrates that accounting for correlations allows for significantly better utility in high-dimensional settings where only a subset of features are truly sensitive.

The work is presented as a step toward more practical privacy-preserving machine learning, acknowledging that real-world data often contains heterogeneous sensitivity levels and complex dependencies that standard DP fails to exploit for utility gains. The authors note limitations, such as the computational cost of estimating TV distances in high dimensions and the requirement for clearly defined sensitive/insensitive partitions, pointing to these as directions for future research.