論文の概要: Langevin Diffusion: An Almost Universal Algorithm for Private Euclidean
(Convex) Optimization
- arxiv url: http://arxiv.org/abs/2204.01585v1
- Date: Mon, 4 Apr 2022 15:33:21 GMT
- ステータス: 処理完了
- システム内更新日: 2022-04-05 17:25:38.343276
- Title: Langevin Diffusion: An Almost Universal Algorithm for Private Euclidean
(Convex) Optimization
- Title（参考訳）: langevin diffusion: プライベートユークリッド(凸)最適化のためのほぼ普遍的なアルゴリズム
- Authors: Arun Ganesh, Abhradeep Thakurta, Jalaj Upadhyay
- Abstract要約: 我々は,Langevinfusion (LD) と呼ばれる統計物理学からのよく研究された連続時間アルゴリズムが,同時に最適なプライバシー/ユーティリティトレードオフを提供することを示した。
本研究は,DP連続時間最適化の体系的研究を開始する。
- 参考スコア（独自算出の注目度）: 27.159784930467232
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper we revisit the problem of differentially private empirical risk
minimization (DP-ERM) and differentially private stochastic convex optimization
(DP-SCO). We show that a well-studied continuous time algorithm from
statistical physics, called Langevin diffusion (LD), simultaneously provides
optimal privacy/utility trade-offs for both DP-ERM and DP-SCO, under
$\epsilon$-DP, and $(\epsilon,\delta)$-DP. Using the uniform stability
properties of LD, we provide the optimal excess population risk guarantee for
$\ell_2$-Lipschitz convex losses under $\epsilon$-DP, which was an open problem
since [BST14].
Along the way, we provide various technical tools, which can be of
independent interest: i) A new R\'enyi divergence bound for LD, when run on
loss functions over two neighboring data sets, ii) Excess empirical risk bounds
for last-iterate LD, analogous to that of Shamir and Zhang for noisy stochastic
gradient descent (SGD), and iii) A two phase excess risk analysis of LD, where
the first phase is when the diffusion has not converged in any reasonable sense
to a stationary distribution, and in the second phase when the diffusion has
converged to a variant of Gibbs distribution. Our universality results
crucially rely on the dynamics of LD. When it has converged to a stationary
distribution, we obtain the optimal bounds under $\epsilon$-DP. When it is run
only for a very short time $\propto 1/p$, we obtain the optimal bounds under
$(\epsilon,\delta)$-DP. Here, $p$ is the dimensionality of the model space.
Our work initiates a systematic study of DP continuous time optimization. We
believe this may have ramifications in the design of discrete time DP
optimization algorithms analogous to that in the non-private setting, where
continuous time dynamical viewpoints have helped in designing new algorithms,
including the celebrated mirror-descent and Polyak's momentum method.
- Abstract（参考訳）: 本稿では,微分プライベートな経験的リスク最小化(dp-erm)と微分プライベート確率凸最適化(dp-sco)の問題を再検討する。
統計物理学でよく研究されているランジュバン拡散(ld)と呼ばれる連続時間アルゴリズムは、dp-ermとdp-scoの両方に対して、$\epsilon$-dpと$(\epsilon,\delta)$-dpの下で最適なプライバシー/有効性トレードオフを提供する。
LDの均一安定性特性を用いて、[BST14]以降の未解決問題である$\epsilon$-DPの下での$\ell_2$-Lipschitz凸損失に対する最適余剰集団リスクを保証する。
その過程で、私たちは様々な技術ツールを提供しています。
一 隣り合う2つのデータセット上の損失関数を走らせるとき、LDに縛られる新しいR\enyi分散
二 耐雑音性確率勾配降下(SGD)に対するシャミールと張の法則に類似した、終点LDに対する経験的リスク境界の過剰
三 拡散が定常分布に何らかの合理的な意味で収束していないとき及び拡散がギブス分布の変種に収束しているときの二相超過リスク分析
我々の普遍性はLDの力学に大きく依存している。
定常分布に収束すると、$\epsilon$-DP の下で最適境界を得る。
非常に短時間の$\propto 1/p$ でのみ実行されると、$(\epsilon,\delta)$-dp 以下の最適境界が得られる。
ここで、$p$ はモデル空間の次元である。
本研究はDP連続時間最適化の体系的研究を開始する。
これは、離散時間DP最適化アルゴリズムの設計において、連続時間動的視点が新しいアルゴリズムの設計に役立っている非プライベートな設定と類似したものであると信じている。
関連論文リスト
- Convergence of Score-Based Discrete Diffusion Models: A Discrete-Time Analysis [56.442307356162864]
連続時間マルコフ連鎖(CTMC)に基づくスコアベース離散拡散モデルの理論的側面について検討する。
本稿では,事前定義された時間点におけるスコア推定値を利用する離散時間サンプリングアルゴリズムを一般状態空間$[S]d$に導入する。
我々の収束解析はジルサノフ法を用いて離散スコア関数の重要な性質を確立する。
論文 参考訳（メタデータ） (2024-10-03T09:07:13Z) - Taming Nonconvex Stochastic Mirror Descent with General Bregman
Divergence [25.717501580080846]
本稿では、現代の非最適化設定における勾配フォワードミラー(SMD)の収束を再考する。
トレーニングのために,線形ネットワーク問題に対する確率収束アルゴリズムを開発した。
論文 参考訳（メタデータ） (2024-02-27T17:56:49Z) - Distributed Markov Chain Monte Carlo Sampling based on the Alternating
Direction Method of Multipliers [143.6249073384419]
本論文では,乗算器の交互方向法に基づく分散サンプリング手法を提案する。
我々は,アルゴリズムの収束に関する理論的保証と,その最先端性に関する実験的証拠の両方を提供する。
シミュレーションでは,線形回帰タスクとロジスティック回帰タスクにアルゴリズムを配置し,その高速収束を既存の勾配法と比較した。
論文 参考訳（メタデータ） (2024-01-29T02:08:40Z) - 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) - GFlowNet-EM for learning compositional latent variable models [115.96660869630227]
ラテントの後方のモデリングにおける重要なトレードオフは、表現性とトラクタブルな最適化の間にある。
非正規化密度からサンプリングするアルゴリズムであるGFlowNetsを提案する。
GFlowNetsをトレーニングして、後部から潜伏者へのサンプルをトレーニングすることにより、それらの強度をアモータライズされた変分アルゴリズムとして活用する。
論文 参考訳（メタデータ） (2023-02-13T18:24:21Z) - On the Privacy-Robustness-Utility Trilemma in Distributed Learning [7.778461949427662]
本稿では,少数の対向マシンに対してロバスト性を保証するアルゴリズムによって得られた誤差を,まず厳密に解析する。
私たちの分析は、プライバシ、堅牢性、ユーティリティの基本的なトレードオフを示しています。
論文 参考訳（メタデータ） (2023-02-09T17:24:18Z) - The Poisson binomial mechanism for secure and private federated learning [19.399122892615573]
本稿では,分散平均推定(DME)のための離散的差分プライバシー機構を導入し,フェデレーション学習と分析に応用する。
我々は、プライバシー保証の厳密な分析を行い、連続的なガウス機構と同じプライバシーと精度のトレードオフを達成することを示す。
論文 参考訳（メタデータ） (2022-07-09T05:46:28Z) - Differential Privacy of Dirichlet Posterior Sampling [0.0]
ディリクレ後部分布から1枚のドローを放出する固有のプライバシーについて検討する。
トランカットされた集中微分プライバシー(tCDP)の概念により、ディリクレ後方サンプリングの単純なプライバシー保証を導き出すことができる。
論文 参考訳（メタデータ） (2021-10-03T07:41:19Z) - Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy
Amplification by Shuffling [49.43288037509783]
ランダムシャッフルは、局所的ランダム化データの差分プライバシー保証を増幅する。
私たちの結果は、以前の作業よりも単純で、ほぼ同じ保証で差分プライバシーに拡張された新しいアプローチに基づいています。
論文 参考訳（メタデータ） (2020-12-23T17:07:26Z) - Differentially Private Federated Learning with Laplacian Smoothing [72.85272874099644]
フェデレートラーニングは、ユーザ間でプライベートデータを共有せずに、協調的にモデルを学習することで、データのプライバシを保護することを目的としている。
敵は、リリースしたモデルを攻撃することによって、プライベートトレーニングデータを推測することができる。
差別化プライバシは、トレーニングされたモデルの正確性や実用性を著しく低下させる価格で、このような攻撃に対する統計的保護を提供する。
論文 参考訳（メタデータ） (2020-05-01T04:28:38Z) - Distributionally Robust Bayesian Optimization [121.71766171427433]
そこで本研究では,ゼロ次雑音最適化のための分散ロバストなベイズ最適化アルゴリズム(DRBO)を提案する。
提案アルゴリズムは, 種々の設定において, 線形に頑健な後悔を確実に得る。
提案手法は, 実世界のベンチマークと実世界のベンチマークの両方において, 頑健な性能を示す。
論文 参考訳（メタデータ） (2020-02-20T22:04:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。