論文の概要: 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$ は条件数であり、強凸二次問題に対して収束する。
さらに、理論的な収束率を持つ例が構成され、我々の束縛の厳密さを示している。
関連論文リスト
- 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 for Solving Variational Inequalities with
General-form Constraints [81.32297040574083]
Yang et al. (2023) は最近、一階法により等式と不等式制約で変分不等式 (VIs) を解くというオープンな問題に対処した。
本稿では,各イテレーションで約1つのサブプロブレムを解くウォームスタート手法を採用する。
我々はこの収束を証明し、演算子が$L$-Lipschitz および monotone であるとき、この不正確な-ACVI 法の最後の繰り返しのギャップ関数が $mathcalO(frac1sqrtK)$ で減少することを示す。
論文 参考訳(メタデータ) (2022-10-27T17:59:09Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal
Convergence Guarantee [96.71652414591051]
本研究では,非制約問題に対するグローバルなサドル点を求めるために,不正確なニュートン型正規化手法を提案し,解析する。
提案アルゴリズムは,有界集合内に留まるイテレートを生成し,制限されたイテレート関数の項で$O(-2/3)$ギャップに収束することを示す。
論文 参考訳(メタデータ) (2022-10-23T21:24:37Z) - Accelerating Frank-Wolfe via Averaging Step Directions [2.806911268410107]
ステップ方向が過去のオラクル呼び出しの単純な重み付け平均であるフランク=ウルフの修正を考える。
本手法は, スパース多様体が検出された後に, いくつかの問題に対して収束率を向上することを示す。
論文 参考訳(メタデータ) (2022-05-24T05:26:25Z) - A Fast and Accurate Splitting Method for Optimal Transport: Analysis and
Implementation [19.6590956326761]
我々は,高速かつ信頼性の高い大規模最適輸送(OT)問題を,前例のない速度と精度の組み合わせで解く方法を開発した。
ダグラス・ラフフォード分割法に基づいて構築され、近似正規化問題を解く代わりに、元のOT問題に直接取り組んだ。
論文 参考訳(メタデータ) (2021-10-22T12:16:08Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。