🤖 machine learning

Private Prediction via PAC Privacy

This paper proposes a PAC privacy framework for private machine learning prediction that leverages instance-based empirical stability and a new adaptive adversarial composition theorem to achieve linear mutual information accumulation, enabling high-utility model serving and subsequent private model distillation with significantly stronger privacy guarantees than traditional differential privacy.

Original authors: Xiaochen Zhu, Mayuri Sridhar, Srinivas Devadas

Published 2026-06-15

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Xiaochen Zhu, Mayuri Sridhar, Srinivas Devadas

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 "Glass House" of AI

Imagine a company trains a super-smart AI model on a secret list of private data (like medical records or bank transactions). They want to let people ask the AI questions (e.g., "Is this transaction suspicious?") without revealing the secret list.

The problem is that if the AI is too perfect, a clever hacker can trick it into revealing the secret list. They can ask thousands of questions, analyze the answers, and eventually figure out exactly which people were in the training data. This is called a Membership Inference Attack.

The Old Solution: The "Blindfolded Guard" (Differential Privacy)

For years, the standard solution has been Differential Privacy (DP). Think of this as a guard who answers every question but adds a random "fog" or noise to the answer to hide the truth.

The Flaw: To be safe, the guard assumes the worst-case scenario. They assume the AI is incredibly unstable and that one tiny change in the secret data could completely change the answer. So, they add a huge amount of fog.
The Result: The answers become so blurry that the AI stops being useful. It's like trying to read a map through a thick blizzard. Also, if you ask too many questions, the fog gets too thick, and the guard has to stop answering.

The New Idea: The "Stable Crystal Ball" (PAC Privacy)

This paper proposes a new approach called PAC Privacy. Instead of assuming the worst, it looks at how stable the AI actually is.

The Analogy: Imagine the AI is a crystal ball. If you shake the secret data a little bit (swap one person in the training list), does the crystal ball's prediction change wildly?
- In reality: For many AI models, the answer is no. The prediction stays almost the same. The AI is "stable."
- The Innovation: PAC Privacy measures this stability. If the AI is stable, the system knows it only needs a tiny bit of fog to hide the secret. If the AI is unstable, it adds more fog.
The Benefit: Because the AI is usually very stable, the system adds almost no fog. The answers remain crystal clear, and the privacy is still mathematically guaranteed.

The Hard Part: The "Adaptive Adversary"

There was a catch. Previous methods worked well if the questions were random. But what if the attacker is smart? What if they look at the answer to Question #1, then use that to craft a tricky Question #2, and so on? This is called an Adaptive Adversary.

The Old Failure: Previous methods couldn't handle this. If an attacker asked questions adaptively, the "fog" budget would run out instantly, or the math would break.
The Paper's Breakthrough: The authors created a new mathematical rule (a "composition theorem") that handles smart attackers.
- How it works: The system keeps a "belief state." It constantly updates its understanding of what the attacker knows based on the history of questions. If the attacker learns something, the system instantly adjusts the noise to stay one step ahead.
- The Magic: Even with a smart, adaptive attacker, the "privacy cost" only grows linearly (slowly), not exponentially. This means the system can answer millions of questions while keeping the secret safe.

The Results: Clear Answers, Safe Secrets

The authors tested this on real-world data (like images of cats and dogs, or bank records).

High Accuracy: Even with extremely strict privacy settings (so strict that the math says the attacker has almost zero chance of guessing), the AI still got 87.79% of the answers right on a standard test.
Millions of Queries: They proved that you could ask one million questions, and the attacker's chance of guessing if a specific person was in the training data would still be barely better than flipping a coin (51.08%).
Comparison: To get the same level of privacy with the old "Blindfolded Guard" (Differential Privacy), the AI would have to guess randomly, getting almost 0% accuracy.

The "Bonus" Feature: The "Distilled Student"

The paper also shows a clever trick to get unlimited answers.

