💻 computer science

Sliced Rényi Pufferfish Privacy: Directional Additive Noise Mechanism and Private Learning with Gradient Clipping

This paper introduces Sliced Rényi Pufferfish Privacy (SRPP), a framework that overcomes the curse of dimensionality and composition limitations in existing Pufferfish Privacy models by utilizing projection-based measures and sliced Wasserstein mechanisms to enable efficient, scalable private learning with gradient clipping and advanced accounting tools.

Original authors: Tao Zhang, Yevgeniy Vorobeychik

Published 2026-02-09

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Tao Zhang, Yevgeniy Vorobeychik

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 reading habits of your patrons. You want to release a report about what books are popular, but you don't want anyone to figure out exactly who read what.

In the world of data privacy, there are different ways to measure how well you are protecting those secrets. The most famous method is called Differential Privacy (DP). It's like saying, "No matter what you know about the library, my report won't tell you if one specific person was there."

But sometimes, the secret isn't just "was this person here?" It might be something more complex, like "Is the average age of readers in this section higher than 50?" or "Are there more mystery novels than sci-fi?" This is where a framework called Pufferfish Privacy (PP) comes in. It's a super-flexible system that lets you define any secret you want to protect, not just individual records.

However, the paper you provided points out two major problems with the current version of Pufferfish Privacy (specifically a version called Rényi Pufferfish Privacy or RPP):

The "High-Dimensional" Nightmare: To protect these complex secrets, the math currently requires calculating the distance between massive, multi-dimensional clouds of data. Imagine trying to measure the distance between two clouds of smoke in a 3D room, but the room has 1,000 dimensions. It's computationally impossible for computers to do this quickly. It's like trying to count every single grain of sand on a beach to measure the beach's size.
The "Stacking" Problem: If you want to run a machine learning algorithm that learns over many steps (like training an AI), you have to add up the privacy "cost" of every single step. Current Pufferfish methods make this math so messy that you can't easily add them up. It's like trying to calculate the total weight of a stack of boxes where the weight of each box changes depending on the one below it.

The Solution: Sliced Rényi Pufferfish Privacy (SRPP)

The authors propose a new framework called SRPP to fix these two problems. Here is how they do it, using simple analogies:

1. The "Slicing" Trick (Solving the Dimensionality Problem)

Instead of trying to measure the distance between two giant, complex 1,000-dimensional clouds of data all at once, the authors suggest slicing them.

The Analogy: Imagine you have two giant, fuzzy clouds of smoke. Instead of trying to measure the distance between the whole clouds (which is hard), you shine a flashlight through them from different angles. You look at the 2D shadows (slices) they cast on the wall.
The Magic: Measuring the distance between two 2D shadows is easy and fast. The authors prove that if you measure the distance between these shadows from many different angles and average them out, you get a very accurate picture of the privacy risk without ever having to do the impossible 1,000-dimensional math.
The Result: They created a new "Sliced Wasserstein Mechanism." Think of this as a noise-generator that uses these easy-to-calculate 2D shadows to decide how much "static" (noise) to add to the data. It's much faster and works on huge datasets.

2. The "History-Uniform Cap" (Solving the Stacking Problem)

When training an AI, the system makes thousands of tiny updates. To protect privacy, you need to know how much the secret changes from one step to the next.

The Old Way: You had to look at the worst-case scenario for every single step, assuming the worst possible combination of data. This was like assuming every single step you take in a dark room is a fall down a cliff, so you add a massive safety net every time. This made the privacy "noise" so loud that the AI couldn't learn anything useful.
The New Way (SRPP-SGD): The authors introduce a concept called History-Uniform Caps (HUC).
- The Analogy: Instead of assuming every step is a cliff, they calculate a "cap" or a limit on how much the secret can shift on average across all possible paths, while still being safe. They also have a "Subsampling-Aware" version (sa-HUC) that realizes that when you pick a random small group of data (a mini-batch) to learn from, the randomness actually helps smooth things out.
- The Result: This allows them to add up the privacy costs of all the training steps in a clean, simple way (like adding up the cost of individual items in a grocery cart). This means they can add less noise while still guaranteeing the secret is safe, leading to much smarter AI models.

