Anchored Likelihood-Ratio Geometry of Anonymous Shuffle Experiments: Exact Privacy Envelopes and Universal Low-Budget Design
This work addresses privacy guarantees in data shuffling for researchers and practitioners in differential privacy, offering foundational theoretical results rather than incremental improvements.
The paper tackles the problem of designing privacy-preserving anonymous shuffle experiments by developing a geometric framework based on anchored likelihood-ratio laws, showing that binary randomized response universally extremizes convex f-divergences and hockey-stick profiles after shuffling, and proving that augmented randomized response is minimax-optimal in low-budget regimes with sharp constants.
We develop a geometric framework for anonymous shuffle experiments based on an anchored affine likelihood-ratio law: a mean-zero measure on the regular simplex polytope. Every finite-output d-ary channel corresponds, up to refinements, to a unique anchored law, and conversely. On privacy: among all epsilon_0-LDP channels, binary randomized response universally extremizes all convex f-divergences and hockey-stick profiles after shuffling. A rigidity converse shows that saturation of both directed envelopes at finite n forces the binary endpoint law. On design: under the pairwise chi_* budget, we prove exact trace-cap and two-orbit frontier theorems. Every frontier point is realized by a mixture of at most two orbit laws. In the low-budget regime, augmented randomized response is minimax-optimal to the sharp constant over all channels and estimators. Under the raw LDP cap, the problem reduces to subset-selection with explicit optimal subset size. The arguments are self-contained and independent of the author's trilogy.