論文の概要: Analysis of Shuffling Beyond Pure Local Differential Privacy

• arxiv url: http://arxiv.org/abs/2601.19154v1
• Date: Tue, 27 Jan 2026 03:35:03 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-28 15:26:51.157169
• Title: Analysis of Shuffling Beyond Pure Local Differential Privacy
• Title（参考訳）: 純局所微分プライバシーを超えるシャッフルの解析
• Authors: Shun Takagi, Seng Pei Liew,
• Abstract要約: Shufflingは、プライベート分散データ分析において、ローカルなランダム化器のプライバシを増幅する強力な方法である。 軽度正規性仮定の下で局所確率化器の幅広いクラスに適用可能な解析法を開発した。 有限の$n$で毛布の発散を計算するためにFFTベースのアルゴリズムを用いる。
• 参考スコア（独自算出の注目度）: 2.4264122405649045
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Shuffling is a powerful way to amplify privacy of a local randomizer in private distributed data analysis, but existing analyses mostly treat the local differential privacy (DP) parameter $\varepsilon_0$ as the only knob and give generic upper bounds that can be loose and do not even characterize how shuffling amplifies privacy for basic mechanisms such as the Gaussian mechanism. We revisit the privacy blanket bound of Balle et al. (the blanket divergence) and develop an asymptotic analysis that applies to a broad class of local randomizers under mild regularity assumptions, without requiring pure local DP. Our key finding is that the leading term of the blanket divergence depends on the local mechanism only through a single scalar parameter $χ$, which we call the shuffle index. By applying this asymptotic analysis to both upper and lower bounds, we obtain a tight band for $δ_n$ in the shuffled mechanism's $(\varepsilon_n,δ_n)$-DP guarantee. Moreover, we derive a simple structural necessary and sufficient condition on the local randomizer under which the blanket-divergence-based upper and lower bounds coincide asymptotically. $k$-RR families with $k\ge3$ satisfy this condition, while for generalized Gaussian mechanisms the condition may not hold but the resulting band remains tight. Finally, we complement the asymptotic theory with an FFT-based algorithm for computing the blanket divergence at finite $n$, which offers rigorously controlled relative error and near-linear running time in $n$, providing a practical numerical analysis for shuffle DP.
• Abstract（参考訳）: Shufflingは、プライベートな分散データ分析においてローカルなランダム化器のプライバシを増幅する強力な方法だが、既存の分析では、ローカルな差分プライバシー(DP)パラメータである$\varepsilon_0$を唯一のノブとして扱い、緩くなりうる一般的な上限を与える。 本研究では,Ball et al のプライバシ・毛布境界(毛布のばらつき)を再検討し,純粋なローカルDPを必要とせず,緩やかな規則性仮定の下で局所ランダム化器の幅広いクラスに適用可能な漸近解析法を開発した。 我々の重要な発見は、ブランケットの分岐の先頭項が局所的なメカニズムに依存しているということであり、これはシャッフル指数と呼ばれる単一のスカラーパラメータ(英語版)$(英語版)を通してのみである。 この漸近解析を上界と下界の両方に適用することにより、シャッフル機構の$(\varepsilon_n,δ_n)$-DP保証において、$δ_n$のタイトバンドを得る。 さらに,毛布分割に基づく上と下の境界が漸近的に一致する局所確率化器において,簡単な構造的必要十分条件を導出する。 k$-RRファミリと$k\ge3$は、この条件を満たすが、一般化されたガウス機構では、この条件は成立しないが、結果として生じるバンドは厳密なままである。 最後に、この漸近理論を有限$n$で毛布分散を計算するためのFFTベースのアルゴリズムで補完し、厳密に制御された相対誤差とほぼ直線的な実行時間を$n$で提供し、シャッフルDPの実用的な数値解析を行う。

関連論文リスト

• Unified Enhancement of Privacy Bounds for Mixture Mechanisms via $f$-Differential Privacy [41.51051636162107]
  本稿では、シャッフルモデルと1点差分勾配勾配のプライバシー境界の改善に焦点をあてる。 シャッフルモデルに対するトレードオフ関数のクローズドフォーム式を導出し、最新の結果よりも優れる。 また, ホッケースティックの進行した関節凸性の$f$-DPアナログを, $(epsilon,delta)$-DPに関連するホッケースティックのばらつきについて検討した。
  論文  参考訳（メタデータ） (2023-10-30T19:37:51Z)
• Some Constructions of Private, Efficient, and Optimal $K$-Norm and Elliptic Gaussian Noise [54.34628844260993]
  微分プライベートな計算は、しばしば$d$次元統計学の感度に束縛されて始まる。 純粋な微分プライバシーのために、$K$-normメカニズムは統計学の感度空間に合わせた規範を用いてこのアプローチを改善することができる。 本稿では,総和,数,投票の単純な統計量について両問題を解く。
  論文  参考訳（メタデータ） (2023-09-27T17:09:36Z)
• General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean Estimation [58.03500081540042]
  プライベート平均推定に対する古典的なアプローチは、真の平均を計算し、バイアスのないがおそらく相関のあるガウスノイズを加えることである。 すべての入力データセットに対して、集中的な差分プライバシーを満たす非バイアス平均推定器が、少なくとも多くのエラーをもたらすことを示す。
  論文  参考訳（メタデータ） (2023-01-31T18:47:42Z)
• Optimal Scaling for Locally Balanced Proposals in Discrete Spaces [65.14092237705476]
  離散空間におけるMetropolis-Hastings (M-H) アルゴリズムの効率は、対象分布に依存しない受容率によって特徴づけられることを示す。 最適受容率の知識は、連続空間におけるステップサイズ制御と直接的に類似して、離散空間における提案分布の近傍サイズを自動的に調整することを可能にする。
  論文  参考訳（メタデータ） (2022-09-16T22:09:53Z)
• Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond [63.59034509960994]
  シャッフルに基づく変種(ミニバッチと局所ランダムリシャッフル)について検討する。 ポリアック・ロジャシエヴィチ条件を満たす滑らかな函数に対して、これらのシャッフル型不変量(英語版)(shuffling-based variants)がそれらの置換式よりも早く収束することを示す収束境界を得る。 我々は, 同期シャッフル法と呼ばれるアルゴリズムの修正を提案し, ほぼ均一な条件下では, 下界よりも収束速度が速くなった。
  論文  参考訳（メタデータ） (2021-10-20T02:25:25Z)
• Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
  カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。 我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。 MRP のサブクラスに対する minimax の下位境界を証明する。
  論文  参考訳（メタデータ） (2021-09-24T14:48:20Z)
• 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)
• Tight Differential Privacy for Discrete-Valued Mechanisms and for the Subsampled Gaussian Mechanism Using FFT [6.929834518749884]
  離散的な1次元の出力を持つアルゴリズムに対して,厳密な$(varepsilon,delta)$-privacy損失を評価するための数値会計法を提案する。 本稿では,従来の文献と同等のプライバシーで,ノイズ分散を最大75%低減できることを示す。
  論文  参考訳（メタデータ） (2020-06-12T12:46:42Z)

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

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