論文の概要: A Central Limit Theorem for Differentially Private Query Answering

• arxiv url: http://arxiv.org/abs/2103.08721v1
• Date: Mon, 15 Mar 2021 21:06:25 GMT
• ステータス: 処理完了
• システム内更新日: 2021-03-17 23:46:52.432218
• Title: A Central Limit Theorem for Differentially Private Query Answering
• Title（参考訳）: 差分私的問合せ解答のための中心極限定理
• Authors: Jinshuo Dong, Weijie J. Su, Linjun Zhang
• Abstract要約: プライバシパラメータの積を示し、そのメカニズムの$ell$-lossは次元によって境界が低くなることを示す。 私たちの発見は数値実験によって裏付けられる。
• 参考スコア（独自算出の注目度）: 23.015107368002884
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Perhaps the single most important use case for differential privacy is to privately answer numerical queries, which is usually achieved by adding noise to the answer vector. The central question, therefore, is to understand which noise distribution optimizes the privacy-accuracy trade-off, especially when the dimension of the answer vector is high. Accordingly, extensive literature has been dedicated to the question and the upper and lower bounds have been matched up to constant factors [BUV18, SU17]. In this paper, we take a novel approach to address this important optimality question. We first demonstrate an intriguing central limit theorem phenomenon in the high-dimensional regime. More precisely, we prove that a mechanism is approximately Gaussian Differentially Private [DRS21] if the added noise satisfies certain conditions. In particular, densities proportional to $\mathrm{e}^{-\|x\|_p^\alpha}$, where $\|x\|_p$ is the standard $\ell_p$-norm, satisfies the conditions. Taking this perspective, we make use of the Cramer--Rao inequality and show an "uncertainty principle"-style result: the product of the privacy parameter and the $\ell_2$-loss of the mechanism is lower bounded by the dimension. Furthermore, the Gaussian mechanism achieves the constant-sharp optimal privacy-accuracy trade-off among all such noises. Our findings are corroborated by numerical experiments.
• Abstract（参考訳）: 差分プライバシーの唯一の重要なユースケースは、一般に答えベクトルにノイズを加えることで達成される数値クエリにプライベートに答えることだろう。 したがって,どのノイズ分布がプライバシと精度のトレードオフを最適化するか,特に回答ベクトルの次元が高い場合の理解が重要となる。 したがって、この問題に広範な文献が注がれており、上下の境界は定数因子 [BUV18, SU17] に一致している。 本稿では,この重要な最適性問題に対処するための新しいアプローチを提案する。 まず,高次元環境において興味深い中心極限定理現象を示す。 より正確には、付加ノイズが特定の条件を満たす場合、そのメカニズムがガウス微分プライベート[DRS21]にほぼ一致することを示す。 特に、$\mathrm{e}^{-\|x\|_p^\alpha}$に比例する密度では、$\|x\|_p$は標準の$\ell_p$-normであり、条件を満たす。 この観点からは、cracker-raoの不等式を用いて、プライバシパラメータとメカニズムの$\ell_2$-lossの積は次元によって境界が低くなるという「不確実性原理」スタイルの結果を示す。 さらに、ガウスのメカニズムは、そのような全てのノイズの間で、一定のシャープな最適プライバシー・正確性トレードオフを達成する。 我々の発見は数値実験によって裏付けられている。

関連論文リスト

• Some Constructions of Private, Efficient, and Optimal $K$-Norm and Elliptic Gaussian Noise [54.34628844260993]
  微分プライベートな計算は、しばしば$d$次元統計学の感度に束縛されて始まる。 純粋な微分プライバシーのために、$K$-normメカニズムは統計学の感度空間に合わせた規範を用いてこのアプローチを改善することができる。 本稿では,総和,数,投票の単純な統計量について両問題を解く。
  論文  参考訳（メタデータ） (2023-09-27T17:09:36Z)
• Differential Privacy with Higher Utility by Exploiting Coordinate-wise Disparity: Laplace Mechanism Can Beat Gaussian in High Dimensions [9.20186865054847]
  我々は、i.n.d. Gaussian と Laplace のメカニズムを研究し、これらのメカニズムがプライバシーを保証する条件を得る。 i.n.d.ノイズは, (a) 座標降下, (b) 主成分分析, (c) グループクリッピングによる深層学習における性能を向上することを示す。
  論文  参考訳（メタデータ） (2023-02-07T14:54:20Z)
• General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean Estimation [58.03500081540042]
  プライベート平均推定に対する古典的なアプローチは、真の平均を計算し、バイアスのないがおそらく相関のあるガウスノイズを加えることである。 すべての入力データセットに対して、集中的な差分プライバシーを満たす非バイアス平均推定器が、少なくとも多くのエラーをもたらすことを示す。
  論文  参考訳（メタデータ） (2023-01-31T18:47:42Z)
• Brownian Noise Reduction: Maximizing Privacy Subject to Accuracy Constraints [53.01656650117495]
  研究者と実践者の間には、プライバシとユーティリティのトレードオフの扱い方の違いがある。 ブラウン機構は、まず擬ブラウン運動の最終点に対応する高分散のガウス雑音を加えることで機能する。 我々は、古典的AboveThresholdアルゴリズムの一般化であるReduceedAboveThresholdでブラウン機構を補完する。
  論文  参考訳（メタデータ） (2022-06-15T01:43:37Z)
• Optimal Algorithms for Mean Estimation under Local Differential Privacy [55.32262879188817]
  そこで本研究では,PrivUnitが局所的プライベートな乱数化器群間の最適分散を実現することを示す。 また,ガウス分布に基づくPrivUnitの新たな変種も開発しており,数学的解析に適しており,同じ最適性保証を享受できる。
  論文  参考訳（メタデータ） (2022-05-05T06:43:46Z)
• Differential privacy for symmetric log-concave mechanisms [0.0]
  データベースクエリ結果にランダムノイズを加えることは、プライバシを達成するための重要なツールである。 我々は、すべての対称および対数凹形ノイズ密度に対して、$(epsilon, delta)$-differential privacyに対して十分かつ必要な条件を提供する。
  論文  参考訳（メタデータ） (2022-02-23T10:20:29Z)
• A unified interpretation of the Gaussian mechanism for differential privacy through the sensitivity index [61.675604648670095]
  GMの一般的な3つの解釈、すなわち$(varepsilon, delta)$-DP, f-DP, R'enyi DPは1つのパラメータ$psi$で表現できる。 $psi$は、クエリの感度とノイズ摂動の大きさの2つの基本量をカプセル化することによって、GMとその特性を特徴付ける。
  論文  参考訳（メタデータ） (2021-09-22T06:20:01Z)
• Non-Euclidean Differentially Private Stochastic Convex Optimization [15.302167005107135]
  雑音勾配降下法(SGD)アルゴリズムは低次元状態において最適過大なリスクを達成できることを示す。 私たちの作品は、規則性、均一凸性、均一な平滑性の概念など、規範空間の幾何学から概念を導き出します。
  論文  参考訳（メタデータ） (2021-03-01T19:48:44Z)
• Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling [49.43288037509783]
  ランダムシャッフルは、局所的ランダム化データの差分プライバシー保証を増幅する。 私たちの結果は、以前の作業よりも単純で、ほぼ同じ保証で差分プライバシーに拡張された新しいアプローチに基づいています。
  論文  参考訳（メタデータ） (2020-12-23T17:07:26Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。