論文の概要: A Banach-Space Theory of Markovian Halpern Iteration for Non-Expansive Maps
- arxiv url: http://arxiv.org/abs/2608.15966v1
- Date: Sun, 16 Aug 2026 23:41:42 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-18 19:59:03.483027
- Title: A Banach-Space Theory of Markovian Halpern Iteration for Non-Expansive Maps
- Title(参考訳): 非拡大写像に対するマルコフ的ハルパーン反復のバナッハ空間理論
- Abstract要約: 本稿では,ポアソン方程式を用いてリフレッシュおよび同状態差分ブロックを解析した分散還元型マルコフ型PAGE-Halpern法を提案する。
変位レベルハルパーン境界はヒルベルト空間ポテンシャルに置き換わり、元の非拡張性ノルムにおいて$tilde O(-3)$サンプル複雑性をもたらす。
- 参考スコア(独自算出の注目度): 7.788141970705731
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study stochastic approximation of fixed points of a non-expansive operator when the oracle samples originate from a continuing Markovian trajectory. A direct block-minibatch implementation of Halpern iteration attains an expected last-iterate residual of order $O(\log N/N)$, but accrues a substantive complexity of $\tilde O(ε^{-5})$ Markovian samples. We therefore introduce a variance-reduced Markovian PAGE-Halpern method whose refresh and same-state difference blocks are analyzed through the Poisson equation. In Hilbert spaces, the cocoercivity of $I-T$ results in an $O(ε^{-3})$ sample complexity. Our main result extends this construction to a general finite-dimensional Banach space. A displacement-level Halpern bound replaces the Hilbert-space potential and yields $\tilde O(ε^{-3})$ sample complexity in the original non-expansiveness norm. We also establish a high-probability guarantee with the same leading accuracy dependence by measuring the estimator in an auxiliary smooth norm. Non-smooth sup and block-sup geometries are covered through norm smoothing.
- Abstract(参考訳): 本研究では, 連続するマルコフ軌道から, オラクルサンプルが導出されるとき, 非膨張作用素の不動点の確率近似について検討する。
Halpern 反復の直接ブロック最小化実装は、$O(\log N/N)$の期待された最後のイテレート残基を得るが、$\tilde O(ε^{-5})$ Markovian サンプルの実体複雑性を生じる。
そこで我々は,ポアソン方程式を用いて,リフレッシュおよび同状態差分ブロックを解析した分散還元マルコフ型PAGE-Halpern法を提案する。
ヒルベルト空間において、$I-T$の共保性は$O(ε^{-3})$サンプル複雑性をもたらす。
我々の主な結果は、この構成を一般有限次元バナッハ空間に拡張する。
変位レベルハルパーン境界はヒルベルト空間ポテンシャルに置き換わり、元の非拡張性ノルムにおいて$\tilde O(ε^{-3})$サンプル複雑性をもたらす。
また,推定器を補助的スムーズなノルムで測定することにより,同じ精度で高い確率保証を実現する。
非滑らかなsupとBlock-supのジオメトリはノルム平滑化によってカバーされる。
関連論文リスト
- A Finite Sample Analysis for Quantile Temporal Difference Learning in Distributional Reinforcement Learning [18.875039998204848]
分散強化学習における同期量子時間差分学習(QTD)のグローバル有限サンプル保証を確立する。
大域的な比較論は、報酬累積分布関数の順序単調性と分布ベルマン作用素の$W_infty$収縮に基づいて、局所近傍に任意に安定性をもたらす。
論文 参考訳(メタデータ) (2026-08-27T16:16:09Z) - Demixing Sparse Signals from Nonlinear Observations using Generalized Non-convex Regularization [0.0]
重畳の非線形観測回数が限られていることから, スパースベクトルの回復を考察する。
本稿では, 一般化畳み込みペナルティとハマー化データ忠実度を組み合わせた正規化に基づくフレームワークを提案する。
仮に局所的な定常点を保った位数$sqrtslog(n)/m$の誤差境界を導出する。
論文 参考訳(メタデータ) (2026-07-12T07:29:39Z) - Optimal Dimension-Free Sampling for Regularized Classification [56.72526267755301]
我々は、リプシッツ連続分類損失関数の幅広いクラスに対して、$(1pmvarepsilon)$-relativeエラーを達成する最適サンプリング境界を証明した。
これにはロジスティックやシグモイドの損失、ヒンジの損失、ReLUの損失といった重要な機能が含まれており、顕著で一般的な例である。
論文 参考訳(メタデータ) (2026-05-22T15:05:33Z) - Optimal Unconstrained Self-Distillation in Ridge Regression: Strict Improvements, Precise Asymptotics, and One-Shot Tuning [61.07540493350384]
自己蒸留(英: Self-distillation, SD)とは、教師自身の予測と地道の混合で学生を訓練する過程である。
任意の予測リスクに対して、各正規化レベルにおいて、最適に混合された学生がリッジ教師に改善されることが示される。
本稿では,グリッド探索やサンプル分割,再構成なしに$star$を推定する一貫したワンショットチューニング手法を提案する。
論文 参考訳(メタデータ) (2026-02-19T17:21:15Z) - Harmful Overfitting in Sobolev Spaces [49.47221415754556]
ソボレフ空間$Wk, p(mathbbRd)$における関数の一般化挙動を、ノイズの多いトレーニングデータセットに完全に適合するものとして研究する。
約ノルム最小化補間器は、滑らかさバイアスによって選択される正準解であり、有害なオーバーフィッティングを示す。
我々の証明では,ソボレフの不等式を用いたトレーニングデータの有害な近傍を同定する幾何学的議論を用いている。
論文 参考訳(メタデータ) (2026-01-31T17:40:56Z) - Stabilizing Fixed-Point Iteration for Markov Chain Poisson Equations [49.702772230127465]
有限状態マルコフ鎖を$n$状態と遷移行列$P$で研究する。
すべての非退化モードが実周辺不変部分空間 $mathcalK(P)$ によってキャプチャされ、商空間 $mathbbRn/mathcalK(P) 上の誘導作用素が厳密に収縮し、ユニークな商解が得られることを示す。
論文 参考訳(メタデータ) (2026-01-31T02:57:01Z) - Complexity Analysis of Normalizing Constant Estimation: from Jarzynski Equality to Annealed Importance Sampling and beyond [40.79840141270367]
非正規化確率密度 $piproptomathrme-V$ が与えられたとき、正規化定数 $Z=int_mathbbRdmathrme-V(x)mathrmdx$ または自由エネルギー $F=-log Z$ はベイズ統計学、統計力学、機械学習において重要な問題である。
本稿では,逆拡散サンプリングに基づく新しいアルゴリズムを提案し,その複雑さを解析するためのフレームワークを構築し,マルチモーダリティに対処する際の効率を実証的に実証する。
論文 参考訳(メタデータ) (2025-02-07T00:05:28Z) - Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。
本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
論文 参考訳(メタデータ) (2024-04-29T15:04:07Z) - Stochastic Halpern iteration in normed spaces and applications to reinforcement learning [0.30693357740321775]
我々は,Halpern反復のオラクル複雑性をミニバッチで解析する。
我々は,平均値と割引値の報酬MDPに対する新しいモデルフリーアルゴリズムを提案する。
論文 参考訳(メタデータ) (2024-03-19T01:07:35Z) - Optimal and instance-dependent guarantees for Markovian linear stochastic approximation [47.912511426974376]
標準スキームの最後の繰り返しの2乗誤差に対して、$t_mathrmmix tfracdn$の非漸近境界を示す。
マルコフ雑音による政策評価について,これらの結果のまとめを導出する。
論文 参考訳(メタデータ) (2021-12-23T18:47:50Z) - Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。
我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。
MRP のサブクラスに対する minimax の下位境界を証明する。
論文 参考訳(メタデータ) (2021-09-24T14:48:20Z) - Nonparametric approximation of conditional expectation operators [0.3655021726150368]
最小の仮定の下で、$[Pf](x) := mathbbE[f(Y) mid X = x ]$ で定義される$L2$-operatorの近似について検討する。
我々は、再生されたカーネル空間上で作用するヒルベルト・シュミット作用素により、作用素ノルムにおいて$P$が任意に適切に近似できることを証明した。
論文 参考訳(メタデータ) (2020-12-23T19:06:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。