Certified Accounting for Adaptive Shuffled Gaussian Training

Abstract

Many differentially private training pipelines shuffle the data once per epoch and read fixed-size batches, but account for privacy as if the batches were Poisson subsampled. This mismatch can understate the cost. We give a certified accountant for multi-epoch shuffled training with Gaussian noise. It remains valid when each query may depend on all earlier releases and the items are heterogeneous. A null-clone reduction hides the differing item among a random number of candidates. We bound the likelihood sum at each candidate count and merge the resulting bounds into one finite rational dominating pair that composes across epochs. With 1000 batches per epoch, five epochs, noise multiplier 1 and δ = 10⁻⁸, the worst-case epsilon of the full adaptive transcript lies in (6.423, 7.97], while matched Poisson sampling is certified at 0.507. We also show that the pair conjectured by Chua et al. to dominate all adaptive queries does not. The dominating-pair construction and the counterexample are verified in Lean 4, along with supporting lemmas for the reduction and the certificate.