We study the oracle complexity of computing a point with small fixed-point residual
∥T(x)−x∥≤ε, for a general norm
∥⋅∥ and a self-map
T of a compact convex set. We study this problem in the setting where
T is nonexpansive with respect to the same norm
∥⋅∥ and accessed via an unbiased stochastic oracle with bounded variance
σ2. We provide an algorithm that solves such instances for any norm with a weak Rademacher type
q>1, with high probability. The algorithm is based on a recursive anchoring technique. For type-
2 spaces, such as
ℓp-spaces for
p∈[2,∞], our algorithm attains stochastic oracle complexity
O~(σ2ε−3+ε−1). We further prove a near-matching lower bound (i.e., matching up to poly-log factors) for such
ℓ∞-norm instances in high dimensions. Our lower bound holds against any randomized algorithm that succeeds with constant probability. It further extends to settings with ``sparse'' noise, where variance measured with respect to any
ℓp norm is of the same order, ruling out the possibility of improving oracle complexity as a function of
ε by measuring variance in a non-matching
ℓp norm.