論文の概要: Stochastic Subgradient Descent on a Generic Definable Function Converges to a Minimizer

• arxiv url: http://arxiv.org/abs/2109.02455v1
• Date: Mon, 6 Sep 2021 13:35:56 GMT
• ステータス: 処理完了
• システム内更新日: 2021-09-07 16:24:14.170500
• Title: Stochastic Subgradient Descent on a Generic Definable Function Converges to a Minimizer
• Title（参考訳）: 最小化器に収束するジェネリック定義可能な関数上の確率的下勾配
• Authors: Sholom Schechtman
• Abstract要約: この研究の最初の部分において、弱凸性仮定が第三のタイプの点に失敗したとき、鋭く反発的な臨界点が現れることを示す。 この研究の第2部では、列上の密度のような仮定の下で、下降降下(SGD)は確率1の急激な反発臨界点を避けることを示した。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: It was previously shown by Davis and Drusvyatskiy that every Clarke critical point of a generic, semialgebraic (and more generally definable in an o-minimal structure), weakly convex function is lying on an active manifold and is either a local minimum or an active strict saddle. In the first part of this work, we show that when the weak convexity assumption fails a third type of point appears: a sharply repulsive critical point. Moreover, we show that the corresponding active manifolds satisfy the Verdier and the angle conditions which were introduced by us in our previous work. In the second part of this work, we show that, under a density-like assumption on the perturbation sequence, the stochastic subgradient descent (SGD) avoids sharply repulsive critical points with probability one. We show that such a density-like assumption could be obtained upon adding a small random perturbation (e.g. a nondegenerate Gaussian) at each iteration of the algorithm. These results, combined with our previous work on the avoidance of active strict saddles, show that the SGD on a generic definable (e.g. semialgebraic) function converges to a local minimum.
• Abstract（参考訳）: Davis と Drusvyatskiy は以前、一般半代数的(そしてより一般には O-極小構造で定義できる)クラークのすべての臨界点は、弱凸函数が活性多様体上にあり、局所最小あるいは活性厳密なサドルであることを示した。 この研究の最初の部分では、弱い凸性の仮定が失敗したとき、第三のタイプの点が現れる:鋭く反発的な臨界点である。 さらに、対応する活性多様体は、我々の以前の研究で導入されたヴェルディエおよび角度条件を満たすことを示す。 本研究の第2部では,摂動列の密度的仮定の下で,確率的劣次降下 (sgd) が確率1で鋭く反発する臨界点を回避できることを示す。 このような密度のような仮定は、小さな乱数摂動(例えば)を加えることで得られる。 アルゴリズムの各イテレーションにおける非退化ガウス型)。 これらの結果は、アクティブな厳密なサドルの回避に関するこれまでの研究と組み合わさって、SGDが一般的な定義可能な(例えば)ものであることを示す。 半代数)関数は局所最小値に収束する。

関連論文リスト

• Convergence Rates for Stochastic Approximation: Biased Noise with Unbounded Variance, and Applications [2.0584253077707477]
  目的関数 $J(cdot)$ の定常点を求めるグラディエント・Descent (SGD) 法の収束特性について検討した。 この結果は、すべての定常点が大域最小値である性質を持つ invex' 関数のクラスに適用できる。
  論文  参考訳（メタデータ） (2023-12-05T15:22:39Z)
• Riemannian stochastic optimization methods avoid strict saddle points [68.80251170757647]
  研究中のポリシーは、確率 1 の厳密なサドル点/部分多様体を避けていることを示す。 この結果は、アルゴリズムの極限状態が局所最小値にしかならないことを示すため、重要な正当性チェックを提供する。
  論文  参考訳（メタデータ） (2023-11-04T11:12:24Z)
• Curvature-Independent Last-Iterate Convergence for Games on Riemannian Manifolds [77.4346324549323]
  本研究では, 多様体の曲率に依存しないステップサイズが, 曲率非依存かつ直線的最終点収束率を達成することを示す。 我々の知る限りでは、曲率非依存率や/または最終点収束の可能性はこれまでに検討されていない。
  論文  参考訳（メタデータ） (2023-06-29T01:20:44Z)
• From Gradient Flow on Population Loss to Learning with Stochastic Gradient Descent [50.4531316289086]
  SGD(Gradient Descent)は、大規模非ルートモデルの学習方法である。 集団損失のGFが収束すると仮定して、総合的な条件 SGD が収束する。 我々は、凸損失のような古典的な設定だけでなく、Retrieval Matrix sq-rootのようなより複雑な問題に対してもGD/SGDを統一的に解析する。
  論文  参考訳（メタデータ） (2022-10-13T03:55:04Z)
• A Stochastic Bregman Primal-Dual Splitting Algorithm for Composite Optimization [2.9112649816695204]
  実バナッハ空間上の凸凹サドル点問題の第一次原始双対解法について検討する。 我々のフレームワークは一般であり、アルゴリズムにおいてブレグマンの発散を誘導するエントロピーの強い凸性を必要としない。 数値的な応用としては、エントロピー的正則化ワッサーシュタイン・バリセンタ問題や、単純体上の正則化逆問題などが挙げられる。
  論文  参考訳（メタデータ） (2021-12-22T14:47:44Z)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  クラスタリングは教師なし学習における基本的なプリミティブである。 最近の研究は、低次手法のクラスに対する低い境界を確立している。 意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
  論文  参考訳（メタデータ） (2021-12-07T18:50:17Z)
• Stochastic Subgradient Descent Escapes Active Strict Saddles on Weakly Convex Functions [5.113513399537608]
  我々は、最近デービスとドルスヴィアツキーによる活性厳密なサドルと呼ばれる臨界点への降下降下(SGD)の非収束性を確立する。 この多様体の外では、クラーク部分微分$f$のノルムは下界である。
  論文  参考訳（メタデータ） (2021-08-04T14:10:17Z)
• Asymptotic Escape of Spurious Critical Points on the Low-rank Matrix Manifold [2.692735698714241]
  低ランク行列多様体が不完全集合であることを考えると、この問題は初めて克服される。 動的低ランク近似と再スケール勾配流を用いることで、いくつかの急激な臨界点を古典的な厳密なサドル点に変換することができることを示す。
  論文  参考訳（メタデータ） (2021-07-20T00:25:54Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  本稿では,ランダムウォークラプラシアンを用いたグラフスペクトル埋め込みが,ノード次数に対して完全に補正されたベクトル表現を生成することを示す。 次数補正ブロックモデルの特別な場合、埋め込みはK個の異なる点に集中し、コミュニティを表す。
  論文  参考訳（メタデータ） (2021-05-03T16:36:27Z)
• 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)
• Approximation Schemes for ReLU Regression [80.33702497406632]
  我々はReLU回帰の根本的な問題を考察する。 目的は、未知の分布から引き出された2乗損失に対して、最も適したReLUを出力することである。
  論文  参考訳（メタデータ） (2020-05-26T16:26:17Z)

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

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