論文の概要: Practical Sharpness-Aware Minimization Cannot Converge All the Way to
Optima
- arxiv url: http://arxiv.org/abs/2306.09850v2
- Date: Mon, 26 Jun 2023 15:27:47 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-27 21:53:02.518232
- Title: Practical Sharpness-Aware Minimization Cannot Converge All the Way to
Optima
- Title（参考訳）: 実用的シャープネス認識最小化はオプティマへの道のりで収束しない
- Authors: Dongkuk Si, Chulhee Yun
- Abstract要約: Sharpness-Aware Minimization (SAM) は、$y_t = x_t + rho fracbla f(x_t)lt blablax_t での摂動に基づくステップを取る。
- 参考スコア（独自算出の注目度）: 18.668531108219415
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Sharpness-Aware Minimization (SAM) is an optimizer that takes a descent step
based on the gradient at a perturbation $y_t = x_t + \rho \frac{\nabla
f(x_t)}{\lVert \nabla f(x_t) \rVert}$ of the current point $x_t$. Existing
studies prove convergence of SAM for smooth functions, but they do so by
assuming decaying perturbation size $\rho$ and/or no gradient normalization in
$y_t$, which is detached from practice. To address this gap, we study
deterministic/stochastic versions of SAM with practical configurations (i.e.,
constant $\rho$ and gradient normalization in $y_t$) and explore their
convergence properties on smooth functions with (non)convexity assumptions.
Perhaps surprisingly, in many scenarios, we find out that SAM has limited
capability to converge to global minima or stationary points. For smooth
strongly convex functions, we show that while deterministic SAM enjoys tight
global convergence rates of $\tilde \Theta(\frac{1}{T^2})$, the convergence
bound of stochastic SAM suffers an inevitable additive term $O(\rho^2)$,
indicating convergence only up to neighborhoods of optima. In fact, such
$O(\rho^2)$ factors arise for stochastic SAM in all the settings we consider,
and also for deterministic SAM in nonconvex cases; importantly, we prove by
examples that such terms are unavoidable. Our results highlight vastly
different characteristics of SAM with vs. without decaying perturbation size or
gradient normalization, and suggest that the intuitions gained from one version
may not apply to the other.
- Abstract（参考訳）: Sharpness-Aware Minimization (SAM) は、現在の点$x_t$の摂動の勾配に基づいて降下ステップを取る最適化器である。
既存の研究は、滑らかな函数に対するSAMの収束を証明しているが、それらは減衰する摂動サイズを$\rho$と仮定し、実践から切り離された$y_t$の勾配正規化をしない。
このギャップに対処するために、SAMの決定論的・確率的バージョンを実践的な構成(例えば、定数$\rho$ と $y_t$ の勾配正規化)で研究し、(非)凸性仮定を持つ滑らかな函数上のそれらの収束性を探る。
おそらく、多くのシナリオにおいて、SAM が大域ミニマ点や定常点に収束する能力に制限があることが分かる。
滑らかな強凸函数に対して、決定論的SAMは$\tilde \Theta(\frac{1}{T^2})$の厳密な大域収束率を享受する一方で、確率的SAMの収束境界は必然的な加法的項$O(\rho^2)$を被り、オプティマの近傍のみの収束を示す。
実際、そのような$O(\rho^2)$の因子は、私たちが考慮しているすべての設定において確率的SAMに対して、また非凸の場合において決定論的SAMに対して生じる。
その結果,摂動サイズや勾配正規化を損なうことなく,対数でsamの特性が大きく異なることが明らかとなり,一方のバージョンから得られる直観は他方に当てはまらない可能性が示唆された。
関連論文リスト
- Bilateral Sharpness-Aware Minimization for Flatter Minima [61.17349662062522]
Sharpness-Aware Minimization (SAM) は Max-Sharpness (MaxS) を減らして一般化を促進する
本稿では,現在の重量を囲む周辺地域のトレーニング損失と最小損失の差を利用して,Min-Sharpness (MinS) と表現する。
MaxSとMinSをマージすることで、最適化中により平坦な方向を示すより良いFIを作成しました。特に、このFIをSAMと組み合わせて提案されたバイラテラルSAM(BSAM)に組み込むことにより、SAMよりもより平坦な最小値を求めることができます。
論文 参考訳（メタデータ） (2024-09-20T03:01:13Z) - Transfer Operators from Batches of Unpaired Points via Entropic
Transport Kernels [3.099885205621181]
そこで我々は,最大形推論関数を導出し,計算可能な近似を提案し,それらの特性を解析する。
我々は、ブロック数$N$が無限に近づくと、経験的近似から真の密度を回復できることを示す$Gamma$-convergenceの結果を証明する。
論文 参考訳（メタデータ） (2024-02-13T12:52:41Z) - Convergence Rates for Stochastic Approximation: Biased Noise with Unbounded Variance, and Applications [2.0584253077707477]
目的関数 $J(cdot)$ の定常点を求めるグラディエント・Descent (SGD) 法の収束特性について検討した。
この結果は、すべての定常点が大域最小値である性質を持つ invex' 関数のクラスに適用できる。
論文 参考訳（メタデータ） (2023-12-05T15:22:39Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Achieving the Asymptotically Optimal Sample Complexity of Offline Reinforcement Learning: A DRO-Based Approach [36.88301225561535]
オフライン強化学習は、アクティブな探索なしに、事前に収集されたデータセットから学習することを目的としている。
既存のアプローチでは、不確実性に対する悲観的なスタンスを採用し、探索されていない状態-作用対の報酬を、保守的に値関数を推定する。
分散ロバスト最適化(DRO)に基づくアプローチはこれらの課題にも対処でき、漸近的に最小限の最適化であることを示す。
論文 参考訳（メタデータ） (2023-05-22T17:50:18Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Randomized Coordinate Subgradient Method for Nonsmooth Composite
Optimization [11.017632675093628]
非滑らかな問題に対処するコーディネート型劣階法は、リプシッツ型仮定の性質のセットのため、比較的過小評価されている。
論文 参考訳（メタデータ） (2022-06-30T02:17:11Z) - Sharper Rates and Flexible Framework for Nonconvex SGD with Client and
Data Sampling [64.31011847952006]
我々は、平均$n$スムーズでおそらくは非カラー関数のほぼ定常点を求める問題を再考する。
我々は$smallsfcolorgreen$を一般化し、事実上あらゆるサンプリングメカニズムで確実に動作するようにします。
我々は、スムーズな非カラー状態における最適境界の最も一般的な、最も正確な解析を提供する。
論文 参考訳（メタデータ） (2022-06-05T21:32:33Z) - Thinking Outside the Ball: Optimal Learning with Gradient Descent for
Generalized Linear Stochastic Convex Optimization [37.177329562964765]
我々は凸リプシッツ損失を伴う線形予測、あるいはより一般に一般化線型形式の凸最適化問題を考える。
この設定では、初期反復が明示的な正規化や投影を伴わずにグラディエント Descent (GD) を停止し、過大なエラーを最大$epsilon$で保証することを示した。
しかし、標準球における一様収束は、$Theta (1/epsilon4)$サンプルを用いた最適下界学習を保証できることを示しているが、分布依存球における一様収束に依存している。
論文 参考訳（メタデータ） (2022-02-27T09:41:43Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳（メタデータ） (2020-06-04T17:51:00Z) - A Simple Convergence Proof of Adam and Adagrad [74.24716715922759]
我々はAdam Adagradと$O(d(N)/st)$アルゴリズムの収束の証明を示す。
Adamはデフォルトパラメータで使用する場合と同じ収束$O(d(N)/st)$で収束する。
論文 参考訳（メタデータ） (2020-03-05T01:56:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。