Optimal Algorithms for Mean Estimation under Local Differential Privacy

Hilal AsiVitaly FeldmanKunal Talwar

article2022ICML51 citations

Proves that the PrivUnit algorithm achieves optimal variance for unbiased locally differentially private mean estimation and introduces a Gaussian-based variant, PrivUnitG, that enables dimension-independent parameter optimization and precise error analysis.

Listen

Modern data applications like federated learning and distributed machine learning frequently aggregate user data without relying on a trusted central party. Local differential privacy protects individual privacy by having each user randomize their own data vector before sharing it. While existing literature has established asymptotic rates showing how error scales generally with data dimension and privacy budgets, competing methods exhibit large differences in actual performance due to hidden constant factors. Because strict privacy budgets are non-negotiable and collecting more user data is often expensive or unfeasible, identifying the exact algorithm that delivers the smallest estimation error is essential.

The main objective of the article is to identify and characterize the strictly optimal algorithm for estimating the mean of Euclidean unit vectors under non-interactive, unbiased local differential privacy. The article evaluates existing mechanisms and formulates a new approach to achieve the lowest possible variance.

The article utilizes a rigorous mathematical and structural optimization approach. It first demonstrates that canonical protocols—which pair a local randomizer with standard additive aggregation—can achieve optimal error across all possible unbiased mechanisms. It then exploits domain rotational and reflection symmetries to express the optimal randomizer design as a linear program, subsequently validating the analytical findings through numerical simulations across varying dimensions and privacy parameters.

The investigation produced several key findings. First, the article proves that the existing PrivUnit algorithm, when configured with optimized parameters, achieves strictly optimal variance among all unbiased local private procedures. Second, it introduces PrivUnitG, a Gaussian-based variant that achieves the same optimal error up to a negligible multiplicative factor as the dimension grows. Third, unlike standard PrivUnit, the optimal operating parameters for PrivUnitG are independent of the data dimension, making high-dimensional implementations computationally efficient. Finally, analytical and empirical evaluations show that the normalized error constant converges cleanly to an asymptotic limit of approximately 0.614 as the privacy budget and dimensions increase.

These findings have direct operational and strategic implications for private analytics. System architects no longer need to guess among competing algorithms or accept poor empirical constants; optimized PrivUnit-style mechanisms provide the guaranteed best accuracy for a target privacy level. This optimizes the trade-off between user privacy and model utility, reducing the total sample size needed to hit target performance thresholds and lowering overall data collection costs.

Engineering teams deploying local differential privacy or shuffle-model architectures should adopt PrivUnit with optimal parameters or its Gaussian variant PrivUnitG. Practitioners operating in high dimensions should favor PrivUnitG to take advantage of its dimension-independent parameter tuning. Furthermore, developers should consider combining PrivUnitG with lossy compression techniques to minimize network communication overhead while preserving near-optimal statistical accuracy.

The conclusions are mathematically proven and backed by consistent numerical experiments, providing high confidence within the evaluated scope. However, key limitations apply: the optimality guarantees assume non-interactive protocols, unbiased estimators, and inputs bounded within the Euclidean unit sphere. Stakeholders should exercise caution if extending these exact mechanisms to interactive systems, biased estimation pipelines, or alternative data geometries without further validation.

Apple Stanford University differential privacies estimation method individual privacy local differential privacy private mean estimation optimal local randomizer

arXiv: 2205.02466

Paper: What Can We Learn Privately?, Shiva Prasad Kasiviswanathan et al. (2008). This foundational work introduces the theoretical formulation and sample complexity boundaries of local differential privacy protocols upon which private mean estimation algorithms build.

No sufficiently relevant recommendations were found.

Cover for Optimal Algorithms for Mean Estimation under Local Differential Privacy

Abstract

We study the problem of mean estimation of ℓ2-bounded vectors under the constraint of local differential privacy. While the literature has a variety of algorithms that achieve the asymptotically optimal rates for this problem, the performance of these algorithms in practice can vary significantly due to varying (and often large) hidden constants. In this work, we investigate the question of designing the protocol with the smallest variance. We show that PrivUnit (Bhowmick et al., 2018) with optimized parameters achieves the optimal variance among a large family of locally private randomizers. To prove this result, we establish some properties of local randomizers, and use symmetrization arguments that allow us to write the optimal randomizer as the optimizer of a certain linear program. These structural results, which should extend to other problems, then allow us to show that the optimal randomizer belongs to the PrivUnit family.

