論文の概要: Finite-time analysis of Multi-timescale Stochastic Optimization Algorithms

• arxiv url: http://arxiv.org/abs/2603.29380v1
• Date: Tue, 31 Mar 2026 07:50:11 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-01 15:25:03.267661
• Title: Finite-time analysis of Multi-timescale Stochastic Optimization Algorithms
• Title（参考訳）: マルチ時間確率最適化アルゴリズムの有限時間解析
• Authors: Kaustubh Kartikey, Shalabh Bhatnagar,
• Abstract要約: シミュレーションに基づく最適化のための2つのスムーズな関数近似アルゴリズムの有限時間解析を行う。 どちらのアルゴリズムも、目的関数 $J$ の勾配/ヘシアンに対するゼロ次推定を含む。 同じフレームワークの下で勾配アルゴリズムに対して、対応する有限時間保証を提供する。
• 参考スコア（独自算出の注目度）: 5.796747542837171
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present a finite-time analysis of two smoothed functional stochastic approximation algorithms for simulation-based optimization. The first is a two time-scale gradient-based method, while the second is a three time-scale Newton-based algorithm that estimates both the gradient and the Hessian of the objective function $J$. Both algorithms involve zeroth order estimates for the gradient/Hessian. Although the asymptotic convergence of these algorithms has been established in prior work, finite-time guarantees of two-timescale stochastic optimization algorithms in zeroth order settings have not been provided previously. For our Newton algorithm, we derive mean-squared error bounds for the Hessian estimator and establish a finite-time bound on $\min\limits_{0 \le m \le T} \mathbb{E}\| \nabla J(θ(m)) \|^2$, showing convergence to first-order stationary points. The analysis explicitly characterizes the interaction between multiple time-scales and the propagation of estimation errors. We further identify step-size choices that balance dominant error terms and achieve near-optimal convergence rates. We also provide corresponding finite-time guarantees for the gradient algorithm under the same framework. The theoretical results are further validated through experiments on the Continuous Mountain Car environment.
• Abstract（参考訳）: シミュレーションに基づく最適化のための2つのスムーズな関数確率近似アルゴリズムの有限時間解析を行う。 1つは2つの時間スケール勾配法、もう1つは3つの時間スケールニュートンに基づくアルゴリズムで、目的関数の勾配とヘシアンの両方を推定する。 どちらのアルゴリズムも勾配/ヘシアンのゼロ次推定を含む。 これらのアルゴリズムの漸近収束は以前の研究で確立されているが、ゼロ階設定における2時間スケール確率最適化アルゴリズムの有限時間保証は、これまで提供されていなかった。 ニュートンアルゴリズムでは、ヘッセン推定器の平均二乗誤差境界を導出し、$\min\limits_{0 \le m \le T} \mathbb{E}\| \nabla J(θ(m)) \|^2$ 上の有限時間境界を確立し、一階定常点への収束を示す。 この分析は、複数の時間スケールと推定誤差の伝搬の間の相互作用を明示的に特徴づける。 さらに、支配的なエラー項のバランスをとり、ほぼ最適収束率を達成するステップサイズの選択を同定する。 また、同じフレームワーク下での勾配アルゴリズムに対して、対応する有限時間保証を提供する。 理論的結果は、連続マウンテンカー環境の実験を通じてさらに検証される。

関連論文リスト

• Non-Expansive Mappings in Two-Time-Scale Stochastic Approximation: Finite-Time Analysis [0.0]
  2時間スケール近似アルゴリズムは、最適化、強化学習、制御などのアプリケーションで使用される。 我々は、より高速な時間スケールが、より遅い時間スケールで非拡張性をもたらすプロジェクションステップを持つ変種について研究する。
  論文  参考訳（メタデータ） (2025-01-18T16:00:14Z)
• Fully Zeroth-Order Bilevel Programming via Gaussian Smoothing [7.143879014059895]
  ビルベル問題の解法としてゼロ階近似アルゴリズムを研究・解析する。 我々の知る限りでは、完全ゼロ階二階最適化アルゴリズムのためにサンプル境界が確立されたのはこれが初めてである。
  論文  参考訳（メタデータ） (2024-03-29T21:12:25Z)
• A Stochastic-Gradient-based Interior-Point Algorithm for Solving Smooth Bound-Constrained Optimization Problems [12.29270365918848]
  提案アルゴリズムは、他のインテリアポイント法からの主観的特異な制約に基づいている。 提案アルゴリズムは,プロジェクション,ステップサイズ,シーケンスシーケンスのバランスを慎重に保ち,数値的および決定論的両方の設定において収束を保証する。
  論文  参考訳（メタデータ） (2023-04-28T15:30:43Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [61.98523595657983]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Explicit Second-Order Min-Max Optimization: Practical Algorithms and Complexity Analysis [71.05708939639537]
  本研究では,非制約問題に対するグローバルなサドル点を求めるために,不正確なNewton型手法をいくつか提案し,解析する。 提案手法は,Sur分解の必要回数の$O(log(1/eps)$因子をシェービングすることで,既存のライン検索に基づくmin-max最適化を改善する。
  論文  参考訳（メタデータ） (2022-10-23T21:24:37Z)
• Reinforcement Learning with Unbiased Policy Evaluation and Linear Function Approximation [11.345796608258434]
  マルコフ決定プロセスを制御するためのシミュレーションベースのポリシーイテレーションの変種に対して,性能保証を提供する。 第一のアルゴリズムは最小二乗アプローチを伴い、各反復において、特徴ベクトルに関連する新しい重みの集合が少なくとも二乗によって得られる。 第2のアルゴリズムは、最小二乗解への勾配降下を数ステップ行う2段階の近似アルゴリズムを含む。
  論文  参考訳（メタデータ） (2022-10-13T20:16:19Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)

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

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