論文の概要: Decomposition-Based Optimal Bounds for Privacy Amplification via Shuffling

• arxiv url: http://arxiv.org/abs/2504.07414v5
• Date: Tue, 15 Jul 2025 12:20:33 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-16 15:29:04.461091
• Title: Decomposition-Based Optimal Bounds for Privacy Amplification via Shuffling
• Title（参考訳）: シャッフルによるプライバシー増幅のための分解に基づく最適境界
• Authors: Pengcheng Su, Haibo Cheng, Ping Wang,
• Abstract要約: Shufflingは、異なるプライバシー保証を増幅し、より好ましいプライバシーユーティリティのトレードオフを可能にすることが示されている。 我々は,すべての可能な分解を仮定する,統一的な分析フレームワーク - 一般的なクローンパラダイム- を導入する。 本稿では,Fast Fourier Transform (FFT) に基づく簡易かつ効率的なアルゴリズムを開発し,最適なプライバシー増幅境界を求める。
• 参考スコア（独自算出の注目度）: 6.702635586444281
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Shuffling has been shown to amplify differential privacy guarantees, enabling a more favorable privacy-utility trade-off. To characterize and compute this amplification, two fundamental analytical frameworks have been proposed: the \emph{privacy blanket} by Balle et al. (CRYPTO 2019) and the \emph{clone}--including both the standard and stronger variant--by Feldman et al. (FOCS 2021, SODA 2023). These frameworks share a common foundation: decomposing local randomizers into structured components for analysis. In this work, we introduce a unified analytical framework--the general clone paradigm--which subsumes all possible decompositions, with the clone and blanket decompositions arising as special cases. Within this framework, we identify the optimal decomposition, which is precisely the one used by the privacy blanket. Moreover, we develop a simple and efficient algorithm based on the Fast Fourier Transform (FFT) to compute optimal privacy amplification bounds. Experimental results show that our computed upper bounds nearly match the lower bounds, demonstrating the tightness of our method. Building on this method, we also derive optimal amplification bounds for both \emph{joint} and \emph{parallel} compositions of LDP mechanisms in the shuffle model.
• Abstract（参考訳）: Shufflingは、異なるプライバシー保証を増幅し、より好ましいプライバシーユーティリティのトレードオフを可能にすることが示されている。 この増幅を特徴づけ、計算するために、Balle et al (CRYPTO 2019) の \emph{privacy blanket} と、Feldman et al (FOCS 2021, SODA 2023) による標準およびより強力な変種の両方を含む \emph{clone} という2つの基本的な分析フレームワークが提案されている。 これらのフレームワークは共通基盤を共有しており、分析のためにローカルなランダム化器を構造化されたコンポーネントに分解する。 そこで本研究では, クローンと毛布の分解を特殊ケースとして, 可能なすべての分解を仮定する, 一般化された解析的枠組みを導入する。 このフレームワーク内では、プライバシーブランケットが正確に使用する最適分解を識別する。 さらに,Fast Fourier Transform (FFT) に基づく簡易かつ効率的なアルゴリズムを開発し,最適なプライバシー増幅境界を求める。 実験の結果, 計算された上界は下界にほぼ一致することがわかった。 この方法に基づいて、シャッフルモデルにおけるLPP機構の \emph{joint} と \emph{parallel} の最適増幅境界も導出する。

関連論文リスト

• Sample-Optimal Private Regression in Polynomial Time [3.3748750222488657]
  アルゴリズムのサンプル複雑性の改善は,統計的クエリや情報理論的下位境界に反することを示した。 アルゴリズムは任意の外れ値の小さな部分に対して頑健であり、外れ値の小さな部分の関数として最適誤差率を達成する。
  論文  参考訳（メタデータ） (2025-03-31T17:08:12Z)
• Privacy amplification by random allocation [18.231854497751137]
  我々は,ユーザのデータがランダムに選択された$k$ステップにおいて,$t$ステップのシーケンス(あるいはセット)から一様に選択されるサンプリングスキームのプライバシアンプリフィケーション特性について考察する。 このスキームの既存の分析は、シャッフルによるプライバシーの増幅に頼り、過度に保守的な境界を導いたり、モンテカルロシミュレーションを必要とする。 特に、ランダムな$k$-out-of-t$アロケーションのプライバシ保証は、よく研究されている独立性(あるいはPoisson)サブサンプリングのプライバシー保証によって上限づけられることを示す。
  論文  参考訳（メタデータ） (2025-02-12T08:32:10Z)
• The Cost of Shuffling in Private Gradient Based Optimization [40.31928071333575]
  その結果, DP-ShuffleGはDP-SGDと比較して, データのシャッフル処理により過大なリスクが生じることがわかった。 我々は、プライベートな最適化に公開データサンプルを統合するハイブリッドアプローチである textitInterleaved-ShuffleG を提案する。
  論文  参考訳（メタデータ） (2025-02-05T22:30:00Z)
• Individualized Privacy Accounting via Subsampling with Applications in Combinatorial Optimization [55.81991984375959]
  本研究では、以下の簡単な観察を通して、個別化されたプライバシ会計を解析する新しい手法を提案する。 我々は、分解可能な部分モジュラーおよびセットアルゴリズム被覆を含む、プライベート最適化問題に対するいくつかの改良されたアルゴリズムを得る。
  論文  参考訳（メタデータ） (2024-05-28T19:02:30Z)
