🤖 machine learning

Privacy Amplification in Differentially Private Zeroth-Order Optimization with Hidden States

This paper presents the first convergent differentially private bound for zeroth-order optimization by introducing a hybrid noise mechanism and a novel coupling analysis that overcomes the limitations of standard shifted divergence frameworks caused by anisotropic updates.

Original authors: Eli Chien, Wei-Ning Chen, Pan Li

Published 2026-05-04

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Eli Chien, Wei-Ning Chen, Pan Li

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: Hiding the Trail While Fixing a Giant Puzzle

Imagine you have a massive, complex puzzle (a huge AI model) that you need to solve. You want to solve it using a specific method called Zeroth-Order Optimization.

The Problem:
Usually, to solve a puzzle, you look at the pieces and figure out exactly which way to move them (gradients). But in "Zeroth-Order," you aren't allowed to look at the pieces directly. Instead, you have to guess a move, see how the picture looks, guess a different move, see how that looks, and then average those guesses to figure out the best direction. It's like trying to find the exit of a dark maze by bumping into walls and listening for echoes, rather than seeing the map.

The Privacy Challenge:
You want to solve this puzzle using data from many people, but you must protect their privacy (Differential Privacy). To do this, you usually add "noise" (static) to your guesses so no one can tell if a specific person's data was used.

The Old Way (The "Composition" Trap):
Previous methods treated every single step of the puzzle-solving process as a separate event. They thought, "If I add noise to step 1, step 2, step 3... and so on, the total privacy cost adds up like a bill." If you take 1,000 steps, the privacy cost becomes huge, and you eventually have to stop because you've "spent" all your privacy budget. It's like paying a toll for every single mile you drive; eventually, you can't afford to finish the trip.

The Paper's Breakthrough:
This paper says: "Wait a minute! We don't need to pay a toll for every single step if we keep the intermediate steps hidden."

They introduce a concept called Privacy Amplification by Iteration (PABI). Think of it like this:

The Old Way: You tell everyone your location every 10 feet. They can trace your exact path.
The New Way: You only tell everyone where you started and where you ended. You keep the path in between a secret. Because the path is hidden, the "noise" you added at the beginning actually does a much better job of protecting your identity by the time you reach the end. The privacy cost stops growing and actually levels off.

The Specific Hurdles They Overcame

The authors faced two main problems when trying to apply this "hidden path" idea to Zeroth-Order methods:

1. The "Anisotropic" Noise Problem (The One-Way Static)
In standard methods, you add noise in all directions (like static on a TV screen everywhere). In Zeroth-Order, you only add noise along the specific direction you guessed (like static on just one line).

The Issue: The math tools used to prove privacy for the "all-direction" noise don't work for "one-direction" noise. It's like trying to use a square peg in a round hole. The standard math says, "This doesn't work because the noise isn't uniform."

2. The "Lipschitz" Barrier (The Slippery Slope)
To prove privacy, mathematicians usually need to prove that the system is "stable"—meaning a small change in input leads to a small, predictable change in output.

The Issue: In Zeroth-Order, because the directions are random, the system isn't perfectly stable all the time. It's only stable most of the time. The old math tools require it to be stable always, so they failed.

The Solution: A Hybrid Engine and a "Ghost" Process

The authors built a new engine to solve these problems:

1. The Hybrid Noise Mechanism
Instead of choosing between "noise everywhere" or "noise in one direction," they created a mix.

They add noise along the specific direction they are guessing (to keep the puzzle-solving efficient).
They also add a tiny bit of noise in all other directions (just enough to satisfy the math requirements).
The Result: This gives them the best of both worlds: good puzzle-solving performance and a math structure that allows for privacy proofs.

2. The "Ghost" Process (The Coupling Trick)
Since they couldn't use the old math tools, they invented a new trick.

Imagine two people, Alice and Bob, trying to solve the puzzle with slightly different data.
The authors created a "Ghost" version of the process that sits exactly in the middle of Alice and Bob.
They proved that Alice and the Ghost are very close, and Bob and the Ghost are very close.
By using this "Ghost" as a bridge, they could prove that Alice and Bob are also close enough to be considered private, even without the old math tools.

