📊 statistics

Sampling-Free Privacy Accounting for Matrix Mechanisms under Random Allocation

This paper introduces a sampling-free privacy accounting framework based on Rényi divergence and conditional composition to provide efficient, deterministic, and tighter privacy guarantees for differentially private matrix mechanisms under random allocation, addressing the limitations of existing sampling-based approaches.

Original authors: Jan Schuchardt, Nikita Kalinin

Published 2026-05-18

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jan Schuchardt, Nikita Kalinin

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 in a Crowd

Imagine you are trying to train a smart computer (a machine learning model) to recognize cats in photos. You have a huge album of photos, and you want the computer to learn without anyone being able to figure out if a specific person's photo was in the album. This is the goal of Differential Privacy (DP).

To do this, the computer learns in small groups (batches). To protect privacy, it adds a little bit of "static" or "noise" to the learning process, like turning up the volume on a radio to drown out a whisper. The more noise you add, the safer the privacy, but the "dumber" the computer becomes because the signal is buried.

The challenge this paper solves is: How do we add the least amount of noise possible while still keeping the privacy promise?

The Problem: The "Random Lottery" vs. The "Assigned Seats"

In the past, researchers tried to protect privacy by randomly picking which photos to look at in each step (like a lottery).

The Lottery Problem: Sometimes a photo gets picked 10 times in a row; other times, it never gets picked at all. This creates "uneven coverage" and makes the math for calculating privacy very messy and slow.
The New Method (Balls-in-Bins): A newer method, called "Random Allocation" (or Balls-in-Bins), is like assigning every photo a specific seat number. If you have 100 seats and 10 rounds, every photo gets to sit in a seat exactly once per round. It's fair, predictable, and efficient.

The Old Solution: The "Guessing Game"

When using this "Assigned Seats" method with advanced noise techniques (called Matrix Mechanisms, which are like a sophisticated way of correlating the static so it cancels itself out better), researchers previously had to use a method called Monte Carlo sampling.

The Analogy: Imagine you want to know the exact average height of everyone in a stadium. The old method said: "Let's just guess! We'll pick 1 million random people, measure them, and hope our average is close enough."

The Flaw: This is slow. If you want to be extremely sure (high privacy), you need to guess millions of times. It's like trying to find a needle in a haystack by looking at one grain of sand at a time. Also, the answer you get is only "probably" right, not 100% guaranteed.

The New Solution: The "Calculator"

This paper introduces a new way to calculate privacy that doesn't rely on guessing. Instead, it uses two new "accountants" (mathematical tools) that calculate the exact privacy cost directly.

1. The "Rényi Accountant" (The Dynamic Map)

Think of the noise in the system as a complex maze. The old way tried to walk through the maze randomly to see how long it took.

The Innovation: The authors created a dynamic map (Dynamic Programming). Instead of walking the maze, they calculate the shortest path instantly by breaking the maze into small, manageable chunks.
The Result: They can now calculate the privacy cost for simple cases (DP-SGD) much faster than before—turning a task that took exponential time (like $2^{100}$ ) into something polynomial (like $100^2$ ). It's like switching from walking every path in a forest to having a drone fly over and map it in seconds.

2. The "Conditional Composition Accountant" (The Safety Net)

Sometimes, the "Dynamic Map" is too rough for very strict privacy rules (when you need to be super safe).

The Innovation: This method breaks the training process down into individual steps. It asks: "If we are in a 'good' situation, is the privacy safe? If we are in a 'bad' situation (which is very rare), how bad is it?"
The Result: It allows the system to say, "We are 99.999% sure we are safe, and for that tiny 0.001% chance of being unsafe, here is exactly how much extra noise we need." This gives a deterministic guarantee (100% certainty) rather than a "high probability" guess.

Why This Matters

The paper compares their new "Calculator" methods against the old "Guessing Game" (Monte Carlo).

