論文の概要: Beyond Lipschitz: Sharp Generalization and Excess Risk Bounds for Full-Batch GD

• arxiv url: http://arxiv.org/abs/2204.12446v1
• Date: Tue, 26 Apr 2022 17:05:57 GMT
• ステータス: 処理完了
• システム内更新日: 2022-04-27 15:10:20.251307
• Title: Beyond Lipschitz: Sharp Generalization and Excess Risk Bounds for Full-Batch GD
• Title（参考訳）: リプシッツを超えて:gdの鋭い一般化と過剰なリスク限界
• Authors: Konstantinos E. Nikolakakis, Farzin Haddadpour, Amin Karbasi, Dionysios S. Kalogerias
• Abstract要約: 我々は、スムーズな損失(おそらく非Lipschitz)に対するフルバッチグラディエントデセント(GD)に対して、鋭い経路依存および過大なエラー保証を提供する。 我々の全バッチ一般化誤差と過剰リスク境界は、損失が滑らかである(しかし、おそらく非リプシッツ)GDの既存の境界よりもかなり厳密である。
• 参考スコア（独自算出の注目度）: 31.80268332522017
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We provide sharp path-dependent generalization and excess error guarantees for the full-batch Gradient Decent (GD) algorithm for smooth losses (possibly non-Lipschitz, possibly nonconvex). At the heart of our analysis is a novel generalization error technique for deterministic symmetric algorithms, that implies average output stability and a bounded expected gradient of the loss at termination leads to generalization. This key result shows that small generalization error occurs at stationary points, and allows us to bypass Lipschitz assumptions on the loss prevalent in previous work. For nonconvex, convex and strongly convex losses, we show the explicit dependence of the generalization error in terms of the accumulated path-dependent optimization error, terminal optimization error, number of samples, and number of iterations. For nonconvex smooth losses, we prove that full-batch GD efficiently generalizes close to any stationary point at termination, under the proper choice of a decreasing step size. Further, if the loss is nonconvex but the objective is PL, we derive vanishing bounds on the corresponding excess risk. For convex and strongly-convex smooth losses, we prove that full-batch GD generalizes even for large constant step sizes, and achieves a small excess risk while training fast. Our full-batch GD generalization error and excess risk bounds are significantly tighter than the existing bounds for (stochastic) GD, when the loss is smooth (but possibly non-Lipschitz).
• Abstract（参考訳）: 我々は,滑らかな損失(おそらく非リプシッツ,あるいは非凸)に対する全バッチ勾配正規化(gd)アルゴリズムに対して,鋭い経路依存の一般化と過大な誤差保証を提供する。 我々の分析の核心は、決定論的対称アルゴリズムのための新しい一般化誤差法であり、平均出力安定性と終了時の損失の有界な予測勾配が一般化に繋がる。 この鍵となる結果は、小さな一般化誤差が定常点で発生し、以前の研究でよく見られる損失に関するリプシッツの仮定を回避できることを示している。 非凸,凸,強凸の損失に対して,累積経路依存最適化誤差,終端最適化誤差,サンプル数,反復数の観点から一般化誤差の明示的依存性を示す。 非凸スムーズな損失に対して、全バッチ GD は、ステップサイズを減少させる適切な選択の下で、終点の任意の定常点に近く効率的に一般化することを証明する。 さらに、損失が非凸であるが目的がPLである場合、対応する余剰リスクの消滅境界を導出する。 凸と強凸の滑らかな損失に対しては、フルバッチgdが大きな定数ステップサイズでも一般化し、トレーニングが高速である一方でリスクが小さいことが証明される。 完全なgd一般化誤差と過大なリスク境界は、損失が滑らかな場合(おそらくリプシッツではない)、既存のgdの限界よりもかなり厳密である。

関連論文リスト

• Estimating Generalization Performance Along the Trajectory of Proximal SGD in Robust Regression [4.150180443030652]
  本稿では,反復アルゴリズムの軌道に沿った反復の一般化誤差を正確に追跡する推定器を提案する。 結果は、ハマー回帰(英語版)、擬ハマー回帰(英語版)、および非滑らかな正則化子を持つそれらのペナル化変種(英語版)など、いくつかの例を通して説明される。
  論文  参考訳（メタデータ） (2024-10-03T16:13:42Z)
