論文の概要: Non-Expansive Mappings in Two-Time-Scale Stochastic Approximation: Finite-Time Analysis

• arxiv url: http://arxiv.org/abs/2501.10806v1
• Date: Sat, 18 Jan 2025 16:00:14 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-22 19:37:19.154177
• Title: Non-Expansive Mappings in Two-Time-Scale Stochastic Approximation: Finite-Time Analysis
• Title（参考訳）: 2時間スケール確率近似における非拡張写像:有限時間解析
• Authors: Siddharth Chandak,
• Abstract要約: より遅い時間スケールが拡張性のないマッピングを持つ2段階のイテレーションについて検討する。 平均二乗誤差は$O (1/k1/4-epsilon)$で減衰し、$epsilon>0$は任意に小さくなる。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Two-time-scale stochastic approximation is an iterative algorithm used in applications such as optimization, reinforcement learning, and control. Finite-time analysis of these algorithms has primarily focused on fixed point iterations where both time-scales have contractive mappings. In this paper, we study two-time-scale iterations, where the slower time-scale has a non-expansive mapping. For such algorithms, the slower time-scale can be considered a stochastic inexact Krasnoselskii-Mann iteration. We show that the mean square error decays at a rate $O(1/k^{1/4-\epsilon})$, where $\epsilon>0$ is arbitrarily small. We also show almost sure convergence of iterates to the set of fixed points. We show the applicability of our framework by applying our results to minimax optimization, linear stochastic approximation, and Lagrangian optimization.
• Abstract（参考訳）: 2時間スケール確率近似(英: two-time-scale stochastic approximation)は、最適化、強化学習、制御などのアプリケーションで使われる反復アルゴリズムである。 これらのアルゴリズムの有限時間解析は主に、両方の時間スケールが縮尺写像を持つ固定点反復に焦点をあてている。 本稿では,より遅い時間スケールが拡張性のないマッピングを持つ2段階の反復について検討する。 そのようなアルゴリズムでは、遅い時間スケールは確率的不正確なクラスノセルスキー・マン反復と見なすことができる。 平均二乗誤差は$O(1/k^{1/4-\epsilon})$で減衰し、$\epsilon>0$は任意に小さい。 また、固定点の集合への反復の収束をほぼ確実に示している。 本稿では,最小値最適化,線形確率近似,ラグランジアン最適化に適用することで,我々のフレームワークの適用性を示す。

関連論文リスト

• $O(1/k)$ Finite-Time Bound for Non-Linear Two-Time-Scale Stochastic Approximation [0.0]
  非線形2時間スケール近似に対して$O (1/k)$の勾配境界を改良した。 この結果は、降下度や2時間スケールのラグランジアン最適化などのアルゴリズムに適用できる。
  論文  参考訳（メタデータ） (2025-04-27T22:45:00Z)
• Finite-Time Bounds for Two-Time-Scale Stochastic Approximation with Arbitrary Norm Contractions and Markovian Noise [7.770605097524015]
  2時間スケール近似(英: Two-time-scale Approximation、SA)は、強化学習と最適化に応用した反復アルゴリズムである。 強化学習の応用により、非線型2時間スケール SA 上の最初の平均正方形を与える。
  論文  参考訳（メタデータ） (2025-03-24T07:03:23Z)
• Fast Nonlinear Two-Time-Scale Stochastic Approximation: Achieving $O(1/k)$ Finite-Sample Complexity [2.5382095320488665]
  本稿では,2つの結合非線形作用素の根を探すために,2時間スケールのモノトン近似の新しい変種を開発することを提案する。 私たちのキーとなるアイデアは、古典的なRuppert-Polyak平均化技術を活用して、それらのサンプルを通して演算子を動的に推定することです。 これらの平均ステップの見積値は、望まれる解を見つけるために、2時間スケールの近似更新で使用される。
  論文  参考訳（メタデータ） (2024-01-23T13:44:15Z)
• Min-Max Optimization Made Simple: Approximating the Proximal Point Method via Contraction Maps [77.8999425439444]
  本稿では,凸/凹凸 min-max 問題に対して,ほぼ最適収束率を許容する一階法を提案する。 我々の研究は、近点法の更新規則を精度良く近似できるという事実に基づいている。
  論文  参考訳（メタデータ） (2023-01-10T12:18:47Z)
• Finite-Time Error Bounds for Greedy-GQ [20.51105692499517]
  We show that Greedy-GQ algorithm converges fast-time error。 我々の分析は、ステップサイズを選択するために、より高速な収束ステップサイズを提供する。
  論文  参考訳（メタデータ） (2022-09-06T15:04:57Z)
• Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergence [69.65563161962245]
  ニュートン法を用いて,滑らかで強凸な目的関数を考える。 最適段階において局所収束に遷移する普遍重み付き平均化スキームが存在することを示す。
  論文  参考訳（メタデータ） (2022-04-20T07:14:21Z)
• Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with Variance Reduction and its Application to Optimization [50.83356836818667]
  勾配ランゲヴィン・ダイナミクスは非エプス最適化問題を解くための最も基本的なアルゴリズムの1つである。 本稿では、このタイプの2つの変種、すなわち、分散還元ランジュバンダイナミクスと再帰勾配ランジュバンダイナミクスを示す。
  論文  参考訳（メタデータ） (2022-03-30T11:39:00Z)
• Mirror Descent Strikes Again: Optimal Stochastic Convex Optimization under Infinite Noise Variance [17.199063087458907]
  我々は一様凸ミラーマップのクラスを用いてミラーDescentアルゴリズムの収束率を定量化する。 このアルゴリズムは明確な勾配クリッピングや正規化を必要としない。 我々は,1次オラクルのみを用いた他のアルゴリズムでは改善率を達成できないことを示す情報理論の下界を補完する。
  論文  参考訳（メタデータ） (2022-02-23T17:08:40Z)
• A Two-Time-Scale Stochastic Optimization Framework with Applications in Control and Reinforcement Learning [13.908826484332282]
  最適化問題の解法として,新しい2段階勾配法を提案する。 最初の貢献は、提案した2時間スケール勾配アルゴリズムの有限時間複雑性を特徴づけることである。 我々は、強化学習における勾配に基づく政策評価アルゴリズムに適用する。
  論文  参考訳（メタデータ） (2021-09-29T23:15:23Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic [142.1492359556374]
  双レベル最適化は、2レベル構造を示す問題のクラスである。 このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。 本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
  論文  参考訳（メタデータ） (2020-07-10T05:20:02Z)
• Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
  本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。 Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。 本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
  論文  参考訳（メタデータ） (2020-05-10T19:52:03Z)

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

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