論文の概要: The Normal Distributions Indistinguishability Spectrum and its
Application to Privacy-Preserving Machine Learning
- arxiv url: http://arxiv.org/abs/2309.01243v2
- Date: Tue, 5 Mar 2024 21:23:15 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-07 18:01:02.579980
- Title: The Normal Distributions Indistinguishability Spectrum and its
Application to Privacy-Preserving Machine Learning
- Title(参考訳): 正規分布の識別不能スペクトルとプライバシ保存機械学習への応用
- Authors: Yun Lu, Malik Magdon-Ismail, Yu Wei, Vassilis Zikas
- Abstract要約: ビッグデータ分析では、ランダムなスケッチ/アグリゲーションアルゴリズムを使用して、高次元データの処理を可能にすることが多い。
本研究では,非識別性スペクトル定理の正規分布を理論的に証明する。
我々の新しいDPメカニズムは、基礎となるアルゴリズムのランダム性を生かして、優れたプライバシー/ユーティリティトレードオフを実現する。
- 参考スコア(独自算出の注目度): 8.316835880556104
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: To achieve differential privacy (DP) one typically randomizes the output of
the underlying query. In big data analytics, one often uses randomized
sketching/aggregation algorithms to make processing high-dimensional data
tractable. Intuitively, such machine learning (ML) algorithms should provide
some inherent privacy, yet most if not all existing DP mechanisms do not
leverage this inherent randomness, resulting in potentially redundant noising.
The motivating question of our work is:
(How) can we improve the utility of DP mechanisms for randomized ML queries,
by leveraging the randomness of the query itself?
Towards a (positive) answer, we prove the Normal Distributions
Indistinguishability Spectrum Theorem (in short, NDIS Theorem), a theoretical
result with far-reaching practical implications. In a nutshell, NDIS is a
closed-form analytic computation for the
$(\epsilon,\delta)$-indistinguishability-spectrum (in short,
$(\epsilon,\delta)$-IS) of two arbitrary (multi-dimensional) normal
distributions $X$ and $Y$, i.e., the optimal $\delta$ (for any given
$\epsilon$) such that $X$ and $Y$ are ($\epsilon,\delta$)-close according to
the DP distance. The NDIS theorem (1) yields efficient estimators for the above
IS, and (2) allows us to analyze DP-mechanisms with normally-distributed
outputs, as well as more general mechanisms by leveraging their behavior on
large inputs.
We apply the NDIS theorem to derive DP mechanisms for queries with
normally-distributed outputs -- i.e., Gaussian Random Projections (RP) -- and
for more general queries -- i.e., Ordinary Least Squares (OLS). Both RP and OLS
are highly relevant in data analytics. Our new DP mechanisms achieve superior
privacy/utility trade-offs by leveraging the randomness of the underlying
algorithms, and identifies, for the first time, the range of
$(\epsilon,\delta)$ for which no additional noising is needed.
- Abstract(参考訳): 差分プライバシー(DP)を達成するには、一般に基礎となるクエリの出力をランダムにする。
ビッグデータ分析では、ランダム化されたスケッチ/アグリゲーションアルゴリズムを使用して、高次元データの処理を可能にすることが多い。
直感的には、そのような機械学習(ML)アルゴリズムは固有のプライバシーを提供するべきであるが、ほとんどの場合、既存のDPメカニズムがこの固有のランダム性を利用していないため、潜在的に冗長なノイズが発生する。
クエリ自体のランダム性を活用することで、(どのように)ランダム化されたmlクエリに対するdpメカニズムの有用性を向上させることができるのか?
正の解を求めるために,NDIS理論に基づく正規分布独立性スペクトル定理(NDIS理論)を証明した。
簡単に言えば、NDIS は任意の(多重次元)正規分布の $(\epsilon,\delta)$-indistinguishability-spectrum (略して $(\epsilon,\delta)$-IS) に対する閉形式解析計算である。
ndis定理(1)は、上記の場合の効率的な推定子を与え、(2)正規分布アウトプットを用いたdp-メカニズムの解析を可能にするとともに、より一般的な機構を大規模入力の振る舞いに活用できる。
NDIS定理を適用し、正規分布の出力を持つクエリー、すなわちガウスランダム射影(RP)、およびより一般的なクエリー、すなわち通常最小正方形(OLS)に対するDP機構を導出する。
rpとolsはどちらもデータ分析に非常に関係がある。
私たちの新しいdpメカニズムは、基礎となるアルゴリズムのランダム性を利用して、優れたプライバシ/有効性トレードオフを実現し、追加のノージングを必要としない$(\epsilon,\delta)$の範囲を初めて特定します。
関連論文リスト
- Efficiently Computing Similarities to Private Datasets [19.99000806126529]
微分プライベートモデルトレーニングの多くの方法は、クエリポイント(公開データや合成データなど)とプライベートデータとの類似性を計算することに依存している。
類似関数$f$と大きな高次元プライベートデータセット$XサブセットmathbbRd$を与えられた場合、任意のクエリ$y$に対して、X f(x,y)$のsum_xを近似した差分プライベート(DP)データ構造を出力する。
論文 参考訳(メタデータ) (2024-03-13T19:19:19Z) - Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。
我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
論文 参考訳(メタデータ) (2024-03-08T18:50:19Z) - Closed-form Filtering for Non-linear Systems [83.91296397912218]
我々は密度近似と計算効率の面でいくつかの利点を提供するガウスPSDモデルに基づく新しいフィルタのクラスを提案する。
本研究では,遷移や観測がガウスPSDモデルである場合,フィルタリングを効率的にクローズド形式で行うことができることを示す。
提案する推定器は, 近似の精度に依存し, 遷移確率の正則性に適応する推定誤差を伴って, 高い理論的保証を享受する。
論文 参考訳(メタデータ) (2024-02-15T08:51:49Z) - General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean
Estimation [58.03500081540042]
プライベート平均推定に対する古典的なアプローチは、真の平均を計算し、バイアスのないがおそらく相関のあるガウスノイズを加えることである。
すべての入力データセットに対して、集中的な差分プライバシーを満たす非バイアス平均推定器が、少なくとも多くのエラーをもたらすことを示す。
論文 参考訳(メタデータ) (2023-01-31T18:47:42Z) - Simple Binary Hypothesis Testing under Local Differential Privacy and
Communication Constraints [8.261182037130407]
局所差分プライバシー (LDP) と通信制約の両面から, 単純な二分仮説テストについて検討する。
我々はその結果をミニマックス最適かインスタンス最適かのどちらかとみなす。
論文 参考訳(メタデータ) (2023-01-09T18:36:49Z) - 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) - Differentially-Private Bayes Consistency [70.92545332158217]
差分プライバシー(DP)を満たすベイズ一貫した学習ルールを構築する。
ほぼ最適なサンプル複雑性を持つ半教師付き環境で,任意のVCクラスをプライベートに学習できることを実証する。
論文 参考訳(メタデータ) (2022-12-08T11:57:30Z) - Normalized/Clipped SGD with Perturbation for Differentially Private
Non-Convex Optimization [94.06564567766475]
DP-SGDとDP-NSGDは、センシティブなトレーニングデータを記憶する大規模モデルのリスクを軽減する。
DP-NSGD は DP-SGD よりも比較的チューニングが比較的容易であるのに対して,これらの2つのアルゴリズムは同様の精度を実現する。
論文 参考訳(メタデータ) (2022-06-27T03:45:02Z) - Shuffle Gaussian Mechanism for Differential Privacy [2.7564955518050693]
$$ epsilon(lambda) leq frac1lambda-1logleft(frace-da/2sigma2ndasum_substackk_+dotsc+k_n=lambda;k_nlambda!k_nlambda!k_nlambda!
論文 参考訳(メタデータ) (2022-06-20T04:54:16Z) - Auditing Differential Privacy in High Dimensions with the Kernel Quantum
R\'enyi Divergence [29.796646032324514]
本稿では,確率分布の新たな相違点に基づく差分プライバシーの緩和を提案する。
正規化カーネル R'enyi の発散は高次元においてもサンプルから推定可能であることを示す。
論文 参考訳(メタデータ) (2022-05-27T12:34:17Z) - Private Stochastic Non-Convex Optimization: Adaptive Algorithms and
Tighter Generalization Bounds [72.63031036770425]
有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。
標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
論文 参考訳(メタデータ) (2020-06-24T06:01:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。