The Surprising Discovery: More Directions = Better Privacy

One of the coolest findings in the paper is about $K$ , the number of directions you guess at once.

Old Belief: Using more directions ( $K > 1$ ) makes the puzzle easier to solve (better utility) but costs more privacy.
New Finding: Under this new "hidden path" analysis, using more directions actually improves privacy while keeping the puzzle-solving quality high.
The Analogy: Imagine trying to find a needle in a haystack. If you only look at one spot, you need a lot of "cover" (noise) to hide what you're doing. If you look at 10 spots at once, the "cover" spreads out more effectively, making it harder for an observer to figure out which specific spot you were looking at.

Summary of What They Claim

They created the first mathematical proof that Zeroth-Order optimization can have a convergent privacy cost. This means the privacy cost stops growing after a certain number of steps, rather than growing forever.
They proved that by hiding the intermediate steps of the optimization, you get much stronger privacy guarantees than previously thought possible.
They showed that using multiple random directions at once (orthonormal directions) is not just good for speed, but actually a secret weapon for privacy.
They provided a new "Hybrid Noise" recipe that makes this possible.

What they do NOT claim:

They do not claim this works for every type of AI model or data set immediately; their math relies on specific assumptions (like the loss function being "smooth" and "convex").
They do not claim this solves all privacy issues in AI, only that it provides a better theoretical bound for this specific type of optimization method.
They do not provide a ready-to-use software tool for the public yet; this is a theoretical framework that paves the way for future tools.

1. Problem Statement

The paper addresses the challenge of training large-scale models (e.g., LLMs) under Differential Privacy (DP) constraints while managing strict memory limitations.

Context: Standard first-order DP methods (like DP-SGD) require storing per-sample gradients during backpropagation, leading to massive memory overhead that scales poorly with model size.
Solution Trend: Zeroth-order optimization (ZO) methods have emerged as a memory-efficient alternative because they only require forward passes (loss evaluations) and do not compute explicit gradients.
The Gap: While existing ZO methods (e.g., DPZero) work well empirically, their theoretical privacy analysis relies on standard composition theorems. This results in privacy costs that grow linearly with the number of training steps ( $T$ ), forcing a trade-off between utility and privacy.
The Core Challenge: Extending Privacy Amplification by Iteration (PABI)—a technique that yields convergent (constant) privacy bounds for first-order methods—to zeroth-order methods.
- Why it's hard: First-order PABI relies on adding isotropic (direction-independent) Gaussian noise to gradients, allowing the use of "shifted Rényi divergence" lemmas. In contrast, efficient ZO methods add anisotropic (direction-dependent) scalar noise along random update directions. This anisotropy breaks the global Lipschitz property required by standard shifted-divergence frameworks, rendering existing PABI tools inapplicable.

2. Methodology

The authors propose a novel framework combining a Hybrid Noise Mechanism and a Coupling Analysis to bypass the limitations of standard analysis.

A. Hybrid Noise Mechanism (Noisy-ZOGD)

Instead of choosing purely directional noise (efficient but hard to analyze) or purely isotropic noise (easy to analyze but utility-wasting), the authors propose a unified update rule:
$w_{t+1} = \Pi_{\mathcal{B}_R} \left[ w_t - \frac{\eta}{K} \sum_{k=1}^K \hat{g}_t(w_t; u_{t,k}) + \frac{\eta}{\sqrt{K}} \sum_{k=1}^K G^{(1)}_{t,k} u_{t,k} + \eta \sqrt{d} G^{(2)}_t \right]$

$K$ -dimensional updates: Uses $K$ random directions per step to reduce gradient estimation variance.
Hybrid Noise:
1. Directional Noise ( $G^{(1)}$ ): Scalar Gaussian noise added along the update directions $u_{t,k}$ . This preserves utility by concentrating noise where sensitivity exists.
2. Isotropic Noise ( $G^{(2)}$ ): Small isotropic Gaussian noise added across all dimensions. This is crucial for the theoretical analysis to handle the "shift" in the coupling process.
Orthonormal Directions: The update directions $\{u_{t,k}\}$ are sampled as an orthonormal set from the Stiefel manifold (rather than i.i.d. random vectors), which tightens the privacy bounds.