Speed: The new methods are vastly faster, especially when you need very high privacy (low $\delta$ ). The old method gets slower and slower the stricter you get; the new method stays fast.
Accuracy: The new methods provide a hard, mathematical guarantee. You don't have to hope your random guesses were right.
Flexibility: They work with all kinds of "Matrix Mechanisms" (different ways of adding noise), not just the simple ones.

Summary

The authors built a fast, deterministic calculator for privacy.

Before: You had to run a slow, expensive simulation (guessing millions of times) to get a "probably safe" answer.
Now: You can use a smart algorithm to get a "100% guaranteed safe" answer almost instantly.

This allows developers to train smarter, more private AI models without getting bogged down in hours of computation just to check if their privacy settings are correct.

Technical Summary: Sampling-Free Privacy Accounting for Matrix Mechanisms under Random Allocation

Problem Statement

The paper addresses the challenge of computing tight, deterministic privacy guarantees for differentially private model training that utilizes matrix factorization mechanisms combined with random allocation (also known as the "balls-in-bins" or balanced iteration subsampling scheme).

While privacy amplification by subsampling is a standard technique to reduce noise in Differentially Private Stochastic Gradient Descent (DP-SGD), the "balls-in-bins" scheme is preferred over Poisson subsampling for large-scale training due to its computational efficiency and uniform data coverage. However, when combined with matrix factorization (which introduces correlated noise across iterations to improve utility), existing privacy accounting methods face significant limitations:

Monte Carlo Dependency: Recent approaches (e.g., Choquette-Choo et al., 2025) rely on Monte Carlo sampling to estimate amplification parameters. This approach is computationally expensive, particularly in high-privacy regimes where the required number of samples scales inversely with $\delta$ (e.g., showing $(\epsilon, 10^{-8})$ -DP is $10^5$ times more expensive than $(\epsilon, 10^{-3})$ -DP).
Probabilistic Guarantees: These sampling-based methods often yield guarantees that hold only with high probability or require the mechanism to employ random abstention, rather than providing deterministic $(\epsilon, \delta)$ -DP bounds.
Computational Intractability: The privacy loss distribution for matrix mechanisms under random allocation involves high-dimensional mixtures, making exact evaluation of the hockey-stick divergence intractable without sampling.

Methodology

The authors propose two distinct, sampling-free accounting procedures that compute deterministic bounds explicitly, leveraging the structure of the random allocation scheme and the correlations introduced by matrix factorization.

1. Rényi Divergence Accountant (Dynamic Programming)

This method computes an upper bound on the Rényi divergence, which is then converted to $(\epsilon, \delta)$ -DP using standard conversion theorems.

Core Insight: The privacy loss distribution for the "remove" direction (where a data point is removed from the dataset) can be expressed as a sum over a Gram matrix $G$ derived from the strategy matrix $C$ .
Complexity Reduction: For general matrices, computing this sum is proven to be #P-complete. However, for structured matrices (e.g., banded matrices where the strategy matrix $C$ has bandwidth $p$ ), the Gram matrix $G$ inherits a cyclically banded structure.
Algorithm: The authors formulate a dynamic programming approach to compute the sum exactly for $p$ $p$ -banded matrices.
- Complexity: The runtime is reduced from exponential $O(2^\alpha)$ (in the order $\alpha$ ) to polynomial $O(b p \alpha^{2p})$ , where $b$ is the number of batches per epoch.
- Truncation: For matrices that are not strictly banded but have rapidly decaying entries (e.g., banded inverse matrices), the method truncates the Gram matrix and adds a computable additive correction term to ensure the bound remains valid.
Add Direction: A separate, tight analytical upper bound is derived for the "add" direction using the arithmetic mean-geometric mean (AM-GM) inequality.

2. Conditional Composition Accountant

This method addresses the "small $\epsilon$ " (high privacy) regime where Rényi conversion formulas can be loose. It overcomes the interdependence of steps caused by noise correlation and fixed participation counts.

