On the Convergence of HalpernSGD

We study a stochastic anchored gradient scheme, namely HalpernSGD, which combines the classical Halpern iteration for finding a minimizer of a convex and $L$-smooth objective function with a stochastic {first-order} oracle. The algorithm is simple and does not require projections, line-search, or similar techniques. This provides, to the best of our knowledge, the first almost sure convergence guarantee for a Halpern-type stochastic gradient scheme, without requiring variance reduction or multi-point oracle mechanisms. Under standard stepsize assumptions, we prove that the iterates converge almost surely to the anchor-selected minimizer $x^{\ast }=P_S(u)$. In addition, for a natural choice of the step sequences, we derive a sublinear asymptotic estimate for the expected optimality gap, namely ${\mathrm{lim\hspace{0.17em}inf}}_{n\to \mathrm{\infty }}\sqrt{n+1}\mathbb{E}[f(X_n)-f(x^{\ast })]=0.$ As shown, a full last iterate rate estimate cannot be reached in the present setting.