論文の概要: Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages
- arxiv url: http://arxiv.org/abs/2404.10201v2
- Date: Thu, 25 Apr 2024 05:09:49 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-26 20:28:54.231466
- Title: Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages
- Title（参考訳）: シャッフルモデルにおけるプライベートベクトル平均推定:多くのメッセージを必要とする最適なレート
- Authors: Hilal Asi, Vitaly Feldman, Jelani Nelson, Huy L. Nguyen, Kunal Talwar, Samson Zhou,
- Abstract要約: 本稿では,プライバシのシャッフルモデルにおけるプライベートベクトル平均推定の問題について検討する。
我々は,$tildemathcalOleft(min(nvarepsilon2,d)right)$ message per users を用いて,最適なエラーを実現する新しいマルチメッセージプロトコルを提案する。
- 参考スコア（独自算出の注目度）: 63.366380571397
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: 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 $\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 $\mathcal{O}(dn^{d/(d+2)}\varepsilon^{-4/(d+2)})$. Moreover, we show that any single-message protocol must incur mean squared error $\Omega(dn^{d/(d+2)})$, showing that our protocol is optimal in the standard setting where $\varepsilon = \Theta(1)$. Finally, we study robustness to malicious users and show that malicious users can incur large additive error with a single shuffler.
- Abstract（参考訳）: プライバシのシャッフルモデルにおいて,プライバシのプライベートベクトル平均推定の問題は,それぞれが単位ベクトル$v^{(i)} \in\mathbb{R}^d$を持つ場合である。
我々は,$\tilde{\mathcal{O}}\left(\min(n\varepsilon^2,d)\right)$ message per users を用いて,最適なエラーを実現する新しいマルチメッセージプロトコルを提案する。
さらに、最適なエラーを達成するための(バイアスのない)プロトコルは、各ユーザーが$\Omega(\min(n\varepsilon^2,d)/\log(n))$メッセージを送信し、メッセージ複雑性の最適性を対数要素まで示す必要があることを示す。
さらに、シングルメッセージ設定について検討し、平均二乗誤差 $\mathcal{O}(dn^{d/(d+2)}\varepsilon^{-4/(d+2)})$ を達成するプロトコルを設計する。
さらに、任意のシングルメッセージプロトコルが平均2乗誤差$\Omega(dn^{d/(d+2)})$を発生させなければならないことを示し、このプロトコルが$\varepsilon = \Theta(1)$の標準設定で最適であることを示す。
最後に、悪意のあるユーザに対するロバスト性を調査し、悪意のあるユーザが単一のシャフラーで大きな付加的エラーを発生させることができることを示す。
関連論文リスト
- Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。
本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-11-01T17:59:53Z) - Asynchronous Approximate Agreement with Quadratic Communication [23.27199615640474]
非同期ネットワークは$n$のメッセージ送信パーティで、そのうちの最大$t$はビザンチンです。
本研究では,入力の凸内積にほぼ等しい出力が得られるような近似一致について検討する。
これは、信頼できるブロードキャスト毎に$Theta(n2)$メッセージ、またはイテレーション毎に$Theta(n3)$メッセージを取る。
論文 参考訳（メタデータ） (2024-08-10T09:03:06Z) - Almost Instance-optimal Clipping for Summation Problems in the Shuffle Model of Differential Privacy [36.04370583654189]
クリッピング機構が$O(max_i x_i cdot loglog U /varepsilon)$のインスタンス最適誤差を実現する方法を示す。
また、この手法を高次元和推定問題とスパースベクトルアグリゲーションに拡張する。
論文 参考訳（メタデータ） (2024-03-15T09:04:00Z) - Privacy Amplification via Compression: Achieving the Optimal
Privacy-Accuracy-Communication Trade-off in Distributed Mean Estimation [20.909302074826666]
プライバシとコミュニケーションの制約は、連邦学習(FL)と分析(FA)の2つの主要なボトルネックである
それぞれのクライアントが$Thetaleft(n minleft(varepsilon, varepsilon2right)$ bits for FL と $Thetaleft(logleft(minleft(varepsilon, varepsilon2right)$)$ bits for FA の送信に十分であることを示す。
論文 参考訳（メタデータ） (2023-04-04T05:37:17Z) - Concurrent Shuffle Differential Privacy Under Continual Observation [60.127179363119936]
個人的連続和問題(対数問題)について検討する。
並列シャッフルモデルでは,標準シャッフルモデルに比べて誤差が大幅に改善できることが示されている。
論文 参考訳（メタデータ） (2023-01-29T20:42:54Z) - Near Sample-Optimal Reduction-based Policy Learning for Average Reward
MDP [58.13930707612128]
この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。
我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
論文 参考訳（メタデータ） (2022-12-01T15:57:58Z) - Tight Bounds for the Randomized and Quantum Communication Complexities
of Equality with Small Error [1.6522364074260811]
誤差が小さいEquality関数のランダム化および量子化通信複雑性を$epsilon$で調べる。
任意の$log(n/epsilon)-log(sqrtn/epsilon)+3$プロトコルが少なくとも$log(n/epsilon)-log(sqrtn/epsilon)-O(1)$ qubitsを通信することを示す。
論文 参考訳（メタデータ） (2021-07-25T13:52:42Z) - On Distributed Differential Privacy and Counting Distinct Elements [52.701425652208734]
我々は、$n$ユーザのそれぞれが離散集合から要素を保持する設定について研究する。
目標は、すべてのユーザーに対して異なる要素の数を数えることだ。
論文 参考訳（メタデータ） (2020-09-21T04:13:34Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。