論文の概要: Stochastic Halpern iteration in normed spaces and applications to reinforcement learning

• arxiv url: http://arxiv.org/abs/2403.12338v2
• Date: Fri, 12 Apr 2024 19:14:59 GMT
• ステータス: 処理完了
• システム内更新日: 2024-04-16 20:12:09.265922
• Title: Stochastic Halpern iteration in normed spaces and applications to reinforcement learning
• Title（参考訳）: ノルム空間における確率的ハルパーン反復と強化学習への応用
• Authors: Mario Bravo, Juan Pablo Contreras,
• Abstract要約: 基礎となるオラクルが一様有界であれば,本手法は全体のオラクル複雑性が$tildeO(varepsilon-5)$であることを示す。 平均報酬と割引報酬を決定するための新しい同期アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 0.30693357740321775
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We analyze the oracle complexity of the stochastic Halpern iteration with variance reduction, where we aim to approximate fixed-points of nonexpansive and contractive operators in a normed finite-dimensional space. We show that if the underlying stochastic oracle is with uniformly bounded variance, our method exhibits an overall oracle complexity of $\tilde{O}(\varepsilon^{-5})$, improving recent rates established for the stochastic Krasnoselskii-Mann iteration. Also, we establish a lower bound of $\Omega(\varepsilon^{-3})$, which applies to a wide range of algorithms, including all averaged iterations even with minibatching. Using a suitable modification of our approach, we derive a $O(\varepsilon^{-2}(1-\gamma)^{-3})$ complexity bound in the case in which the operator is a $\gamma$-contraction. As an application, we propose new synchronous algorithms for average reward and discounted reward Markov decision processes. In particular, for the average reward, our method improves on the best-known sample complexity.
• Abstract（参考訳）: 確率的ハルパーン反復のオラクル複雑性を分散還元を用いて解析し、ノルム有限次元空間における非拡張的および収縮的作用素の固定点を近似することを目指す。 基礎となる確率的オラクルが一様有界分散を持つ場合、我々の手法は全体のオラクルの複雑さを$\tilde{O}(\varepsilon^{-5})$で表し、確率的クラスノセルスキイ・マンの反復に対して確立された最近の速度を改善する。 また、小バッチであっても全ての平均反復を含む幅広いアルゴリズムに適用可能な、$\Omega(\varepsilon^{-3})$の低い境界を確立する。 我々のアプローチの適切な修正を用いて、作用素が$\gamma$-contractionである場合、$O(\varepsilon^{-2}(1-\gamma)^{-3})$複雑性を導出する。 アプリケーションとして、平均報酬と割引報酬を決定するための新しい同期アルゴリズムを提案する。 特に、平均的な報酬に対して、本手法は最もよく知られたサンプルの複雑さを改善する。

関連論文リスト

• Accelerated Stochastic Min-Max Optimization Based on Bias-corrected Momentum [30.01198677588252]
  1次アルゴリズムは、$varepsilon-stationary pointを見つけるのに少なくとも$mathcalO(varepsilonepsilon-4)$ complexityを必要とする。 本稿では,高効率な変動複雑性を生かした新しい運動量アルゴリズムを提案する。 本手法の有効性は実世界のデータセットを用いてロジスティック回帰を用いて検証する。
  論文  参考訳（メタデータ） (2024-06-18T20:14:52Z)
• Accelerated Variance-Reduced Forward-Reflected Methods for Root-Finding Problems [8.0153031008486]
  そこで本研究では,Nesterovの高速前方反射法と分散還元法を新たに提案し,根絶問題の解法を提案する。 我々のアルゴリズムは単ループであり、ルートフィリング問題に特化して設計された非バイアス分散還元推定器の新たなファミリーを利用する。
  論文  参考訳（メタデータ） (2024-06-04T15:23:29Z)
• Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization [88.0031283949404]
  多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。 提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
  論文  参考訳（メタデータ） (2022-12-19T14:48:54Z)
• Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum Minimization [52.25843977506935]
  有限サム構造をもつ$L$-smooth, non-deuction関数に対して, AdaSpider と呼ばれる適応分散法を提案する。 そうすることで、$tildeOleft + st/epsilonコールで$epsilon-stationaryポイントを計算することができます。
  論文  参考訳（メタデータ） (2022-11-03T14:41:46Z)
• Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
  我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。 提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
  論文  参考訳（メタデータ） (2022-10-23T21:24:37Z)
• Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergence [69.65563161962245]
  ニュートン法を用いて,滑らかで強凸な目的関数を考える。 最適段階において局所収束に遷移する普遍重み付き平均化スキームが存在することを示す。
  論文  参考訳（メタデータ） (2022-04-20T07:14:21Z)
• A Stochastic Halpern Iteration with Variance Reduction for Stochastic Monotone Inclusion Problems [17.597000481404883]
  機械学習アプリケーションで広く見られるモノトーン包摂問題について検討する。 我々のアルゴリズムは、$mathcalO(frac1epsilon3)$演算子の評価で演算子に$epsilon$ノルムを得る。
  論文  参考訳（メタデータ） (2022-03-17T16:48:57Z)
• A Projection-free Algorithm for Constrained Stochastic Multi-level Composition Optimization [12.096252285460814]
  合成最適化のためのプロジェクションフリー条件付き勾配型アルゴリズムを提案する。 提案アルゴリズムで要求されるオラクルの数と線形最小化オラクルは,それぞれ$mathcalO_T(epsilon-2)$と$mathcalO_T(epsilon-3)$である。
  論文  参考訳（メタデータ） (2022-02-09T06:05:38Z)
• On Stochastic Moving-Average Estimators for Non-Convex Optimization [105.22760323075008]
  本稿では,移動平均(SEMA)問題に基づく広く利用されている推定器のパワーを実証する。 これらすべてのアートな結果に対して、これらのアートな問題に対する結果も提示します。
  論文  参考訳（メタデータ） (2021-04-30T08:50:24Z)
• Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations [54.42518331209581]
  私たちは発見するアルゴリズムを見つけます。 epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using $(epsilon,gamma)$surimateランダムランダムポイント。 ここでの私たちの下限は、ノイズのないケースでも新規です。
  論文  参考訳（メタデータ） (2020-06-24T04:41:43Z)
• Stochastic Gauss-Newton Algorithms for Nonconvex Compositional Optimization [26.313415590777858]
  我々は,非構成最適化問題のクラスを解くための2つの新しいガウスニュートンアルゴリズムを開発した。 標準的な仮定では、期待と有限サムの設定の両方を考慮する。
  論文  参考訳（メタデータ） (2020-02-17T22:56:45Z)

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

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