Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914769762516992 |
|---|---|
| author | Asi, Hilal Feldman, Vitaly Nelson, Jelani Nguyen, Huy L. Talwar, Kunal Zhou, Samson |
| author_facet | Asi, Hilal Feldman, Vitaly Nelson, Jelani Nguyen, Huy L. Talwar, Kunal Zhou, Samson |
| contents | We study the problem of private vector mean estimation in the shuffle model of privacy where $n$ users each have a unit vector $v^{(i)} \in\mathbb{R}^d$. We propose a new multi-message protocol that achieves the optimal error using $\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\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 $\mathcal{O}(dn^{d/(d+2)}\varepsilon^{-4/(d+2)})$. Moreover, we show that any single-message protocol must incur mean squared error $Ω(dn^{d/(d+2)})$, showing that our protocol is optimal in the standard setting where $\varepsilon = Θ(1)$. Finally, we study robustness to malicious users and show that malicious users can incur large additive error with a single shuffler. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_10201 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages Asi, Hilal Feldman, Vitaly Nelson, Jelani Nguyen, Huy L. Talwar, Kunal Zhou, Samson Data Structures and Algorithms Cryptography and Security Information Theory Machine Learning We study the problem of private vector mean estimation in the shuffle model of privacy where $n$ users each have a unit vector $v^{(i)} \in\mathbb{R}^d$. We propose a new multi-message protocol that achieves the optimal error using $\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\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 $\mathcal{O}(dn^{d/(d+2)}\varepsilon^{-4/(d+2)})$. Moreover, we show that any single-message protocol must incur mean squared error $Ω(dn^{d/(d+2)})$, showing that our protocol is optimal in the standard setting where $\varepsilon = Θ(1)$. Finally, we study robustness to malicious users and show that malicious users can incur large additive error with a single shuffler. |
| title | Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages |
| topic | Data Structures and Algorithms Cryptography and Security Information Theory Machine Learning |
| url | https://arxiv.org/abs/2404.10201 |