論文の概要: Mixing Times and Privacy Analysis for the Projected Langevin Algorithm under a Modulus of Continuity

• arxiv url: http://arxiv.org/abs/2501.04134v1
• Date: Tue, 07 Jan 2025 20:46:59 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-09 14:56:26.272930
• Title: Mixing Times and Privacy Analysis for the Projected Langevin Algorithm under a Modulus of Continuity
• Title（参考訳）: 連続率によるランゲヴィン計画アルゴリズムの混合時間とプライバシ解析
• Authors: Mario Bravo, Juan P. Flores-Mella, Cristóbal Guzmán,
• Abstract要約: 我々は、予測ランゲヴィンアルゴリズム(LA)の混合時間とノイズグラディエントDescent(SGD)のプライバシー曲線について検討する。 具体的には、射影LAに対する新しい混合時間境界を導出するが、これはいくつかの重要な場合において、次元自由かつ多対数的である。 サブサンプルノイズSGDアルゴリズムのプライバシー曲線の上限を新たに設定する。
• 参考スコア（独自算出の注目度）: 7.318997639507269
• License:
• Abstract: We study the mixing time of the projected Langevin algorithm (LA) and the privacy curve of noisy Stochastic Gradient Descent (SGD), beyond nonexpansive iterations. Specifically, we derive new mixing time bounds for the projected LA which are, in some important cases, dimension-free and poly-logarithmic on the accuracy, closely matching the existing results in the smooth convex case. Additionally, we establish new upper bounds for the privacy curve of the subsampled noisy SGD algorithm. These bounds show a crucial dependency on the regularity of gradients, and are useful for a wide range of convex losses beyond the smooth case. Our analysis relies on a suitable extension of the Privacy Amplification by Iteration (PABI) framework (Feldman et al., 2018; Altschuler and Talwar, 2022, 2023) to noisy iterations whose gradient map is not necessarily nonexpansive. This extension is achieved by designing an optimization problem which accounts for the best possible R\'enyi divergence bound obtained by an application of PABI, where the tractability of the problem is crucially related to the modulus of continuity of the associated gradient mapping. We show that, in several interesting cases -- including the nonsmooth convex, weakly smooth and (strongly) dissipative -- such optimization problem can be solved exactly and explicitly. This yields the tightest possible PABI-based bounds, where our results are either new or substantially sharper than those in previous works.
• Abstract（参考訳）: 予測されたランゲヴィンアルゴリズム (LA) の混合時間と, 雑音の多い確率勾配Descent (SGD) のプライバシー曲線を, 非拡張的な繰り返しを超えて検討した。 具体的には,射影LAに対する新しい混合時間境界を導出する。これは,いくつかの重要な場合において,スムーズ凸の場合の既存の結果と密に一致し,次元自由かつ多対数的である。 さらに、サブサンプルノイズSGDアルゴリズムのプライバシー曲線の上限を新たに設定する。 これらの境界は勾配の正則性に決定的な依存を示し、滑らかなケースを超えた幅広い凸損失に対して有用である。 我々の分析は、勾配マップが必ずしも使い物にならないようなノイズの多いイテレーションへのPABIフレームワーク(Feldman et al , 2018; Altschuler and Talwar, 2022, 2023)の適切な拡張に依存しています。 この拡張は、PABIの適用により得られる最も可能なR'enyi分散境界を考慮に入れた最適化問題を設計することで達成される。 非滑らか凸、弱滑らかかつ(強く)散逸性を含むいくつかの興味深いケースにおいて、そのような最適化問題は正確かつ明示的に解決できることが示される。 これにより、PABIベースのバウンダリが最も厳格になり、その結果は以前の作品よりも新しいか、はるかにシャープになる。

関連論文リスト

• Linear-Time User-Level DP-SCO via Robust Statistics [55.350093142673316]
  ユーザレベルの差分プライベート凸最適化(DP-SCO)は、マシンラーニングアプリケーションにおけるユーザのプライバシ保護の重要性から、大きな注目を集めている。 微分プライベート勾配勾配(DP-SGD)に基づくような現在の手法は、しばしば高雑音蓄積と準最適利用に苦しむ。 これらの課題を克服するために、ロバストな統計、特に中央値とトリミング平均を利用する新しい線形時間アルゴリズムを導入する。
  論文  参考訳（メタデータ） (2025-02-13T02:05:45Z)
• From Gradient Clipping to Normalization for Heavy Tailed SGD [19.369399536643773]
  最近の実証的な証拠は、機械学習の応用が重尾ノイズを伴い、実際に有界分散の標準的な仮定に挑戦していることを示している。 本稿では, 勾配依存型雑音収束問題において, テール雑音下での厳密性を実現することができることを示す。
  論文  参考訳（メタデータ） (2024-10-17T17:59:01Z)
• Differentially Private Optimization with Sparse Gradients [60.853074897282625]
  微分プライベート(DP)最適化問題を個人勾配の空間性の下で検討する。 これに基づいて、スパース勾配の凸最適化にほぼ最適な速度で純粋および近似DPアルゴリズムを得る。
  論文  参考訳（メタデータ） (2024-04-16T20:01:10Z)
• Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems [56.86067111855056]
  構造密度の重み付き雑音によるクリップ最適化問題を考察する。 勾配が有限の順序モーメントを持つとき、$mathcalO(K-(alpha - 1)/alpha)$よりも高速な収束率が得られることを示す。 得られた推定値が無視可能なバイアスと制御可能な分散を持つことを示す。
  論文  参考訳（メタデータ） (2023-11-07T17:39:17Z)
• Efficient Private SCO for Heavy-Tailed Data via Averaged Clipping [40.69950711262191]
  我々は、差分プライベート(DP)を保証する重み付きデータに対する差分プライベート凸最適化について検討する。 我々は,制約付きおよび制約なし凸問題に対するAClipped-dpSGDというアルゴリズムに対して,新たな収束結果を確立し,複雑性境界を改善した。
  論文  参考訳（メタデータ） (2022-06-27T01:39:15Z)
• Differential Privacy Guarantees for Stochastic Gradient Langevin Dynamics [2.9477900773805032]
  定常的なステップサイズで、スムーズかつ強凸な目標に対して、プライバシー損失は指数関数的に速く収束することを示す。 本稿では,従来のDP-SGDライブラリと比較して,本手法の実用性を示す実装を提案する。
  論文  参考訳（メタデータ） (2022-01-28T08:21:31Z)
• Differentiable Annealed Importance Sampling and the Perils of Gradient Noise [68.44523807580438]
  Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。 差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。 我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
  論文  参考訳（メタデータ） (2021-07-21T17:10:14Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)
• Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses [52.039438701530905]
  任意のリプシッツ非平滑凸損失に対して,数種類の勾配勾配降下(SGD)に対して,鋭い上下境界を与える。 我々の限界は、極端に過剰な集団リスクを伴う、微分的にプライベートな非平滑凸最適化のための新しいアルゴリズムを導出することを可能にする。
  論文  参考訳（メタデータ） (2020-06-12T02:45:21Z)

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

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