Concept: Instead of assuming independent steps, the method uses conditional composition. It identifies "good" outcomes where the conditional distributions of the mechanism at step $n$ are dominated by a pair of fixed, factorizing distributions $(P^{(n)}, Q^{(n)})$ .
Bad Events: The method accounts for "bad" outcomes (where dominance fails) by bounding their probability $\delta_E$ . The total privacy loss is the composition of the independent steps plus $\delta_E$ .
Dominance Criterion: The authors derive a criterion based on reverse hazard functions of Gaussian mixture weights. They show that if the posterior reverse hazard function is pointwise smaller than a target distribution's reverse hazard, dominance holds.
Tail Bounds: To determine the parameters of the dominating distributions, the authors derive analytical tail bounds on the privacy loss of ternary Gaussian mixtures. They utilize a variational family of distributions to tighten these bounds, optimizing over temperature parameters to minimize the standard deviation of the tail bound.
Efficiency: While the initial evaluation is $O(N^2 b^2)$ , subsequent evaluations for different noise multipliers $\sigma$ can be amortized to $O(N b^2)$ , making it efficient for mechanism calibration.

Key Contributions

Deterministic Accounting: The paper introduces the first sampling-free methods to compute deterministic $(\epsilon, \delta)$ -DP guarantees for matrix mechanisms under random allocation, eliminating the need for Monte Carlo estimation.
Improved Complexity for DP-SGD: For the special case of uncorrelated noise (standard DP-SGD), the proposed Rényi accountant improves the computational complexity of exact accounting under random allocation from exponential $O(2^\alpha)$ to polynomial $O(b \alpha^2)$ , significantly outperforming prior exact methods.
Generalization to Correlated Noise: The framework extends to arbitrary banded and non-banded matrix mechanisms (including Banded Square Root, Banded Inverse, and Buffered Linear Toeplitz), handling the complex inter-step correlations inherent in these mechanisms.
Dual-Regime Tightness: The combination of the Rényi accountant (strong in the low-privacy/large- $\epsilon$ regime) and the conditional composition accountant (tighter in the high-privacy/small- $\epsilon$ regime) provides a comprehensive accounting solution.

Results

The authors evaluate their methods against the state-of-the-art Monte Carlo accountant across various matrix mechanisms (DP-SGD, BSR, BISR, BandMF, BandInvMF, BLT) and settings (single and multi-epoch).

Accuracy: In the low-privacy regime ( $\epsilon \ge 2$ ), the Rényi accountant closely matches the Monte Carlo reference. In the high-privacy regime ( $\epsilon \le 1$ ), the conditional composition accountant yields tighter bounds, allowing for smaller calibrated noise multipliers $\sigma$ compared to Monte Carlo estimates.
Robustness: The performance holds across different bandwidths ( $p$ ) and numbers of batches ( $b$ ).
Utility: Experiments on CIFAR-10 demonstrate that the noise multipliers derived from these sampling-free guarantees preserve the utility benefits of using correlated noise over uncorrelated noise.
Runtime: The methods overcome the $O(\delta^{-1})$ dependency of Monte Carlo sampling. While the conditional composition accountant has a higher initial cost for large $N$ , its amortized cost for calibration is significantly lower than Monte Carlo for strict privacy budgets.

Significance and Claims

The paper claims to provide the first sampling-free privacy accounting for mechanisms with correlated gradients and participations. Its significance lies in:

Enabling Deterministic Guarantees: It removes the reliance on probabilistic bounds or random abstention, which are often impractical or theoretically weaker for production systems.
Scalability: By reducing the complexity of exact Rényi accounting for random allocation from exponential to polynomial, it makes precise privacy accounting feasible for large-scale training runs where Monte Carlo sampling would be computationally prohibitive.
Practical Calibration: The ability to efficiently compute tight bounds across a wide range of $\epsilon$ and $\delta$ facilitates better calibration of noise multipliers, directly improving the utility-privacy trade-off in differentially private deep learning.

The authors acknowledge limitations, noting that the Rényi accountant's complexity remains exponential in the bandwidth $p$ (though polynomial in $\alpha$ ), and the conditional composition method relies on a coarse partition of outcomes which may be pessimistic. They suggest future work could explore finer-grained partitions and more efficient variational inference to further tighten bounds.