The Setup: The system uses its "Private Crystal Ball" to label a huge pile of public data (data that isn't secret).
The Filter: Because the system knows exactly how much "fog" it added, it can mathematically check: "Is this answer confident enough to be trusted?" If yes, it keeps the label; if no, it throws it away.
The Result: It trains a new, smaller "Student" model using these high-quality, private labels. This Student model can then be released to the public forever, with no privacy budget limits, because it learned from the private data without ever seeing it directly.

Summary

This paper introduces a way to let AI answer questions privately without making the answers useless.

Old Way: Add huge noise to everything because you are scared. (Result: Useless AI).
New Way: Measure how stable the AI is, add just enough noise to be safe, and use a smart tracking system to handle tricky attackers. (Result: Smart AI that stays secret).

The authors show that by trusting the stability of the AI, we can get the best of both worlds: high utility and strong privacy.

Technical Summary: Private Prediction via PAC Privacy

Problem Statement
Machine learning models are increasingly deployed as black-box services behind APIs, where only predictions are exposed to users rather than model weights. This deployment pattern motivates private prediction: privatizing model outputs rather than parameters. While Differential Privacy (DP) is the standard for privacy, it struggles in this context. DP calibrates noise based on worst-case sensitivity (the maximum change in output between adjacent datasets). For non-convex models (e.g., deep neural networks), calculating tight sensitivity bounds is intractable. Consequently, DP-based private prediction often relies on "sample-and-aggregate" methods (like PATE) or reverts to input-independent noise, leading to a harsh privacy-utility trade-off where utility collapses under high query volumes or strict budgets.

Furthermore, existing privacy frameworks for sequential releases often fail under adaptive and adversarial querying. In realistic scenarios, untrusted users can choose future queries based on the history of previous outputs to maximize information leakage. Standard composition theorems either fail under adaptivity, grow quadratically with the number of queries, or revert to input-independent DP-style noise, discarding the stability advantages of the specific predictor.

Methodology
The paper proposes a framework for Private Prediction via PAC (Probably Approximately Correct) Privacy, addressing the gap in efficient, adaptive composition.

PAC Privacy Framework: Unlike DP, PAC privacy is instance-based. It measures the stability of a data processing function via black-box simulations under a specific input distribution ( $P_S$ ). It controls privacy leakage by bounding the Mutual Information (MI) between the secret input $S$ and the output $R$ . A stable function requires significantly less noise to privatize.
Posterior-Aware Adversarial Composition: The core theoretical contribution is a new composition theorem that handles adaptive, adversarial querying with a persistent secret (the same training set $S$ $S$ is used for all queries).
- Adaptive Noise Calibration: The curator maintains a "belief state"—the posterior distribution of the secret $S$ given the interaction history.
- Mechanism: At each step $t$ , upon receiving an adaptive query $M_t$ , the curator calculates the noise covariance $\Sigma_t$ required to satisfy a per-step MI budget $b_t$ conditioned on the current posterior belief $P_{t-1}$ .
- Bayesian Update: After releasing the noisy response $R_t$ , the curator updates the posterior belief using Bayes' rule.
- Theorem: The authors prove that under this mechanism, the total MI leakage accumulates linearly ( $I(S; R_{1:T}) \le \sum b_t$ ) even under adversarial adaptivity. This preserves the instance-based utility of PAC privacy while providing rigorous linear composition bounds.
Concrete Instantiation for ML:
- Input Distribution: The secret $S$ is a random subset of the universe $U$ , sampled such that each point has a 50% probability of inclusion. To make computation tractable, the support is restricted to a finite collection of $m=128$ subsets.
- Offline Pre-processing: To avoid retraining for every query, $m$ models are trained offline on the $m$ subsets. Online queries involve running inference on these $m$ models, aggregating predictions, and adding calibrated noise.
- Output Stabilization: The system privatizes hard predictions (one-hot labels) rather than soft probabilities. Hard predictions are more stable across different training subsets, resulting in lower output variance and requiring less noise.
Private Model Distillation: To enable unlimited queries after a finite privacy budget is exhausted, the paper proposes distilling a "student" model from the PAC-private predictions.
- Confidence Filtering: A statistical test is applied to the noisy predictions to filter out low-confidence (potentially mislabeled) samples before training the student. This ensures the distilled model is trained only on high-quality labels, bounding the probability of retaining mislabeled data.

Key Results
Experiments across tabular, vision (CIFAR-10, CIFAR-100), and text (IMDb, AG News) modalities demonstrate the efficacy of the approach:

High Utility at Tight Budgets: On CIFAR-10, the method achieves 87.79% accuracy with a per-query MI budget of $2^{-32}$ . This allows serving one million queries while provably bounding membership inference attack (MIA) success to 51.08%. This guarantee is comparable to $(0.04, 10^{-5})$ -DP.
Scalability: The system supports approximately 477 million queries before reaching the MIA guarantee of $(1, 10^{-5})$ -DP. In contrast, DP-based private prediction degrades to random guessing as the number of queries increases due to input-independent sensitivity constraints.
Distillation Performance: Using 210,000 private predictions from a CIFAR-10 teacher to label a public ImageNet subset (CINIC-10), the distilled student model achieves 91.86% accuracy on CIFAR-10. This outperforms the private teacher and matches the MIA guarantee of $(0.02, 10^{-5})$ -DP, while requiring no labeled public data for the distillation process.
Robustness: The method maintains strong utility even as the per-step MI budget tightens to vanishingly small values ( $2^{-32}$ ), a phenomenon attributed to the inherent stability of model predictions across different training subsets.

Significance and Claims
The paper claims to close a critical gap in private machine learning by enabling private prediction that is both privacy-preserving and highly useful under adaptive and adversarial conditions.

Theoretical Breakthrough: It provides the first adversarial composition theorem for PAC privacy with a persistent secret, proving that MI accumulates linearly under adaptive querying. This contrasts with prior work that either failed under adaptivity or required input-independent noise.
Practical Viability: It demonstrates that prediction stability can be leveraged to privatize outputs with minimal noise, offering a "win-win" scenario where robust learning (low variance) naturally leads to better privacy-utility trade-offs.
Alternative to DP Training: The work suggests a path to releasing privacy-preserving models via private prediction and distillation, offering a more favorable utility profile than DP-SGD for inference services, particularly when the threat model aligns with API-based prediction rather than model weight release.
Limitations: The authors acknowledge that the approach relies on a specific input distribution (subsampling) and that the computational cost involves pre-training $m$ models. They also note that the theoretical guarantees assume a computationally unbounded adversary with full knowledge of the system distribution, though they argue this naturally extends to realistic settings.

In summary, the paper argues that by shifting the focus from parameter privacy to output privacy and utilizing instance-based stability via PAC privacy, it is possible to serve millions of queries with strong, provable privacy guarantees that DP-based methods cannot achieve without sacrificing utility.