Sampling-Free Privacy Accounting for Matrix Mechanisms under Random Allocation

Jan Schuchardt, Nikita Kalinin · 2026

Read Sampling-Free Privacy Accounting for Matrix Mechanisms under Random Allocation by Jan Schuchardt, Nikita Kalinin (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-21636.txt.

Introduction

Jan Schuchardt and Nikita Kalinin remove random sampling from privacy accounting for matrix-based training methods. Differentially private training often splits work by random allocation, like balls tossed into bins. A recent method computed the privacy gain by Monte Carlo sampling.

Those guarantees held only with high probability, or needed the mechanism to sit out at random. The authors derive the accounting without sampling, giving firm guarantees. Exact accounting matters because privacy budgets are promises made to real people. A promise that holds only probably, or needs random abstention, is weaker than the ledger suggests.

Catalog record

CREATORJan Schuchardt, Nikita Kalinin
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE90 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-21636

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Sampling-Free Privacy Accounting for Matrix Mechanisms under Random Allocation Jan Schuchardt, Nikita Kalinin Abstract We study privacy amplification for differentially private model training with matrix factorization under random allocation (also known as the balls-in-bins model). Recent work by Choquette-Choo et al. (2025) proposes a sampling-based Monte Carlo approach to compute amplification parameters in this setting. However, their guarantees either only hold with some high probability or require random abstention by the mechanism. Furthermore, the required number of samples for ensuring ( ε , δ ) (\varepsilon,\delta) -DP is inversely proportional to δ \delta . In contrast, we develop sampling-free bounds based on Rényi divergence and conditional composition. The former is facilitated by a dynamic programming formulation to efficiently compute the bounds. The latter complements it by offering stronger privacy guarantees for small ε \varepsilon , where Rényi divergence bounds inherently lead to an over-approximation. Our framework applies to arbitrary banded and non-banded matrices. Through numerical comparisons, we demonstrate the efficacy of our approach across a broad range of matrix mechanisms used in research and practice. 1 Introduction Differential privacy (DP) ( 17 ) offers one of the most well-established and mathematically rigorous definitions of privacy in statistical learning. In the context of deep learning, it is typically enforced via differentially private stochastic gradient descent (DP-SGD) ( 1 ) . In DP-SGD, per-example gradients are clipped to bound the contribution of any individual data point, and Gaussian noise is added to guarantee privacy. While the injected noise inevitably degrades model utility, this loss can be mitigated through privacy amplification by subsampling ( 26 ) . Specifically, by randomly sampling a subset of the data at each iteration, we can achieve the same privacy guarantees with less additive noise. This improvement arises from the adversary’s uncertainty about which examples are included in each batch, introducing additional randomness that strengthens the overall privacy guarantees. Several subsampling schemes have been studied in the context of differentially private training. One of the most commonly used is Poisson subsampling ( 1 ; 29 ; 23 ; 34 ) , in which each data point is independently included in a batch with a fixed probability chosen to achieve a desired expected batch size. However, this scheme poses practical challenges for implementation ( 24 ; 5 ) . In particular, for large datasets and long training runs, two issues arise. First, drawing an independent random subset at every iteration is often computationally infeasible. Second, subsampling can lead to uneven data coverage, with a substantial fraction of examples (approximately 1/e ) not appearing within an epoch, and may increase the variance of gradients ( 19 ) . As a result, a common but problematic practice is to train on shuffled data while reporting privacy guarantees derived for Poisson subsampling ( 24 ) . A principled alternative that has emerged to address this issue is the “balls-in-bins” scheme ( 12 ; 8 ) , also known as balanced iteration subsampling ( 14 ) or as random allocation ( 19 ) . This approach predefines batches for an entire epoch and reuses them throughout training, ensuring a fixed number of participations per data point. As a result, it mitigates both the per-iteration sampling overhead and the uneven within-epoch data coverage, while requiring a noise multiplier comparable to that of Poisson subsampling to attain the same privacy guarantees. Beyond better subsampling schemes, another principled approach to improve upon the utility DP-SGD is to introduce correlated noise. The key idea is to add more noise at each iteration while carefully correlating it across steps so that the aggregate noise has lower variance than in standard DP-SGD, thereby improving model utility. The most common way to implement such noise correlations is through the matrix factorization mechanism ( 25 ; 13 ; 11 ; 10 ) , where Gaussian noise Z is correlated across iterations via the linear transformation C^{-1} , i.e., sampling C^{-1}Z , and then adding it to the gradients. Matrix factorization, however, can be impractical at scale, motivating memory-efficient structured variants. Prior work proposes banded matrix factorizations ( 21 ; 27 ) , where the strategy matrix C is banded and Toeplitz; banded-inverse factorizations ( 22 ) , where C^{-1} is banded; and hybrid constructions such as the Buffered Linear Toeplitz (BLT) matrix ( 16 ; 28 ) . These designs enable correlated-noise mechanisms with substantially reduced memory requirements. Privacy amplification by subsampling and noise correlation techniques can be combined. This has been demonstrated for banded matrix mechanisms under Poisson subsampling ( 10 ; 9 ) , and more recently for general correlation matrices using balls-in-bins subsampling ( 8 ) . The latter, however, relies on Monte Carlo estimation, which can require an intractably large number of samples in the high-privacy regime and thus become computationally expensive. Moreover, it does not directly yield deterministic DP guarantees, but rather privacy bounds that only hold with high probability. Motivated by the recent independent works of 19 ; 14 , who derived privacy bounds for DP-SGD under balls-in-bins batching without Monte Carlo sampling, we propose two procedures for computing amplification bounds for matrix mechanisms under this batching scheme. Our methods avoid Monte Carlo sampling entirely and instead compute the bounds explicitly, leveraging Rényi divergence via dynamic programming as well as conditional composition while accounting for the inter-step correlations unique to matrix mechanisms. Contribution • We introduce deterministic, Rényi divergence based and conditional composition based privacy analyses (accountants) for subsampled matrix mechanisms. • For the special case of DP-SGD, we improve the computational complexity of Rényi accounting under the random allocation (balls-in-bins) batching scheme. 2 Background 2.1 Definitions of Differential Privacy Differential Privacy (DP) is a widely accepted framework for providing rigorous privacy guarantees. We recall its definition below: Definition 2.1 (Differential Privacy ( 17 ) ) . A randomized mechanism is said to provide (\varepsilon,\delta) -differential privacy under a neighboring relation \simeq if, for all datasets D\simeq D^{\prime} , and for all measurable subsets S of the mechanism’s output space: \Pr[M(D)\in S]\leq e^{\varepsilon}\cdot\Pr[M(D^{\prime})\in S]+\delta. (1) In the following, we write M(\cdot\mid D) for the distribution of random variable M(D) . We further use an equivalent definition of differential privacy that is more convenient for privacy accounting, i.e., tracking privacy over multiple applications of a mechanism. Lemma 2.2 (Proposition 2 from ( 4 ) ) . A mechanism provides (\varepsilon,\delta) -DP under \simeq if and only if, for all D\simeq D^{\prime} , H_{e^{\varepsilon}}\left(M(\cdot\mid D),M(\cdot\mid D^{\prime})\right)\leq\delta with hockey-stick divergence H_{\gamma}(P||Q)=\mathbb{E}_{x\sim P}\left[\max\left\{1-\gamma\frac{\mathrm{d}Q}{\mathrm{d}P}(x),\;0\right\}\right]. (2) While (\varepsilon,\delta) -DP corresponds to a bound on the hockey-stick divergence for a single choice of \gamma=e^{\varepsilon} , tight privacy accounting requires bounds for all choices of \gamma . In the following, we recall multiple equivalent ( 34 ) characterizations of this privacy profile that are immediately relevant to our work, beginning with dominating pairs: Definition 2.3 . We say that the pair of distributions (\hat{P},\hat{Q}) dominates (P,Q) , denoted by (P,Q)\prec(\hat{P},\hat{Q}) , if H_{\gamma}(P||Q)\leq H_{\gamma}(\hat{P},\hat{Q}) for all \gamma>0 . Definition 2.4 ( 34 ) . We say that (\hat{P},\hat{Q}) are a dominating pair of mechanism M under neighboring relation \simeq if (M(\cdot\mid D),M(\cdot\mid D^{\prime}))\prec(\hat{P},\hat{Q}) for all D\simeq D^{\prime} . Given a dominating pair (P,Q) , the problem of privacy accounting reduces to quantifying the

Read the complete text