論文の概要: On Differentially Private U Statistics
- arxiv url: http://arxiv.org/abs/2407.04945v1
- Date: Sat, 6 Jul 2024 03:27:14 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-09 21:47:42.852000
- Title: On Differentially Private U Statistics
- Title(参考訳): 微分私的U統計について
- Authors: Kamalika Chaudhuri, Po-Ling Loh, Shourya Pandey, Purnamrita Sarkar,
- Abstract要約: 局所的なH'ajekプロジェクションを用いて、データの異なる部分集合を再重み付けする新しいしきい値に基づくアプローチを提案する。
これは、非退化U統計に対してほぼ最適なプライベート誤差をもたらし、退化U統計に対してほぼ最適であることを示す強い指標となる。
- 参考スコア(独自算出の注目度): 25.683071759227293
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the problem of privately estimating a parameter $\mathbb{E}[h(X_1,\dots,X_k)]$, where $X_1$, $X_2$, $\dots$, $X_k$ are i.i.d. data from some distribution and $h$ is a permutation-invariant function. Without privacy constraints, standard estimators are U-statistics, which commonly arise in a wide range of problems, including nonparametric signed rank tests, symmetry testing, uniformity testing, and subgraph counts in random networks, and can be shown to be minimum variance unbiased estimators under mild conditions. Despite the recent outpouring of interest in private mean estimation, privatizing U-statistics has received little attention. While existing private mean estimation algorithms can be applied to obtain confidence intervals, we show that they can lead to suboptimal private error, e.g., constant-factor inflation in the leading term, or even $\Theta(1/n)$ rather than $O(1/n^2)$ in degenerate settings. To remedy this, we propose a new thresholding-based approach using \emph{local H\'ajek projections} to reweight different subsets of the data. This leads to nearly optimal private error for non-degenerate U-statistics and a strong indication of near-optimality for degenerate U-statistics.
- Abstract(参考訳): パラメータ $\mathbb{E}[h(X_1,\dots,X_k)]$, ここで、$X_1$, $X_2$, $\dots$, $X_k$は、ある分布のデータであり、$h$は置換不変関数である。
プライバシ制約がなければ、標準推定器はU統計器であり、非パラメトリック符号付きランクテスト、対称性テスト、均一性テスト、ランダムネットワークにおけるサブグラフ数などを含む幅広い問題で一般的に発生し、緩やかな条件下では最小分散無バイアス推定器であることが示される。
近年、民間平均推定への関心が高まっているにもかかわらず、民営化のU統計学はほとんど注目されていない。
既存のプライベート平均推定アルゴリズムは信頼区間を得るために適用できるが、このアルゴリズムは、先行項における最適下限のプライベートエラー、例えば、定数係数のインフレーション、あるいは退化条件において$O(1/n^2)$よりも$\Theta(1/n)$にまで導くことができる。
これを改善するために、データの異なる部分集合を再重み付けするために \emph{local H\'ajek projections} を用いた新しいしきい値に基づくアプローチを提案する。
これは、非退化U統計に対してほぼ最適なプライベート誤差をもたらし、退化U統計に対してほぼ最適であることを示す強い指標となる。
関連論文リスト
- Smoothed Normalization for Efficient Distributed Private Optimization [54.197255548244705]
フェデレートされた学習は、参加者のプライバシを備えた機械学習モデルを可能にする。
トレーニングやフィードバックのない問題に対して、差分にプライベートな分散手法は存在しない。
証明可能な収束保証付き分散アルゴリズム$alpha$-$sf NormEC$を導入する。
論文 参考訳(メタデータ) (2025-02-19T07:10:32Z) - Optimized Tradeoffs for Private Prediction with Majority Ensembling [59.99331405291337]
本稿では,データ依存型ランダム化応答行列(DaRRM)アルゴリズムを提案する。
DaRRMはデータ依存ノイズ関数$gamma$でパラメータ化され、全てのプライベートアルゴリズムのクラスに対して効率的なユーティリティ最適化を可能にする。
本稿では,DARRMが共通ベースラインよりも2倍のプライバシゲインを,固定ユーティリティで確実に享受していることを示す。
論文 参考訳(メタデータ) (2024-11-27T00:48:48Z) - Insufficient Statistics Perturbation: Stable Estimators for Private Least Squares [38.478776450327125]
通常の最小二乗に対するサンプルと時間効率の微分プライベートアルゴリズムを提案する。
私たちのほぼ最適精度は、条件番号または指数時間を持つデータセットに対して保持します。
論文 参考訳(メタデータ) (2024-04-23T18:00:38Z) - Better and Simpler Lower Bounds for Differentially Private Statistical
Estimation [7.693388437377614]
任意の$alpha le O(1)$に対して、ガウスの共分散をスペクトル誤差まで推定するには$tildeOmegaleft(fracd3/2alpha varepsilon + fracdalpha2right)$サンプルが必要である。
次に、有界な$k$thモーメントで重み付き分布の平均を推定するには$tildeOmegaleft(fracdalphak/(k-1) varepsilon +
論文 参考訳(メタデータ) (2023-10-10T04:02:43Z) - General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean
Estimation [58.03500081540042]
プライベート平均推定に対する古典的なアプローチは、真の平均を計算し、バイアスのないがおそらく相関のあるガウスノイズを加えることである。
すべての入力データセットに対して、集中的な差分プライバシーを満たす非バイアス平均推定器が、少なくとも多くのエラーをもたらすことを示す。
論文 参考訳(メタデータ) (2023-01-31T18:47:42Z) - DP-PCA: Statistically Optimal and Differentially Private PCA [44.22319983246645]
DP-PCAは、両方の制限を克服するシングルパスアルゴリズムである。
準ガウスデータに対しては、$n=tilde O(d)$ であっても、ほぼ最適な統計的誤差率を提供する。
論文 参考訳(メタデータ) (2022-05-27T02:02:17Z) - Optimal Algorithms for Mean Estimation under Local Differential Privacy [55.32262879188817]
そこで本研究では,PrivUnitが局所的プライベートな乱数化器群間の最適分散を実現することを示す。
また,ガウス分布に基づくPrivUnitの新たな変種も開発しており,数学的解析に適しており,同じ最適性保証を享受できる。
論文 参考訳(メタデータ) (2022-05-05T06:43:46Z) - Nonparametric extensions of randomized response for private confidence sets [51.75485869914048]
本研究は,局所的差分プライバシー(LDP)の制約の下で,集団平均の非パラメトリック,非漸近的統計的推測を行う手法を導出する。
民営化データへのアクセスのみを与えられた場合、$mustar$に対して信頼区間(CI)と時間一様信頼シーケンス(CS)を提示する。
論文 参考訳(メタデータ) (2022-02-17T16:04:49Z) - Covariance-Aware Private Mean Estimation Without Private Covariance Estimation [10.036088581191592]
2つのサンプル係数差分プライベート平均推定器を$d$-dimensional(sub)Gaussian分布に対して提案する。
我々の推定子は、$| tildemu - mu |_Sigma leq alpha$, where $| cdot |_Sigma$がマハラノビス距離であるような$tildemu$を出力します。
論文 参考訳(メタデータ) (2021-06-24T21:40:07Z) - Learning with User-Level Privacy [61.62978104304273]
ユーザレベルの差分プライバシー制約下での学習課題を,アルゴリズムを用いて解析する。
個々のサンプルのプライバシーのみを保証するのではなく、ユーザレベルのdpはユーザの貢献全体を保護します。
プライバシコストが$tau$に比例した$K$適応的に選択されたクエリのシーケンスにプライベートに答えるアルゴリズムを導き出し、私たちが検討する学習タスクを解決するためにそれを適用します。
論文 参考訳(メタデータ) (2021-02-23T18:25:13Z) - Dimension-agnostic inference using cross U-statistics [33.17951971728784]
本稿では,サンプル分割と自己正規化とともに,既存のテスト統計の変分表現を用いた手法を提案する。
結果の統計学は、縮退したU統計を慎重に修正し、対角ブロックを落とし、対角ブロックを外したままにすると見なすことができる。
論文 参考訳(メタデータ) (2020-11-10T12:21:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。