Dual-Anchor Acceleration Is Near-Optimal for Stochastic Monotone Root-Finding

Among distinct optimal acceleration mechanisms for deterministic monotone root-finding problems and fixed-point problems, dual-anchoring has recently been shown to admit a more robust direct stochastic extension than standard anchor acceleration. However, without additional strong monotonicity, the existing stochastic dual-anchoring guarantee by Yoon & Loizou (2026) has two limitations: first, it requires cocoercivity in expectation, and second, it attains only $\mathcal{O}({ϵ}^{-3})$ oracle complexity, leaving a gap to the near-optimal $\tilde{\mathcal{O}}({ϵ}^{-2})$ complexity achieved by other methods. In this work, we address both of these limitations by combining dual-anchoring with stochastic resolvent approximation and optimized variance control. For unbiased stochastic oracles with variance bounded by ${\sigma }^2$, where sample operators are monotone and uniformly $L$-Lipschitz, our algorithm finds a point $x\_ϵ$ satisfying \mathbb{E} \left[ \left\\| F(x\_\epsilon)\right\\|\right] \le \epsilon with a near-optimal oracle complexity of $\mathcal{O}((LD/ϵ)\ell +({\sigma }^2/{ϵ}^2){\ell }^2)$, where $\ell =\log (1+LD/ϵ)$ and $D$ is the initial distance to a solution. This result improves the best known oracle complexity in the noise-dominated regime under these samplewise assumptions, reducing the poly-logarithmic factor from cubic to quadratic.