論文の概要: Stochastic first-order methods with multi-extrapolated momentum for highly smooth unconstrained optimization
- arxiv url: http://arxiv.org/abs/2412.14488v1
- Date: Thu, 19 Dec 2024 03:22:47 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-20 13:32:31.554009
- Title: Stochastic first-order methods with multi-extrapolated momentum for highly smooth unconstrained optimization
- Title(参考訳): 高スムーズな非拘束最適化のための多重運動量をもつ確率的一階法
- Authors: Chuan He,
- Abstract要約: 目的関数の高次滑らかさを$f$で利用することにより,マルチスペクトル運動量を持つSFOMの最適化を高速化できることを示す。
本手法は, 対象関数の任意の順序の滑らかさを加速度に利用した最初のSFOMである。
- 参考スコア(独自算出の注目度): 3.8919212824749296
- License:
- Abstract: In this paper we consider an unconstrained stochastic optimization problem where the objective function exhibits a high order of smoothness. In particular, we propose a stochastic first-order method (SFOM) with multi-extrapolated momentum, in which multiple extrapolations are performed in each iteration, followed by a momentum step based on these extrapolations. We show that our proposed SFOM with multi-extrapolated momentum can accelerate optimization by exploiting the high-order smoothness of the objective function $f$. Specifically, assuming that the gradient and the $p$th-order derivative of $f$ are Lipschitz continuous for some $p\ge2$, and under some additional mild assumptions, we establish that our method achieves a sample complexity of $\widetilde{\mathcal{O}}(\epsilon^{-(3p+1)/p})$ for finding a point $x$ satisfying $\mathbb{E}[\|\nabla f(x)\|]\le\epsilon$. To the best of our knowledge, our method is the first SFOM to leverage arbitrary order smoothness of the objective function for acceleration, resulting in a sample complexity that strictly improves upon the best-known results without assuming the average smoothness condition. Finally, preliminary numerical experiments validate the practical performance of our method and corroborate our theoretical findings.
- Abstract(参考訳): 本稿では、目的関数が高次な滑らかさを示すような制約のない確率的最適化問題を考察する。
特に,各反復において複数の外挿を行い,次にこれらの外挿に基づく運動量ステップを施したマルチ外挿運動量をもつ確率的一階法(SFOM)を提案する。
目的関数の高次滑らかさを$f$で利用することにより,マルチスペクトル運動量を持つSFOMの最適化を高速化できることを示す。
具体的には、$f$の勾配と$p$2次微分が、ある$p\ge2$に対してリプシッツ連続であると仮定し、追加の穏やかな仮定の下で、我々の方法が$\widetilde{\mathcal{O}}(\epsilon^{-(3p+1)/p})$のサンプル複雑性を達成することを証明している。
我々の知る限り、我々の手法は、目標関数の任意の順序の滑らかさを加速度に活用する最初のSFOMであり、その結果、平均の滑らかさ条件を仮定することなく、最もよく知られた結果に対して厳密に改善するサンプル複雑性をもたらす。
最後に、予備的な数値実験により、本手法の実用性能を検証し、理論的な知見を裏付ける。
関連論文リスト
- Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity [50.25258834153574]
我々は、(強に)凸 $(L0)$-smooth 関数のクラスに焦点を当て、いくつかの既存のメソッドに対する新しい収束保証を導出する。
特に,スムーズなグラディエント・クリッピングを有するグラディエント・ディフレッシュと,ポリアク・ステップサイズを有するグラディエント・ディフレッシュのコンバージェンス・レートの改善を導出した。
論文 参考訳(メタデータ) (2024-09-23T13:11:37Z) - Stochastic First-Order Methods with Non-smooth and Non-Euclidean Proximal Terms for Nonconvex High-Dimensional Stochastic Optimization [2.0657831823662574]
非問題が非問題である場合、一階法のサンプルは問題次元に線形に依存することがあるが、望ましくない問題に対するものである。
我々のアルゴリズムは距離を使って複雑さを見積もることができる。
MathO (log d) / EuM4。
DISFOM は $mathO (log d) / EuM4 を用いて分散を鋭くすることができることを示す。
論文 参考訳(メタデータ) (2024-06-27T18:38:42Z) - Stochastic Nonsmooth Convex Optimization with Heavy-Tailed Noises:
High-Probability Bound, In-Expectation Rate and Initial Distance Adaptation [22.758674468435302]
重尾雑音系では、勾配と真の速度の差は有限の$p-thモーメントを持つと仮定される。
本稿では,重み付き雑音を用いた非平滑凸最適化の包括的解析を行う。
論文 参考訳(メタデータ) (2023-03-22T03:05:28Z) - Variance-reduced Clipping for Non-convex Optimization [24.765794811146144]
グラディエント・クリッピング(Gradient clipping)は、大規模言語モデリングのようなディープラーニングアプリケーションで用いられる技法である。
最近の実験的な訓練は、秩序の複雑さを緩和する、非常に特別な振る舞いを持っている。
論文 参考訳(メタデータ) (2023-03-02T00:57:38Z) - A Fully First-Order Method for Stochastic Bilevel Optimization [8.663726907303303]
一階勾配オラクルのみが利用できる場合、制約のない二段階最適化問題を考える。
完全一階近似法(F2SA)を提案し,その非漸近収束特性について検討する。
MNISTデータハイパクリーニング実験において,既存の2次手法よりも提案手法の実用性能が優れていることを示す。
論文 参考訳(メタデータ) (2023-01-26T05:34:21Z) - Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation
Constrained Optimization [88.0031283949404]
多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。
提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
論文 参考訳(メタデータ) (2022-12-19T14:48:54Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。
提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
論文 参考訳(メタデータ) (2022-10-23T21:24:37Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳(メタデータ) (2022-06-17T06:10:20Z) - Riemannian stochastic recursive momentum method for non-convex
optimization [36.79189106909088]
我々は,1回の反復で$mathcalOグラデーション評価を行うための atildeOepsilon$-approximate gradient Evaluations 法を提案する。
提案した実験はアルゴリズムの優越性を実証するものである。
論文 参考訳(メタデータ) (2020-08-11T07:05:58Z) - Second-Order Information in Non-Convex Stochastic Optimization: Power
and Limitations [54.42518331209581]
私たちは発見するアルゴリズムを見つけます。
epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using
$(epsilon,gamma)$surimateランダムランダムポイント。
ここでの私たちの下限は、ノイズのないケースでも新規です。
論文 参考訳(メタデータ) (2020-06-24T04:41:43Z) - Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。
特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
論文 参考訳(メタデータ) (2020-02-10T23:23:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。