論文の概要: Lightweight Protocols for Distributed Private Quantile Estimation

• arxiv url: http://arxiv.org/abs/2502.02990v1
• Date: Wed, 05 Feb 2025 08:39:02 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-06 14:26:18.569758
• Title: Lightweight Protocols for Distributed Private Quantile Estimation
• Title（参考訳）: 分散型プライベート量子推定のための軽量プロトコル
• Authors: Anders Aamand, Fabrizio Boninsegna, Abigail Gentle, Jacob Imola, Rasmus Pagh,
• Abstract要約: 我々は、各ユーザが1つのデータポイントを1つのドメインに[B]$で保持するときに、1つの量子を推定する2つの強調適応アルゴリズムを考察する。 適応的な設定では、$varepsilon$-LDPアルゴリズムを用い、$O(fraclog Bvarepsilon2alpha2)$ユーザしか必要としないエラー$alpha$内の量子化を推定できる。
• 参考スコア（独自算出の注目度）: 12.586899971090277
• License:
• Abstract: Distributed data analysis is a large and growing field driven by a massive proliferation of user devices, and by privacy concerns surrounding the centralised storage of data. We consider two \emph{adaptive} algorithms for estimating one quantile (e.g.~the median) when each user holds a single data point lying in a domain $[B]$ that can be queried once through a private mechanism; one under local differential privacy (LDP) and another for shuffle differential privacy (shuffle-DP). In the adaptive setting we present an $\varepsilon$-LDP algorithm which can estimate any quantile within error $\alpha$ only requiring $O(\frac{\log B}{\varepsilon^2\alpha^2})$ users, and an $(\varepsilon,\delta)$-shuffle DP algorithm requiring only $\widetilde{O}((\frac{1}{\varepsilon^2}+\frac{1}{\alpha^2})\log B)$ users. Prior (nonadaptive) algorithms require more users by several logarithmic factors in $B$. We further provide a matching lower bound for adaptive protocols, showing that our LDP algorithm is optimal in the low-$\varepsilon$ regime. Additionally, we establish lower bounds against non-adaptive protocols which paired with our understanding of the adaptive case, proves a fundamental separation between these models.
• Abstract（参考訳）: 分散データ分析は、ユーザデバイスの大規模な増加と、データの集中ストレージを取り巻くプライバシー上の懸念によって、大きく成長する分野である。 我々は、各ユーザが1つのドメインに1つのデータポイントを持つとき、1つの量子化(例えば、中央値)を推定するための2つの \emph{adaptive}アルゴリズムをプライベートなメカニズムを通じて一度クエリできる$[B]$、ローカルな差分プライバシー(LDP)とシャッフルな差分プライバシー(シャッフルDP)について検討する。 適応的な設定では、$\varepsilon$-LDPアルゴリズムを用い、エラー内での量子化を推定できる$\alpha$は$O(\frac{\log B}{\varepsilon^2\alpha^2})$ユーザ、$(\varepsilon,\delta)$-shuffle DPアルゴリズムは$\widetilde{O}((\frac{1}{\varepsilon^2}+\frac{1}{\alpha^2})\log B)$ユーザのみを要求する$(\varepsilon,\delta)$-shuffle DPアルゴリズムを提供する。 事前(非適応)アルゴリズムでは、いくつかの対数係数を$B$で要求する。 さらに、適応プロトコルの一致した下位境界を提供し、我々の LDP アルゴリズムが低値の\varepsilon$ regime において最適であることを示す。 さらに、適応的ケースの理解と組み合わせた非適応的プロトコルに対する下位境界を確立し、これらのモデル間の根本的な分離を証明した。

関連論文リスト

• Private Mean Estimation with Person-Level Differential Privacy [6.621676316292624]
  複数のサンプルを持つ場合の個人レベルの個人別平均推定について検討した。 我々は、計算効率のよいアルゴリズムを、純粋DPで、計算効率の悪いアルゴリズムを、ほぼ一致する下界は、近似DPの最も寛容な場合を抑える。
  論文  参考訳（メタデータ） (2024-05-30T18:20:35Z)
• Differentially Private Clustering in Data Streams [65.78882209673885]
  オフラインのDPコアセットやクラスタリングアルゴリズムをブラックボックスとしてのみ必要とする,差分プライベートなストリーミングクラスタリングフレームワークを提案する。 我々のフレームワークはまた、連続的なリリース設定の下で微分プライベートであり、すなわち、全てのタイムスタンプにおけるアルゴリズムの出力の和は常に微分プライベートである。
  論文  参考訳（メタデータ） (2023-07-14T16:11:22Z)
• Discrete Distribution Estimation under User-level Local Differential Privacy [37.65849910114053]
  ユーザレベルの局所差分プライバシー(LDP)に基づく離散分布推定について検討する。 ユーザレベルの$varepsilon$-LDPでは、各ユーザは$mge1$サンプルを持ち、すべての$m$サンプルのプライバシを同時に保存する必要がある。
  論文  参考訳（メタデータ） (2022-11-07T18:29:32Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Normalized/Clipped SGD with Perturbation for Differentially Private Non-Convex Optimization [94.06564567766475]
  DP-SGDとDP-NSGDは、センシティブなトレーニングデータを記憶する大規模モデルのリスクを軽減する。 DP-NSGD は DP-SGD よりも比較的チューニングが比較的容易であるのに対して,これらの2つのアルゴリズムは同様の精度を実現する。
  論文  参考訳（メタデータ） (2022-06-27T03:45:02Z)
• Scalable Differentially Private Clustering via Hierarchically Separated Trees [82.69664595378869]
  我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。 最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
  論文  参考訳（メタデータ） (2022-06-17T09:24:41Z)
• DP-PCA: Statistically Optimal and Differentially Private PCA [44.22319983246645]
  DP-PCAは、両方の制限を克服するシングルパスアルゴリズムである。 準ガウスデータに対しては、$n=tilde O(d)$ であっても、ほぼ最適な統計的誤差率を提供する。
  論文  参考訳（メタデータ） (2022-05-27T02:02:17Z)
• Frequency Estimation Under Multiparty Differential Privacy: One-shot and Streaming [10.952006057356714]
  プライバシと通信の制約下での周波数推定の基本的問題について検討し,そのデータを$k$のパーティ間で分散する。 私たちは、ローカルディファレンシャルプライバシ(LDP)と(分散)ディファレンシャルプライバシよりも一般的なマルチパーティディファレンシャルプライバシ(MDP)のモデルを採用しています。 我々のプロトコルは、より厳密な2つの制約によって許容可能な最適性(対数因子まで)を達成する。
  論文  参考訳（メタデータ） (2021-04-05T08:15:20Z)
• Learning with User-Level Privacy [61.62978104304273]
  ユーザレベルの差分プライバシー制約下での学習課題を,アルゴリズムを用いて解析する。 個々のサンプルのプライバシーのみを保証するのではなく、ユーザレベルのdpはユーザの貢献全体を保護します。 プライバシコストが$tau$に比例した$K$適応的に選択されたクエリのシーケンスにプライベートに答えるアルゴリズムを導き出し、私たちが検討する学習タスクを解決するためにそれを適用します。
  論文  参考訳（メタデータ） (2021-02-23T18:25:13Z)
• Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Bounds [72.63031036770425]
  有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。 標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
  論文  参考訳（メタデータ） (2020-06-24T06:01:24Z)

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

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