論文の概要: Learning discrete distributions: user vs item-level privacy
- arxiv url: http://arxiv.org/abs/2007.13660v3
- Date: Mon, 11 Jan 2021 22:15:07 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-06 08:28:31.342935
- Title: Learning discrete distributions: user vs item-level privacy
- Title（参考訳）: 個別分布の学習:ユーザー対アイテムレベルのプライバシー
- Authors: Yuhan Liu, Ananda Theertha Suresh, Felix Yu, Sanjiv Kumar, Michael
Riley
- Abstract要約: 近年,フェデレート学習のような実践的なアプリケーションでは,単一ユーザのすべての項目に対するプライバシ保護が求められている。
ユーザレベルの差分プライバシーを持つシンボルを$k$で学習する際の基本的な問題について検討する。
ユーザ数が$tildemathcalO(k/(malpha2) + k/sqrtmepsilonalpha)$とスケールする仕組みを提案する。
- 参考スコア（独自算出の注目度）: 47.05234904407048
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Much of the literature on differential privacy focuses on item-level privacy,
where loosely speaking, the goal is to provide privacy per item or training
example. However, recently many practical applications such as federated
learning require preserving privacy for all items of a single user, which is
much harder to achieve. Therefore understanding the theoretical limit of
user-level privacy becomes crucial.
We study the fundamental problem of learning discrete distributions over $k$
symbols with user-level differential privacy. If each user has $m$ samples, we
show that straightforward applications of Laplace or Gaussian mechanisms
require the number of users to be $\mathcal{O}(k/(m\alpha^2) +
k/\epsilon\alpha)$ to achieve an $\ell_1$ distance of $\alpha$ between the true
and estimated distributions, with the privacy-induced penalty
$k/\epsilon\alpha$ independent of the number of samples per user $m$. Moreover,
we show that any mechanism that only operates on the final aggregate counts
should require a user complexity of the same order. We then propose a mechanism
such that the number of users scales as $\tilde{\mathcal{O}}(k/(m\alpha^2) +
k/\sqrt{m}\epsilon\alpha)$ and hence the privacy penalty is
$\tilde{\Theta}(\sqrt{m})$ times smaller compared to the standard mechanisms in
certain settings of interest. We further show that the proposed mechanism is
nearly-optimal under certain regimes.
We also propose general techniques for obtaining lower bounds on restricted
differentially private estimators and a lower bound on the total variation
between binomial distributions, both of which might be of independent interest.
- Abstract（参考訳）: 差分プライバシーに関する文献の多くは、アイテムレベルのプライバシーに焦点を当てている。
しかし近年,フェデレート学習のような実践的なアプリケーションでは,単一ユーザのすべての項目に対するプライバシ保護が求められている。
したがって、ユーザレベルのプライバシーの理論的限界を理解することが重要である。
ユーザレベルの差分プライバシーを持つシンボルを$k$で学習する基本的な問題について検討する。
それぞれのユーザが$m$のサンプルを持っている場合、ラプラスやガウス機構の直接的な適用では、$m$のサンプル数とは独立に、$\mathcal{o}(k/(m\alpha^2) + k/\epsilon\alpha)$の$\ell_1$の距離は$\alpha$であり、プライバシによって引き起こされるペナルティ$k/\epsilon\alpha$である。
さらに,最終集計数のみで動作するメカニズムは,同じ順序でユーザを複雑にする必要があることを示す。
次に,ユーザ数が$\tilde{\mathcal{o}}(k/(m\alpha^2) + k/\sqrt{m}\epsilon\alpha)$となるようにスケールするメカニズムを提案する。
さらに、提案手法は特定の体制下でほぼ最適であることを示す。
また, 制限付き微分的非自明な推定子に対する下限を求める一般的な手法と, 両者が独立に利害関係を持つような二項分布間の全変動について下限を求める手法を提案する。
関連論文リスト
- User-Level Differential Privacy With Few Examples Per User [73.81862394073308]
サンプルスカース方式では,各ユーザが少数のサンプルしか持たないため,以下の結果が得られる。
近似DPについては,任意の項目レベルDPアルゴリズムをユーザレベルDPアルゴリズムに汎用変換する。
ユーザレベル設定に指数的機構(McSherry, Talwar FOCS 2007)を適用するための簡単な手法を提案する。
論文 参考訳（メタデータ） (2023-09-21T21:51:55Z) - Differentially-Private Bayes Consistency [70.92545332158217]
差分プライバシー(DP)を満たすベイズ一貫した学習ルールを構築する。
ほぼ最適なサンプル複雑性を持つ半教師付き環境で,任意のVCクラスをプライベートに学習できることを実証する。
論文 参考訳（メタデータ） (2022-12-08T11:57:30Z) - Discrete Distribution Estimation under User-level Local Differential
Privacy [37.65849910114053]
ユーザレベルの局所差分プライバシー(LDP)に基づく離散分布推定について検討する。
ユーザレベルの$varepsilon$-LDPでは、各ユーザは$mge1$サンプルを持ち、すべての$m$サンプルのプライバシを同時に保存する必要がある。
論文 参考訳（メタデータ） (2022-11-07T18:29:32Z) - Robust Estimation of Discrete Distributions under Local Differential
Privacy [1.52292571922932]
局所的な差分プライバシー制約の下で,n$の汚染データバッチから離散分布を推定する問題を考察する。
2つの制約を組み合わせることで、$epsilonsqrtd/alpha2 k+sqrtd2/alpha2 kn$を$sqrtlog (1/epsilon)$ factorに設定できる。
論文 参考訳（メタデータ） (2022-02-14T15:59:02Z) - Tight and Robust Private Mean Estimation with Few Users [16.22135057266913]
ユーザレベルの差分プライバシーに基づく高次元平均推定について検討する。
可能な限り少数のユーザを使って、$(eps,delta)$-differentially privateメカニズムを設計します。
論文 参考訳（メタデータ） (2021-10-22T16:02:21Z) - User-Level Private Learning via Correlated Sampling [49.453751858361265]
我々は、各ユーザが$m$のサンプルを持ち、プライバシ保護が各ユーザのデータレベルで実施される設定について検討する。
この設定では、より少ない数のユーザーで学習できることが示されます。
論文 参考訳（メタデータ） (2021-10-21T15:33:53Z) - Learning with User-Level Privacy [61.62978104304273]
ユーザレベルの差分プライバシー制約下での学習課題を,アルゴリズムを用いて解析する。
個々のサンプルのプライバシーのみを保証するのではなく、ユーザレベルのdpはユーザの貢献全体を保護します。
プライバシコストが$tau$に比例した$K$適応的に選択されたクエリのシーケンスにプライベートに答えるアルゴリズムを導き出し、私たちが検討する学習タスクを解決するためにそれを適用します。
論文 参考訳（メタデータ） (2021-02-23T18:25:13Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。