Solving Stochastic Fixed-Point Equations with High Probability

We study stochastic fixed-point equations T(x) = x over normed spaces (E, |\cdot|), where the operator 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 x \in E such that |T(x) - 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 τ(x; ξ) itself, we clip stochastic differences at the Lipschitz scale γ|x - 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 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}.