論文の概要: Infinitely Divisible Noise for Differential Privacy: Nearly Optimal Error in the High $\varepsilon$ Regime

• arxiv url: http://arxiv.org/abs/2504.05202v1
• Date: Mon, 07 Apr 2025 15:50:46 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-08 14:08:23.028300
• Title: Infinitely Divisible Noise for Differential Privacy: Nearly Optimal Error in the High $\varepsilon$ Regime
• Title（参考訳）: 差別的プライバシーのための無限に異なるノイズ:高い$\varepsilon$ Regimeの最適誤差に近い
• Authors: Charlie Harrison, Pasin Manurangsi,
• Abstract要約: 差分プライバシー(DP)は、複数のパーティがDPでデータセット全体を保護するために独立したノイズを付加する分散方式で達成できる。 本設定では, 一般化離散ラプラス(GDL)機構と, 負二項共有の相違による分布, マルチスケール離散ラプラス(MSDLap)機構の2つのメカニズムを解析した。
• 参考スコア（独自算出の注目度）: 31.65647145855917
• License:
• Abstract: Differential privacy (DP) can be achieved in a distributed manner, where multiple parties add independent noise such that their sum protects the overall dataset with DP. A common technique here is for each party to sample their noise from the decomposition of an infinitely divisible distribution. We analyze two mechanisms in this setting: 1) the generalized discrete Laplace (GDL) mechanism, whose distribution (which is closed under summation) follows from differences of i.i.d. negative binomial shares, and 2) the multi-scale discrete Laplace (MSDLap) mechanism, a novel mechanism following the sum of multiple i.i.d. discrete Laplace shares at different scales. For $\varepsilon \geq 1$, our mechanisms can be parameterized to have $O\left(\Delta^3 e^{-\varepsilon}\right)$ and $O\left(\min\left(\Delta^3 e^{-\varepsilon}, \Delta^2 e^{-2\varepsilon/3}\right)\right)$ MSE, respectively, where $\Delta$ denote the sensitivity; the latter bound matches known optimality results. We also show a transformation from the discrete setting to the continuous setting, which allows us to transform both mechanisms to the continuous setting and thereby achieve the optimal $O\left(\Delta^2 e^{-2\varepsilon / 3}\right)$ MSE. To our knowledge, these are the first infinitely divisible additive noise mechanisms that achieve order-optimal MSE under pure DP, so our work shows formally there is no separation in utility when query-independent noise adding mechanisms are restricted to infinitely divisible noise. For the continuous setting, our result improves upon the Arete mechanism from [Pagh and Stausholm, ALT 2022] which gives an MSE of $O\left(\Delta^2 e^{-\varepsilon/4}\right)$. Furthermore, we give an exact sampler tuned to efficiently implement the MSDLap mechanism, and we apply our results to improve a state of the art multi-message shuffle DP protocol in the high $\varepsilon$ regime.
• Abstract（参考訳）: 差分プライバシー(DP)は、複数のパーティがDPでデータセット全体を保護するために独立したノイズを付加する分散方式で達成できる。 ここでの一般的な手法は、各パーティが無限に可除な分布の分解からノイズをサンプリングすることである。 この設定では2つのメカニズムを分析します。 1) 一般化離散ラプラス(GDL)機構は、(和で閉じた)分布は負二項共有(負二項共有)の差に従う。 2) マルチスケール離散ラプラス(MSDLap)機構は,複数 i.d.離散ラプラスの異なるスケールでの共有の和に続く新しいメカニズムである。 我々のメカニズムは、$O\left(\Delta^3 e^{-\varepsilon}\right)$と$O\left(\Delta^3 e^{-\varepsilon}, \Delta^2 e^{-2\varepsilon/3}\right)\right)$ MSEとパラメータ化され、$O\left(\Delta^3 e^{-\varepsilon}\right)$と$O\left(\Delta^3 e^{-\varepsilon}, \Delta^2 e^{-2\varepsilon/3}\right)\right)$ MSEで、$\Delta$は感度を表す。 また、離散的な設定から連続的な設定への変換を示し、それによって両方の機構を連続的な設定に変換し、最適な$O\left(\Delta^2 e^{-2\varepsilon / 3}\right)$ MSE が得られる。 我々の知る限り、これらは純粋DPの下で順序最適MSEを達成する最初の無限分割可能な付加雑音機構であり、クエリ非依存ノイズ付加機構が無限分割可能な雑音に制限されている場合に、公式には実用性に分離がないことを示す。 連続的な設定では、Arete機構は[Pagh and Stausholm, ALT 2022]から改善され、$O\left(\Delta^2 e^{-\varepsilon/4}\right)$のMSEが得られる。 さらに,MSDLap機構を効率的に実装するために調整された正確なサンプルを提示し,その結果を高額な$\varepsilon$レジストレーションにおける最先端のマルチメッセージシャッフルDPプロトコルの改善に応用する。

