View publication

We study the problem of private vector mean estimation in the shuffle model of privacy where nn users each have a unit vector in dd dimensions. We propose a new multi-message protocol that achieves the optimal error using O~(min(nε2,d))\tilde{\mathcal{O}}\left(\min(n\varepsilon^2,d)\right) messages per user. Moreover, we show that any (unbiased) protocol that achieves optimal error requires each user to send Ω(min(nε2,d)/log(n))\Omega(\min(n\varepsilon^2,d)/\log(n)) messages, demonstrating the optimality of our message complexity up to logarithmic factors.

Additionally, we study the single-message setting and design a protocol that achieves mean squared error O(dnd/(d+2)ε4/(d+2))\mathcal{O}(dn^{d/(d+2)}\varepsilon^{-4/(d+2)}). Moreover, we show that any single-message protocol must incur mean squared error Ω(dnd/(d+2))\Omega(dn^{d/(d+2)}), showing that our protocol is optimal in the standard setting where ε=Θ(1)\varepsilon = \Theta(1). Finally, we study robustness to malicious users and show that malicious users can incur large additive error with a single shuffler.

Related readings and updates.

Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometry

Stochastic convex optimization over an ℓ1ℓ_1ℓ1​-bounded domain is ubiquitous in machine learning applications such as LASSO but remains poorly understood when learning with differential privacy. We show that, up to logarithmic factors the optimal excess population loss of any (ε,δ)(\varepsilon, \delta)(ε,δ)-differentially private optimizer is log⁡(d)/n  +\sqrt{\log(d)/n}\; +log(d)/n​+ d/εn.\sqrt{d}/\varepsilon n.d​/εn. The upper bound is based on…
See paper details

Lower Bounds for Locally Private Estimation via Communication Complexity

We develop lower bounds for estimation under local privacy constraints—including differential privacy and its relaxations to approximate or Rényi differential privacy—by showing an equivalence between private estimation and communication-restricted estimation problems. Our results apply to arbitrarily interactive privacy mechanisms, and they also give sharp lower bounds for all levels of differential privacy protections, that is, privacy…
See paper details