論文の概要: Private, Efficient, and Optimal K-Norm and Elliptic Gaussian Noise For Sum, Count, and Vote

• arxiv url: http://arxiv.org/abs/2309.15790v2
• Date: Mon, 4 Mar 2024 10:56:32 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-17 17:10:47.122809
• Title: Private, Efficient, and Optimal K-Norm and Elliptic Gaussian Noise For Sum, Count, and Vote
• Title（参考訳）: サム, カウント, 投票のためのプライベート, 効率的, 最適K-ノルムおよび楕円型ガウスノイズ
• Authors: Matthew Joseph, Alexander Yu,
• Abstract要約: 本稿では, 総和, カウント, 投票の簡単な問題を考察し, 両方の設定で高速なアルゴリズムを提供する。 我々は、最適偏微分プライベートな$K$-norm機構サンプリング器を構築し、最適な偏微分プライベートなガウス雑音に対する閉形式式を導出する。
• 参考スコア（独自算出の注目度）: 54.34628844260993
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Differentially private computation often begins with a bound on some $d$-dimensional statistic's $\ell_p$ sensitivity. For pure differential privacy, the $K$-norm mechanism can improve on this approach using statistic-specific (and possibly non-$\ell_p$) norms. However, sampling such mechanisms requires sampling from the corresponding norm balls. These are $d$-dimensional convex polytopes, for which the fastest known general sampling algorithm takes time $\tilde O(d^{3+\omega})$, where $\omega \geq 2$ is the matrix multiplication exponent. For concentrated differential privacy, elliptic Gaussian noise offers similar improvement over spherical Gaussian noise, but the general method for computing the problem-specific elliptic noise requires solving a semidefinite program for each instance. This paper considers the simple problems of sum, count, and vote and provides faster algorithms in both settings. We construct optimal pure differentially private $K$-norm mechanism samplers and derive closed-form expressions for optimal concentrated differentially private elliptic Gaussian noise. Their runtimes are, respectively, $\tilde O(d^2)$ and $O(1)$, and the resulting algorithms all yield meaningful accuracy improvements. More broadly, we suggest that problem-specific sensitivity space analysis may be an overlooked tool for private additive noise.
• Abstract（参考訳）: 微分プライベートな計算は、ある$d$次元統計学の$\ell_p$感度に束縛されて始まることが多い。 純粋な微分プライバシーのために、$K$-normメカニズムは統計学的(そしておそらくは非$$\ell_p$)ノルムを使ってこのアプローチを改善することができる。 しかし、そのようなメカニズムをサンプリングするには、対応する標準球からのサンプリングが必要である。 これらは$d$次元凸多面体であり、既知の最も高速な一般サンプリングアルゴリズムは$\tilde O(d^{3+\omega})$であり、$\omega \geq 2$は行列乗法指数である。 偏微分プライバシーのためには、楕円型ガウスノイズは球状ガウスノイズよりも類似した改善をもたらすが、問題固有の楕円型ノイズを計算する一般的な方法は、各インスタンスに対して半定値プログラムを解く必要がある。 本稿では, 総和, カウント, 投票の単純な問題について考察し, 両方の設定においてより高速なアルゴリズムを提供する。 我々は、最適偏微分プライベートな$K$-norm機構サンプリング器を構築し、最適な偏微分プライベートなガウス雑音に対する閉形式式を導出する。 それらのランタイムはそれぞれ$\tilde O(d^2)$と$O(1)$であり、結果のアルゴリズムはすべて有意義な精度の改善をもたらす。 より広範に、問題固有の感度空間解析は、個人的な付加音に対する見落とされがちなツールである可能性が示唆された。

関連論文リスト

• General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean Estimation [58.03500081540042]
  プライベート平均推定に対する古典的なアプローチは、真の平均を計算し、バイアスのないがおそらく相関のあるガウスノイズを加えることである。 すべての入力データセットに対して、集中的な差分プライバシーを満たす非バイアス平均推定器が、少なくとも多くのエラーをもたらすことを示す。
  論文  参考訳（メタデータ） (2023-01-31T18:47:42Z)
• Private estimation algorithms for stochastic block models and mixture models [63.07482515700984]
  効率的なプライベート推定アルゴリズムを設計するための一般的なツール。 最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
  論文  参考訳（メタデータ） (2023-01-11T09:12:28Z)
• 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)
• Higher degree sum-of-squares relaxations robust against oblivious outliers [14.58610686291355]
  我々は、$Y=X*+N$という形の推定モデルを考える。 本稿では,2乗推定アルゴリズムが存在するすべての推定問題において,軽度仮定の下で信号が$X*$に回復するアルゴリズム群を紹介する。
  論文  参考訳（メタデータ） (2022-11-14T13:09:12Z)
• Private Convex Optimization in General Norms [23.166642097170545]
  任意のノルム$normxcdot$におけるリプシッツである凸関数の微分プライベート最適化のための新しいフレームワークを提案する。 本稿では,このメカニズムが差分プライバシーを満足し,DP-ERM(経験的リスク最小化)とDP-SCO(確率的凸最適化)の両方を解決することを示す。 我々のフレームワークは、一般ノルム空間におけるプライベート凸最適化に初めて適用され、ミラー降下によって達成された非プライベートSCOレートを直接回復する。
  論文  参考訳（メタデータ） (2022-07-18T02:02:22Z)
• Scalable Differentially Private Clustering via Hierarchically Separated Trees [82.69664595378869]
  我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。 最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
  論文  参考訳（メタデータ） (2022-06-17T09:24:41Z)
• Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
  本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。 Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。 本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
  論文  参考訳（メタデータ） (2020-05-10T19:52:03Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)

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

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