論文の概要: 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)$であり、結果のアルゴリズムはすべて有意義な精度の改善をもたらす。
より広範に、問題固有の感度空間解析は、個人的な付加音に対する見落とされがちなツールである可能性が示唆された。
関連論文リスト
- Optimized Tradeoffs for Private Prediction with Majority Ensembling [59.99331405291337]
本稿では,データ依存型ランダム化応答行列(DaRRM)アルゴリズムを提案する。
DaRRMはデータ依存ノイズ関数$gamma$でパラメータ化され、全てのプライベートアルゴリズムのクラスに対して効率的なユーティリティ最適化を可能にする。
本稿では,DARRMが共通ベースラインよりも2倍のプライバシゲインを,固定ユーティリティで確実に享受していることを示す。
論文 参考訳（メタデータ） (2024-11-27T00:48:48Z) - Count on Your Elders: Laplace vs Gaussian Noise [9.546521474972485]
多くの環境では、ラプラスノイズはガウスノイズよりも好まれるかもしれないと我々は主張する。
ガウス機構によって付加される雑音は、常に同値な分散のラプラスノイズに置き換えることができることを示す。
これはガウスノイズが高次元雑音に使用されるという従来の知恵に挑戦する。
論文 参考訳（メタデータ） (2024-08-13T16:36:33Z) - General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean
Estimation [58.03500081540042]
プライベート平均推定に対する古典的なアプローチは、真の平均を計算し、バイアスのないがおそらく相関のあるガウスノイズを加えることである。
すべての入力データセットに対して、集中的な差分プライバシーを満たす非バイアス平均推定器が、少なくとも多くのエラーをもたらすことを示す。
論文 参考訳（メタデータ） (2023-01-31T18:47:42Z) - 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) - Optimal Algorithms for Mean Estimation under Local Differential Privacy [55.32262879188817]
そこで本研究では,PrivUnitが局所的プライベートな乱数化器群間の最適分散を実現することを示す。
また,ガウス分布に基づくPrivUnitの新たな変種も開発しており,数学的解析に適しており,同じ最適性保証を享受できる。
論文 参考訳（メタデータ） (2022-05-05T06:43:46Z) - Learning with User-Level Privacy [61.62978104304273]
ユーザレベルの差分プライバシー制約下での学習課題を,アルゴリズムを用いて解析する。
個々のサンプルのプライバシーのみを保証するのではなく、ユーザレベルのdpはユーザの貢献全体を保護します。
プライバシコストが$tau$に比例した$K$適応的に選択されたクエリのシーケンスにプライベートに答えるアルゴリズムを導き出し、私たちが検討する学習タスクを解決するためにそれを適用します。
論文 参考訳（メタデータ） (2021-02-23T18:25:13Z) - Faster Differentially Private Samplers via R\'enyi Divergence Analysis
of Discretized Langevin MCMC [35.050135428062795]
ランゲヴィン力学に基づくアルゴリズムは、統計距離のようなある程度の距離測度の下で、はるかに高速な代替手段を提供する。
我々の手法は単純で汎用的で、アンダーダムドランゲヴィン力学に適用できる。
論文 参考訳（メタデータ） (2020-10-27T22:52:45Z) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。
Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。
本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文 参考訳（メタデータ） (2020-05-10T19:52:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。