論文の概要: Gradient Methods Never Overfit On Separable Data
- arxiv url: http://arxiv.org/abs/2007.00028v2
- Date: Thu, 10 Sep 2020 10:51:50 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-15 04:53:11.481435
- Title: Gradient Methods Never Overfit On Separable Data
- Title（参考訳）: 分離可能なデータに対する勾配法
- Authors: Ohad Shamir
- Abstract要約: 標準勾配法は分離可能なデータに過度に適合しないことを示す。
データセットに対するマージン違反数の非漸近的境界を示す。
- 参考スコア（独自算出の注目度）: 31.714928102950584
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A line of recent works established that when training linear predictors over
separable data, using gradient methods and exponentially-tailed losses, the
predictors asymptotically converge in direction to the max-margin predictor. As
a consequence, the predictors asymptotically do not overfit. However, this does
not address the question of whether overfitting might occur non-asymptotically,
after some bounded number of iterations. In this paper, we formally show that
standard gradient methods (in particular, gradient flow, gradient descent and
stochastic gradient descent) never overfit on separable data: If we run these
methods for $T$ iterations on a dataset of size $m$, both the empirical risk
and the generalization error decrease at an essentially optimal rate of
$\tilde{\mathcal{O}}(1/\gamma^2 T)$ up till $T\approx m$, at which point the
generalization error remains fixed at an essentially optimal level of
$\tilde{\mathcal{O}}(1/\gamma^2 m)$ regardless of how large $T$ is. Along the
way, we present non-asymptotic bounds on the number of margin violations over
the dataset, and prove their tightness.
- Abstract（参考訳）: 最近の一連の研究は、線形予測器を分離可能なデータよりも訓練するとき、勾配法と指数関数的尾尾損失を用いて、予測器は漸近的に最大マージン予測器に収束することを示した。
その結果、予測器は漸近的に過度に適合しない。
しかし、これはオーバーフィッティングが非漸近的に起こるかどうかという問題には対処しない。
In this paper, we formally show that standard gradient methods (in particular, gradient flow, gradient descent and stochastic gradient descent) never overfit on separable data: If we run these methods for $T$ iterations on a dataset of size $m$, both the empirical risk and the generalization error decrease at an essentially optimal rate of $\tilde{\mathcal{O}}(1/\gamma^2 T)$ up till $T\approx m$, at which point the generalization error remains fixed at an essentially optimal level of $\tilde{\mathcal{O}}(1/\gamma^2 m)$ regardless of how large $T$ is.
その過程で,データセット上のマージン違反数に対する非漸近的境界を示し,その厳密性を証明する。
関連論文リスト
- Large Stepsize Gradient Descent for Logistic Loss: Non-Monotonicity of the Loss Improves Optimization Efficiency [47.8739414267201]
線形分離可能なデータを用いたロジスティック回帰に一定の段差を持つ勾配降下(GD)を考える。
GD はこの初期振動位相を急速に終了し、$mathcalO(eta)$ steps となり、その後$tildemathcalO (1 / (eta t) )$ convergence rate が得られることを示す。
我々の結果は、予算が$T$ ステップであれば、GD は攻撃的なステップサイズで $tildemathcalO (1/T2)$ の加速損失を達成できることを示している。
論文 参考訳（メタデータ） (2024-02-24T23:10:28Z) - On the Convergence of Gradient Descent for Large Learning Rates [55.33626480243135]
固定ステップサイズを使用すると収束が不可能であることを示す。
正方形損失を持つ線形ニューラルネットワークの場合,これを証明した。
また、勾配に対するリプシッツ連続性のような強い仮定を必要とせず、より一般的な損失に対する収束の不可能性も証明する。
論文 参考訳（メタデータ） (2024-02-20T16:01:42Z) - Tight Risk Bounds for Gradient Descent on Separable Data [33.593203156666746]
分離線形分類に適用した非正規化勾配法の一般化特性について検討した。
リスク低い境界は、この文脈で最初のものであり、与えられたテール崩壊率に対する上限の厳密性を確立する。
論文 参考訳（メタデータ） (2023-03-02T10:31:58Z) - Precise Learning Curves and Higher-Order Scaling Limits for Dot Product
Kernel Regression [41.48538038768993]
本稿では,ドット積カーネルのカーネルリッジ回帰問題に焦点をあてる。
我々は、任意の整数$r$に対して$m approx dr/r!$が常に学習曲線のピークを観測し、複数のサンプルワイズと非自明な振る舞いを複数のスケールで達成する。
論文 参考訳（メタデータ） (2022-05-30T04:21:31Z) - Convergence of First-Order Methods for Constrained Nonconvex
Optimization with Dependent Data [7.513100214864646]
収束$tildeO(t-1/4)$とMoreautildeO(vareps-4)$がスムーズな非最適化のために最悪の場合の複雑性を示す。
適応的なステップサイズと最適収束度を持つ投影勾配法に基づく従属データに対する最初のオンライン非負行列分解アルゴリズムを得る。
論文 参考訳（メタデータ） (2022-03-29T17:59:10Z) - High-probability Bounds for Non-Convex Stochastic Optimization with
Heavy Tails [55.561406656549686]
我々は、勾配推定が末尾を持つ可能性のある一階アルゴリズムを用いたヒルベルト非最適化を考える。
本研究では, 勾配, 運動量, 正規化勾配勾配の収束を高確率臨界点に収束させることと, 円滑な損失に対する最もよく知られた繰り返しを示す。
論文 参考訳（メタデータ） (2021-06-28T00:17:01Z) - Agnostic Learning of Halfspaces with Gradient Descent via Soft Margins [92.7662890047311]
勾配降下は、分類誤差$tilde O(mathsfOPT1/2) + varepsilon$ in $mathrmpoly(d,1/varepsilon)$ time and sample complexity.
論文 参考訳（メタデータ） (2020-10-01T16:48:33Z) - ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。
我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。
有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
論文 参考訳（メタデータ） (2020-08-28T14:46:56Z) - Carath\'eodory Sampling for Stochastic Gradient Descent [79.55586575988292]
本稿では,Tchakaloff と Carath'eodory の古典的な結果から着想を得た手法を提案する。
我々は、測定値の低減を行う降下ステップを適応的に選択する。
これをBlock Coordinate Descentと組み合わせることで、測定の削減を極めて安価に行えるようにします。
論文 参考訳（メタデータ） (2020-06-02T17:52:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。