Solving Stochastic Fixed-Point Equations with High Probability

We study stochastic fixed-point equations T(x) = x over normed spaces (E, |·|), where the operator T is nonexpansive or contractive and is accessed only through unbiased stochastic evaluations with bounded second central moment. Given ε > 0, δ ∈ (0, 1), the goal is to output x ∈ E such that |T(x) - x| ≤ ε 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; xi) 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 γ ∈ (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.