論文の概要: Private Mean Estimation with Person-Level Differential Privacy
- arxiv url: http://arxiv.org/abs/2405.20405v1
- Date: Thu, 30 May 2024 18:20:35 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-03 18:34:31.576338
- Title: Private Mean Estimation with Person-Level Differential Privacy
- Title(参考訳): 個人レベル差分プライバシを用いた個人平均推定
- Authors: Sushant Agarwal, Gautam Kamath, Mahbod Majid, Argyris Mouzakis, Rose Silver, Jonathan Ullman,
- Abstract要約: 個人が複数のサンプルを持っている場合の個人平均推定について検討する。
我々のアルゴリズムは、よく知られたノイズクラッピング平均法に基づいているが、我々の設定に対する解析は、独立なベクトル値の有界モード変数の和のテールに新しい境界を必要とする。
- 参考スコア(独自算出の注目度): 6.621676316292624
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study differentially private (DP) mean estimation in the case where each person holds multiple samples. Commonly referred to as the "user-level" setting, DP here requires the usual notion of distributional stability when all of a person's datapoints can be modified. Informally, if $n$ people each have $m$ samples from an unknown $d$-dimensional distribution with bounded $k$-th moments, we show that \[n = \tilde \Theta\left(\frac{d}{\alpha^2 m} + \frac{d }{ \alpha m^{1/2} \varepsilon} + \frac{d}{\alpha^{k/(k-1)} m \varepsilon} + \frac{d}{\varepsilon}\right)\] people are necessary and sufficient to estimate the mean up to distance $\alpha$ in $\ell_2$-norm under $\varepsilon$-differential privacy (and its common relaxations). In the multivariate setting, we give computationally efficient algorithms under approximate DP (with slightly degraded sample complexity) and computationally inefficient algorithms under pure DP, and our nearly matching lower bounds hold for the most permissive case of approximate DP. Our computationally efficient estimators are based on the well known noisy-clipped-mean approach, but the analysis for our setting requires new bounds on the tails of sums of independent, vector-valued, bounded-moments random variables, and a new argument for bounding the bias introduced by clipping.
- Abstract(参考訳): 個人が複数のサンプルを持つ場合のDP平均推定について検討した。
一般に "user-level" という設定で呼ばれる DP では、ある人のすべてのデータポイントを修正できる場合、分散安定性という通常の概念が要求される。
インフォーマルに、$n$の人々が、有界な$k$-次モーメントを持つ未知の$d$-次元分布から$m$のサンプルを持つなら、 \[n = \tilde \Theta\left(\frac{d}{\alpha^2 m} + \frac{d }{ \alpha m^{1/2} \varepsilon} + \frac{d}{\alpha^{k/(k-1)} m \varepsilon} + \frac{d}{\varepsilon}\right)\] 国民は、$\ell_2$-norm で$\ell_2$-norm までの距離を推定するのに十分である。
多変量設定では、近似DPの下で計算効率の良いアルゴリズム(わずかに劣化したサンプル複雑性を持つ)と純粋DP下で計算効率の悪いアルゴリズムを与える。
我々の計算効率の高い推定器は、よく知られたノイズクラッピング平均法に基づいているが、我々の設定では、独立、ベクトル値、有界モードのランダム変数の和のテールの新たな境界と、クリップによって導入されたバイアスを束縛するための新しい議論が必要である。
関連論文リスト
- Robust Distribution Learning with Local and Global Adversarial Corruptions [17.22168727622332]
誤差を$sqrtvarepsilon k + rho + tildeO(dsqrtkn-1/(k lor2)$で有界な共分散を持つ場合、効率的な有限サンプルアルゴリズムを開発する。
我々の効率的な手順は、理想的だが難解な2-ワッサーシュタイン射影推定器の新たなトレースノルム近似に依存する。
論文 参考訳(メタデータ) (2024-06-10T17:48:36Z) - 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) - Near Sample-Optimal Reduction-based Policy Learning for Average Reward
MDP [58.13930707612128]
この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。
我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
論文 参考訳(メタデータ) (2022-12-01T15:57:58Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳(メタデータ) (2022-08-11T04:12:50Z) - DP-PCA: Statistically Optimal and Differentially Private PCA [44.22319983246645]
DP-PCAは、両方の制限を克服するシングルパスアルゴリズムである。
準ガウスデータに対しては、$n=tilde O(d)$ であっても、ほぼ最適な統計的誤差率を提供する。
論文 参考訳(メタデータ) (2022-05-27T02:02:17Z) - Differentially Private Exploration in Reinforcement Learning with Linear
Representation [102.17246636801649]
まず,線形混合MDP(Ayob et al., 2020)の設定(モデルベース設定)について検討し,共同・局所微分プライベート(DP)探索を統一的に分析するための枠組みを提供する。
我々はさらに、線形MDP(Jin et al., 2020)におけるプライバシー保護探索(つまりモデルフリー設定)について研究し、$widetildeO(sqrtK/epsilon)$ regret bound for $(epsilon,delta)を提供する。
論文 参考訳(メタデータ) (2021-12-02T19:59:50Z) - Locally differentially private estimation of nonlinear functionals of
discrete distributions [9.028773906859541]
離散分布の非線形関数を局所的差分プライバシーの文脈で推定する問題について検討する。
alpha$-locally differentially private (LDP) サンプルのみが公開されているが、'local' という用語は、各$z_i$が1つの個々の$x_i$を使って生成されることを意味する。
パワー和関数 $F_gamma = sum_k=1K p_kgamma$, $gamma > 0$ を $K, n の関数として推定する二次リスクの挙動を記述する。
論文 参考訳(メタデータ) (2021-07-08T16:11:10Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳(メタデータ) (2020-07-16T06:44:44Z) - Private Stochastic Non-Convex Optimization: Adaptive Algorithms and
Tighter Generalization Bounds [72.63031036770425]
有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。
標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
論文 参考訳(メタデータ) (2020-06-24T06:01:24Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳(メタデータ) (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。