論文の概要: Some Constructions of Private, Efficient, and Optimal $K$-Norm and Elliptic Gaussian Noise
- arxiv url: http://arxiv.org/abs/2309.15790v3
- Date: Tue, 21 May 2024 15:58:21 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-22 19:10:52.895738
- Title: Some Constructions of Private, Efficient, and Optimal $K$-Norm and Elliptic Gaussian Noise
- Title（参考訳）: プライベート, 効率的, 最適$K$-Norm, 楕円型ガウスノイズの構成法
- Authors: Matthew Joseph, Alexander Yu,
- Abstract要約: 微分プライベートな計算は、しばしば$d$次元統計学の感度に束縛されて始まる。
純粋な微分プライバシーのために、$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 a norm tailored to the statistic's sensitivity space. Writing down a closed-form description of this optimal norm is often straightforward. However, running the $K$-norm mechanism reduces to uniformly sampling the norm's unit ball; this ball is a $d$-dimensional convex body, so general sampling algorithms can be slow. Turning to concentrated differential privacy, elliptic Gaussian noise offers similar improvement over spherical Gaussian noise. Once the shape of this ellipse is determined, sampling is easy; however, identifying the best such shape may be hard. This paper solves both problems for the simple statistics of sum, count, and vote. For each statistic, we provide a sampler for the optimal $K$-norm mechanism that runs in time $\tilde O(d^2)$ and derive a closed-form expression for the optimal shape of elliptic Gaussian noise. The resulting algorithms all yield meaningful accuracy improvements while remaining fast and simple enough to be practical. 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メカニズムは統計学の感度空間に合わせた規範を用いてこのアプローチを改善することができる。
この最適ノルムの閉形式記述を書くことは、しばしば単純である。
しかし、$K$-norm の機構を実行すると、標準の単位球を均一にサンプリングすることになり、この球は$d$次元凸体であるため、一般的なサンプリングアルゴリズムは遅くなる。
偏微分プライバシーに転換し、楕円型ガウスノイズは球状ガウスノイズよりも類似した改善をもたらす。
この楕円の形状が決定されるとサンプリングが簡単になるが、最良の形状を特定することは困難である。
本稿では,総和,数,投票の単純な統計量について両問題を解く。
各統計量に対して、時間$\tilde O(d^2)$で動作し、楕円ガウス雑音の最適形状に対する閉形式式を導出する最適な$K$-norm機構のサンプリング器を提供する。
結果のアルゴリズムはすべて有意義な精度向上を実現し、実用性に十分な速さと単純さを保ったままである。
より広範に、問題固有の感度空間解析は、個人的な付加音に対する見落とされがちなツールである可能性が示唆された。
関連論文リスト
- Count on Your Elders: Laplace vs Gaussian Noise [10.428888893980739]
多くの環境では、ラプラスノイズはガウスノイズよりも好まれるかもしれないと我々は主張する。
ガウス機構によって付加される雑音は、常に同値な分散のラプラスノイズに置き換えることができることを示す。
論文 参考訳（メタデータ） (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) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。