B. Novel Coupling Analysis (Bypassing Shifted Divergence)

The standard PABI proof relies on the Shifted Rényi Divergence lemma, which requires a global Lipschitz condition. Since the ZO update map is not globally Lipschitz (only pointwise Lipschitz with high probability), the authors construct a coupled auxiliary process $\tilde{W}_t$ :

Construction: They define an auxiliary trajectory $\tilde{W}_t$ that sits "in the middle" of two adjacent training processes ( $W_t$ on dataset $D$ and $W'_t$ on dataset $D'$ ).
Decomposition: The privacy analysis is split into two parts:
- Total Variation (TV) Bound: Measures the probability that the coupling fails (i.e., $W_t$ and $\tilde{W}_t$ diverge). This is bounded using the pointwise Lipschitz property of the ZO update (which holds with high probability).
- Rényi Divergence Bound: Measures the divergence between the auxiliary process $\tilde{W}_t$ and the adjacent process $W'_t$ . Since $\tilde{W}_t$ is constructed to align with the noise structure, this part can be analyzed using standard shifted Gaussian mechanisms.
Result: This approach avoids the need for a global Lipschitz constant, allowing for a convergent privacy bound even with anisotropic noise.

3. Key Contributions

First Convergent PABI for Zeroth-Order: The paper provides the first theoretical proof that zeroth-order optimization with hidden states achieves a convergent privacy bound (privacy cost saturates after a fixed number of steps) rather than growing linearly with $T$ .
Hybrid Noise Mechanism: Introduces a noise injection scheme that balances utility (via directional noise) and analytical tractability (via a small isotropic component).
Role of Update Dimension ( $K$ ):
- Reveals that under hidden-state analysis, increasing the number of update directions $K$ reduces privacy loss (contrary to standard composition analysis where $K$ increases cost).
- Demonstrates that using orthonormal update directions significantly improves privacy bounds compared to i.i.d. random directions.
Novel Coupling Technique: Develops a specific auxiliary process construction that circumvents the global Lipschitz barrier, a technique potentially applicable to other non-smooth or non-Lipschitz optimization settings.

4. Key Results

Privacy Bound: For smooth, strongly convex losses, the proposed Noisy-ZOGD algorithm satisfies $(\epsilon, \delta)$ $(ϵ, δ)$ -DP with:
$\epsilon = O\left( \sqrt{\frac{\Delta^2 \log(1/\delta)}{n^2 \sigma^2} \min\left(T, \frac{R n \sqrt{d}}{K \Delta}\right)} \right)$
- The bound saturates at $T \approx \frac{R n \sqrt{d}}{K \Delta}$ , meaning further iterations do not increase privacy cost.
- The bound is inversely proportional to $K$ , showing that using more directions improves privacy.
Comparison:
- vs. Standard Composition: Standard analysis yields $\epsilon \propto \sqrt{T}$ , which grows unbounded. The proposed method converges.
- vs. Output Perturbation: While output perturbation (adding noise only at the end) is independent of $T$ , it is generally weaker for practical $T$ . The proposed method offers a tighter bound for intermediate $T$ .
Utility: The hybrid noise mechanism maintains the same utility guarantees as purely directional noise (DPZero) because the total noise variance is preserved.

5. Significance

Scalability: This work enables the theoretical justification of training massive models (billions of parameters) with DP and limited memory, a critical bottleneck in current LLM fine-tuning.
Algorithmic Design: It overturns the belief that using multiple zeroth-order directions ( $K > 1$ ) is purely a utility trade-off. The paper proves it is also a privacy benefit, encouraging the use of higher-dimensional updates in DP-ZO algorithms.
Theoretical Advancement: By solving the "anisotropic noise" problem in PABI, the paper bridges a significant gap between first-order and zeroth-order privacy theory, offering a new toolkit (coupling with auxiliary processes) for analyzing complex, non-Lipschitz optimization dynamics under privacy constraints.
Practical Impact: Provides concrete guidelines for practitioners: use orthonormal directions, tune the hybrid noise parameter $\beta_t$ , and leverage larger $K$ to achieve better privacy-utility trade-offs without increasing memory costs.