• Select without Fear: Almost All Mini-Batch Schedules Generalize Optimally [38.3493773521059]
  我々は、GD(GD)の上限値と一般化誤差境界値と、決定論的あるいは他の独立なデータとの整合性を確立する。 スムーズで非適応的な非損失に対して、フルバッチ(決定論的)GDが本質的にバッチスケジュールの中で最適であることを示す。
  論文  参考訳（メタデータ） (2023-05-03T16:32:30Z)
• A Non-Asymptotic Moreau Envelope Theory for High-Dimensional Generalized Linear Models [33.36787620121057]
  ガウス空間の任意のクラスの線型予測器を示す新しい一般化境界を証明した。 私たちは、Zhou et al. (2021) の「最適化率」を直接回復するために、有限サンプルバウンドを使用します。 ローカライズされたガウス幅を用いた有界一般化の適用は、一般に経験的リスク最小化に対してシャープであることを示す。
  論文  参考訳（メタデータ） (2022-10-21T16:16:55Z)
• Private Stochastic Optimization With Large Worst-Case Lipschitz Parameter [14.040676498310198]
  我々は、全てのデータに対して最悪のリプシッツパラメータを持つ損失関数を持つ差分プライベート(DP)不等式最適化(SO)について検討する。 スムーズな損失関数に対して、我々は最先端の過剰リスクを持つ線形時間アルゴリズムを提供する。 また,非最適凸損失関数を扱う最初のアルゴリズムも提供する。
  論文  参考訳（メタデータ） (2022-09-15T16:03:23Z)
• Last Iterate Risk Bounds of SGD with Decaying Stepsize for Overparameterized Linear Regression [122.70478935214128]
  勾配降下(SGD)は、多くのディープラーニングアプリケーションでよく一般化されている。 本稿では, 崩壊段階のSGDの最終反復リスク境界に関する問題依存解析を行う。
  論文  参考訳（メタデータ） (2021-10-12T17:49:54Z)
• Benign Overfitting of Constant-Stepsize SGD for Linear Regression [122.70478935214128]
  帰納バイアスは 経験的に過剰フィットを防げる中心的存在です この研究は、この問題を最も基本的な設定として考慮している: 線形回帰に対する定数ステップサイズ SGD。 我々は、(正規化されていない)SGDで得られるアルゴリズム正則化と、通常の最小二乗よりも多くの顕著な違いを反映する。
  論文  参考訳（メタデータ） (2021-03-23T17:15:53Z)
• Large-Scale Methods for Distributionally Robust Optimization [53.98643772533416]
  我々のアルゴリズムは、トレーニングセットのサイズとパラメータの数によらず、多くの評価勾配を必要とすることを証明している。 MNIST と ImageNet の実験により,本手法の 9-36 倍の効率性を持つアルゴリズムの理論的スケーリングが確認された。
  論文  参考訳（メタデータ） (2020-10-12T17:41:44Z)
• Balancing Rates and Variance via Adaptive Batch-Size for Stochastic Optimization Problems [120.21685755278509]
  本研究は,ステップサイズの減衰が正確な収束に必要であるという事実と,一定のステップサイズがエラーまでの時間でより速く学習するという事実のバランスをとることを目的とする。 ステップサイズのミニバッチを最初から修正するのではなく,パラメータを適応的に進化させることを提案する。
  論文  参考訳（メタデータ） (2020-07-02T16:02:02Z)
• Gradient descent follows the regularization path for general losses [33.155195855431344]
  任意の凸損失を持つ線形予測器上での実証的リスク最小化について,勾配降下経路とアルゴリズム非依存正規化経路は同じ方向に収束することを示す。 我々は、広く使われている指数関数的損失の正当化を提供する。
  論文  参考訳（メタデータ） (2020-06-19T17:01:25Z)
• Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses [52.039438701530905]
  任意のリプシッツ非平滑凸損失に対して,数種類の勾配勾配降下(SGD)に対して,鋭い上下境界を与える。 我々の限界は、極端に過剰な集団リスクを伴う、微分的にプライベートな非平滑凸最適化のための新しいアルゴリズムを導出することを可能にする。
  論文  参考訳（メタデータ） (2020-06-12T02:45:21Z)
• Approximation Schemes for ReLU Regression [80.33702497406632]
  我々はReLU回帰の根本的な問題を考察する。 目的は、未知の分布から引き出された2乗損失に対して、最も適したReLUを出力することである。
  論文  参考訳（メタデータ） (2020-05-26T16:26:17Z)

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

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