We also develop a new variant of PrivUnit based on the Gaussian distribution which is more amenable to mathematical analysis and enjoys the same optimality guarantees. This allows us to establish several useful properties on the exact constants of the optimal error as well as to numerically estimate these constants.

Topics

differential privacies estimation method individual privacy

Keywords

local differential privacy private mean estimation optimal local randomizer privacy mechanisms additive aggregation shuffle model Gaussian distribution

1. Introduction
1.1. Our contributions
1.2. Related work
2. Problem setting and preliminaries
3. Optimality of PrivUnit
3.1. PrivUnit
3.2. Optimality
3.3. Optimality of canonical protocols
3.4. Optimality of PrivUnit among canonical randomizers
4. PrivUnitG: an optimal algorithm based on Gaussian distribution
4.1. Analytical expression for optimal error
5. Conclusions
References

Knowls

Knowl 1 — Strict Optimality of PrivUnit for Locally Private Mean Estimation
theoretical result
Let $\mathbb{S}^{d-1} = \{v \in \mathbb{R}^d : \|v\|_2 = 1\}$ denote the Euclidean unit sphere in $\mathbb{R}^d$ . Consider the problem of non-interactive, unbiased mean estimation under $\epsilon$ -local differential privacy ( $\epsilon$ -LDP), where each of $n$ users holds an input vector $v_i \in \mathbb{S}^{d-1}$ . A private protocol is defined by an $\epsilon$ -LDP local randomizer $\mathcal{R}: \mathbb{S}^{d-1} \to \mathcal{Z}$ and an aggregation function $\mathcal{A}: \mathcal{Z}^n \to \mathbb{R}^d$ that satisfy the unbiasedness condition $\mathbb{E}[\mathcal{A}(\mathcal{R}(v_1), \dots, \mathcal{R}(v_n))] = \frac{1}{n} \sum_{i=1}^n v_i$ for all $v_1, \dots, v_n \in \mathbb{S}^{d-1}$ . The protocol's worst-case mean squared error is $\mathrm{Err}_n(\mathcal{A}, \mathcal{R}) = \sup_{v_1, \dots, v_n \in \mathbb{S}^{d-1}} \mathbb{E}\left[\left\|\mathcal{A}(\mathcal{R}(v_1), \dots, \mathcal{R}(v_n)) - \frac{1}{n}\sum_{i=1}^n v_i\right\|_2^2\right].$ For the canonical additive aggregator $\mathcal{A}^+(z_1, \dots, z_n) = \frac{1}{n} \sum_{i=1}^n z_i$ , there exist optimal parameters $p^* \in [0, 1]$ and $\gamma^* \in [0, 1]$ such that the $\mathrm{PrivUnit}(p^*, \gamma^*)$ randomizer satisfies $\epsilon$ -LDP and strictly minimizes the worst-case variance across all possible unbiased $\epsilon$ -LDP protocols: $\mathrm{Err}_n(\mathcal{A}^+, \mathrm{PrivUnit}(p^*, \gamma^*)) \le \mathrm{Err}_n(\mathcal{A}, \mathcal{R}).$
Knowl 2 — PrivUnit Randomizer and Exact Local Privacy Condition
model/method
Given an input vector $v \in \mathbb{S}^{d-1} = \{u \in \mathbb{R}^d : \|u\|_2 = 1\}$ , the $\mathrm{PrivUnit}(p, \gamma)$ mechanism samples a random vector $W \sim \mathrm{Uni}(\mathbb{S}^{d-1})$ uniformly from the unit sphere, and draws its unnormalized output according to the mixture: $\mathrm{PrivUnit}(p, \gamma) \sim \begin{cases} W \mid \langle W, v \rangle \ge \gamma & \text{with probability } p, \\ W \mid \langle W, v \rangle < \gamma & \text{with probability } 1 - p. \end{cases}$ The output is then multiplied by a normalization constant to satisfy $\mathbb{E}[\mathrm{PrivUnit}(p, \gamma)] = v$ .

