論文の概要: Shrinking-Tube Concentration for Adaptive Markovian Stochastic Approximation

• arxiv url: http://arxiv.org/abs/2609.29833v1
• Date: Thu, 24 Sep 2026 14:04:10 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-25 21:10:09.971626
• Title: Shrinking-Tube Concentration for Adaptive Markovian Stochastic Approximation
• Title（参考訳）: 適応マルコフ確率近似のための収縮管濃度
• Abstract要約: 適応鎖によって駆動されるマルコフ近似に束縛された収縮管濃度を確立する。 耐性の低下の速さと将来の出口の確率の低下の速さのトレードオフを示す。 この理論を在庫依存需要と固定在庫コストによる在庫学習に適用する。
• 参考スコア（独自算出の注目度）: 8.047936111776549
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Adaptive algorithms increasingly make decisions while reshaping the dynamics that generate their future data. We establish a shrinking-tube concentration bound for projected stochastic approximation driven by an adaptive Markov chain. The bound guarantees, with high probability, that every iterate after a chosen time remains within a tolerance around the target that tightens over time. The probability of any exit after the chosen time admits a polynomially decaying upper bound, and a matching lower bound shows that its polynomial exponent cannot be improved in general under finite second moments. The result therefore identifies a sharp tradeoff between how quickly the tolerance shrinks and how rapidly the probability of any future exit decreases. We also extend the analysis to recursions with additional martingale-difference noise and predictable bias, showing how growth in the martingale-difference noise scale slows the decay of the exit-probability bound while predictable bias restricts the admissible tube shrinkage. The proof combines backward kernel replacement, a finite-time mean-squared-error bound, and a blockwise maximal first-exit argument. We apply the theory to inventory learning with stockout-dependent demand and fixed stockout costs, and quantify how numerical gradient accuracy affects the all-future reliability of the resulting policies.
• Abstract（参考訳）: 適応アルゴリズムは、将来のデータを生成するダイナミクスを再構築しながら、ますます決定を下す。 我々は適応マルコフ連鎖によって駆動される射影確率近似に束縛された縮小管濃度を確立する。 制限は、高い確率で、選択された時間後の全ての反復が、時間とともに引き締めるターゲットの周りの許容範囲内にあることを保証します。 選択された時間後の出口の確率は多項式的に崩壊する上界を認め、一致する下界は、多項式指数が一般に有限秒のモーメントで改善できないことを示す。 この結果から, 許容値の減少速度と, 将来の終了確率の低下速度との間には, 急激なトレードオフが生じる。 また,マルティンゲール差分ノイズと予測可能なバイアスを付加した再帰解析にも拡張し,マルティンゲール差分ノイズスケールの成長が,予測可能なバイアスが許容可能なチューブ収縮を制限する一方で,出口確率の減衰を遅くすることを示す。 この証明は、後向きのカーネル置換、有限時間平均二乗誤差境界、ブロックワイズ第一外引数を組み合わせたものである。 この理論を,在庫依存需要と固定在庫コストによる在庫学習に適用し,数値勾配の精度が今後の政策の信頼性に与える影響を定量化する。

関連論文リスト

• Beyond Optimal Rates in Stochastic Optimization: Trajectory-Adaptive Stopping Rules [42.38093055717409]
  我々は、新しい信頼系列法と、適応されたプロセスに対する時間一様経験的バーンスタイン不等式を開発する。 結果の停止規則は、自然勾配の地平線より少ない数桁の順序を必要とすることが示される。
  論文  参考訳（メタデータ） (2026-08-26T09:02:46Z)
• Regret and Sample Complexity of Online Q-Learning via Concentration of Stochastic Approximation with Time-Inhomogeneous Markov Chains [23.565936864449636]
  無限水平割引マルコフ決定過程における古典的オンラインQ-ラーニングに対する最初の高い確率的後悔を示す。 十分な大きなギャップでは、後悔はサブリニアであり、小さなギャップでは劣化し、線形成長に近づく。
  論文  参考訳（メタデータ） (2026-02-18T08:47:07Z)
• Stopping Rules for Stochastic Gradient Descent via Anytime-Valid Confidence Sequences [51.56484100374058]
  凸最適化のための勾配降下(SGD)の停止規則について検討した。 我々は、投影されたSGDの重み付き平均準最適度に対して、任意の有意、データ依存の高信頼シーケンスを開発する。 これらは、厳格でタイムユニフォームなパフォーマンス保証と、有限時間$varepsilon$-optimality証明書である。
  論文  参考訳（メタデータ） (2025-12-15T09:26:45Z)
• Ultimate Kinetic Uncertainty Relation and Optimal Performance of Stochastic Clocks [0.0]
  クロックの1回通過時間の不確かさと最適長時間動作の正確な限界を確立する。 結果は量子リセットプロセスを含む半マルコフ過程に一般化される。
  論文  参考訳（メタデータ） (2024-07-13T10:26:39Z)
• Relaxed Quantile Regression: Prediction Intervals for Asymmetric Noise [51.87307904567702]
  量子レグレッション(Quantile regression)は、出力の分布における量子の実験的推定を通じてそのような間隔を得るための主要なアプローチである。 本稿では、この任意の制約を除去する量子回帰に基づく区間構成の直接的な代替として、Relaxed Quantile Regression (RQR)を提案する。 これにより、柔軟性が向上し、望ましい品質が向上することが実証された。
  論文  参考訳（メタデータ） (2024-06-05T13:36:38Z)
• Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling [73.5602474095954]
  マルコフサンプリングの遅延更新による近似スキームの非漸近的性能について検討した。 我々の理論的な発見は、幅広いアルゴリズムの遅延の有限時間効果に光を当てた。
  論文  参考訳（メタデータ） (2024-02-19T03:08:02Z)
• Super fast rates in structured prediction [88.99819200562784]
  連続的な問題が連続的な値を予測しているときに、離散的な問題が本質的に離散的なアウトプットを予測しているという事実を活用する方法を示す。 まず、近接する隣人に基づく予測器について説明し、二項分類で知られている確率を、構造的予測の枠組み内の任意の離散問題に一般化する。 次に、カーネルリッジの回帰について検討し、問題の硬さを特徴付けるパラメータによって、n-1/4$の既知のレートを任意に高速化する。
  論文  参考訳（メタデータ） (2021-02-01T10:50:04Z)
• Online Stochastic Convex Optimization: Wasserstein Distance Variation [15.313864176694832]
  滑らかな凸関数の期待値の最小値を追跡するためのオンライン近勾配法について検討する。 システムや制御文献にインスパイアされた推定・追跡誤差の概念を再考する。 我々は、強い凸性、勾配のリプシッツ性、確率分布のドリフトに対する境界を与える。
  論文  参考訳（メタデータ） (2020-06-02T05:23:22Z)
• Stochastic Approximation with Markov Noise: Analysis and applications in reinforcement learning [0.0]
  マルコフ雑音によって駆動される2つの時間スケール近似の収束解析を初めて提示する。 両方の時間スケールにおける差分包摂を限定することで、フレームワークの挙動を分析する。 ポリシ評価アルゴリズムの関数近似における最初の情報的誤差境界を求める。
  論文  参考訳（メタデータ） (2020-04-08T03:59:21Z)

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

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