論文の概要: 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)$の標準設定で最適であることを示す。
最後に、悪意のあるユーザに対するロバスト性を調査し、悪意のあるユーザが単一のシャフラーで大きな付加的エラーを発生させることができることを示す。
関連論文リスト
- $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。
p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。
p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
論文 参考訳(メタデータ) (2023-07-11T08:51:53Z) - 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) - Fast, Sample-Efficient, Affine-Invariant Private Mean and Covariance
Estimation for Subgaussian Distributions [8.40077201352607]
我々は,高次元共分散認識平均推定のための高速,微分プライベートなアルゴリズムを提案する。
我々のアルゴリズムは$tildemu$を生成し、$|mu|_Sigma leq alpha$が$n gtrsim tfrac d alpha2 + tfracd sqrtlog 1/deltaalpha varepsilon+fracdlog 1/deltavarepsilon$である。
論文 参考訳(メタデータ) (2023-01-28T16:57:46Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。