Shuffling-Aware Optimization for Private Vector Mean Estimation

Shun Takagi, Seng Pei Liew · 2026

Read Shuffling-Aware Optimization for Private Vector Mean Estimation by Shun Takagi, Seng Pei Liew (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-2604-28032.txt.

Introduction

Takagi and Liew study private mean estimation when each user sends one privatised message and the analyser sees only the shuffled pile. They frame design after shuffling as an explicit optimisation using the shuffle index, and prove a lower bound on mean squared error in terms of that index. The bound shows locally optimal mechanisms can fail once shuffled, while their new mechanism is asymptotically optimal at high privacy, nearly matching the central Gaussian mechanism.

Catalog record

CREATORShun Takagi, Seng Pei Liew
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE105338
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.28032

Browse the full library · About the Tower of Babel

Full text

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

Shuffling-Aware Optimization for Private Vector Mean Estimation Shun Takagi, Seng Pei Liew Abstract We study d d -dimensional unbiased mean estimation in the single-message shuffle model, where each user sends a single privatized message and the analyzer only observes the shuffled multiset of reports. While minimax-optimal mechanisms are well understood in the local differential privacy setting, the corresponding notion of optimality after shuffling has remained largely unexplored. To address this gap, we introduce the recently proposed shuffle index and use it to formulate the post-shuffling mechanism design problem as an explicit optimization problem. We then establish a minimax lower bound on the achievable mean squared error in terms of the shuffle index, which implies that mechanisms that are optimal under LDP can become suboptimal once shuffling is applied. Finally, we construct an asymptotically minimax optimal mechanism in the high privacy regime, which as a consequence achieves a privacy-utility trade-off nearly identical to that of the central Gaussian mechanism. 1 Introduction Differential privacy (DP) [ 16 , 15 ] enables principled privacy-preserving data analysis. In the central model, a trusted curator collects raw data and releases a privatized aggregate, achieving strong utility at the cost of a strong trust assumption. In the local model (LDP) [ 14 ] , each user randomizes their data before communication, removing the need for trust but often degrading accuracy significantly. The shuffle model [ 18 , 11 , 4 , 20 ] offers an appealing intermediate point: users send locally randomized messages through an anonymization layer (the shuffler), which permutes the reports before analysis. By breaking the linkage between users and messages, shuffling amplifies privacy and can approach central-model utility. We focus on the single-message randomize-then-shuffle setting [ 4 ] , where each user sends exactly one privatized message. This is the simplest and most practical instantiation of the shuffle model, and it also serves as a basic component for understanding more complex multi-message constructions [ 1 ] . Despite its importance, optimal mechanism design for fundamental statistical tasks in the single-message shuffle model remains poorly understood. In this work we study d -dimensional mean estimation over the unit \ell_{2} ball \mathbb{B}_{2}^{d} . Given inputs x_{1},\ldots,x_{n}\in\mathbb{B}_{2}^{d} , the goal is to estimate the mean \frac{1}{n}\sum_{i=1}^{n}x_{i} from the shuffled multiset of privatized messages. While minimax-optimal mechanisms are well understood under LDP [ 2 ] , the analogous question after shuffling has remained largely unexplored: which local randomizer yields the best accuracy under a shuffled DP constraint? A key difficulty is that privacy after shuffling is inherently global and depends on n and on privacy amplification, making it hard to pose an explicit optimization problem in terms of the local randomizer alone. As a result, existing approaches often design mechanisms for LDP and then apply amplification, implicitly assuming that local optimality transfers to the shuffled setting. We address this gap using the recently proposed shuffle index [ 26 ] , a scalar quantity determined solely by the structure of the local randomizer. In the high privacy regime, the privacy profile [ 3 ] of the shuffled mechanism is asymptotically governed by the shuffle index in a monotone way as n\to\infty , which allows us to replace a global (\varepsilon,\delta) constraint by a local constraint. This yields a clean post-shuffling mechanism design problem: minimize the worst-case mean squared error (MSE) among unbiased single-message protocols subject to a shuffle-index constraint. Our main results show that this formulation leads to a sharp minimax theory. We prove a minimax lower bound showing that any unbiased protocol with shuffle index \chi must incur worst-case MSE at least d\chi^{2} . This bound implies that LDP-optimal mechanisms can be suboptimal after shuffling. In particular, we show that PrivUnit [ 7 ] , which is minimax-optimal for mean estimation under LDP, fails to attain the shuffle-index lower bound by a constant factor in high dimensions. Finally, we construct an explicit mechanism that asymptotically matches the lower bound in the high privacy regime. Our blanket-mixed Gaussian local randomizer outputs a Gaussian with mean 0 with some probability and otherwise outputs a Gaussian centered at the user’s input, together with a universal unbiased estimator. We achieve MSE d\chi^{2}(1+o(1)) as \chi\to\infty , establishing asymptotic minimax optimality. Moreover, we prove a central-limit-type correspondence: in the high privacy regime \varepsilon_{n}=O(\sqrt{\log n/n}) , the privacy profile of our shuffled mechanism converges to that of the central Gaussian mechanism with the matching noise level, which sharpens earlier order-level and empirical observations in [ 10 ] by establishing a precise theoretical correspondence, matching constants. 1.1 Related Work and Contributions Lower bounds. For single-message shuffled mean estimation, most existing lower bounds are typically stated in a form that is uniform over \varepsilon [ 4 , 1 ] (i.e., \Omega\left(d\,n^{-2/(d+2)}\right) ), which is well suited to the moderate-privacy regime but provides limited resolution in the high privacy scaling \varepsilon_{n}=o(1) as n\to\infty . In the high privacy regime, it is common to compare shuffled protocols against trivial lower bounds obtained by invoking minimax lower bounds for mean estimation of the central model [ 8 ] . However, such central-model lower bounds ignore the shuffling structure entirely and can therefore be loose. Moreover, central-model lower bounds are rarely suited to resolving fine-grained privacy–utility trade-offs (e.g., matching leading constants). Upper bounds. In the single-message shuffle model, order-optimal protocols are known in the moderate-privacy regime \varepsilon_{n}=\Theta(1) (see, e.g., 4 , 1 ). In the high privacy scaling \varepsilon_{n}=o(1) , there are also constructions achieving the corresponding order-optimal rates up to constant factors [ 10 ] . Moreover, the resulting MSE is suggestive of convergence up to constants to that of the central Gaussian mechanism as \varepsilon_{n} decreases. What has been missing, however, is a theory establishing whether and in what sense single-message shuffling can match the central Gaussian trade-off in the high privacy regime, and how the approach to the Gaussian limit depends quantitatively on the scaling of \varepsilon_{n} . 25 propose a single-message vector aggregation protocol, but their analysis incurs additional error terms stemming from coordinate/dimension sampling, which can make the resulting upper bounds loose in regimes where one aims for sharp constants. While one can alternatively formulate and optimize protocols under an explicit communication constraint, as explored, for instance, by 10 , in this work we primarily focus on the privacy-utility trade-off and do not attempt to optimize communication. Multi-message shuffling. Multi-message shuffle protocols appear in (at least) two distinct forms. In the first, each user decomposes their contribution into multiple messages (multi-message per user), which are then shuffled jointly. These additional messages can strictly increase what is achievable: in the 1 -dimensional mean estimation, there are multi-message constructions whose accuracy can surpass that of the central Gaussian mechanism at comparable privacy levels [ 21 ] . For d>1 , however, no comparably efficient multi-message-per-user protocols are known that provably beat the central Gaussian mechanism. In the second form, one repeats a single-message shuffled primitive over multiple rounds and composes the privacy losses (multi-round shuffling). This is the dominant approach in d>1 , where mean estimation is invoked repeatedly and one can exploit composition to convert many high privacy rounds into an overall moderate-privacy guarantee [ 1 , 10 ] . Such multi-round constructions are known to

Read the complete text