What They Found (The Experiments)

The authors tested their new system on real data:

Static Data: They tried to release statistics about census data (like race or heart disease) without revealing individual secrets. They found that their "sliced" method worked just as well as the old, slow methods but was much faster.
Training AI: They trained image recognition models (like identifying cats in photos) using their new method.
- The Result: Their new method (specifically the "Subsampling-Aware" version) allowed the AI to learn much better than previous methods. It achieved higher accuracy with the same level of privacy protection. In some cases, the new method needed 10 times less noise to achieve the same safety, meaning the AI could actually "see" the data clearly instead of being blinded by static.

Summary

The paper introduces SRPP, a new way to protect complex secrets in data.

It uses slicing (looking at 2D shadows) to make the math fast and easy, avoiding the "curse of dimensionality."
It uses caps (smart limits) to make it easy to add up privacy costs during AI training, allowing for less noise and better results.

Essentially, they found a shortcut that lets us protect complex data secrets without slowing down our computers or blinding our AI models with too much noise.

Technical Summary: Sliced Rényi Pufferfish Privacy

Problem Statement

The paper addresses two fundamental limitations in the Pufferfish Privacy (PP) and Rényi Pufferfish Privacy (RPP) frameworks, which generalize Differential Privacy (DP) to allow customizable secrets and probabilistic secret–dataset relationships.

Curse of Dimensionality in Mechanism Design: Existing PP/RPP privatization mechanisms (e.g., General Wasserstein Mechanism) rely on optimal transport (OT) distances (specifically $\infty$ -Wasserstein distance) to calibrate noise. Computing these distances in high dimensions is statistically and computationally expensive (NP-hard in general), limiting practical scalability.
Lack of Practical Composition for Iterative Learning: PP/RPP lacks general-purpose composition theorems for stochastic optimization algorithms like Stochastic Gradient Descent (SGD). The probabilistic nature of secret–dataset relationships induces inter-mechanism dependencies that break standard composition rules. Existing solutions either rely on restrictive structural assumptions (e.g., contractivity) or require solving infinite-dimensional convex programs, making integration with iterative learning nontrivial.

Methodology

The authors propose Sliced Rényi Pufferfish Privacy (SRPP), a framework that replaces high-dimensional Rényi divergence with projection-based quantification to achieve tractability while preserving PP semantics.

1. Sliced Wasserstein Sensitivity (SW-sensitivity)

To overcome the computational bottleneck of OT, the authors introduce Sliced Wasserstein Sensitivity. Instead of computing the full-dimensional Wasserstein distance, the method projects the conditional data distributions onto 1-D directions (slices) defined by a set of directions $U$ and a probability measure $\omega$ .

The sensitivity is defined as the maximum $\infty$ -Wasserstein distance between projected distributions along these slices.
This reduces the problem from high-dimensional OT to a set of 1-D Wasserstein calculations, which admit closed-form solutions via quantile functions.

2. SRPP Definitions

Two variants of SRPP are defined to align with the sliced sensitivity:

Average SRPP (Ave-SRPP): Bounds the $\omega$ -average of per-slice Rényi divergences.
Joint SRPP (Joint-SRPP): Aggregates per-slice divergences via a joint log-moment bound, making it more sensitive to rare, high-risk directions.

3. Sliced Wasserstein Mechanism (SWM)

The authors develop the Sliced Wasserstein Mechanism, which adds Gaussian noise calibrated to the SW-sensitivity.

Closed-form Calibration: Theoretical results (Theorems 4.5 and 4.6) provide closed-form formulas for the Gaussian noise variance ( $\sigma^2$ ) required to satisfy $(\alpha, \epsilon, \omega)$ -Ave-SRPP or Joint-SRPP.
Finite-Sample Guarantees: The framework includes PAC-style calibrations (Theorems 4.7 and 4.8) that account for Monte Carlo slicing and finite-sample estimation of distributions, ensuring guarantees hold with high probability.

