論文の概要: Practical Sharpness-Aware Minimization Cannot Converge All the Way to
Optima
- arxiv url: http://arxiv.org/abs/2306.09850v1
- Date: Fri, 16 Jun 2023 13:47:04 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-19 13:40:59.551742
- 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の特性が大きく異なることが明らかとなり,一方のバージョンから得られる直観は他方に当てはまらない可能性が示唆された。
関連論文リスト
- Transfer Operators from Batches of Unpaired Points via Entropic
Transport Kernels [3.099885205621181]
そこで我々は,最大形推論関数を導出し,計算可能な近似を提案し,それらの特性を解析する。
我々は、ブロック数$N$が無限に近づくと、経験的近似から真の密度を回復できることを示す$Gamma$-convergenceの結果を証明する。
論文 参考訳(メタデータ) (2024-02-13T12:52:41Z) - The Sample Complexity Of ERMs In Stochastic Convex Optimization [13.896417716930687]
実際に$tildeO(fracdepsilon+frac1epsilon2)$データポイントも十分であることを示す。
さらに、この結果を一般化し、全ての凸体に対して同様の上界が成り立つことを示す。
論文 参考訳(メタデータ) (2023-11-09T14:29:25Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳(メタデータ) (2023-06-30T08:34:29Z) - Achieving the Minimax Optimal Sample Complexity of Offline Reinforcement
Learning: A DRO-Based Approach [41.45280954901834]
オフライン強化学習は、アクティブな探索なしに、事前に収集されたデータセットから学習することを目的としている。
既存のアプローチでは、探索されていない状態-作用対の報酬を罰することで不確実性に対する悲観的なスタンスを採用している。
分布的にロバストな最適化手法はこれらの課題にも対処でき、最小限の最適化であることを示す。
論文 参考訳(メタデータ) (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) - A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
凸凹対象 $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, ここで、$f$ は局所リプシッツ勾配を持つ凸関数であり、$g$ は凸かつ非滑らかである。
主勾配ステップと2段ステップを交互に交互に行うCondat-Vuアルゴリズムの適応バージョンを提案する。
論文 参考訳(メタデータ) (2021-10-28T14:19:30Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。