論文の概要: Gradient descent with adaptive stepsize converges (nearly) linearly under fourth-order growth

• arxiv url: http://arxiv.org/abs/2409.19791v1
• Date: Sun, 29 Sep 2024 21:27:00 GMT
• ステータス: 処理完了
• システム内更新日: 2024-11-05 17:39:51.754627
• Title: Gradient descent with adaptive stepsize converges (nearly) linearly under fourth-order growth
• Title（参考訳）: 適応的な段差収束を伴う勾配降下は(ほぼ)4次成長の下で線形に収束する
• Authors: Damek Davis, Dmitriy Drusvyatskiy, Liwei Jiang,
• Abstract要約: 適応的な段差のある勾配降下は、任意の滑らかな関数に対して局所(ほぼ)線形速度で収束することを示す。 私たちが提案する適応的な段階化は、興味深い分解定理から生じる。
• 参考スコア（独自算出の注目度）: 12.452887246184318
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A prevalent belief among optimization specialists is that linear convergence of gradient descent is contingent on the function growing quadratically away from its minimizers. In this work, we argue that this belief is inaccurate. We show that gradient descent with an adaptive stepsize converges at a local (nearly) linear rate on any smooth function that merely exhibits fourth-order growth away from its minimizer. The adaptive stepsize we propose arises from an intriguing decomposition theorem: any such function admits a smooth manifold around the optimal solution -- which we call the ravine -- so that the function grows at least quadratically away from the ravine and has constant order growth along it. The ravine allows one to interlace many short gradient steps with a single long Polyak gradient step, which together ensure rapid convergence to the minimizer. We illustrate the theory and algorithm on the problems of matrix sensing and factorization and learning a single neuron in the overparameterized regime.
• Abstract（参考訳）: 最適化スペシャリストの間では、勾配降下の線型収束は、その最小化子から2次に成長する関数に付随するという考えが有力である。 この研究では、この信念は不正確であると主張する。 適応的な段差のある勾配降下は、その最小値から4階成長しか示さない任意の滑らかな関数に対して局所(ほぼ)線形速度で収束することを示す。 任意のそのような函数は最適解 (ravine) と呼ばれる最適解の周りの滑らかな多様体を許容するので、函数は谷から少なくとも2次に成長し、それに沿って一定の順序展開を持つ。 渓谷は、多くの短い勾配ステップを1つの長いポリアク勾配ステップでインターレースすることができ、これにより最小化器への急激な収束が保証される。 本稿では,行列検出と因子化の問題に関する理論とアルゴリズムについて解説し,パラメータ化状態における単一ニューロンの学習について述べる。

関連論文リスト

• Directional Smoothness and Gradient Methods: Convergence and Adaptivity [16.779513676120096]
  我々は、最適化の経路に沿った目的の条件付けに依存する勾配降下に対する新しい準最適境界を開発する。 我々の証明の鍵となるのは方向の滑らかさであり、これは、目的の上のバウンドを開発するために使用する勾配変動の尺度である。 我々は,方向の滑らかさの知識を使わずとも,ポリアクのステップサイズと正規化GDが高速で経路依存の速度を得ることを示した。
  論文  参考訳（メタデータ） (2024-03-06T22:24:05Z)
• Non-Uniform Smoothness for Gradient Descent [5.64297382055816]
  リプシッツ連続勾配滑らか度条件を一般化する局所一階滑らか度オラクル(LFSO)を導入する。 このオラクルは、適切な修正を施した勾配降下法のために、チューニングの段階化に関するすべての問題情報をエンコードできることを示す。 また、この修正された一階法におけるLFSOは、非常に平坦な最小値を持つ非強凸問題に対して、大域的線形収束率が得られることを示す。
  論文  参考訳（メタデータ） (2023-11-15T00:44:08Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。 最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
  論文  参考訳（メタデータ） (2023-10-20T12:45:12Z)
• MinMax Networks [0.0]
  本稿では,連続的な分数次線形関数に対する離散的なMinMax学習手法について述べる。 制約付き片次線形関数学習の収束速度は、各局所線型領域の指数収束率と等価であることを示す。
  論文  参考訳（メタデータ） (2023-06-15T16:30:33Z)
• Proximal Gradient Descent-Ascent: Variable Convergence under K{\L} Geometry [49.65455534654459]
  有限降下指数パラメータ (GDA) はミニマックス最適化問題の解法として広く応用されている。 本稿では、KL-L型幾何学の収束を研究することにより、そのようなギャップを埋める。
  論文  参考訳（メタデータ） (2021-02-09T05:35:53Z)
• Balancing Rates and Variance via Adaptive Batch-Size for Stochastic Optimization Problems [120.21685755278509]
  本研究は,ステップサイズの減衰が正確な収束に必要であるという事実と,一定のステップサイズがエラーまでの時間でより速く学習するという事実のバランスをとることを目的とする。 ステップサイズのミニバッチを最初から修正するのではなく,パラメータを適応的に進化させることを提案する。
  論文  参考訳（メタデータ） (2020-07-02T16:02:02Z)
• Cogradient Descent for Bilinear Optimization [124.45816011848096]
  双線形問題に対処するために、CoGDアルゴリズム(Cogradient Descent Algorithm)を導入する。 一方の変数は、他方の変数との結合関係を考慮し、同期勾配降下をもたらす。 本アルゴリズムは,空間的制約下での1変数の問題を解くために応用される。
  論文  参考訳（メタデータ） (2020-06-16T13:41:54Z)
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits [99.70167985955352]
  強凸関数のゼロ次最適化問題について検討する。 予測勾配降下アルゴリズムのランダム化近似を考察する。 その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-14T10:42:23Z)
• Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets [71.05306664267832]
  適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。 本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。 実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
  論文  参考訳（メタデータ） (2019-12-26T22:10:10Z)

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

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