論文の概要: Solving Stochastic Fixed-Point Equations with High Probability
- arxiv url: http://arxiv.org/abs/2607.09097v1
- Date: Fri, 10 Jul 2026 04:59:20 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-13 14:47:12.782584
- Title: Solving Stochastic Fixed-Point Equations with High Probability
- Title（参考訳）: 確率の高い確率的不動点方程式の解法
- Authors: Jelena Diakonikolas,
- Abstract要約: オラクルの不動点方程式 $mathbfT(mathbfx) = mathbfx$ をノルム空間上で研究する。
本稿では,2次スムーズなバナッハ空間に対する分散還元段階Halpern法であるVR-GHALを紹介する。
- 参考スコア（独自算出の注目度）: 22.376855234542813
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study stochastic fixed-point equations $\mathbf{T}(\mathbf{x}) = \mathbf{x}$ over normed spaces $(\mathcal{E}, \|\cdot\|)$, where the operator $\mathbf{T}$ is nonexpansive or contractive and is accessed only through unbiased stochastic evaluations with bounded second central moment. Given $ε> 0, δ\in (0, 1)$, the goal is to output $\mathbf{x} \in \mathcal{E}$ such that $\|\mathbf{T}(\mathbf{x}) - \mathbf{x}\| \leq ε$ with probability at least $1-δ$. We introduce VR-GHAL, a variance-reduced gradual Halpern method for quadratically smoothable Banach spaces. The key algorithmic ingredient is a recursive stochastic estimator based on clipped differences of oracle evaluations: instead of clipping $τ(\mathbf{x}; ξ)$ itself, we clip stochastic differences at the Lipschitz scale $γ\|\mathbf{x} - \mathbf{y}\|$. This makes the estimator pathwise Lipschitz along the algorithmic trajectory while permitting martingale concentration under finite second moments in the native norm. Our main theorem gives an anytime high-probability residual bound: on a single event of probability at least $1 - δ$, the residual decreases nearly geometrically across epochs, up to lower-order logarithmic factors. Under only bounded variance, displaying only the dependence on the target error $ε$ and Lipschitz constant $γ\in (0, 1]$ of $\mathbf{T}$, the resulting oracle complexity is $\min\{ε^{-5}, (1-γ)^{-3}ε^{-2}\}$. Under a Lipschitz-in-expectation oracle, the dependence improves to the corresponding $ε^{-3}$ nonexpansive rate (i.e., for $γ= 1$), and under samplewise nonexpansiveness to $ε^{-2}$.
- Abstract（参考訳）: 確率的不動点方程式 $\mathbf{T}(\mathbf{x}) = \mathbf{x}$ をノルム空間 $(\mathcal{E}, \|\cdot\|)$ 上で研究する。
ε> 0, δ\in (0, 1)$ が与えられたとき、ゴールは $\mathbf{x} \in \mathcal{E}$ を$\|\mathbf{T}(\mathbf{x}) - \mathbf{x}\| \leq ε$ を少なくとも1-δ$ の確率で出力することである。
本稿では,2次スムーズなバナッハ空間に対する分散還元段階Halpern法であるVR-GHALを紹介する。
鍵となるアルゴリズム的成分は、オラクル評価のクリッピング差に基づく再帰確率的推定器である:$τ(\mathbf{x}; )$自体をクリップする代わりに、リプシッツスケール$γ\|\mathbf{x} - \mathbf{y}\|$で確率的差をクリップする。
これにより、推定子はアルゴリズムの軌道に沿ってパスワイズ・リプシッツとなり、ネイティブノルムの有限第二モーメントの下でマルティンゲール濃度を許容する。
我々の主定理は、常に高い確率的残差(英語版)を与える:少なくとも1 - δ$の確率の単一の事象において、残差はエポックにわたって幾何的に減少し、下位の対数係数まで減少する。
リプシッツ定数 $γ\in (0, 1]$ of $\mathbf{T}$, 結果として生じるオラクルの複雑さは$\min\{ε^{-5}, (1-γ)^{-3}ε^{-2}\}$である。
リプシッツ・イン・エクスプロメーションのオラクルの下では、依存は対応する$ε^{-3}=非エクスカンシブレート(すなわち$γ=1$)に改善され、サンプルの非エクスカンシブネスは$ε^{-2}$に改善される。
関連論文リスト
- A Mathematical Theory of Top-$k$ Sparse Attention via Total Variation Distance [7.014801584517052]
我々は,分散レベルと出力レベルの両方でエラーを定量化する,Top-$$ attention truncationという統一フレームワークを開発した。
総偏差距離は捨てられたソフトマックスのテール質量と一致し,$mathrmTV(P,hat P)=1-e-mathrmTV(P,hat P)=1-e-mathrmTV(P,hat P)$を満たすことを示す。
論文 参考訳（メタデータ） (2025-12-08T15:36:41Z) - Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
このタスクに対する効率的な統計的クエリアルゴリズムは、VSTATの複雑さを少なくとも$tildeOmega(d1/2/alpha2)$で要求する。
論文 参考訳（メタデータ） (2025-10-12T15:42:44Z) - Estimation and Inference in Distributional Reinforcement Learning [28.253677740976197]
サイズ$widetilde Oleft(frac|mathcalS||mathcalA|epsilon2 (1-gamma)4right)$ suffices to ensure the Kolmogorov metric and total variation metric between $hatetapi$ and $etapi$ is below $epsilon$ with high probability。
以上の結果から,多種多様な統計的汎関数の統計的推測への統一的アプローチがもたらされた。
論文 参考訳（メタデータ） (2023-09-29T14:14:53Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - Near Optimal Heteroscedastic Regression with Symbiotic Learning [29.16456701187538]
我々は不連続線形回帰の問題を考察する。
正則ノルムにおいて$mathbfw*$を$tildeOleft(|mathbff*|2cdot left(frac1n + left(dnright)2right)$の誤差まで推定し、一致する下界を証明できる。
論文 参考訳（メタデータ） (2023-06-25T16:32:00Z) - Statistical Learning under Heterogeneous Distribution Shift [71.8393170225794]
ground-truth predictor is additive $mathbbE[mathbfz mid mathbfx,mathbfy] = f_star(mathbfx) +g_star(mathbfy)$.
論文 参考訳（メタデータ） (2023-02-27T16:34:21Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - AI without networks [0.0]
我々は、生成モデリングを取り入れたAIのためのネットワークフリーフレームワークを開発する。
我々は、この枠組みを、民族学、制御理論、数学の3つの異なる分野の例で示す。
また、生成AIによる倫理的法的課題に対処するために、この枠組みに基づいて容易に計算された信用割当手法を提案する。
論文 参考訳（メタデータ） (2021-06-07T05:50:02Z) - Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and
ReLUs under Gaussian Marginals [49.60752558064027]
ガウス境界の下では、半空間とReLUを不可知的に学習する基本的な問題について検討する。
我々の下限は、これらのタスクの現在の上限が本質的に最良のものであるという強い証拠を与える。
論文 参考訳（メタデータ） (2020-06-29T17:10:10Z) - Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
論文 参考訳（メタデータ） (2020-05-29T07:20:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。