論文の概要: Noise is All You Need: Private Second-Order Convergence of Noisy SGD
- arxiv url: http://arxiv.org/abs/2410.06878v1
- Date: Wed, 9 Oct 2024 13:43:17 GMT
- ステータス: 処理完了
- システム内更新日: 2024-10-31 23:47:07.732222
- Title: Noise is All You Need: Private Second-Order Convergence of Noisy SGD
- Title(参考訳): ノイズは必要なものすべて:ノイズの多いSGDの2次収束
- Authors: Dmitrii Avdiukhin, Michael Dinitz, Chenglin Fan, Grigory Yaroslavtsev,
- Abstract要約: プライバシーのために必要となるノイズは、標準の滑らか性仮定の下で既に二階収束を示唆していることが示される。
DP-SGDは、最小限の仮定の下で、二階定常点を見つけるために使用できる。
- 参考スコア(独自算出の注目度): 15.31952197599396
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Private optimization is a topic of major interest in machine learning, with differentially private stochastic gradient descent (DP-SGD) playing a key role in both theory and practice. Furthermore, DP-SGD is known to be a powerful tool in contexts beyond privacy, including robustness, machine unlearning, etc. Existing analyses of DP-SGD either make relatively strong assumptions (e.g., Lipschitz continuity of the loss function, or even convexity) or prove only first-order convergence (and thus might end at a saddle point in the non-convex setting). At the same time, there has been progress in proving second-order convergence of the non-private version of ``noisy SGD'', as well as progress in designing algorithms that are more complex than DP-SGD and do guarantee second-order convergence. We revisit DP-SGD and show that ``noise is all you need'': the noise necessary for privacy already implies second-order convergence under the standard smoothness assumptions, even for non-Lipschitz loss functions. Hence, we get second-order convergence essentially for free: DP-SGD, the workhorse of modern private optimization, under minimal assumptions can be used to find a second-order stationary point.
- Abstract(参考訳): プライベート最適化は機械学習に大きな関心を持つトピックであり、理論と実践の両方において、微分プライベート確率勾配降下(DP-SGD)が重要な役割を果たしている。
さらに、DP-SGDは、堅牢性、機械学習など、プライバシーを超えたコンテキストにおいて強力なツールとして知られている。
DP-SGD の既存の解析は、相対的に強い仮定(例えば、損失関数のリプシッツ連続性、あるいは凸性)を行うか、一階収束のみを証明する(したがって、非凸設定のサドル点で終わる)。
同時に、'`noisy SGD'' の非プライベートバージョンの二階収束の証明や、DP-SGD よりも複雑で二階収束を保証するアルゴリズムの設計の進歩が進んでいる。
我々はDP-SGDを再検討し、'Noise is all you need''を示す: プライバシーに必要なノイズは、Lipschitz非損失関数であっても、標準の滑らかさ仮定の下で既に二階収束を示唆している。
したがって、基本的には2階収束は自由である: DP-SGD は、最小の仮定の下で、二階定常点を見つけるために使用できる。
関連論文リスト
- Differentially Private Random Block Coordinate Descent [51.62669821275571]
スケッチ行列を用いて各反復における確率の異なる複数の座標を選択する差分プライベートな座標降下法を提案する。
提案アルゴリズムはDP-CDと従来のDP-SGDの両方を一般化し,有効性を保証する。
論文 参考訳(メタデータ) (2024-12-22T15:06:56Z) - Convergent Privacy Loss of Noisy-SGD without Convexity and Smoothness [16.303040664382138]
有界領域上の隠れ状態雑音-SGDアルゴリズムの差分プライバシー(DP)保証について検討する。
我々は非滑らかな非滑らかな損失に対して収束R'enyi DPを証明した。
我々はまた、滑らかな凸損失に対する最先端の結果と比較して、厳格に優れたプライバシー境界を提供する。
論文 参考訳(メタデータ) (2024-10-01T20:52:08Z) - It's Our Loss: No Privacy Amplification for Hidden State DP-SGD With Non-Convex Loss [0.76146285961466]
特定の損失関数に対して、DP-SGDの最終繰り返しは、最終損失関数と同じくらい多くの情報をリークすることを示す。
DP-SGDは一般にすべての(非)損失関数に対してプライバシーの増幅は不可能である。
論文 参考訳(メタデータ) (2024-07-09T01:58:19Z) - How Private are DP-SGD Implementations? [61.19794019914523]
2種類のバッチサンプリングを使用する場合、プライバシ分析の間に大きなギャップがあることが示される。
その結果,2種類のバッチサンプリングでは,プライバシ分析の間に大きなギャップがあることが判明した。
論文 参考訳(メタデータ) (2024-03-26T13:02:43Z) - Differential Privacy of Noisy (S)GD under Heavy-Tailed Perturbations [6.220757855114254]
降下反復音(SGD)に重尾ノイズを注入することは,ここ数年で注目されている。
重み付き摂動を持つSGDは、(0, tildemathcalO (1/n)$ DP保証が得られることを示す。
重み付きノイズ発生機構はガウスの場合と同じようなDP保証を実現し,軽み付きノイズの代替となる可能性が示唆された。
論文 参考訳(メタデータ) (2024-03-04T13:53:41Z) - DPIS: An Enhanced Mechanism for Differentially Private SGD with Importance Sampling [23.8561225168394]
ディファレンシャルプライバシ(DP)は、プライバシ保護の十分に受け入れられた標準となり、ディープニューラルネットワーク(DNN)は、機械学習において非常に成功した。
この目的のための古典的なメカニズムはDP-SGDであり、これは訓練に一般的に使用される勾配降下(SGD)の微分プライベートバージョンである。
DPISは,DP-SGDのコアのドロップイン代替として使用できる,微分プライベートなSGDトレーニングのための新しいメカニズムである。
論文 参考訳(メタデータ) (2022-10-18T07:03:14Z) - Normalized/Clipped SGD with Perturbation for Differentially Private
Non-Convex Optimization [94.06564567766475]
DP-SGDとDP-NSGDは、センシティブなトレーニングデータを記憶する大規模モデルのリスクを軽減する。
DP-NSGD は DP-SGD よりも比較的チューニングが比較的容易であるのに対して,これらの2つのアルゴリズムは同様の精度を実現する。
論文 参考訳(メタデータ) (2022-06-27T03:45:02Z) - Differentially Private SGDA for Minimax Problems [83.57322009102973]
本研究は, 勾配勾配降下上昇(SGDA)が原始二重集団リスクの弱さの観点から最適に有効であることを示す。
これは、非滑らかで強固なコンケーブ設定において、初めて知られている結果である。
論文 参考訳(メタデータ) (2022-01-22T13:05:39Z) - Smoothed Differential Privacy [55.415581832037084]
微分プライバシー(DP)は、最悪のケース分析に基づいて広く受け入れられ、広く適用されているプライバシーの概念である。
本稿では, 祝賀されたスムーズな解析の背景にある最悪の平均ケースのアイデアに倣って, DPの自然な拡張を提案する。
サンプリング手順による離散的なメカニズムはDPが予測するよりもプライベートであるのに対して,サンプリング手順による連続的なメカニズムはスムーズなDP下では依然としてプライベートではないことが証明された。
論文 参考訳(メタデータ) (2021-07-04T06:55:45Z) - Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses [52.039438701530905]
任意のリプシッツ非平滑凸損失に対して,数種類の勾配勾配降下(SGD)に対して,鋭い上下境界を与える。
我々の限界は、極端に過剰な集団リスクを伴う、微分的にプライベートな非平滑凸最適化のための新しいアルゴリズムを導出することを可能にする。
論文 参考訳(メタデータ) (2020-06-12T02:45:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。