論文の概要: Concurrent Shuffle Differential Privacy Under Continual Observation

• arxiv url: http://arxiv.org/abs/2301.12535v1
• Date: Sun, 29 Jan 2023 20:42:54 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-31 16:29:27.772960
• Title: Concurrent Shuffle Differential Privacy Under Continual Observation
• Title（参考訳）: 連続観察における同時シャッフル差分プライバシー
• Authors: Jay Tenenbaum, Haim Kaplan, Yishay Mansour, Uri Stemmer
• Abstract要約: 個人的連続和問題(対数問題)について検討する。 並列シャッフルモデルでは,標準シャッフルモデルに比べて誤差が大幅に改善できることが示されている。
• 参考スコア（独自算出の注目度）: 60.127179363119936
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce the concurrent shuffle model of differential privacy. In this model we have multiple concurrent shufflers permuting messages from different, possibly overlapping, batches of users. Similarly to the standard (single) shuffle model, the privacy requirement is that the concatenation of all shuffled messages should be differentially private. We study the private continual summation problem (a.k.a. the counter problem) and show that the concurrent shuffle model allows for significantly improved error compared to a standard (single) shuffle model. Specifically, we give a summation algorithm with error $\tilde{O}(n^{1/(2k+1)})$ with $k$ concurrent shufflers on a sequence of length $n$. Furthermore, we prove that this bound is tight for any $k$, even if the algorithm can choose the sizes of the batches adaptively. For $k=\log n$ shufflers, the resulting error is polylogarithmic, much better than $\tilde{\Theta}(n^{1/3})$ which we show is the smallest possible with a single shuffler. We use our online summation algorithm to get algorithms with improved regret bounds for the contextual linear bandit problem. In particular we get optimal $\tilde{O}(\sqrt{n})$ regret with $k= \tilde{\Omega}(\log n)$ concurrent shufflers.
• Abstract（参考訳）: 差分プライバシーの同時シャッフルモデルを導入する。 このモデルでは、複数の同時シャフラーが、異なる、おそらく重複している、ユーザのバッチからメッセージを調整する。 標準(シングル)シャッフルモデルと同様に、プライバシー要件はすべてのシャッフルメッセージの結合は異なるプライベートであることである。 本研究では, 逐次和問題(対数問題)について検討し, 同時シャッフルモデルにより, 標準シャッフルモデルに比べて誤差が大幅に改善されることを示す。 具体的には、誤差$\tilde{O}(n^{1/(2k+1)})$と$k$の同時シャフラーを長さ$n$の列にまとめるアルゴリズムを与える。 さらに、アルゴリズムがバッチのサイズを適応的に選択できるとしても、この境界は任意の$k$に対して厳密であることを示す。 k=\log n$ shuffler の場合、結果として生じる誤差は多対数であり、1つのシャッシャーで可能な最小の値を示す $\tilde{\theta}(n^{1/3})$ よりもずっと良い。 オンライン要約アルゴリズムを用いて、文脈線形帯域問題に対する後悔境界を改良したアルゴリズムを得る。 特に、最適な$\tilde{o}(\sqrt{n})$ regret with $k= \tilde{\omega}(\log n)$ concurrent shufflers が得られる。

関連論文リスト

• 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)
• Variance-Aware Sparse Linear Bandits [64.70681598741417]
  余分な線形包帯に対する最悪のミニマックスは$widetildeThetaleft(sqrtdTright)$である。 ノイズがなく、アクションセットが単位球面である良性設定では、ディビジョン・アンド・コンカーを使用して、$widetildemathcal O(1)$ regretを達成することができる。 我々は,任意の分散対応線形帯域幅アルゴリズムを分散対応線形帯域幅アルゴリズムに変換する汎用フレームワークを開発した。
  論文  参考訳（メタデータ） (2022-05-26T15:55:44Z)
• Differentially Private Multi-Armed Bandits in the Shuffle Model [58.22098764071924]
  シャッフルモデルにおけるマルチアームバンディット(MAB)問題に対して,$(varepsilon,delta)$-differentially privateアルゴリズムを提案する。 我々の上限は、集中モデルにおいて最もよく知られたアルゴリズムの後悔とほぼ一致し、局所モデルにおいて最もよく知られたアルゴリズムを著しく上回っている。
  論文  参考訳（メタデータ） (2021-06-05T14:11:01Z)
• On Distributed Differential Privacy and Counting Distinct Elements [52.701425652208734]
  我々は、$n$ユーザのそれぞれが離散集合から要素を保持する設定について研究する。 目標は、すべてのユーザーに対して異なる要素の数を数えることだ。
  論文  参考訳（メタデータ） (2020-09-21T04:13:34Z)
• The Sparse Hausdorff Moment Problem, with Application to Topic Models [5.151973524974052]
  我々は$m=2k$iid二進確率変数のサンプルを用いて$k$-mixtureを同定するアルゴリズムを提案する。 加法精度$w_mincdotzetaO(k)$のモーメントを知るだけで十分である。
  論文  参考訳（メタデータ） (2020-07-16T04:23:57Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Connecting Robust Shuffle Privacy and Pan-Privacy [11.367579037903734]
  差分プライバシのEmphshuffleモデルでは、データ保持ユーザはセキュアなシャフラーにランダム化されたメッセージを送信し、シャフラーはメッセージを置換する。 Emphpan-privateモデルでは、アルゴリズムがストリームデータに関して異なるプライベートな内部状態を維持しながら、データのストリームを処理する。 弊社の結果は、プライバシー保証が悪意のあるユーザの影響を大きく受けていないプライベートプロトコルを不当にシャッフルすることに焦点を当てている。
  論文  参考訳（メタデータ） (2020-04-20T17:58:14Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)
• Optimal $\delta$-Correct Best-Arm Selection for Heavy-Tailed Distributions [2.2940141855172036]
  我々は、$delta$-correctアルゴリズムを用いて、最大平均値を持つものを識別する問題を考察する。 $delta$-correctアルゴリズムの下位境界はよく知られている。 我々は,下界の$delta$-correctアルゴリズムを提案し,$delta$を0に還元する。
  論文  参考訳（メタデータ） (2019-08-24T05:31:49Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。