論文の概要: Gradient-Free Approaches is a Key to an Efficient Interaction with Markovian Stochasticity

• arxiv url: http://arxiv.org/abs/2601.01160v1
• Date: Sat, 03 Jan 2026 11:27:07 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-06 16:25:22.060137
• Title: Gradient-Free Approaches is a Key to an Efficient Interaction with Markovian Stochasticity
• Title（参考訳）: マルコフ確率性との効率的な相互作用の鍵となるグラディエントフリーアプローチ
• Authors: Boris Prokhorov, Semyon Chebykin, Alexander Gasnikov, Aleksandr Beznosikov,
• Abstract要約: このような問題を解決するための新しい微分自由法を提案し,解析する。 基礎となる雑音列の混合時間$$が問題の次元$d$より小さい場合、我々の手法の収束推定は$$に依存しないことを示す。
• 参考スコア（独自算出の注目度）: 80.65200796386168
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper deals with stochastic optimization problems involving Markovian noise with a zero-order oracle. We present and analyze a novel derivative-free method for solving such problems in strongly convex smooth and non-smooth settings with both one-point and two-point feedback oracles. Using a randomized batching scheme, we show that when mixing time $τ$ of the underlying noise sequence is less than the dimension of the problem $d$, the convergence estimates of our method do not depend on $τ$. This observation provides an efficient way to interact with Markovian stochasticity: instead of invoking the expensive first-order oracle, one should use the zero-order oracle. Finally, we complement our upper bounds with the corresponding lower bounds. This confirms the optimality of our results.
• Abstract（参考訳）: 本稿では,ゼロ次オラクルを持つマルコフ雑音を含む確率的最適化問題に対処する。 本研究では,一点フィードバックと二点フィードバックの両方のオラクルを用いて,円滑で滑らかな非滑らかな設定において,そのような問題を解決するための新しい微分自由解法を提案し,解析する。 ランダム化されたバッチ方式を用いて、基礎となる雑音列の混合時間$τ$が、問題の次元$d$より小さい場合、我々の手法の収束推定は$τ$に依存しないことを示す。 この観察はマルコフ確率性と相互作用する効率的な方法を与える:高価な一階のオラクルを呼び出す代わりに、ゼロ階のオラクルを使うべきである。 最後に、上界と対応する下界を補完する。 これは我々の結果の最適性を確認する。

関連論文リスト

• Continuum-armed Bandit Optimization with Batch Pairwise Comparison Oracles [14.070618685107645]
  ここでは,関数の最大値が$f(x)$以上であるような帯域最適化問題について検討する。 このようなペアワイズ比較は、共同価格と在庫補充問題に重要な応用を見出すことを示す。
  論文  参考訳（メタデータ） (2025-05-28T13:41:00Z)
• Sign Operator for Coping with Heavy-Tailed Noise in Non-Convex Optimization: High Probability Bounds Under $(L_0, L_1)$-Smoothness [74.18546828528298]
  SignSGD with Majority Votingは,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappaka ppakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa -1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappappapa-1right,Kappaを用いて,複雑性の全範囲で堅牢に動作することを示す。
  論文  参考訳（メタデータ） (2025-02-11T19:54:11Z)
• Stochastic Halpern iteration in normed spaces and applications to reinforcement learning [0.30693357740321775]
  我々は,Halpern反復のオラクル複雑性をミニバッチで解析する。 我々は,平均値と割引値の報酬MDPに対する新しいモデルフリーアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-03-19T01:07:35Z)
• Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully First-Order Oracles [13.077441411315759]
  両レベル最適化は、低レベル問題が強い凸である場合に考慮する。 我々は,2段階の更新を組み込んで,最適に近い$tilde MathcalO(epsilon-2)$ 1次オラクル複雑性を実現する。
  論文  参考訳（メタデータ） (2023-06-26T17:07:54Z)
• First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities [91.46841922915418]
  本稿では,一階変分法の理論解析のための統一的アプローチを提案する。 提案手法は非線形勾配問題とモンテカルロの強い問題の両方をカバーする。 凸法最適化問題の場合、オラクルに強く一致するような境界を与える。
  論文  参考訳（メタデータ） (2023-05-25T11:11:31Z)
• Extra-Newton: A First Approach to Noise-Adaptive Accelerated Second-Order Methods [57.050204432302195]
  本研究では,2次スムーズな凸関数を最小化するための普遍的かつ適応的な2次法を提案する。 我々のアルゴリズムは、オラクルフィードバックが分散$sigma2$であるときに$O(sigma / sqrtT)$収束を達成し、決定論的オラクルで$O(1 / T3)$に収束を改善する。
  論文  参考訳（メタデータ） (2022-11-03T14:12:51Z)
• 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)
• Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
  マルコフ決定過程における純粋探索問題について検討する。 エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
  論文  参考訳（メタデータ） (2021-06-05T09:16:28Z)
• Zeroth-Order Algorithms for Smooth Saddle-Point Problems [117.44028458220427]
  ゼロオーダーのオラクルを用いてサドルポイント問題を解くアルゴリズムをいくつか提案する。 解析により、この項の収束率は、一階法よりも$log n$因子の方が悪いことが示されている。 また、混合構成を考慮し、その部分に対してゼロ階のオラクルを使用する1/2階法を開発する。
  論文  参考訳（メタデータ） (2020-09-21T14:26:48Z)
• 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)
• Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noise [28.891930079358954]
  線形2時間スケールSAスキームに対して有限時間解析を行う。 我々の境界はマルコフ音とマルティンゲール音の収束速度に差がないことを示している。 一致した下界を持つ予測誤差の拡張を示す。
  論文  参考訳（メタデータ） (2020-02-04T13:03:17Z)

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

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