論文の概要: Robust Estimation of Discrete Distributions under Local Differential Privacy

• arxiv url: http://arxiv.org/abs/2202.06825v1
• Date: Mon, 14 Feb 2022 15:59:02 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-15 17:42:28.418363
• Title: Robust Estimation of Discrete Distributions under Local Differential Privacy
• Title（参考訳）: 局所微分プライバシー下における離散分布のロバスト推定
• Authors: Julien Chhor and Flore Sentenac
• Abstract要約: 局所的な差分プライバシー制約の下で,n$の汚染データバッチから離散分布を推定する問題を考察する。 2つの制約を組み合わせることで、$epsilonsqrtd/alpha2 k+sqrtd2/alpha2 kn$を$sqrtlog (1/epsilon)$ factorに設定できる。
• 参考スコア（独自算出の注目度）: 1.52292571922932
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Although robust learning and local differential privacy are both widely studied fields of research, combining the two settings is an almost unexplored topic. We consider the problem of estimating a discrete distribution in total variation from $n$ contaminated data batches under a local differential privacy constraint. A fraction $1-\epsilon$ of the batches contain $k$ i.i.d. samples drawn from a discrete distribution $p$ over $d$ elements. To protect the users' privacy, each of the samples is privatized using an $\alpha$-locally differentially private mechanism. The remaining $\epsilon n $ batches are an adversarial contamination. The minimax rate of estimation under contamination alone, with no privacy, is known to be $\epsilon/\sqrt{k}+\sqrt{d/kn}$, up to a $\sqrt{\log(1/\epsilon)}$ factor. Under the privacy constraint alone, the minimax rate of estimation is $\sqrt{d^2/\alpha^2 kn}$. We show that combining the two constraints leads to a minimax estimation rate of $\epsilon\sqrt{d/\alpha^2 k}+\sqrt{d^2/\alpha^2 kn}$ up to a $\sqrt{\log(1/\epsilon)}$ factor, larger than the sum of the two separate rates. We provide a polynomial-time algorithm achieving this bound, as well as a matching information theoretic lower bound.
• Abstract（参考訳）: 堅牢な学習と局所微分プライバシーはどちらも研究分野として広く研究されているが、この2つの設定を組み合わせることは、ほとんど検討されていない話題である。 我々は,局所的微分プライバシー制約下でのn$汚染されたデータバッチから,総変動の離散分布を推定する問題を考える。 バッチの1-\epsilon$は、離散分布の$p$ over $d$要素から引き出された$k$、すなわち$d.d.サンプルを含む。 ユーザのプライバシを保護するために、各サンプルは$\alpha$-locally differentially privateメカニズムを使用して民営化される。 残りの$\epsilon n $ batchesは逆汚染である。 汚染のみ下での最小推定率は、プライバシーのない場合、$\epsilon/\sqrt{k}+\sqrt{d/kn}$であり、$\sqrt{\log(1/\epsilon)}$ factorである。 プライバシーの制約だけでは、最小推定率は$\sqrt{d^2/\alpha^2 kn}$である。 2つの制約を組み合わせることで、$\epsilon\sqrt{d/\alpha^2 k}+\sqrt{d^2/\alpha^2 kn}$$$\sqrt{\log(1/\epsilon)}$因子の最小推定速度が2つの異なるレートの和よりも大きくなることを示す。 このバウンドを達成する多項式時間アルゴリズムと、マッチング情報理論下限を提供する。

関連論文リスト

• Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
  以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。 本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-11-01T17:59:53Z)
• Distribution-Aware Mean Estimation under User-level Local Differential Privacy [5.267844649650687]
  ユーザレベルのローカル差分プライバシに基づく平均推定の問題について考察する。 分布認識平均推定アルゴリズムに基づいて、平均推定タスクに対して、最悪の場合のリスクに対して、$M$依存上界を確立する。
  論文  参考訳（メタデータ） (2024-10-12T11:57:52Z)
• Private Mean Estimation with Person-Level Differential Privacy [6.621676316292624]
  複数のサンプルを持つ場合の個人レベルの個人別平均推定について検討した。 我々は、計算効率のよいアルゴリズムを、純粋DPで、計算効率の悪いアルゴリズムを、ほぼ一致する下界は、近似DPの最も寛容な場合を抑える。
  論文  参考訳（メタデータ） (2024-05-30T18:20:35Z)
• Contraction of Locally Differentially Private Mechanisms [8.547801169402923]
  我々は、$PK$と$QK$の出力分布が$epsilon$-LDPメカニズムの$K$のばらつきに基づいて、厳密な境界を導出する。 次に、これらの境界を利用して、バンツリーの不等式、ル・カム、アスード、および相互情報手法の局所的プライベートバージョンを確立する。
  論文  参考訳（メタデータ） (2022-10-24T16:38:12Z)
• 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)
• On Distributed Differential Privacy and Counting Distinct Elements [52.701425652208734]
  我々は、$n$ユーザのそれぞれが離散集合から要素を保持する設定について研究する。 目標は、すべてのユーザーに対して異なる要素の数を数えることだ。
  論文  参考訳（メタデータ） (2020-09-21T04:13:34Z)
• Learning discrete distributions: user vs item-level privacy [47.05234904407048]
  近年,フェデレート学習のような実践的なアプリケーションでは,単一ユーザのすべての項目に対するプライバシ保護が求められている。 ユーザレベルの差分プライバシーを持つシンボルを$k$で学習する際の基本的な問題について検討する。 ユーザ数が$tildemathcalO(k/(malpha2) + k/sqrtmepsilonalpha)$とスケールする仕組みを提案する。
  論文  参考訳（メタデータ） (2020-07-27T16:15:14Z)
• Private Query Release Assisted by Public Data [96.6174729958211]
  本研究では,公開データへのアクセスを補助する差分プライベートクエリリリースの問題について検討する。 我々は、$d/alpha$公開サンプルと$sqrtpd3/2/alpha2$プライベートサンプルのみを用いて、有限VC次元のクエリクラス$mathcalH$の問題を解くことができることを示した。
  論文  参考訳（メタデータ） (2020-04-23T02:46:37Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)

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

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