論文の概要: User-Level Differential Privacy With Few Examples Per User
- arxiv url: http://arxiv.org/abs/2309.12500v1
- Date: Thu, 21 Sep 2023 21:51:55 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-25 16:43:13.055843
- Title: User-Level Differential Privacy With Few Examples Per User
- Title（参考訳）: ユーザレベルのディファレンシャルプライバシ : ユーザ毎の例はほとんどない
- Authors: Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Raghu Meka,
Chiyuan Zhang
- Abstract要約: サンプルスカース方式では,各ユーザが少数のサンプルしか持たないため,以下の結果が得られる。
近似DPについては,任意の項目レベルDPアルゴリズムをユーザレベルDPアルゴリズムに汎用変換する。
ユーザレベル設定に指数的機構(McSherry, Talwar FOCS 2007)を適用するための簡単な手法を提案する。
- 参考スコア（独自算出の注目度）: 73.81862394073308
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Previous work on user-level differential privacy (DP) [Ghazi et al. NeurIPS
2021, Bun et al. STOC 2023] obtained generic algorithms that work for various
learning tasks. However, their focus was on the example-rich regime, where the
users have so many examples that each user could themselves solve the problem.
In this work we consider the example-scarce regime, where each user has only a
few examples, and obtain the following results:
1. For approximate-DP, we give a generic transformation of any item-level DP
algorithm to a user-level DP algorithm. Roughly speaking, the latter gives a
(multiplicative) savings of $O_{\varepsilon,\delta}(\sqrt{m})$ in terms of the
number of users required for achieving the same utility, where $m$ is the
number of examples per user. This algorithm, while recovering most known bounds
for specific problems, also gives new bounds, e.g., for PAC learning.
2. For pure-DP, we present a simple technique for adapting the exponential
mechanism [McSherry, Talwar FOCS 2007] to the user-level setting. This gives
new bounds for a variety of tasks, such as private PAC learning, hypothesis
selection, and distribution learning. For some of these problems, we show that
our bounds are near-optimal.
- Abstract（参考訳）: ユーザレベルの差分プライバシー (DP) [Ghazi et al. NeurIPS 2021, Bun et al. STOC 2023] に関するこれまでの研究は、様々な学習タスクに使える汎用アルゴリズムを得た。
しかし、彼らの焦点は、ユーザ自身が問題を解決できるような多くの例がある、サンプル豊富な体制にある。
本研究では,各ユーザのサンプル数が少ない実例スカース方式を考察し,以下の結果を得た。 1. 近似DPでは,任意の項目レベルのDPアルゴリズムをユーザレベルのDPアルゴリズムに総称変換する。
大まかに言えば、後者は、同じユーティリティを達成するのに必要なユーザ数の観点から、$O_{\varepsilon,\delta}(\sqrt{m})$の(多重的な)貯蓄を与える。
このアルゴリズムは、特定の問題に対して最もよく知られた境界を復元する一方で、PAC学習のための新しい境界を与える。
2. 純粋DPでは, 指数的機構(McSherry, Talwar FOCS 2007)をユーザレベル設定に適用するための簡単な手法を提案する。
これにより、プライベートPAC学習、仮説選択、分散学習など、さまざまなタスクに新たな境界が与えられる。
これらの問題のいくつかについて、我々の境界がほぼ最適であることを示す。
関連論文リスト
- On Computing Pairwise Statistics with Local Differential Privacy [55.81991984375959]
例えば$binomn2-1 sum_i ne j f(x_i, x_j)$, $x_i$ は$i$thユーザへの入力を表し、ローカルモデルでは差分プライバシ(DP)である。
この定式化は、Kendallの$tau$ coefficient、Area Under Curve、Giniの平均差、Giniのエントロピーなどの重要なメトリクスをキャプチャする。
論文 参考訳（メタデータ） (2024-06-24T04:06:09Z) - Individualized Privacy Accounting via Subsampling with Applications in Combinatorial Optimization [55.81991984375959]
本研究では、以下の簡単な観察を通して、個別化されたプライバシ会計を解析する新しい手法を提案する。
我々は、分解可能な部分モジュラーおよびセットアルゴリズム被覆を含む、プライベート最適化問題に対するいくつかの改良されたアルゴリズムを得る。
論文 参考訳（メタデータ） (2024-05-28T19:02:30Z) - Privately Estimating a Gaussian: Efficient, Robust and Optimal [6.901744415870126]
純微分プライバシー(DP)モデルと近似微分プライバシー(DP)モデルの両方において、ガウス分布をプライベートに推定する効率的なアルゴリズムを提供する。
純粋なDP設定では、未知の$d$次元ガウス分布を任意の全変分誤差まで推定する効率的なアルゴリズムを与える。
平均推定の特別な場合、我々のアルゴリズムは$widetilde O(d1.5)$の最適なサンプル複雑性を達成し、以前の作業から$widetilde O(d1.5)$のバウンドを改善する。
論文 参考訳（メタデータ） (2022-12-15T18:27:39Z) - Discrete Distribution Estimation under User-level Local Differential
Privacy [37.65849910114053]
ユーザレベルの局所差分プライバシー(LDP)に基づく離散分布推定について検討する。
ユーザレベルの$varepsilon$-LDPでは、各ユーザは$mge1$サンプルを持ち、すべての$m$サンプルのプライバシを同時に保存する必要がある。
論文 参考訳（メタデータ） (2022-11-07T18:29:32Z) - Multi-User Reinforcement Learning with Low Rank Rewards [41.15103860230677]
我々の主な貢献は、N$ユーザ固有のMDPと協調して報酬を探索するアルゴリズムである。
N$が大きめでランクが一定であれば、MDPあたりのサンプルの複雑さは状態空間のサイズに対数的に依存する。
論文 参考訳（メタデータ） (2022-10-11T11:36: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) - Private Stochastic Non-Convex Optimization: Adaptive Algorithms and
Tighter Generalization Bounds [72.63031036770425]
有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。
標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
論文 参考訳（メタデータ） (2020-06-24T06:01:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。