Let $q = \mathbb{P}(W_1 \le \gamma)$ , where $W_1$ is a single coordinate marginal of $W \sim \mathrm{Uni}(\mathbb{S}^{d-1})$ . The randomizer $\mathrm{PrivUnit}(p, \gamma)$ satisfies pure $\epsilon$ -local differential privacy if and only if the parameters $p, q \in [0, 1]$ satisfy $\frac{p}{1-p} \cdot \frac{q}{1-q} \le e^\epsilon.$
Knowl 3 — PrivUnitG Gaussian Local Randomizer and Variance Formula
model/method
PrivUnitG is a Gaussian-based local differential privacy randomizer for vectors on $\mathbb{S}^{d-1} = \{v \in \mathbb{R}^d : \|v\|_2 = 1\}$ . Given an input $v \in \mathbb{S}^{d-1}$ , variance parameter $\sigma^2 = 1/d$ , CDF probability $q \in [0, 1]$ , threshold $\gamma = \sigma \Phi^{-1}(q) = \frac{\Phi^{-1}(q)}{\sqrt{d}}$ (where $\Phi$ is the standard Gaussian cumulative distribution function), and probability $p \in [0, 1]$ , the mechanism samples $U \sim \mathcal{N}(0, \sigma^2 I_d)$ conditioned on thresholding: $U \sim \begin{cases} U \mid \langle U, v \rangle \ge \gamma & \text{with probability } p, \\ U \mid \langle U, v \rangle < \gamma & \text{with probability } 1 - p. \end{cases}$ To ensure unbiasedness $\mathbb{E}[\mathrm{PrivUnitG}(v)] = v$ , the output is normalized as $U / \mathbb{E}[\alpha]$ , where $\alpha = \langle U, v \rangle$ .

If $\frac{p}{1-p}\frac{q}{1-q} \le e^\epsilon$ , $\mathrm{PrivUnitG}(p, q)$ is an $\epsilon$ -DP local randomizer. Its single-sample variance is $\mathrm{Err}(\mathrm{PrivUnitG}(p, q)) = \frac{\mathbb{E}[\alpha^2] + \frac{d-1}{d}}{\mathbb{E}[\alpha]^2} - 1.$ Furthermore, defining $m = \sigma \phi(\gamma/\sigma) \left(\frac{p}{1-q} - \frac{1-p}{q}\right)$ where $\phi$ is the standard Gaussian density function, the error satisfies $\lim_{d \to \infty} m^2 \cdot \mathrm{Err}(\mathrm{PrivUnitG}(p, q)) = 1.$
Knowl 4 — Asymptotic Error Equivalence of PrivUnitG and PrivUnit
theoretical result
Let $\mathrm{Err}^*_{\epsilon, d}(\mathrm{PrivUnit})$ and $\mathrm{Err}^*_{\epsilon, d}(\mathrm{PrivUnitG})$ denote the minimum mean squared estimation errors over all parameter choices $p, q \in [0, 1]$ satisfying the $\epsilon$ -LDP condition $\frac{pq}{(1-p)(1-q)} \le e^\epsilon$ in dimension $d$ : $\mathrm{Err}^*_{\epsilon, d}(\mathrm{PrivUnit}) = \inf_{p, q : \frac{pq}{(1-p)(1-q)} \le e^\epsilon} \mathrm{Err}(\mathrm{PrivUnit}(p, q)),$ $\mathrm{Err}^*_{\epsilon, d}(\mathrm{PrivUnitG}) = \inf_{p, q : \frac{pq}{(1-p)(1-q)} \le e^\epsilon} \mathrm{Err}(\mathrm{PrivUnitG}(p, q)).$ For any parameter pair $(p, q) \in [0, 1]^2$ satisfying $\epsilon$ -LDP, $\mathrm{PrivUnitG}(p, q)$ is also $\epsilon$ -LDP, and the error ratio satisfies $\frac{\mathrm{Err}(\mathrm{PrivUnitG}(p, q))}{\mathrm{Err}(\mathrm{PrivUnit}(p, q))} \le 1 + O\left(\sqrt{\frac{\epsilon + \log d}{d}}\right).$ Consequently, the optimal errors of the two mechanisms match up to an asymptotically vanishing multiplicative factor: $\frac{\mathrm{Err}^*_{\epsilon, d}(\mathrm{PrivUnitG})}{\mathrm{Err}^*_{\epsilon, d}(\mathrm{PrivUnit})} \le 1 + O\left(\sqrt{\frac{\epsilon + \log d}{d}}\right).$
Knowl 5 — Optimality of Canonical Protocols for Locally Private Mean Estimation
theoretical result
A protocol $(\mathcal{R}, \mathcal{A})$ for mean estimation of unit vectors on $\mathbb{S}^{d-1}$ is called canonical if the local randomizer outputs vectors in $\mathbb{R}^d$ ( $\mathcal{R}: \mathbb{S}^{d-1} \to \mathbb{R}^d$ ) with $\mathbb{E}[\mathcal{R}(v)] = v$ , and the aggregation function is the simple empirical average $\mathcal{A}^+(z_1, \dots, z_n) = \frac{1}{n} \sum_{i=1}^n z_i$ .