4. SRPP-SGD and Accountants

For iterative learning, the paper introduces SRPP-SGD, an analogue to DP-SGD that utilizes gradient clipping.

History-Uniform Caps (HUC): To handle the lack of graceful composition, the authors define HUCs. These are deterministic, history-uniform bounds on the directional displacement of the update map between neighboring datasets.
Subsampling-Aware HUC (sa-HUC): A refined variant that bounds the expected squared directional shift over subsampling randomness rather than the worst-case shift. This leverages the averaging effect of subsampling to reduce noise requirements.
Decompose-then-Compose: Using HUCs/sa-HUCs, the framework enables a "decompose-then-compose" strategy. The privacy cost of the entire training trajectory is computed by summing per-iteration costs derived from the caps, avoiding the need to compute Wasserstein sensitivities at every step or assume contractivity.
Additive Composition: The authors prove that under a shared slicing geometry, the privacy costs of multiple SRPP-SGD mechanisms add up linearly, enabling modular accounting for pipelines.

Key Contributions

SRPP Framework: A new privacy definition that preserves PP/RPP semantics (customizable secrets, priors) while replacing high-dimensional divergence with tractable, projection-based measures (Average and Joint Sliced Rényi Divergence).
Tractable Mechanism: The Sliced Wasserstein Mechanism (SWM), which provides sound SRPP certificates and closed-form Gaussian noise calibration without high-dimensional OT computations.
Iterative Learning Scheme: The SRPP-SGD algorithm with gradient clipping, supported by HUC and sa-HUC accountants. This enables privacy accounting for stochastic iterative methods without requiring contractivity assumptions or solving complex convex programs.
Composition Theorems: Proof of graceful additive composition for SRPP mechanisms under a common slicing geometry, facilitating modular privacy accounting for multi-stage pipelines.
Empirical Validation: Demonstration of favorable privacy–utility trade-offs and scalability on both static query release (tabular data) and iterative learning (image classification with ResNet).

Experimental Results

The authors evaluated the framework on static queries and iterative learning (SRPP-SGD):

Static Queries: Experiments on the Adult Census dataset (attribute privacy) showed that SRPP mechanisms achieve favorable utility–privacy trade-offs. Joint-SRPP was found to be more conservative than Ave-SRPP, inducing higher noise but providing uniformly lower attacker accuracy, particularly in moderate privacy regimes.
Iterative Learning (SRPP-SGD):
- On CIFAR-10, sa-SRPP-SGD (using subsampling-aware caps) consistently required significantly smaller Gaussian noise than worst-case SRPP-SGD for the same privacy budget $\epsilon$ .
- This reduction in noise translated to substantially higher test accuracy (reaching 60–70% at large budgets vs. 20–35% for worst-case SRPP).
- Comparisons with Group-DP-SGD showed that converting DP to Group-DP using expected discrepancy sizes resulted in overly conservative noise calibration compared to the tailored SRPP approach.
- Empirical membership inference attacks confirmed that tighter sa-SRPP budgets effectively suppressed attack signals while maintaining utility.

Significance and Claims

The paper claims that SRPP resolves the two primary obstacles preventing the operational use of Pufferfish Privacy in practice:

Scalability: By replacing high-dimensional optimal transport with sliced projections, the framework makes mechanism design computationally tractable for high-dimensional data.
Iterative Learning: By introducing HUCs and sa-HUCs, the framework enables a decompose-then-compose privatization strategy for SGD that does not rely on restrictive assumptions like contractivity or complex composition theorems.

The authors emphasize that their approach allows for customizable secrets and prior-aware privacy (handling subjective adversarial beliefs) while achieving practical scalability and favorable utility compared to existing PP/RPP methods and standard Group-DP adaptations. The framework is presented as a step toward making Pufferfish Privacy operational for real-world iterative learning systems.