Shuffling-Aware Optimization for Private Vector Mean Estimation

• URL: http://arxiv.org/abs/2604.28032v1
• Date: Thu, 30 Apr 2026 15:47:17 GMT
• Title: Shuffling-Aware Optimization for Private Vector Mean Estimation
• Abstract summary: We introduce the recently proposed shuffle index and use it to formulate the post-shuffling mechanism problem as an explicit optimization problem.<n>We then establish a minimax lower bound on the 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.
• Score: 2.4264122405649045
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study $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.

Related papers

• First-Order Softmax Weighted Switching Gradient Method for Distributed Stochastic Minimax Optimization with Stochastic Constraints [9.141425189503794]
  We propose a novel first-order Softmax-Weighted Switching Gradient method tailored for federated learning.<n>Under full client participation, our algorithm achieves the standard $mathcalO(-4)$ oracle complexity.<n>We provide a unified error decomposition and establish a sharp $mathcalO(logfrac1)$ high-probability convergence guarantee.
  arXiv  Detail & Related papers  (2026-03-06T00:14:46Z)
• Analysis of Shuffling Beyond Pure Local Differential Privacy [2.4264122405649045]
  Shuffling is a powerful way to amplify privacy of a local randomizer in private distributed data analysis.<n>We develop an analysis that applies to a broad class of local randomizers under mild regularity assumptions.<n>We use an FFT-based algorithm for computing the blanket divergence at finite $n$.
  arXiv  Detail & Related papers  (2026-01-27T03:35:03Z)
• Zeroth-Order Optimization Finds Flat Minima [51.41529512093436]
  We show that zeroth-order optimization with the standard two-point estimator favors solutions with small trace of Hessian.<n>We further provide convergence rates of zeroth-order optimization to approximate flat minima for convex and sufficiently smooth functions.
  arXiv  Detail & Related papers  (2025-06-05T17:59:09Z)
• Optimal Survey Design for Private Mean Estimation [4.70569058594556]
  This work identifies the first privacy-aware stratified sampling scheme that minimizes the variance for general private mean estimation.<n>We propose an efficient algorithm to identify the integer-optimal design and offer insights on the structure of the optimal design.
  arXiv  Detail & Related papers  (2025-01-30T03:51:25Z)
• Near-Universally-Optimal Differentially Private Minimum Spanning Trees [0.0]
  We prove that a simple differentially private mechanism for approximately releasing the minimum spanning tree is near-optimal in the sense of universal optimality for the $ell_infty$ neighbor relation. We show that one may implement the exponential mechanism for MST in time, and that this results in universal near-optimality for both the $ell_infty$ and the $ell_infty$ neighbor relations.
  arXiv  Detail & Related papers  (2024-04-23T13:39:25Z)
• On User-Level Private Convex Optimization [59.75368670035683]
  We introduce a new mechanism for convex optimization (SCO) with user-level differential privacy guarantees. Our mechanism does not require any smoothness assumptions on the loss. Our bounds are the first where the minimum number of users needed for user-level privacy has no dependence on the dimension.
  arXiv  Detail & Related papers  (2023-05-08T17:47:28Z)
• General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean Estimation [58.03500081540042]
  A classical approach to private mean estimation is to compute the true mean and add unbiased, but possibly correlated, Gaussian noise to it. We show that for every input dataset, an unbiased mean estimator satisfying concentrated differential privacy introduces approximately at least as much error.
  arXiv  Detail & Related papers  (2023-01-31T18:47:42Z)
• Quantization for decentralized learning under subspace constraints [61.59416703323886]
  We consider decentralized optimization problems where agents have individual cost functions to minimize subject to subspace constraints. We propose and study an adaptive decentralized strategy where the agents employ differential randomized quantizers to compress their estimates. The analysis shows that, under some general conditions on the quantization noise, the strategy is stable both in terms of mean-square error and average bit rate.
  arXiv  Detail & Related papers  (2022-09-16T09:38:38Z)
• Distributed Sketching for Randomized Optimization: Exact Characterization, Concentration and Lower Bounds [54.51566432934556]
  We consider distributed optimization methods for problems where forming the Hessian is computationally challenging. We leverage randomized sketches for reducing the problem dimensions as well as preserving privacy and improving straggler resilience in asynchronous distributed systems.
  arXiv  Detail & Related papers  (2022-03-18T05:49:13Z)
• A Dimensionality Reduction Method for Finding Least Favorable Priors with a Focus on Bregman Divergence [108.28566246421742]
  This paper develops a dimensionality reduction method that allows us to move the optimization to a finite-dimensional setting with an explicit bound on the dimension. In order to make progress on the problem, we restrict ourselves to Bayesian risks induced by a relatively large class of loss functions, namely Bregman divergences.
  arXiv  Detail & Related papers  (2022-02-23T16:22:28Z)
• Optimum Noise Mechanism for Differentially Private Queries in Discrete Finite Sets [3.5379819043314176]
  We introduce a novel framework for designing an optimal noise Mass Probability Function tailored to discrete and finite query sets. Our framework seeks to optimize the noise distribution under an arbitrary $(epsilon, delta)$ constraint, thereby enhancing the accuracy and utility of the response. Numerical experiments highlight the superior performance of our proposed optimal mechanisms compared to state-of-the-art methods.
  arXiv  Detail & Related papers  (2021-11-23T05:24:34Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.