• Shifted Interpolation for Differential Privacy [6.1836947007564085]
  雑音勾配降下とその変種は、微分プライベート機械学習の主要なアルゴリズムである。 本稿では、$f$差分プライバシの統一化フレームワークにおいて、"corollary によるプライバシ増幅" 現象を確立する。 これは、強力な凸最適化の基礎的な設定において、最初の正確なプライバシー分析につながる。
  論文  参考訳（メタデータ） (2024-03-01T04:50:04Z)
• Enhancing Trade-offs in Privacy, Utility, and Computational Efficiency through MUltistage Sampling Technique (MUST) [3.0939420223851446]
  プライバシ・アンプリフィケーション(PA)のためのサブサンプリング手法のクラスを提案する。 本研究は2段階MUST法におけるPA効果と実用性について包括的に解析する。 MUSTの繰り返し適用に関するプライバシー損失構成分析を行う。
  論文  参考訳（メタデータ） (2023-12-20T19:38:29Z)
• A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization [53.14532968909759]
  ALEXRと呼ばれる,効率的な単ループプリマル・デュアルブロック座標アルゴリズムを提案する。 本研究では, ALEXR の凸面および強凸面の収束速度を滑らか性および非滑らか性条件下で確立する。 CFCCO の ROC 曲線の下での GDRO および部分領域の実験結果から,提案アルゴリズムの有望な性能を示す。
  論文  参考訳（メタデータ） (2023-12-04T19:00:07Z)
• PARL: A Unified Framework for Policy Alignment in Reinforcement Learning from Human Feedback [106.63518036538163]
  我々は、強化学習におけるポリシーアライメントの最近強調された重要な問題に対処するために、新しい統合された二段階最適化ベースのフレームワーク、textsfPARLを提案する。 本フレームワークは, 上向きの目標(逆設計)の分布を, 下向きの最適変数で明示的にパラメータ化することにより, これらの問題に対処する。 その結果,提案したtextsfPARL が RL のアライメントの懸念に対処できる可能性が示唆された。
  論文  参考訳（メタデータ） (2023-08-03T18:03:44Z)
• Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms [64.10576998630981]
  最適なヘッセン依存型サンプルの複雑さを, 初めて厳密に評価した。 ヘシアン非依存のアルゴリズムは、すべてのヘシアンインスタンスに対して最適なサンプル複雑さを普遍的に達成する。 本アルゴリズムにより得られたサンプルの最適複雑さは,重み付き雑音分布においても有効である。
  論文  参考訳（メタデータ） (2023-06-21T17:03:22Z)
• Theoretically Principled Federated Learning for Balancing Privacy and Utility [61.03993520243198]
  モデルパラメータを歪ませることでプライバシを保護する保護機構の一般学習フレームワークを提案する。 フェデレートされた学習における各コミュニケーションラウンドにおいて、各クライアント上の各モデルパラメータに対して、パーソナライズされたユーティリティプライバシトレードオフを実現することができる。
  論文  参考訳（メタデータ） (2023-05-24T13:44:02Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。 微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
  論文  参考訳（メタデータ） (2023-02-24T18:41:48Z)
• Differentially Private Federated Clustering over Non-IID Data [59.611244450530315]
  クラスタリングクラスタ(FedC)問題は、巨大なクライアント上に分散されたラベルなしデータサンプルを、サーバのオーケストレーションの下で有限のクライアントに正確に分割することを目的としている。 本稿では,DP-Fedと呼ばれる差分プライバシー収束手法を用いた新しいFedCアルゴリズムを提案する。 提案するDP-Fedの様々な属性は、プライバシー保護の理論的解析、特に非識別的かつ独立に分散された(非i.d.)データの場合において得られる。
  論文  参考訳（メタデータ） (2023-01-03T05:38:43Z)
• Stronger Privacy Amplification by Shuffling for R\'enyi and Approximate Differential Privacy [43.33288245778629]
  このモデルにおける重要な結果は、ランダムにランダム化されたデータをランダムにシャッフルすると、差分プライバシー保証が増幅されることである。 このような増幅は、匿名でデータが提供されるシステムにおいて、はるかに強力なプライバシー保証を意味する。 本研究では,理論的にも数値的にも,アートプライバシの増幅状態を改善する。
  論文  参考訳（メタデータ） (2022-08-09T08:13:48Z)
• Differentially Private Sampling from Rashomon Sets, and the Universality of Langevin Diffusion for Convex Optimization [15.404265455635587]
  プライバシー分析が凸性に依存しず、プライバシーを損なうことなくいつでも停止することができる指数関数機構からのサンプリングアルゴリズムを提案する。 我々は、純粋および近似微分プライバシー(DP)の下で(強く)凸損失に対する最適過大な経験と人口リスクの保証を得る。 このフレームワークにより、Rashomon集合からDP一様サンプリングを設計できる。
  論文  参考訳（メタデータ） (2022-04-04T15:33:21Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)
• Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling [49.43288037509783]
  ランダムシャッフルは、局所的ランダム化データの差分プライバシー保証を増幅する。 私たちの結果は、以前の作業よりも単純で、ほぼ同じ保証で差分プライバシーに拡張された新しいアプローチに基づいています。
  論文  参考訳（メタデータ） (2020-12-23T17:07:26Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Patch-level Neighborhood Interpolation: A General and Effective Graph-based Regularization Strategy [77.34280933613226]
  我々は、ネットワークの計算において非局所的な表現を行うtextbfPatch-level Neighborhood Interpolation(Pani)と呼ばれる一般的な正規化器を提案する。 提案手法は,異なる層にパッチレベルグラフを明示的に構築し,その近傍のパッチ特徴を線形に補間し,汎用的で効果的な正規化戦略として機能する。
  論文  参考訳（メタデータ） (2019-11-21T06:31:59Z)

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

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