論文の概要: Stability vs Implicit Bias of Gradient Methods on Separable Data and
Beyond
- arxiv url: http://arxiv.org/abs/2202.13441v1
- Date: Sun, 27 Feb 2022 19:56:36 GMT
- ステータス: 処理完了
- システム内更新日: 2022-03-01 17:22:06.152590
- Title: Stability vs Implicit Bias of Gradient Methods on Separable Data and
Beyond
- Title（参考訳）: 分離データとそれを超えるグラディエント手法の安定性と暗示バイアス
- Authors: Matan Schliserman and Tomer Koren
- Abstract要約: 分離線形分類に適用された非正規化勾配に基づく学習手順の一般化特性に着目する。
この一般化についてさらに統一的な説明をし、実現可能性と自己有界性(self-boundedness)と呼ぶ。
これらのケースのいくつかでは、文献における既存の一般化誤差境界に対して、我々の境界は著しく改善される。
- 参考スコア（独自算出の注目度）: 33.593203156666746
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: An influential line of recent work has focused on the generalization
properties of unregularized gradient-based learning procedures applied to
separable linear classification with exponentially-tailed loss functions. The
ability of such methods to generalize well has been attributed to the their
implicit bias towards large margin predictors, both asymptotically as well as
in finite time. We give an additional unified explanation for this
generalization and relate it to two simple properties of the optimization
objective, that we refer to as realizability and self-boundedness. We introduce
a general setting of unconstrained stochastic convex optimization with these
properties, and analyze generalization of gradient methods through the lens of
algorithmic stability. In this broader setting, we obtain sharp stability
bounds for gradient descent and stochastic gradient descent which apply even
for a very large number of gradient steps, and use them to derive general
generalization bounds for these algorithms. Finally, as direct applications of
the general bounds, we return to the setting of linear classification with
separable data and establish several novel test loss and test accuracy bounds
for gradient descent and stochastic gradient descent for a variety of loss
functions with different tail decay rates. In some of these case, our bounds
significantly improve upon the existing generalization error bounds in the
literature.
- Abstract（参考訳）: 最近の研究の影響力ある線は、指数的尾の損失関数を持つ分離線形分類に適用された非正規化勾配に基づく学習手順の一般化特性に焦点を当てている。
このような方法をうまく一般化する能力は、非漸近的にも有限時間においても、大きなマージン予測者に対する暗黙のバイアスに起因している。
この一般化についてさらに統一的な説明を加え、最適化目的の2つの単純な性質、すなわち実現可能性と自己有界性(self-boundedness)を関連付ける。
これらの特性と制約のない確率凸最適化の一般的な設定を導入し、アルゴリズム安定性のレンズを通して勾配法の一般化を解析する。
この広義の設定では、非常に多くの勾配ステップにも適用できる勾配降下と確率勾配降下に対する鋭い安定性境界を求め、これらのアルゴリズムの一般化境界を導出するためにそれらを用いる。
最後に、一般境界の直接適用として、分離可能なデータによる線形分類の設定に戻り、異なる尾崩壊率の様々な損失関数に対して、勾配降下と確率勾配降下のための新しいテスト損失とテスト精度境界を確立する。
これらのケースのいくつかでは、文献における既存の一般化誤差境界を大幅に改善する。
関連論文リスト
- Gradient-Variation Online Learning under Generalized Smoothness [56.38427425920781]
勾配変分オンライン学習は、オンライン関数の勾配の変化とともにスケールする後悔の保証を達成することを目的としている。
ニューラルネットワーク最適化における最近の取り組みは、一般化された滑らかさ条件を示唆し、滑らかさは勾配ノルムと相関する。
ゲームにおける高速収束と拡張逆最適化への応用について述べる。
論文 参考訳（メタデータ） (2024-08-17T02:22:08Z) - Non-Uniform Smoothness for Gradient Descent [5.64297382055816]
リプシッツ連続勾配滑らか度条件を一般化する局所一階滑らか度オラクル(LFSO)を導入する。
このオラクルは、適切な修正を施した勾配降下法のために、チューニングの段階化に関するすべての問題情報をエンコードできることを示す。
また、この修正された一階法におけるLFSOは、非常に平坦な最小値を持つ非強凸問題に対して、大域的線形収束率が得られることを示す。
論文 参考訳（メタデータ） (2023-11-15T00:44:08Z) - The Inductive Bias of Flatness Regularization for Deep Matrix
Factorization [58.851514333119255]
この研究は、ディープ線形ネットワークにおけるヘッセン解の最小トレースの帰納バイアスを理解するための第一歩となる。
測定値の標準等尺性(RIP)が1より大きいすべての深さについて、ヘッセンのトレースを最小化することは、対応する終端行列パラメータのシャッテン 1-ノルムを最小化するのとほぼ同値であることを示す。
論文 参考訳（メタデータ） (2023-06-22T23:14:57Z) - Convex and Non-convex Optimization Under Generalized Smoothness [69.69521650503431]
凸法と非最適化法の分析は、しばしばリプシッツ勾配を必要とし、この軌道による解析を制限する。
最近の研究は、非一様滑らか性条件を通した勾配設定を一般化している。
論文 参考訳（メタデータ） (2023-06-02T04:21:59Z) - Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector
Problems [98.34292831923335]
オンライン相関解析の問題から,emphStochastic Scaled-Gradient Descent (SSD)アルゴリズムを提案する。
我々はこれらのアイデアをオンライン相関解析に適用し、局所収束率を正規性に比例した最適な1時間スケールのアルゴリズムを初めて導いた。
論文 参考訳（メタデータ） (2021-12-29T18:46:52Z) - High-probability Bounds for Non-Convex Stochastic Optimization with
Heavy Tails [55.561406656549686]
我々は、勾配推定が末尾を持つ可能性のある一階アルゴリズムを用いたヒルベルト非最適化を考える。
本研究では, 勾配, 運動量, 正規化勾配勾配の収束を高確率臨界点に収束させることと, 円滑な損失に対する最もよく知られた繰り返しを示す。
論文 参考訳（メタデータ） (2021-06-28T00:17:01Z) - Benign Overfitting of Constant-Stepsize SGD for Linear Regression [122.70478935214128]
帰納バイアスは 経験的に過剰フィットを防げる中心的存在です
この研究は、この問題を最も基本的な設定として考慮している: 線形回帰に対する定数ステップサイズ SGD。
我々は、(正規化されていない)SGDで得られるアルゴリズム正則化と、通常の最小二乗よりも多くの顕著な違いを反映する。
論文 参考訳（メタデータ） (2021-03-23T17:15:53Z) - Stochasticity helps to navigate rough landscapes: comparing
gradient-descent-based algorithms in the phase retrieval problem [8.164433158925593]
本研究では,動的降下,永続勾配,ランジュバン景観降下などの解析ベースアルゴリズムについて検討する。
統計的軌道からの統計場理論をアルゴリズムにフルタイムで適用し、開始時と大規模なシステムサイズで適用します。
論文 参考訳（メタデータ） (2021-03-08T17:06:18Z) - Exact Linear Convergence Rate Analysis for Low-Rank Symmetric Matrix
Completion via Gradient Descent [22.851500417035947]
因数分解に基づく勾配降下は、因数分解行列の完備化を解くためのスケーラブルで効率的なアルゴリズムである。
勾配勾配降下は, 地球自然問題の解を推定するために, 高速収束を楽しむことを示す。
論文 参考訳（メタデータ） (2021-02-04T03:41:54Z) - Information-Theoretic Generalization Bounds for Stochastic Gradient
Descent [13.757095663704858]
局所統計に依存する技術的誤りの限界を提供する。
主な要因は、勾配の客観的な分散、勾配の滑らかさ、摂動に対する損失関数の感度である。
我々の鍵となるツールは、以前SGDのランダム化された変種を解析するために使われた情報理論の一般化境界と、経路の摂動解析を組み合わせることである。
論文 参考訳（メタデータ） (2021-02-01T16:00:34Z) - Implicit Gradient Regularization [18.391141066502644]
勾配降下は、過度に適合せず、明示的な正規化もなく、ディープニューラルネットワークを最適化するのに驚くほど適しています。
我々はImplicit Gradient Regularization (IGR)と呼び、後方誤差解析を用いて正規化のサイズを計算する。
論文 参考訳（メタデータ） (2020-09-23T14:17:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。