論文の概要: The rate of convergence of Bregman proximal methods: Local geometry vs. regularity vs. sharpness

• arxiv url: http://arxiv.org/abs/2211.08043v2
• Date: Wed, 2 Aug 2023 09:12:54 GMT
• ステータス: 処理完了
• システム内更新日: 2023-08-03 18:13:17.830849
• Title: The rate of convergence of Bregman proximal methods: Local geometry vs. regularity vs. sharpness
• Title（参考訳）: Bregman近位法の収束率:局所幾何対正規性対シャープネス
• Authors: Wa\"iss Azizian and Franck Iutzeler and J\'er\^ome Malick and Panayotis Mertikopoulos
• Abstract要約: 与えられた手法の収束率は、関連するルジャンドル指数に大きく依存することを示す。 特に、境界解はゼロとノンゼロのルジャンドル指数を持つ手法の分離を示すことを示す。
• 参考スコア（独自算出の注目度）: 33.48987613928269
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We examine the last-iterate convergence rate of Bregman proximal methods - from mirror descent to mirror-prox and its optimistic variants - as a function of the local geometry induced by the prox-mapping defining the method. For generality, we focus on local solutions of constrained, non-monotone variational inequalities, and we show that the convergence rate of a given method depends sharply on its associated Legendre exponent, a notion that measures the growth rate of the underlying Bregman function (Euclidean, entropic, or other) near a solution. In particular, we show that boundary solutions exhibit a stark separation of regimes between methods with a zero and non-zero Legendre exponent: the former converge at a linear rate, while the latter converge, in general, sublinearly. This dichotomy becomes even more pronounced in linearly constrained problems where methods with entropic regularization achieve a linear convergence rate along sharp directions, compared to convergence in a finite number of steps under Euclidean regularization.
• Abstract（参考訳）: ミラー降下からミラープロックスおよび楽観的変種へのブレグマン近位法のラストイテレート収束速度を,この手法を定義するプロキシマップによって誘導される局所幾何の関数として検討する。 一般論として、制約付き非単調な変分不等式の局所解に焦点をあて、与えられた方法の収束率は、その関連するルジャンドル指数(英語版)に大きく依存していることを示し、その解の近傍にあるブルグマン関数(ユークリッド、エントロピーなど)の成長速度を測る概念である。 特に、境界解は 0 と 0 でないルジャンドル指数を持つ方法の間のレギュレーションを極端に分離していることが示される: 前者は線型速度で収束するが、後者は一般に直交的に収束する。 この二分法は、ユークリッド正則化の下で有限ステップの収束よりも、エントロピー正則化の手法が鋭い方向に沿った線形収束率を達成する線形制約付き問題においてさらに顕著になる。

関連論文リスト

• A Unified Theory of Stochastic Proximal Point Methods without Smoothness [52.30944052987393]
  近点法はその数値的安定性と不完全なチューニングに対する頑健性からかなりの関心を集めている。 本稿では,近位点法(SPPM)の幅広いバリエーションの包括的解析について述べる。
  論文  参考訳（メタデータ） (2024-05-24T21:09:19Z)
• Incremental Quasi-Newton Methods with Faster Superlinear Convergence Rates [50.36933471975506]
  各成分関数が強く凸であり、リプシッツ連続勾配とヘシアンを持つ有限和最適化問題を考える。 最近提案されたインクリメンタル準ニュートン法は、BFGSの更新に基づいて、局所的な超線形収束率を達成する。 本稿では、対称ランク1更新をインクリメンタルフレームワークに組み込むことにより、より効率的な準ニュートン法を提案する。
  論文  参考訳（メタデータ） (2024-02-04T05:54:51Z)
• Online Learning Guided Curvature Approximation: A Quasi-Newton Method with Global Non-Asymptotic Superlinear Convergence [22.286753988825048]
  非漸近的超線形収束率を明示する最初の大域的収束準ニュートン法を提案する。 古典的準ニュートン法とは異なり、我々はハイブリッド近位外勾配法に基づいてアルゴリズムを構築する。
  論文  参考訳（メタデータ） (2023-02-16T20:58:09Z)
• Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policies [115.86431674214282]
  我々は、無限水平割引マルコフ決定過程を考察し、自然政策勾配(NPG)とQ-NPG法の収束率を対数線形ポリシークラスで検討する。 両手法が線形収束率と $mathcalO (1/epsilon2)$サンプル複雑度を, 単純で非適応的な幾何的に増加するステップサイズを用いて達成できることを示す。
  論文  参考訳（メタデータ） (2022-10-04T06:17:52Z)
• On the Convergence Rates of Policy Gradient Methods [9.74841674275568]
  有限状態部分空間における幾何的に割引された支配問題を考える。 試料中の直交勾配のパラリゼーションにより、勾配の一般的な複雑さを解析できることが示される。
  論文  参考訳（メタデータ） (2022-01-19T07:03:37Z)
• On Asymptotic Linear Convergence of Projected Gradient Descent for Constrained Least Squares [22.851500417035947]
  この写本は、制約最小二乗の文脈における射影勾配降下の解析のための統一的な枠組みを提示する。 本稿では,PGDの収束解析のレシピを提示し,このレシピを4つの基本的な問題に応用して実証する。
  論文  参考訳（メタデータ） (2021-12-22T09:49:51Z)
• The Last-Iterate Convergence Rate of Optimistic Mirror Descent in Stochastic Variational Inequalities [29.0058976973771]
  本稿では,アルゴリズムの収束率とBregman関数によって誘導される局所幾何学との複雑な関係を示す。 この指数はアルゴリズムの最適ステップサイズポリシーと得られた最適レートの両方を決定する。
  論文  参考訳（メタデータ） (2021-07-05T09:54:47Z)
• On the Convergence of Stochastic Extragradient for Bilinear Games with Restarted Iteration Averaging [96.13485146617322]
  本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。 平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
  論文  参考訳（メタデータ） (2021-06-30T17:51:36Z)
• Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
  ヒルベルト空間の既知の低次元部分空間を探索することにより、確率観測の集合を用いて近似解を計算する手法を検討する。 本稿では,線形関数近似を用いた政策評価問題に対する時間差分学習手法の誤差を正確に評価する方法について述べる。
  論文  参考訳（メタデータ） (2020-12-09T20:19:32Z)
• Iterative Pre-Conditioning for Expediting the Gradient-Descent Method: The Distributed Linear Least-Squares Problem [0.966840768820136]
  本稿では,サーバエージェントネットワークにおけるマルチエージェント線形最小二乗問題について考察する。 エージェントの目標は、個々のローカルデータポイントを共有することなく、すべてのエージェントが保持する集合データポイントに最適に適合する線形モデルを計算することである。 本稿では,データ点の条件付けによる劣化効果を緩和する反復的プレコンディショニング手法を提案する。
  論文  参考訳（メタデータ） (2020-08-06T20:01:18Z)
• Random extrapolation for primal-dual coordinate descent [61.55967255151027]
  本稿では,データ行列の疎度と目的関数の好適な構造に適応する,ランダムに外挿した原始-双対座標降下法を提案する。 一般凸凹の場合, 主対差と目的値に対するシーケンスのほぼ確実に収束と最適サブ線形収束率を示す。
  論文  参考訳（メタデータ） (2020-07-13T17:39:35Z)

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

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