論文の概要: A Generalized Version of Chung's Lemma and its Applications

• arxiv url: http://arxiv.org/abs/2406.05637v1
• Date: Sun, 9 Jun 2024 04:25:10 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-11 18:46:42.938902
• Title: A Generalized Version of Chung's Lemma and its Applications
• Title（参考訳）: Chung's Lemmaの一般化版とその応用
• Authors: Li Jiang, Xiao Li, Andre Milzarek, Junwen Qiu,
• Abstract要約: 我々はChung's lemmaの一般化バージョンを開発し、より一般的なステップサイズルールの族に対する単純な非漸近収束フレームワークを提供する。 解析の副産物として、指数的なステップサイズが目的関数の幾何学に適応し、基礎となる景観の正確な知識を必要とせずに最適な収束率を達成することができることを観察する。
• 参考スコア（独自算出の注目度）: 10.570672679063394
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Chung's lemma is a classical tool for establishing asymptotic convergence rates of (stochastic) optimization methods under strong convexity-type assumptions and appropriate polynomial diminishing step sizes. In this work, we develop a generalized version of Chung's lemma, which provides a simple non-asymptotic convergence framework for a more general family of step size rules. We demonstrate broad applicability of the proposed generalized Chung's lemma by deriving tight non-asymptotic convergence rates for a large variety of stochastic methods. In particular, we obtain partially new non-asymptotic complexity results for stochastic optimization methods, such as stochastic gradient descent and random reshuffling, under a general $(\theta,\mu)$-Polyak-Lojasiewicz (PL) condition and for various step sizes strategies, including polynomial, constant, exponential, and cosine step sizes rules. Notably, as a by-product of our analysis, we observe that exponential step sizes can adapt to the objective function's geometry, achieving the optimal convergence rate without requiring exact knowledge of the underlying landscape. Our results demonstrate that the developed variant of Chung's lemma offers a versatile, systematic, and streamlined approach to establish non-asymptotic convergence rates under general step size rules.
• Abstract（参考訳）: チャンの補題(Chung's lemma)は、強い凸性型仮定と適切な多項式減少ステップサイズの下で(確率的な)最適化手法の漸近収束率を確立する古典的なツールである。 本研究では、より一般的なステップサイズルールの族に対する単純な非漸近収束フレームワークを提供する、Chung's lemmaの一般化版を開発する。 本研究では,多種多様な確率的手法に対する厳密な非漸近収束率を導出することにより,Chung's lemmaの広範な適用性を示す。 特に,確率的勾配降下やランダムリシャッフルといった確率的最適化手法に対して,一般の$(\theta,\mu)$-Polyak-Lojasiewicz (PL)条件の下で,多項式,定数,指数,余弦的なステップサイズルールを含む様々なステップサイズ戦略に対して,部分的に新しい非漸近的複雑性結果を得る。 特に、我々の分析の副産物として、指数的なステップサイズが目的関数の幾何に適応し、基礎となる景観の正確な知識を必要とせずに最適な収束率を達成することができることを観察する。 以上の結果から,Chung's lemma の展開した変種は,一般的なステップサイズルールの下での非漸近収束率を確立するために,多種多様で体系的かつ合理的なアプローチを提供することが示された。

関連論文リスト

• A Unified Theory of Stochastic Proximal Point Methods without Smoothness [52.30944052987393]
  近点法はその数値的安定性と不完全なチューニングに対する頑健性からかなりの関心を集めている。 本稿では,近位点法(SPPM)の幅広いバリエーションの包括的解析について述べる。
  論文  参考訳（メタデータ） (2024-05-24T21:09:19Z)
• Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policies [115.86431674214282]
  我々は、無限水平割引マルコフ決定過程を考察し、自然政策勾配(NPG)とQ-NPG法の収束率を対数線形ポリシークラスで検討する。 両手法が線形収束率と $mathcalO (1/epsilon2)$サンプル複雑度を, 単純で非適応的な幾何的に増加するステップサイズを用いて達成できることを示す。
  論文  参考訳（メタデータ） (2022-10-04T06:17:52Z)
• A Unified Convergence Theorem for Stochastic Optimization Methods [4.94128206910124]
  一連の統一最適化手法に対する収束結果の導出に使用される基本的な統一収束定理を提供する。 直接応用として、一般的な設定下での収束結果をほぼ確実に回復する。
  論文  参考訳（メタデータ） (2022-06-08T14:01:42Z)
• On the Convergence Rates of Policy Gradient Methods [9.74841674275568]
  有限状態部分空間における幾何的に割引された支配問題を考える。 試料中の直交勾配のパラリゼーションにより、勾配の一般的な複雑さを解析できることが示される。
  論文  参考訳（メタデータ） (2022-01-19T07:03:37Z)
• Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems [98.34292831923335]
  オンライン相関解析の問題から,emphStochastic Scaled-Gradient Descent (SSD)アルゴリズムを提案する。 我々はこれらのアイデアをオンライン相関解析に適用し、局所収束率を正規性に比例した最適な1時間スケールのアルゴリズムを初めて導いた。
  論文  参考訳（メタデータ） (2021-12-29T18:46:52Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• Beyond Exact Gradients: Convergence of Stochastic Soft-Max Policy Gradient Methods with Entropy Regularization [20.651913793555163]
  古典的エントロピー正規化政策勾配法をソフトマックス政策パラメトリゼーションで再検討する。 提案したアルゴリズムに対して,大域的最適収束結果と$widetildemathcalO(frac1epsilon2)$のサンプル複雑性を確立する。
  論文  参考訳（メタデータ） (2021-10-19T17:21:09Z)
• On the Convergence of Stochastic Extragradient for Bilinear Games with Restarted Iteration Averaging [96.13485146617322]
  本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。 平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
  論文  参考訳（メタデータ） (2021-06-30T17:51:36Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。 私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。 提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
  論文  参考訳（メタデータ） (2020-07-07T21:26:35Z)
• A Unified Analysis of Stochastic Gradient Methods for Nonconvex Federated Optimization [16.714109768541785]
  非非状態におけるSGD不変量を満たすすべての方法について単一の解析を行う。 また、PL条件下での非非状態におけるより高速な線形収束を得るための統一解析も提供する。
  論文  参考訳（メタデータ） (2020-06-12T08:58:03Z)

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

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