arXiv:2607.09097math.OCcs.DS2026-07

提出新算法求解随机不动点方程,高概率保证收敛速度更快。

Solving Stochastic Fixed-Point Equations with High Probability

  • 设计基于截断差分的递归估计器,提升稳定性与收敛性
  • 在有限二阶矩条件下实现近几何级残差下降,复杂度最优
  • 适用于高精度要求的强化学习与优化问题,尤其适合非扩张算子

我们研究定义在赋范空间 $(\mathcal{E}, \|\cdot\|)$ 上的随机不动点方程 $\mathbf{T}(\mathbf{x}) = \mathbf{x}$,其中算子 $\mathbf{T}$ 为非扩张或压缩型,仅可通过无偏随机评估访问,且评估值具有有界二阶中心矩。给定 $ε > 0$、$δ \in (0,1)$,目标是输出 $\mathbf{x} \in \mathcal{E}$,使得 $\|\mathbf{T}(\mathbf{x}) - \mathbf{x}\| \leq ε$ 的概率至少为 $1-δ$。本文提出 VR-GHAL 算法,一种适用于可二次光滑巴拿赫空间的方差缩减渐进 Halpern 法。核心在于使用基于截断差分的递归随机估计器:不直接截断 $τ(\mathbf{x}; ξ)$,而是在利普希茨尺度 $γ\|\mathbf{x} - \mathbf{y}\|$ 处截断随机差分。该估计器沿算法轨迹路径上保持利普希茨性,同时在原范数下支持鞅集中性。主定理给出任意时刻的高概率残差界:在概率至少 $1-δ$ 的事件上,残差在各轮次中近乎几何衰减,仅受低阶对数因子影响。仅需有界方差时,所获查询复杂度为 $\min\{ε^{-5}, (1-γ)^{-3}ε^{-2}\}$;在期望利普希茨条件下,依赖性优化至 $ε^{-3}$ 非扩张率(即 $γ=1$);在样本层面非扩张条件下,可进一步降至 $ε^{-2}$。

原文摘要 · Abstract (English)

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}$.

优化算法随机逼近不动点高概率分析

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。