For any non-interactive $\epsilon$ -LDP protocol $(\mathcal{R}, \mathcal{A})$ with an arbitrary output domain $\mathcal{Z}$ and arbitrary aggregation function $\mathcal{A}: \mathcal{Z}^n \to \mathbb{R}^d$ satisfying the unbiasedness condition $\mathbb{E}[\mathcal{A}(\mathcal{R}(v_1), \dots, \mathcal{R}(v_n))] = \frac{1}{n}\sum_{i=1}^n v_i$ , there exists a canonical $\epsilon$ -LDP randomizer $\mathcal{R}': \mathbb{S}^{d-1} \to \mathbb{R}^d$ such that $\mathrm{Err}_n(\mathcal{A}^+, \mathcal{R}') \le \mathrm{Err}_n(\mathcal{A}, \mathcal{R}),$ where $\mathrm{Err}_n(\mathcal{A}, \mathcal{R}) = \sup_{v_1, \dots, v_n \in \mathbb{S}^{d-1}} \mathbb{E}\left[\left\|\mathcal{A}(\mathcal{R}(v_1), \dots, \mathcal{R}(v_n)) - \frac{1}{n}\sum_{i=1}^n v_i\right\|_2^2\right]$ .
Knowl 6 — Symmetrization and Two-Point Density Structure of Optimal Local Randomizers
theoretical result
Let $\mathcal{R}: \mathbb{S}^{d-1} \to \mathbb{R}^d$ be an unbiased $\epsilon$ -DP local randomizer satisfying $\mathbb{E}[\mathcal{R}(v)] = v$ for all $v \in \mathbb{S}^{d-1}$ . For any tolerance $\tau > 0$ , there exists a constant $C > 0$ , a base value $p > 0$ , and an $\epsilon$ -DP local randomizer $\mathcal{R}': \mathbb{S}^{d-1} \to C \cdot \mathbb{S}^{d-1}$ supported entirely on a sphere of radius $C$ such that:
1. Unbiasedness: $\mathbb{E}[\mathcal{R}'(v)] = v$ for all $v \in \mathbb{S}^{d-1}$ .
2. Bounded error: $\mathrm{Err}(\mathcal{R}') \le \mathrm{Err}(\mathcal{R}) + \tau$ , where $\mathrm{Err}(\mathcal{R}') = \mathbb{E}[\|\mathcal{R}'(v) - v\|_2^2] = C^2 - 1$ .
3. Reflection symmetry: For input $v = e_1$ , $f_{\mathcal{R}'(e_1)}(u) = f_{\mathcal{R}'(e_1)}(u^-)$ for all $u \in C \cdot \mathbb{S}^{d-1}$ , where $u^- = (u_1, -u_2, \dots, -u_d)$ .
4. Two-level density: The probability density function takes at most two extreme values: $f_{\mathcal{R}'(v)}(u) \in \{e^{-\epsilon/2} p, \; e^{\epsilon/2} p\}$ for all outputs $u \in C \cdot \mathbb{S}^{d-1}$ .
Knowl 7 — Density Sandwich Property for Local Differential Privacy
theoretical result
Let $\mathcal{R}: \mathbb{S}^{d-1} \to \mathbb{R}^d$ be an $\epsilon$ -DP local randomizer with output probability density functions $f_{\mathcal{R}(v)}(u)$ for inputs $v \in \mathbb{S}^{d-1}$ and outputs $u \in \mathbb{R}^d$ . There exists a central reference density $\rho: \mathbb{R}^d \to \mathbb{R}_+$ , defined by $\rho(u) = \sqrt{\left(\inf_{v \in \mathbb{S}^{d-1}} f_{\mathcal{R}(v)}(u)\right) \cdot \left(\sup_{v \in \mathbb{S}^{d-1}} f_{\mathcal{R}(v)}(u)\right)},$ such that for all $v \in \mathbb{S}^{d-1}$ and $u \in \mathbb{R}^d$ : $e^{-\epsilon/2} \le \frac{f_{\mathcal{R}(v)}(u)}{\rho(u)} \le e^{\epsilon/2}.$ Moreover, if $\mathcal{R}$ is rotation-invariant (meaning that for every $v, v' \in \mathbb{S}^{d-1}$ , there exists an orthogonal matrix $V \in \mathbb{R}^{d \times d}$ such that $\mathcal{R}(v) \stackrel{d}{=} V \mathcal{R}(v')$ ), then $\rho(u_1) = \rho(u_2)$ for all $u_1, u_2 \in \mathbb{R}^d$ with $\|u_1\|_2 = \|u_2\|_2$ .
Knowl 8 — Convergence Rate of the PrivUnitG Normalized Variance Constant Across Dimensions
theoretical result
Let $C_{\epsilon, d}$ denote the normalized optimal error constant for the PrivUnitG mechanism in dimension $d$ under local privacy budget $\epsilon$ , defined by $\mathrm{Err}^*_{\epsilon, d}(\mathrm{PrivUnitG}) = C_{\epsilon, d} \frac{d}{\epsilon}.$ For any fixed $\epsilon > 0$ and any dimensions $1 \le d_1 \le d_2$ , the sequence $C_{\epsilon, d}$ satisfies the quantitative convergence rate $\Omega\left(\frac{\epsilon + \log d_2}{d_2} + \frac{\epsilon}{d_1}\right) \le \left|\frac{C_{\epsilon, d_1}}{C_{\epsilon, d_2}} - 1\right| \le O\left(\frac{\epsilon + \log d_1}{d_1}\right).$ In particular, as dimension $d \to \infty$ , $C_{\epsilon, d}$ converges to a dimension-independent limit $C_\epsilon = \lim_{d \to \infty} C_{\epsilon, d}$ .
Knowl 9 — Asymptotic Limit of the Normalized Error Constant for Large Privacy Budgets
theoretical result
Let $C_\epsilon = \lim_{d \to \infty} C_{\epsilon, d} = \lim_{d \to \infty} \frac{\epsilon}{d} \mathrm{Err}^*_{\epsilon, d}(\mathrm{PrivUnitG})$ denote the dimension-free optimal error constant under privacy parameter $\epsilon$ . As the privacy parameter $\epsilon \to \infty$ , the sequence $C_\epsilon$ converges to a universal strictly positive limit: $\lim_{\epsilon \to \infty} C_\epsilon = C^*.$ Numerical estimation shows that this asymptotic limit evaluates to $C^* \approx 0.614177$ .

Coverage note — Omitted the step-by-step discretization analysis of the linear program and the repetitive sample compression discussions from prior works.

References

1.[1] D. Amodei, C. Olah, J. Steinhardt, P. Christiano, J. Schulman, and D. Mané, "Concrete problems in AI safety," arXiv preprint arXiv:1606.06565, 2016.
2.[2] S. Zai, "Building safe AI: Uncertainty and deep learning," 2018. [Online]. Available: https://k2shah.github.io/uncertainty-ml-safe-ai/
3.[3] R. Luo, "Meta-Learning Multi-Task Communication," arXiv preprint arXiv:1804.05801, 2018.
4.[4] S. Gu, E. Holly, T. Lillicrap, and S. Levine, "Deep reinforcement learning for robotic manipulation with asynchronous off-policy learning," arXiv preprint arXiv:1610.00633, 2016.
5.[5] A. A. Rusu, N. C. Rabinowitz, G. Desjardins, H. Soyer, J. Kirkpatrick, K. Kavukcuoglu, R. Pascanu, and R. Hadsell, "Progressive neural networks," arXiv preprint arXiv:1606.04671, 2016.
6.[6] C. Finn, P. Abbeel, and S. Levine, "Model-agnostic meta-learning for fast adaptation of deep networks," arXiv preprint arXiv:1703.03400, 2017.
7.[7] S. Hochreiter and J. Schmidhuber, "Long short-term memory," Neural computation, vol. 9, no. 8, pp. 1735–1780, 1997.
8.[8] V. Mnih, A. P. Badia, M. Mirza, A. Graves, T. Lillicrap, T. Harley, D. Silver, and K. Kavukcuoglu, "Asynchronous methods for deep reinforcement learning," in International conference on machine learning, 2016, pp. 1928–1937.
9.[9] M. Hausknecht and P. Stone, "Deep recurrent q-learning for partially observable mdps," arXiv preprint arXiv:1507.06527, 2015.
10.[10] S. Levine, P. Pastor, A. Krizhevsky, and D. Quillen, "Learning hand-eye coordination for robotic grasping with deep learning and large-scale data collection," arXiv preprint arXiv:1603.02199, 2016.
11.[11] J. G. Rogers and H. Christensen, "Perception for a durable robot," in Robotics: Science and Systems, 2017.
12.[12] B. Wymann, E. Espié, C. Guionneau, C. Dimitrakakis, R. Coulom, and A. Sumner, "Torcs, the open racing car simulator," 2000. [Online]. Available: http://torcs.sourceforge.net
13.[13] A. Juliani, V.-P. Berges, E. Teng, A. Cohen, J. Harper, C. Elion, C. Goy, Y. Gao, H. Henry, M. Moss et al., "Unity: A general platform for intelligent agents," arXiv preprint arXiv:1809.02627, 2018.
14.[14] N. Koenig and A. Howard, "Design and use paradigms for gazebo, an open-source multi-robot simulator," in Intelligent Robots and Systems, 2004.(IROS 2004). Proceedings. 2004 IEEE/RSJ International Conference on, vol. 3. IEEE, 2004, pp. 2149–2154.
15.[15] J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov, "Proximal policy optimization algorithms," arXiv preprint arXiv:1707.06347, 2017.
16.[16] T. Degris, M. White, and R. S. Sutton, "Off-policy actor-critic," arXiv preprint arXiv:1205.4839, 2012.
17.[17] B. Kohler and M. Manzagol, "Efficient parallel stochastic gradient descent for training of deep neural networks," arXiv preprint arXiv:1707.07021, 2017.
18.[18] S. Zhang and R. S. Sutton, "A deeper look at experience replay," arXiv preprint arXiv:1712.01275, 2017.
19.[19] C. Finn, X. Y. Tian, T. Erez, P. Abbeel, and S. Levine, "One-shot visual imitation learning via meta-learning," arXiv preprint arXiv:1709.00493, 2017.
20.[20] S. Zhang, B. Liu, and W. S. Lee, "From max-well to max-q: Driving in a stochastic world with model-free deep reinforcement learning," 2018.
21.[21] Y. Gal, "Uncertainty in deep learning," Ph.D. dissertation, University of Cambridge, 2016.
22.[22] I. Osband, C. Blundell, A. Pritzel, and B. V. Roy, "Deep exploration via bootstrapped dqn," arXiv preprint arXiv:1602.04621, 2016.
23.[23] N. Srivastava, G. Hinton, A. Krizhevsky, I. Sutskever, and R. Salakhutdinov, "Dropout: a simple way to prevent neural networks from overfitting," Journal of Machine Learning Research, vol. 15, no. 1, pp. 1929–1958, 2014.
24.[24] M. Abadi, P. Barham, J. Chen, Z. Chen, A. Davis, J. Dean, M. Devin, S. Ghemawat, G. Irving, M. Isard et al., "Tensorflow: A system for large-scale machine learning," in OSDI, vol. 16, 2016, pp. 265–283.
25.[25] J. Schulman, S. Levine, P. Abbeel, M. Jordan, and P. Moritz, "Trust region policy optimization," in International Conference on Machine Learning, 2015, pp. 1889–1897.
26.[26] S. Levine, "Deep rl, decision making and control," 2017. [Online]. Available: http://rail.eecs.berkeley.edu/deeprlcourse/

Citation

MLA

Asi, H., et al. “Optimal Algorithms for Mean Estimation Under Local Differential Privacy”. International Conference on Machine Learning, vol. 162, 2022, pp. 1046–56, https://proceedings.mlr.press/v162/asi22b.html.

APA

Asi, H., Feldman, V., & Talwar, K. (2022). Optimal Algorithms for Mean Estimation under Local Differential Privacy. International Conference on Machine Learning, 162, 1046–1056. https://proceedings.mlr.press/v162/asi22b.html

Chicago

Asi, H., V. Feldman, and K. Talwar. 2022. “Optimal Algorithms for Mean Estimation Under Local Differential Privacy”. International Conference on Machine Learning 162: 1046–56. https://proceedings.mlr.press/v162/asi22b.html.

Harvard

Asi, H., Feldman, V. and Talwar, K. (2022) “Optimal Algorithms for Mean Estimation under Local Differential Privacy”, International Conference on Machine Learning. PMLR, pp. 1046–1056. Available at: https://proceedings.mlr.press/v162/asi22b.html.

Vancouver

1. Asi H, Feldman V, Talwar K (2022) Optimal Algorithms for Mean Estimation under Local Differential Privacy. In: International Conference on Machine Learning. PMLR, pp 1046–1056

BibTeX

@InProceedings{pmlr-v162-asi22b,
  title = 	 {Optimal Algorithms for Mean Estimation under Local Differential Privacy},
  author =       {Asi, Hilal and Feldman, Vitaly and Talwar, Kunal},
  booktitle = 	 {Proceedings of the 39th International Conference on Machine Learning},
  pages = 	 {1046--1056},
  year = 	 {2022},
  editor = 	 {Chaudhuri, Kamalika and Jegelka, Stefanie and Song, Le and Szepesvari, Csaba and Niu, Gang and Sabato, Sivan},
  volume = 	 {162},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {17--23 Jul},
  publisher =    {PMLR},
  pdf = 	 {https://proceedings.mlr.press/v162/asi22b/asi22b.pdf},
  url = 	 {https://proceedings.mlr.press/v162/asi22b.html},
  abstract = 	 {We study the problem of mean estimation of $\ell_2$-bounded vectors under the constraint of local differential privacy. While the literature has a variety of algorithms that achieve the (asymptotic) optimal rates for this problem, the performance of these algorithms in practice can vary significantly due to varying (and often large) hidden constants. In this work, we investigate the question of designing the randomizer with the smallest variance. We show that PrivUnit (Bhowmick et al. 2018) with optimized parameters achieves the optimal variance among a large family of natural randomizers. To prove this result, we establish some properties of local randomizers, and use symmetrization arguments that allow us to write the optimal randomizer as the optimizer of a certain linear program. These structural results, which should extend to other problems, then allow us to show that the optimal randomizer belongs to the PrivUnit family. We also develop a new variant of PrivUnit based on the Gaussian distribution which is more amenable to mathematical analysis and enjoys the same optimality guarantees. This allows us to establish several useful properties on the exact constants of the optimal error as well as to numerically estimate these constants.}
}

Metadata:DOI registry

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

Optimal Algorithms for Mean Estimation under Local Differential Privacy

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Strict Optimality of PrivUnit for Locally Private Mean Estimation

Knowl 2 — PrivUnit Randomizer and Exact Local Privacy Condition

Knowl 3 — PrivUnitG Gaussian Local Randomizer and Variance Formula

Knowl 4 — Asymptotic Error Equivalence of PrivUnitG and PrivUnit

Knowl 5 — Optimality of Canonical Protocols for Locally Private Mean Estimation

Knowl 6 — Symmetrization and Two-Point Density Structure of Optimal Local Randomizers

Knowl 7 — Density Sandwich Property for Local Differential Privacy

Knowl 8 — Convergence Rate of the PrivUnitG Normalized Variance Constant Across Dimensions

Knowl 9 — Asymptotic Limit of the Normalized Error Constant for Large Privacy Budgets

References

Citation

BibTeX

Access the Paper