Asymptotic Regularity of a Generalised Stochastic Halpern Scheme

Abstract We provide abstract, general and highly uniform rates of asymptotic regularity for a generalized stochastic Halpern-style iteration, which incorporates a second mapping in the style of a Krasnoselskii-Mann iteration. This iteration is general in two ways: First, it incorporates stochasticity completely abstractly, rather than fixing a sampling method; second, it includes as special cases stochastic versions of various schemes from the optimization literature, including Halpern’s iteration as well as a Krasnoselskii-Mann iteration with Tikhonov regularization terms in the sense of Boţ, Csetnek and Meier (where this stochastic variant of the latter is considered for the first time in this paper). For these specific cases, we obtain linear rates of asymptotic regularity, matching (or improving) the currently best known rates for these iterations in stochastic optimization, and quadratic rates of asymptotic regularity are obtained in the context of inner product spaces for the general iteration. We conclude by discussing how variance can be managed in practice through sampling methods in the style of minibatching, how our convergence rates can be adapted to provide oracle complexity bounds, and by sketching how the schemes presented here can be instantiated in the context of reinforcement learning to yield novel methods for Q-learning.