関連論文リスト

• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• Tractable MCMC for Private Learning with Pure and Gaussian Differential Privacy [23.12198546384976]
  後方サンプリングは$varepsilon$-pure差分プライバシー保証を提供する。 これは、$(varepsilon,delta)$-approximate DPによって引き起こされた潜在的に束縛されていないプライバシー侵害に悩まされない。 しかし実際には、マルコフ連鎖モンテカルロのような近似的なサンプリング手法を適用する必要がある。
  論文  参考訳（メタデータ） (2023-10-23T07:54:39Z)
• Restarted Bayesian Online Change-point Detection for Non-Stationary Markov Decision Processes [12.229154524476405]
  我々は、Restarted Bayesian Online Change-Point Detectionアルゴリズム(R-BOCPD)の変種を導入する。 多項分布から標本化された状態遷移カーネルを用いたMPP用UCRL2アルゴリズムの改良版を提案する。 我々は,R-BOCPD-UCRL2が$Oleft(D O sqrtA T K_T logleft (fracTdelta right) + fracK_Tdeltaminlimits_ell の好意的な後悔境界を享受していることを示す。
  論文  参考訳（メタデータ） (2023-04-01T05:26:41Z)
• Efficient Sampling of Stochastic Differential Equations with Positive Semi-Definite Models [91.22420505636006]
  本稿では, ドリフト関数と拡散行列を考慮し, 微分方程式からの効率的なサンプリング問題を扱う。 1/varepsilonは$m2d log (1/varepsilon)$である。 以上の結果から,真の解がより滑らかになるにつれて,どのような凸性も必要とせず,次元の呪いを回避できることが示唆された。
  論文  参考訳（メタデータ） (2023-03-30T02:50:49Z)
• Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP [58.13930707612128]
  この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。 我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
  論文  参考訳（メタデータ） (2022-12-01T15:57:58Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• 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)
• Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrap [84.66885506098724]
  本稿では,アダプティブ・マルチステップ・ブートストラップ (AMB) を用いた表層有限水平マルコフ決定過程 (MDP) のモデルフリーアルゴリズムを提案する。 AMBは,部分最適ギャップの逆の和でのみスケールする,ギャップ依存的後悔境界を達成できることを示す。 また、AMB は $frac|Z_mul|Delta_min$ regret という追加の $frac|Z_mul|Delta_min$ を被っていることも示しています。
  論文  参考訳（メタデータ） (2021-02-09T07:46:34Z)
• SDP Achieves Exact Minimax Optimality in Phase Synchronization [19.909352968029584]
  我々は、ノイズ測定$Y=z*z*+sigma WinmathbbCntimes ntimes nで位相同期問題を研究する。 SDPが誤差境界$ (1+o)fracnp22np$を2乗の$ell$損失で達成することを証明する。
  論文  参考訳（メタデータ） (2021-01-07T03:14:05Z)
• Learning Halfspaces with Tsybakov Noise [50.659479930171585]
  テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。 真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-06-11T14:25:02Z)

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

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