Events

Given two distributions P, Q and an integer t, we analyze two sampling processes. In "random allocation," we first sample an index i uniformly from [t], then draw r_{i} ~ P and r_{j} ~ Q for all other j in [t]. In "Poisson sampling," we independently draw r_{i} ~ 1/t*P + (1-1/t)*Q for each i in [t]. We bound the difference between these processes' output distributions and the baseline of sampling r_{i} ~ Q for all i.

This theoretical result provides key insights for analyzing DP-SGD, a privacy-preserving variant of stochastic gradient descent. While Poisson subsampling has well-understood privacy guarantees, common implementations use element shuffling, which was recently shown to have larger privacy losses in certain regimes. Random allocation offers a middle ground, and we prove its privacy analysis reduces to comparing the distributions described above.

We show that these variants' privacy guarantees are within a constant factor of each other across all parameter regimes and converge asymptotically in t. Our proof has two key components: decomposing Poisson sampling into a mixture of random allocation processes, and showing that random allocation can be viewed as a modified Poisson process where sampling probabilities depend on previous outputs.

Joint work with Vitaly Feldman

The well-known Zig-Zag product and related graph operators, like derandomized squaring, are fundamentally combinatorial in nature. Classical bounds on their behavior often rely on a mix of combinatorics and linear algebra. However, these traditional bounds are not tight and frequently fail to align with experimental results. In this talk, we will present a more refined analysis that utilizes the full spectrum of the graph, rather than relying solely on its spectral expansion. This approach produces results that both match experimental observations and, in a sense, are proved to be optimal. Our technique is analytic, diverging from classical methods: for the upper bound, we apply finite free probability, while for the lower bound, we draw on results from analytic combinatorics.
Based on joint works with Itay Cohen, Gal Maor and Yuval Peled. No prior knowledge is required.