# Privacy Amplification for BandMF via b-Min-Sep Subsampling

arXiv: https://arxiv.org/abs/2602.09338 · HTML: https://mlsanity.com/paper/2602.09338/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Feb 2026.

## Built on by (most cited first, 6 of 6)

- [Efficient privacy loss accounting for subsampling and random allocation](https://mlsanity.com/paper/2602.17284/) (2026)
- [High-Probability Bounds for SGD under the Polyak-Lojasiewicz Condition with Markovian Noise](https://mlsanity.com/paper/2603.14514/) (2026)
- [Less Random, More Private: What is the Optimal Subsampling Scheme for DP-SGD?](https://mlsanity.com/paper/2605.07072/) (2026)
- [Beyond Square Roots: A Memory-Efficient Explicit Factorization for Multi-Epoch Private Learning](https://mlsanity.com/paper/2605.18379/) (2026)
- [High-Probability PL-SGD with Markovian Noise: Optimal Mixing and Tail Dependence](https://mlsanity.com/paper/2606.26316/) (2026)
- [Closed-Form Noise Calibration Against Membership Inference for Random-Allocation DP-SGD](https://mlsanity.com/paper/2610.09651/) (2026)

## Abstract (arXiv)

We study privacy amplification for BandMF, i.e., DP-SGD with correlated noise across iterations via a banded correlation matrix. We propose b-min-sep subsampling, a new subsampling scheme that generalizes Poisson and balls-in-bins subsampling, extends prior practical batching strategies for BandMF, and enables stronger privacy amplification than cyclic Poisson while preserving the structural properties needed for analysis. We give a near-exact privacy analysis using Monte Carlo accounting, based on a dynamic program that leverages the Markovian structure in the subsampling procedure. We show that b-min-sep matches cyclic Poisson subsampling in the high noise regime and achieves strictly better guarantees in the mid-to-low noise regime, with experimental results that bolster our claims. We further show that unlike previous BandMF subsampling schemes, our b-min-sep subsampling naturally extends to the multi-attribution user-level privacy setting.