Oracle Complexity of Stochastic Fixed-Point Equations with Nonexpansive Maps
TL;DR
The lower bound holds against any randomized algorithm that succeeds with constant probability and extends to settings with ``sparse''noise, ruling out the possibility of improving oracle complexity as a function of $\varepsilon$ by measuring variance in a non-matching $\ell_p$ norm.
Abstract
We study the oracle complexity of computing a point with small fixed-point residual $\|T(x)-x\| \leq \epsilon$, for a general norm $\|\cdot\|$ 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 $\|\cdot\|$ and accessed via an unbiased stochastic oracle with bounded variance $\sigma^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 $\ell_p$-spaces for $p \in [2, \infty]$, our algorithm attains stochastic oracle complexity $\tilde O(\sigma^2 \epsilon^{-3} + \epsilon^{-1})$. We further prove a near-matching lower bound (i.e., matching up to poly-log factors) for such $\ell_{\infty}$-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 $\ell_p$ norm is of the same order, ruling out the possibility of improving oracle complexity as a function of $\varepsilon$ by measuring variance in a non-matching $\ell_p$ norm.
