論文の概要: First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities

• arxiv url: http://arxiv.org/abs/2305.15938v2
• Date: Sat, 30 Mar 2024 13:50:06 GMT
• ステータス: 処理完了
• システム内更新日: 2024-04-02 15:54:17.684166
• Title: First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities
• Title（参考訳）: マルコフ雑音を用いた一次法-加速度から変分不等式へ
• Authors: Aleksandr Beznosikov, Sergey Samsonov, Marina Sheshukova, Alexander Gasnikov, Alexey Naumov, Eric Moulines,
• Abstract要約: 本稿では,一階変分法の理論解析のための統一的アプローチを提案する。 提案手法は非線形勾配問題とモンテカルロの強い問題の両方をカバーする。 凸法最適化問題の場合、オラクルに強く一致するような境界を与える。
• 参考スコア（独自算出の注目度）: 91.46841922915418
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper delves into stochastic optimization problems that involve Markovian noise. We present a unified approach for the theoretical analysis of first-order gradient methods for stochastic optimization and variational inequalities. Our approach covers scenarios for both non-convex and strongly convex minimization problems. To achieve an optimal (linear) dependence on the mixing time of the underlying noise sequence, we use the randomized batching scheme, which is based on the multilevel Monte Carlo method. Moreover, our technique allows us to eliminate the limiting assumptions of previous research on Markov noise, such as the need for a bounded domain and uniformly bounded stochastic gradients. Our extension to variational inequalities under Markovian noise is original. Additionally, we provide lower bounds that match the oracle complexity of our method in the case of strongly convex optimization problems.
• Abstract（参考訳）: 本稿ではマルコフ雑音を含む確率的最適化問題について述べる。 確率的最適化と変分不等式に対する一階勾配法の理論解析のための統一的なアプローチを提案する。 提案手法は,非凸および強凸の最小化問題のシナリオを網羅する。 雑音列の混合時間に最適な(線形)依存を実現するために,マルチレベルモンテカルロ法に基づくランダム化バッチ方式を用いる。 さらに,この手法により,有界領域や一様有界確率勾配といったマルコフ雑音に関するこれまでの研究の限界仮定を排除できる。 マルコフ雑音下での変分不等式への拡張はオリジナルである。 さらに,厳密な凸最適化問題の場合,本手法のオラクル複雑性に適合する低境界を提供する。

関連論文リスト

• High-Probability Convergence for Composite and Distributed Stochastic Minimization and Variational Inequalities with Heavy-Tailed Noise [96.80184504268593]
  グラデーション、クリッピングは、優れた高確率保証を導き出すアルゴリズムの鍵となる要素の1つである。 クリッピングは、合成および分散最適化の一般的な方法の収束を損なう可能性がある。
  論文  参考訳（メタデータ） (2023-10-03T07:49:17Z)
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。 これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
  論文  参考訳（メタデータ） (2023-02-02T10:37:23Z)
• Tradeoffs between convergence rate and noise amplification for momentum-based accelerated optimization algorithms [8.669461942767098]
  モーメントに基づく1次最適化アルゴリズムについて検討し, 繰り返しが付加的な白色雑音を受ける場合について検討した。 強い凸2次問題に対しては、雑音増幅の定量化のために最適化変数における誤差の定常分散を用いる。 雑音増幅と定位時間のバランスをとるアルゴリズムの2つのパラメータ化ファミリを導入する。
  論文  参考訳（メタデータ） (2022-09-24T04:26:30Z)
• Tight Last-Iterate Convergence of the Extragradient Method for Constrained Monotone Variational Inequalities [4.6193503399184275]
  制約付きモノトンおよびリプシッツの変分不等式について, 過次法の最終点収束率を示す。 我々は,2乗法プログラミングのパワーと,指数関数法更新規則の低次元性を組み合わせた新しい手法を開発した。
  論文  参考訳（メタデータ） (2022-04-20T05:12:11Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)
• Sparse recovery by reduced variance stochastic approximation [5.672132510411465]
  雑音観測によるスパース信号回復問題に対する反復2次最適化ルーチンの適用について論じる。 本稿では,Median-of-Meansのような手法を用いて,対応するソリューションの信頼性を向上する方法について述べる。
  論文  参考訳（メタデータ） (2020-06-11T12:31:20Z)
• Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping [69.9674326582747]
  そこで本研究では,重み付き分散雑音を用いたスムーズな凸最適化のための,クリップ付きSSTMと呼ばれる新しい1次高速化手法を提案する。 この場合、最先端の結果を上回る新たな複雑さが証明される。 本研究は,SGDにおいて,ノイズに対する光細かな仮定を伴わずにクリッピングを施した最初の非自明な高確率複雑性境界を導出した。
  論文  参考訳（メタデータ） (2020-05-21T17:05:27Z)
• Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalities [14.848525762485872]
  非拡張写像、単調リプシッツ作用素、近位写像の間の接続を利用して、単調包含問題に対する準最適解を得る。 これらの結果は、変分不等式問題に対する強い解の近似、凸凸凹 min-max 最適化問題の近似、および min-max 最適化問題における勾配のノルムの最小化について、ほぼ最適に保証される。
  論文  参考訳（メタデータ） (2020-02-20T17:12:49Z)

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

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