論文の概要: Stochastic Subgradient Descent Escapes Active Strict Saddles on Weakly Convex Functions

• arxiv url: http://arxiv.org/abs/2108.02072v4
• Date: Tue, 25 Jul 2023 12:18:43 GMT
• ステータス: 処理完了
• システム内更新日: 2023-07-26 22:11:32.791644
• Title: Stochastic Subgradient Descent Escapes Active Strict Saddles on Weakly Convex Functions
• Title（参考訳）: ゆるやかな凸関数上のアクティブなスリットサッフルの確率的下行性退化
• Authors: Pascal Bianchi, Walid Hachem and Sholom Schechtman
• Abstract要約: 我々は、最近デービスとドルスヴィアツキーによる活性厳密なサドルと呼ばれる臨界点への降下降下(SGD)の非収束性を確立する。 この多様体の外では、クラーク部分微分$f$のノルムは下界である。
• 参考スコア（独自算出の注目度）: 5.113513399537608
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In non-smooth stochastic optimization, we establish the non-convergence of the stochastic subgradient descent (SGD) to the critical points recently called active strict saddles by Davis and Drusvyatskiy. Such points lie on a manifold $M$ where the function $f$ has a direction of second-order negative curvature. Off this manifold, the norm of the Clarke subdifferential of $f$ is lower-bounded. We require two conditions on $f$. The first assumption is a Verdier stratification condition, which is a refinement of the popular Whitney stratification. It allows us to establish a reinforced version of the projection formula of Bolte \emph{et.al.} for Whitney stratifiable functions, and which is of independent interest. The second assumption, termed the angle condition, allows to control the distance of the iterates to $M$. When $f$ is weakly convex, our assumptions are generic. Consequently, generically in the class of definable weakly convex functions, the SGD converges to a local minimizer.
• Abstract（参考訳）: 非スムース確率最適化では、davis と drusvyatskiy によって最近 active strict saddles と呼ばれる臨界点への確率的劣次降 (sgd) の非収束性を確立する。 そのような点は、函数 $f$ が二階負曲率の方向を持つ多様体 $M$ 上にある。 この多様体の外では、クラーク部分微分$f$のノルムは下界である。 $f$の条件が2つ必要です。 最初の仮定はverdier stratification conditionであり、これは人気のあるwhitney stratificationの改良である。 これにより Bolte \emph{et.al の射影公式の強化版を確立することができる。 ホイットニーの階層化関数で、独立した関心を持つ関数である。 2つ目の仮定は、角度条件と呼ばれ、反復体の距離を$M$に制御することができる。 f$ が弱凸であるとき、我々の仮定は一般的である。 したがって、定義可能な弱凸函数のクラスにおいて、SGDは局所最小化に収束する。

関連論文リスト

• Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity [50.25258834153574]
  我々は、(強に)凸 $(L0)$-smooth 関数のクラスに焦点を当て、いくつかの既存のメソッドに対する新しい収束保証を導出する。 特に,スムーズなグラディエント・クリッピングを有するグラディエント・ディフレッシュと,ポリアク・ステップサイズを有するグラディエント・ディフレッシュのコンバージェンス・レートの改善を導出した。
  論文  参考訳（メタデータ） (2024-09-23T13:11:37Z)
• Convergence Rates for Stochastic Approximation: Biased Noise with Unbounded Variance, and Applications [2.0584253077707477]
  目的関数 $J(cdot)$ の定常点を求めるグラディエント・Descent (SGD) 法の収束特性について検討した。 この結果は、すべての定常点が大域最小値である性質を持つ invex' 関数のクラスに適用できる。
  論文  参考訳（メタデータ） (2023-12-05T15:22:39Z)
• Estimating the minimizer and the minimum value of a regression function under passive design [72.85024381807466]
  最小値 $boldsymbolx*$ と最小値 $f*$ を滑らかで凸な回帰関数 $f$ で推定する新しい手法を提案する。 2次リスクと$boldsymbolz_n$の最適化誤差、および$f*$を推定するリスクについて、漸近的でない上界を導出する。
  論文  参考訳（メタデータ） (2022-11-29T18:38:40Z)
• Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum Minimization [52.25843977506935]
  有限サム構造をもつ$L$-smooth, non-deuction関数に対して, AdaSpider と呼ばれる適応分散法を提案する。 そうすることで、$tildeOleft + st/epsilonコールで$epsilon-stationaryポイントを計算することができます。
  論文  参考訳（メタデータ） (2022-11-03T14:41:46Z)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。 漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
  論文  参考訳（メタデータ） (2022-06-17T06:10:20Z)
• High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad Stepsize [55.0090961425708]
  本研究では,AdaGradのスムーズな非確率問題に対する簡易な高確率解析法を提案する。 我々はモジュラーな方法で解析を行い、決定論的設定において相補的な$mathcal O (1 / TT)$収束率を得る。 我々の知る限りでは、これは真に適応的なスキームを持つAdaGradにとって初めての高い確率である。
  論文  参考訳（メタデータ） (2022-04-06T13:50:33Z)
• A Variance-Reduced Stochastic Accelerated Primal Dual Algorithm [3.2958527541557525]
  このような問題は、堅牢な経験的リスク最小化という文脈で機械学習で頻繁に発生する。 高速化された原始双対 (SAPD) アルゴリズムは勾配雑音に対する頑健な手法であると考えている。 提案手法は,SAPDの実践と理論の両方において改善されていることを示す。
  論文  参考訳（メタデータ） (2022-02-19T22:12:30Z)
• 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)
• Stochastic Subgradient Descent on a Generic Definable Function Converges to a Minimizer [0.0]
  この研究の最初の部分において、弱凸性仮定が第三のタイプの点に失敗したとき、鋭く反発的な臨界点が現れることを示す。 この研究の第2部では、列上の密度のような仮定の下で、下降降下(SGD)は確率1の急激な反発臨界点を避けることを示した。
  論文  参考訳（メタデータ） (2021-09-06T13:35:56Z)
• Convergence Rates of Stochastic Gradient Descent under Infinite Noise Variance [14.06947898164194]
  ヘビーテールは様々なシナリオで勾配降下 (sgd) で現れる。 SGDの収束保証は、潜在的に無限のばらつきを持つ状態依存性および重尾ノイズ下で提供します。 その結果,SGDは無限に分散した重尾雑音下であっても,地球最適値に収束できることが示された。
  論文  参考訳（メタデータ） (2021-02-20T13:45:11Z)
• Escaping Saddle Points for Nonsmooth Weakly Convex Functions via Perturbed Proximal Algorithms [0.0]
  主な結果は、非滑らか関数に対する$epsilon$-approximate Local minimumの新たな特徴に基づいている。 標準的な仮定では、摂動近位点、摂動近位勾配、摂動近位線形アルゴリズムは非滑らかな凸関数に対して$epsilon$-approximate局所最小値を求める。
  論文  参考訳（メタデータ） (2021-02-04T19:17:13Z)

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

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