論文の概要: 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) の最もよく知られたアルゴリズムよりもシンプルで効率的である。

関連論文リスト

• Random Scaling and Momentum for Non-smooth Non-convex Optimization [38.443430569753026]
  ニューラルネットワークのトレーニングには、非常に不規則な、特に凸や滑らかな損失関数が必要である。 一般的なトレーニングアルゴリズムは運動量による勾配降下(SGDM)に基づいており、損失が凸あるいは滑らかである場合にのみ解析が適用される。
  論文  参考訳（メタデータ） (2024-05-16T00:52:03Z)
• Nonconvex Stochastic Bregman Proximal Gradient Method for Nonconvex Composite Problems [9.202586157819693]
  非合成対象関数の勾配法は、典型的には微分可能部分のリプシッツ滑らかさに依存する。 非目的の非Lipschitz勾配を扱う近似モデルを提案する。 ステップ選択感度の観点から最適なロバスト性が得られることを示す。
  論文  参考訳（メタデータ） (2023-06-26T08:54:46Z)
• On Convergence of Incremental Gradient for Non-Convex Smooth Functions [63.51187646914962]
  機械学習とネットワーク最適化では、ミスの数と優れたキャッシュを最小化するため、シャッフルSGDのようなアルゴリズムが人気である。 本稿では任意のデータ順序付けによる収束特性SGDアルゴリズムについて述べる。
  論文  参考訳（メタデータ） (2023-05-30T17:47:27Z)
• Efficient Private SCO for Heavy-Tailed Data via Averaged Clipping [40.69950711262191]
  我々は、差分プライベート(DP)を保証する重み付きデータに対する差分プライベート凸最適化について検討する。 我々は,制約付きおよび制約なし凸問題に対するAClipped-dpSGDというアルゴリズムに対して,新たな収束結果を確立し,複雑性境界を改善した。
  論文  参考訳（メタデータ） (2022-06-27T01:39:15Z)
• 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)
• 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)

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

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