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;ξ) 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.