論文の概要: Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses
- arxiv url: http://arxiv.org/abs/2006.06914v1
- Date: Fri, 12 Jun 2020 02:45:21 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-22 03:25:37.567869
- Title: Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses
- Title(参考訳): 非滑らか凸損失に対する確率勾配降下の安定性
- Authors: Raef Bassily, Vitaly Feldman, Crist\'obal Guzm\'an, Kunal Talwar
- Abstract要約: 任意のリプシッツ非平滑凸損失に対して,数種類の勾配勾配降下(SGD)に対して,鋭い上下境界を与える。
我々の限界は、極端に過剰な集団リスクを伴う、微分的にプライベートな非平滑凸最適化のための新しいアルゴリズムを導出することを可能にする。
- 参考スコア(独自算出の注目度): 52.039438701530905
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Uniform stability is a notion of algorithmic stability that bounds the worst
case change in the model output by the algorithm when a single data point in
the dataset is replaced. An influential work of Hardt et al. (2016) provides
strong upper bounds on the uniform stability of the stochastic gradient descent
(SGD) algorithm on sufficiently smooth convex losses. These results led to
important progress in understanding of the generalization properties of SGD and
several applications to differentially private convex optimization for smooth
losses.
Our work is the first to address uniform stability of SGD on {\em nonsmooth}
convex losses. Specifically, we provide sharp upper and lower bounds for
several forms of SGD and full-batch GD on arbitrary Lipschitz nonsmooth convex
losses. Our lower bounds show that, in the nonsmooth case, (S)GD can be
inherently less stable than in the smooth case. On the other hand, our upper
bounds show that (S)GD is sufficiently stable for deriving new and useful
bounds on generalization error. Most notably, we obtain the first
dimension-independent generalization bounds for multi-pass SGD in the nonsmooth
case. In addition, our bounds allow us to derive a new algorithm for
differentially private nonsmooth stochastic convex optimization with optimal
excess population risk. Our algorithm is simpler and more efficient than the
best known algorithm for the nonsmooth case Feldman et al. (2020).
- Abstract(参考訳): 一様安定性 (uniform stability) とは、データセット内の1つのデータポイントが置き換えられたときに、アルゴリズムが出力するモデルの最悪の場合の変更を制限するアルゴリズム安定性の概念である。
Hardt et al. (2016) の影響力のある研究は、十分に滑らかな凸損失に対する確率勾配勾配勾配(SGD)アルゴリズムの均一性に強い上限を与える。
これらの結果は、SGDの一般化特性の理解と、滑らかな損失に対する微分プライベート凸最適化へのいくつかの応用に重要な進歩をもたらした。
我々の研究は、SGDの凸損失に対する一様安定性に最初に取り組むものである。
具体的には、任意のリプシッツ非滑らか凸損失に対して、いくつかの形のSGDとフルバッチGDに対して、鋭い上下境界を与える。
我々の下界は、非滑らかな場合、(S)GDはスムーズな場合よりも本質的には安定ではないことを示す。
一方、上界は(S)GDが一般化誤差の新しい有用な境界を導出するのに十分安定であることを示している。
特に、非滑らかな場合の多重パス SGD に対する第一次元独立一般化境界を得る。
さらに, この境界により, 遺伝的にプライベートな非スムース確率凸最適化のための新しいアルゴリズムを導出することができる。
我々のアルゴリズムは、非スムースケース feldman et al. (2020) の最もよく知られたアルゴリズムよりもシンプルで効率的である。
関連論文リスト
- On Convergence of Incremental Gradient for Non-Convex Smooth Functions [63.51187646914962]
機械学習とネットワーク最適化では、ミスの数と優れたキャッシュを最小化するため、シャッフルSGDのようなアルゴリズムが人気である。
本稿では任意のデータ順序付けによる収束特性SGDアルゴリズムについて述べる。
論文 参考訳(メタデータ) (2023-05-30T17:47:27Z) - Benign Underfitting of Stochastic Gradient Descent [72.38051710389732]
本研究では,適切な学習データを得ることで,一般化性能を実現する「従来型」学習ルールとして,勾配降下度(SGD)がどの程度理解されるかを検討する。
類似現象が起こらない近縁な交換SGDを解析し、その集団リスクが実際に最適な速度で収束することを証明する。
論文 参考訳(メタデータ) (2022-02-27T13:25:01Z) - Differentially Private SGDA for Minimax Problems [83.57322009102973]
本研究は, 勾配勾配降下上昇(SGDA)が原始二重集団リスクの弱さの観点から最適に有効であることを示す。
これは、非滑らかで強固なコンケーブ設定において、初めて知られている結果である。
論文 参考訳(メタデータ) (2022-01-22T13:05:39Z) - Optimal Rates for Random Order Online Optimization [60.011653053877126]
敵が損失関数を選択できるカテットガルバー2020onlineについて検討するが、一様にランダムな順序で提示される。
2020onlineアルゴリズムが最適境界を達成し,安定性を著しく向上することを示す。
論文 参考訳(メタデータ) (2021-06-29T09:48:46Z) - Optimal Algorithms for Differentially Private Stochastic Monotone
Variational Inequalities and Saddle-Point Problems [5.051036968777244]
差分プライバシー制約下における変動不等式(SVI)とサドル点不等式問題の最初の系統的研究--(DP)
NISPP(Noisy Inexact Proximal Point)とNSEG(Noisy Extragradient)の2つのアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-04-07T08:37:07Z) - SGD Generalizes Better Than GD (And Regularization Doesn't Help) [39.588906680621825]
我々は、勾配勾配(SGD)の一般化性能と全バッチ勾配(GD)の分離結果を与える。
同じステップ数で、GD はオーバーフィットし、$Omega(1)$ generalization error で解を出力することを示した。
本稿では,GDによる経験的リスクの最小化が,基本的には上記の結果を変えるものではないことを論じ,安定性,暗黙バイアス,一般化における学習アルゴリズムの役割を再考する。
論文 参考訳(メタデータ) (2021-02-01T19:18:40Z) - Stochastic optimization with momentum: convergence, fluctuations, and
traps avoidance [0.0]
本稿では,重球法,ネステロフ加速勾配法(S-NAG),広く使用されているアダム法など,勾配勾配勾配のいくつかの変種を統一する一般最適化手法について検討する。
この回避は、非自明な常微分方程式のノイズ離散化として研究される。
論文 参考訳(メタデータ) (2020-12-07T19:14:49Z) - An improved convergence analysis for decentralized online stochastic
non-convex optimization [17.386715847732468]
本稿では,GT-Loakjasiewics(GT-Loakjasiewics)と呼ばれる手法が,GT-Loakjasiewics(GT-Loakjasiewics)が現在の収束率を満たすことを示す。
結果はすぐに適用できるだけでなく、現在知られている最高の収束率にも適用できる。
論文 参考訳(メタデータ) (2020-08-10T15:29:13Z) - Fine-Grained Analysis of Stability and Generalization for Stochastic
Gradient Descent [55.85456985750134]
我々は,SGDの反復的リスクによって制御される新しい境界を開発する,平均モデル安定性と呼ばれる新しい安定性尺度を導入する。
これにより、最良のモデルの振舞いによって一般化境界が得られ、低雑音環境における最初の既知の高速境界が導かれる。
我々の知る限りでは、このことはSGDの微分不能な損失関数でさえも初めて知られている安定性と一般化を与える。
論文 参考訳(メタデータ) (2020-06-15T06:30:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。