論文の概要: Almost Instance-optimal Clipping for Summation Problems in the Shuffle Model of Differential Privacy

• arxiv url: http://arxiv.org/abs/2403.10116v2
• Date: Fri, 30 Aug 2024 15:16:26 GMT
• ステータス: 処理完了
• システム内更新日: 2024-09-02 20:11:53.440073
• Title: Almost Instance-optimal Clipping for Summation Problems in the Shuffle Model of Differential Privacy
• Title（参考訳）: 微分プライバシのシャッフルモデルにおけるサミネーション問題に対するほぼ最適クリッピング
• Authors: Wei Dong, Qiyao Luo, Giulia Fanti, Elaine Shi, Ke Yi,
• Abstract要約: クリッピング機構が$O(max_i x_i cdot loglog U /varepsilon)$のインスタンス最適誤差を実現する方法を示す。 また、この手法を高次元和推定問題とスパースベクトルアグリゲーションに拡張する。
• 参考スコア（独自算出の注目度）: 36.04370583654189
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Differentially private mechanisms achieving worst-case optimal error bounds (e.g., the classical Laplace mechanism) are well-studied in the literature. However, when typical data are far from the worst case, \emph{instance-specific} error bounds -- which depend on the largest value in the dataset -- are more meaningful. For example, consider the sum estimation problem, where each user has an integer $x_i$ from the domain $\{0,1,\dots,U\}$ and we wish to estimate $\sum_i x_i$. This has a worst-case optimal error of $O(U/\varepsilon)$, while recent work has shown that the clipping mechanism can achieve an instance-optimal error of $O(\max_i x_i \cdot \log\log U /\varepsilon)$. Under the shuffle model, known instance-optimal protocols are less communication-efficient. The clipping mechanism also works in the shuffle model, but requires two rounds: Round one finds the clipping threshold, and round two does the clipping and computes the noisy sum of the clipped data. In this paper, we show how these two seemingly sequential steps can be done simultaneously in one round using just $1+o(1)$ messages per user, while maintaining the instance-optimal error bound. We also extend our technique to the high-dimensional sum estimation problem and sparse vector aggregation (a.k.a. frequency estimation under user-level differential privacy).
• Abstract（参考訳）: 最悪ケースの最適誤差境界(例:古典的なラプラス機構)を達成するための異なるプライベートなメカニズムは、文献でよく研究されている。 しかし、典型的なデータが最悪のケースから遠く離れた場合、データセットの最大の値に依存する \emph{instance-specific} エラー境界の方が有意義である。 例えば、各ユーザが領域 $\{0,1,\dots,U\}$ から整数 $x_i$ を持ち、$\sum_i x_i$ を見積もる和推定問題を考える。 これは$O(U/\varepsilon)$の最悪の最適誤差を持つが、最近の研究では、クリッピング機構が$O(\max_i x_i \cdot \log\log U /\varepsilon)$のインスタンス最適誤差を達成できることが示されている。 シャッフルモデルでは、既知のインスタンス最適化プロトコルは通信効率が低い。 クリッピング機構はシャッフルモデルでも機能するが、ラウンド1はクリッピングしきい値を見つけ、ラウンド2はクリッピングを行い、クリッピングデータのノイズ和を計算する。 本稿では,この2つの連続的なステップを1ラウンドで同時に行う方法について,インスタンス-最適エラーバウンダリを維持しながら,ユーザ1人あたり1+o(1)$メッセージで示す。 また、この手法を高次元和推定問題とスパースベクトル集約(すなわち、ユーザレベルの差分プライバシーの下での周波数推定)に拡張する。

関連論文リスト

• Statistical-Computational Trade-offs for Density Estimation [60.81548752871115]
  幅広い種類のデータ構造に対して、それらの境界は著しく改善されないことを示す。 これは密度推定のための新しい統計計算トレードオフである。
  論文  参考訳（メタデータ） (2024-10-30T15:03:33Z)
• Better Locally Private Sparse Estimation Given Multiple Samples Per User [2.9562742331218725]
  ユーザレベルの局所微分プライベートスパース線形回帰について検討する。 我々は、$n$のユーザがそれぞれ$m$のサンプルを提供していれば、$d$の線形依存を排除できることを示した。 本稿では,まず候補変数を選択し,次に狭義の低次元空間で推定を行うフレームワークを提案する。
  論文  参考訳（メタデータ） (2024-08-08T08:47:20Z)
• Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages [63.366380571397]
  本稿では,プライバシのシャッフルモデルにおけるプライベートベクトル平均推定の問題について検討する。 我々は,$tildemathcalOleft(min(nvarepsilon2,d)right)$ message per users を用いて,最適なエラーを実現する新しいマルチメッセージプロトコルを提案する。
  論文  参考訳（メタデータ） (2024-04-16T00:56:36Z)
• Near-Optimal Non-Convex Stochastic Optimization under Generalized Smoothness [21.865728815935665]
  2つの最近の研究は、$O(epsilon-3)$サンプル複雑性を確立し、$O(epsilon)$-定常点を得る。 しかし、どちらも$mathrmploy(epsilon-1)$という大きなバッチサイズを必要とする。 本研究では,STORMアルゴリズムの単純な変種を再検討することにより,従来の2つの問題を同時に解決する。
  論文  参考訳（メタデータ） (2023-02-13T00:22:28Z)
• Concurrent Shuffle Differential Privacy Under Continual Observation [60.127179363119936]
  個人的連続和問題(対数問題)について検討する。 並列シャッフルモデルでは,標準シャッフルモデルに比べて誤差が大幅に改善できることが示されている。
  論文  参考訳（メタデータ） (2023-01-29T20:42:54Z)
• Localization in 1D non-parametric latent space models from pairwise affinities [6.982738885923206]
  対の親和性から一次元トーラスにおける潜伏位置を推定する問題を考察する。 高確率でsqrtlog(n)/n$の順序の最大誤差で全ての潜伏位置を確実にローカライズする推定手順を導入する。
  論文  参考訳（メタデータ） (2021-08-06T13:05:30Z)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。 損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
  論文  参考訳（メタデータ） (2021-03-02T06:53:44Z)
• Differentially private $k$-means clustering via exponential mechanism and max cover [6.736814259597673]
  我々は、$k$-meansクラスタリング問題に対して、新しい$(epsilon_p, delta_p)$-differentially privateアルゴリズムを導入する。
  論文  参考訳（メタデータ） (2020-09-02T17:52:54Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)

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

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