論文の概要: Stochastic Heavy Ball with Polyak Step Size and Armijo Line Search: A General Convergence Analysis

• arxiv url: http://arxiv.org/abs/2609.36668v1
• Date: Tue, 29 Sep 2026 04:09:14 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-30 21:28:47.174339
• Title: Stochastic Heavy Ball with Polyak Step Size and Armijo Line Search: A General Convergence Analysis
• Title（参考訳）: Polyak Step Size と Armijo Line Search を用いた確率重球の一般収束解析
• Abstract要約: 本稿では,Polyak ステップサイズとArmijo ライン探索手法の統一収束解析を開発した。 我々は、PSの変動が減少するSHBの正確な最適性や定常性にほぼ確実に収束することを証明する。
• 参考スコア（独自算出の注目度）: 15.737250249366781
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Polyak step size (PS) and Armijo line search (ALS) have received increasing attention in stochastic optimization, with encouraging empirical performance and theoretical guarantees. However, their convergence theory for stochastic heavy ball (SHB) methods remains limited. In this work, we develop a unified convergence analysis for SHB equipped with PS and ALS. To this end, we introduce a modified Armijo rule that closely parallels the Polyak step size, together with a decoupling analysis that isolates the historical dependence induced by momentum. For SHB with standard PS and ALS, we establish expected convergence for strongly convex, convex, and non-convex objectives without interpolation or restrictive conditions on the momentum parameter. Under interpolation or strong growth, we further strengthen the results to almost sure rates and last-iterate convergence. Moreover, for general settings beyond interpolation, we prove almost sure convergence to the exact optimum or to stationarity for SHB with diminishing variants of PS and ALS. These results provide a more comprehensive theoretical view of Polyak step size and Armijo line search for stochastic heavy ball methods.
• Abstract（参考訳）: Polyak step size (PS) と Armijo line search (ALS) は確率的最適化において注目され、経験的性能と理論的保証が奨励されている。 しかし、確率重球法(SHB)の収束理論はいまだに限られている。 そこで本研究では,PSとALSを備えたSHBの統一収束解析を開発した。 この目的のために、ポリアクステップサイズと密接に平行な修正Armijoルールを導入し、運動量によって引き起こされる歴史的依存を分離するデカップリング解析を行った。 標準PSおよびALSのSHBに対して、運動量パラメータの補間や制限条件を伴わずに、強い凸、凸、および非凸の目標に対する期待収束を確立する。 補間や強い成長の下で、我々はその結果をさらに強化し、ほぼ確実にレートとラスト・イテレートの収束を図った。 さらに、補間以外の一般的な設定については、PSとALSの変動が減少するSHBの正確な最適性や定常性にほぼ確実に収束することが証明される。 これらの結果は、PolyakのステップサイズとArmijoライン探索のより包括的な理論的見解を提供する。

関連論文リスト

• Polyak-Type Extragradient Methods for Monotone Root-Finding Problems [15.294997701022217]
  我々はPolyak-type Extragradient Method(PolyakEG)の統一的決定論的解析を提供する。 まず、すべての成分作用素が共通解を共有するとき、直接変分PolyakSEGの収束を証明します。 また、この条件がなければ、不要なステップサイズを持つPolyakSEGは平均作用素の零点に収束しないかもしれないことも示している。
  論文  参考訳（メタデータ） (2026-09-22T15:27:37Z)
• Quantized Stochastic Primal-Dual Methods for Distributed Optimization under Relaxed Global Geometry [2.15242029196761]
  ランダムな(偏りのない)量子化によってモデル化された勾配と有限ビット通信を用いた分散最適化について検討する。 制限されたセカント不等式 (RSI) の下では、勾配ノイズ、量子化歪み、ネットワーク接続性によって決定される明示的な近傍への線形の縮約が得られる。 PolyakLojasiewicz (PL) の不等式では、同じ量子化環境で線形-近傍収束が得られる。
  論文  参考訳（メタデータ） (2026-06-09T18:18:41Z)
• Fine-grained Analysis of Stability and Generalization for Stochastic Bilevel Optimization [71.33048115652474]
  バイレベル最適化(SBO)は、最近多くの機械学習パラダイムに統合されている。 本稿では,二段階最適化手法の体系的解析について述べる。 結果は再読解を必要とせず、より汎用的な目的関数に適用できる。
  論文  参考訳（メタデータ） (2026-04-05T12:12:58Z)
• Weakly Time-Coupled Approximation of Markov Decision Processes [3.573962752571186]
  有限水平マルコフ決定プロセス(MDPs)は、ベルムダンのバリュエーションやエクササイズ、リアルオプションなど、運用と金融に発生する。 共通近似は基底関数を用いた値関数を表すが、重み付け方法は異なる段階最適化を扱う。 この結合は近似アーキテクチャのアーチファクトであり、段差依存が地平線に依存しない弱時間結合近似(WTCA)を開発する。
  論文  参考訳（メタデータ） (2026-03-13T04:14:42Z)
• Stabilizing Policy Optimization via Logits Convexity [59.242732612484474]
  モデルロジットに対する教師付き微調整損失の凸性は、安定したトレーニングを可能にする上で重要な役割を担っていることを示す。 そこで本研究では,ロジッツ・コンベックス最適化(Logits Convex Optimization, LCO)を提案する。
  論文  参考訳（メタデータ） (2026-03-01T07:40:12Z)
• Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond [63.59034509960994]
  シャッフルに基づく変種(ミニバッチと局所ランダムリシャッフル)について検討する。 ポリアック・ロジャシエヴィチ条件を満たす滑らかな函数に対して、これらのシャッフル型不変量(英語版)(shuffling-based variants)がそれらの置換式よりも早く収束することを示す収束境界を得る。 我々は, 同期シャッフル法と呼ばれるアルゴリズムの修正を提案し, ほぼ均一な条件下では, 下界よりも収束速度が速くなった。
  論文  参考訳（メタデータ） (2021-10-20T02:25:25Z)
• On the Convergence of Stochastic Extragradient for Bilinear Games with Restarted Iteration Averaging [96.13485146617322]
  本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。 平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
  論文  参考訳（メタデータ） (2021-06-30T17:51:36Z)
• The Role of Momentum Parameters in the Optimal Convergence of Adaptive Polyak's Heavy-ball Methods [12.93796690939018]
  適応型Polyak's Heavy-ball (HB) 法は最適な個人収束率を$O(frac1sqrtt)$とする。 新しい解析では,hb運動量とその時間的変動が凸最適化の高速化にどのように役立つかを示す。
  論文  参考訳（メタデータ） (2021-02-15T02:57:14Z)
• Linear Last-iterate Convergence in Constrained Saddle-point Optimization [48.44657553192801]
  我々は、OGDA(Optimistic Gradient Descent Ascent)とOMWU(Optimistic Multiplicative Weights Update)に対する最終段階の独特さの理解を著しく拡大する。 平衡が一意である場合、線形終端収束は、値が普遍定数に設定された学習速度で達成されることを示す。 任意のポリトープ上の双線型ゲームがこの条件を満たすことを示し、OGDAは一意の平衡仮定なしで指数関数的に高速に収束することを示した。
  論文  参考訳（メタデータ） (2020-06-16T20:53:04Z)
• Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition [52.08417569774822]
  本稿では,深層学習(深層AUC)により注目度が高まっている,円滑な非凹部min-max問題の解法に焦点をあてる。
  論文  参考訳（メタデータ） (2020-06-12T00:32:21Z)

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

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