Fugu-MT 論文翻訳(概要): On a Faster $R$-Linear Convergence Rate of the Barzilai-Borwein Method

論文の概要: On a Faster $R$-Linear Convergence Rate of the Barzilai-Borwein Method

arxiv url: http://arxiv.org/abs/2101.00205v2
Date: Fri, 22 Jan 2021 09:31:58 GMT
ステータス: 処理完了
システム内更新日: 2021-04-16 11:06:58.889639
Title: On a Faster $R$-Linear Convergence Rate of the Barzilai-Borwein Method
Title（参考訳）: Barzilai-Borwein法のより高速な$R$-Linear収束率について
Authors: Dawei Li and Ruoyu Sun
Abstract要約: bb 法は、強凸二次問題に対して 1-1/kappa$ のレートで r$ を線形に収束させることを証明し、ここで $kappa$ は条件数である。理論的な収束率を持つ例が構成され、境界の厳密さを示している。
参考スコア（独自算出の注目度）: 13.999702345704511
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: The Barzilai-Borwein (BB) method has demonstrated great empirical success in nonlinear optimization. However, the convergence speed of BB method is not well understood, as the known convergence rate of BB method for quadratic problems is much worse than the steepest descent (SD) method. Therefore, there is a large discrepancy between theory and practice. To shrink this gap, we prove that the BB method converges $R$-linearly at a rate of $1-1/\kappa$, where $\kappa$ is the condition number, for strongly convex quadratic problems. In addition, an example with the theoretical rate of convergence is constructed, indicating the tightness of our bound.
Abstract（参考訳）: Barzilai-Borwein (BB) 法は非線形最適化において実験的な成功を収めた。しかし,二次問題に対するbb法の既知の収束速度は,最急降下法 (sd) よりもかなり悪いため,bb法の収束速度はよく分かっていない。そのため、理論と実践には大きな相違点がある。このギャップを縮小するために、bb 法は 1-1/\kappa$ のレートで r$-線形収束し、ここで $\kappa$ は条件数であり、強凸二次問題に対して収束する。さらに、理論的な収束率を持つ例が構成され、我々の束縛の厳密さを示している。

関連論文リスト

The inexact power augmented Lagrangian method for constrained nonconvex optimization [44.516958213972885]
この研究は、強大な拡張ラグランジアン用語を導入し、拡大項はユークリッドのノルムを権力へと引き上げる。その結果, 長期化に低消費電力を用いると, 残余の減少が遅くなるにもかかわらず, より高速な成長が期待できることがわかった。以上の結果より, 持続時間の短縮には低消費電力が有効であるが, 残留率が低下する傾向が示唆された。
論文参考訳（メタデータ） (2024-10-26T11:31:56Z)
Incremental Quasi-Newton Methods with Faster Superlinear Convergence Rates [50.36933471975506]
各成分関数が強く凸であり、リプシッツ連続勾配とヘシアンを持つ有限和最適化問題を考える。最近提案されたインクリメンタル準ニュートン法は、BFGSの更新に基づいて、局所的な超線形収束率を達成する。本稿では、対称ランク1更新をインクリメンタルフレームワークに組み込むことにより、より効率的な準ニュートン法を提案する。
論文参考訳（メタデータ） (2024-02-04T05:54:51Z)
Multi-Agent Bayesian Optimization with Coupled Black-Box and Affine Constraints [21.38692458445459]
ブラックボックス制約と既知のアフィン制約を結合した分散マルチエージェントベイズ最適化の問題について検討する。単一エージェントの場合と同様の後悔/違反境界を実現するアルゴリズムが提案されている。
論文参考訳（メタデータ） (2023-10-02T08:07:36Z)
Some Primal-Dual Theory for Subgradient Methods for Strongly Convex Optimization [0.0]
我々は、強く凸するが、潜在的に非滑らかな非Lipschitz最適化のための段階的手法を考える。本稿では,古典的下位段階法,近位下位段階法,スイッチング下位段階法に対する等価な2値記述について述べる。
論文参考訳（メタデータ） (2023-05-27T01:56:09Z)
Min-Max Optimization Made Simple: Approximating the Proximal Point Method via Contraction Maps [77.8999425439444]
本稿では,凸/凹凸 min-max 問題に対して,ほぼ最適収束率を許容する一階法を提案する。我々の研究は、近点法の更新規則を精度良く近似できるという事実に基づいている。
論文参考訳（メタデータ） (2023-01-10T12:18:47Z)
A Primal-Dual Approach to Solving Variational Inequalities with General Constraints [54.62996442406718]
Yang et al. (2023) は最近、一般的な変分不等式を解決するために一階勾配法を使う方法を示した。この方法の収束性を証明し、演算子が$L$-Lipschitz と monotone である場合、この手法の最後の繰り返しのギャップ関数が$O(frac1sqrtK)$で減少することを示す。
論文参考訳（メタデータ） (2022-10-27T17:59:09Z)
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)
Accelerating Frank-Wolfe via Averaging Step Directions [2.806911268410107]
ステップ方向が過去のオラクル呼び出しの単純な重み付け平均であるフランク=ウルフの修正を考える。本手法は, スパース多様体が検出された後に, いくつかの問題に対して収束率を向上することを示す。
論文参考訳（メタデータ） (2022-05-24T05:26:25Z)
On the Convergence of Stochastic Extragradient for Bilinear Games with Restarted Iteration Averaging [96.13485146617322]
本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
論文参考訳（メタデータ） (2021-06-30T17:51:36Z)
Fast Rates for the Regret of Offline Reinforcement Learning [69.23654172273085]
無限水平割引決定プロセス(MDP)における固定行動ポリシーによって生成されたオフラインデータからの強化学習の後悔について検討する。最適品質関数 $Q*$ に対する任意の推定が与えられたとき、定義するポリシーの後悔は、$Q*$-estimate の点収束率の指数によって与えられる速度で収束することを示す。
論文参考訳（メタデータ） (2021-01-31T16:17:56Z)
Non-asymptotic Superlinear Convergence of Standard Quasi-Newton Methods [26.328847475942894]
準ニュートンアルゴリズムのブロイデン級の非漸近超線型収束速度を証明した。この結果は, 準ニュートン法に対する非漸近超線形収束率を示すのが最初である。
論文参考訳（メタデータ） (2020-03-30T16:42:41Z)

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