The guarantee in (REF ) provides the same convergence result as in the deterministic-learning-rate case, it holds for arbitrary decreasing step sizes and does not depend on the initial point unlike previous works (cf. [1]}).

The proof for diminishing step size is identical to the proof of Theorem REF  until equation (REF ), except that the fifth inequality in (REF ) now follows from \( a_t=\eta _t u_t \le \eta _1 c_2 \) , and the sixth from (REF ) which gives \( \eta _1 c_2 M_G L-2 \le -1 \)  and therefore \(\eta _t c_2 M_G L-2 \le -1 \) , since \( \eta _t \le \eta _1 \)  for \( t \in \mathbb {N} \) . Then, taking expectations with respect to all \( \xi _i \)  up to time \( t \) :
\(\begin{aligned}[b] {\mathbb {E}_\xi }[f({\theta _{t+1}})] \le {\mathbb {E}_\xi }[f({\theta _t})] - c{a_t}({\mathbb {E}_\xi }[f({\theta _t})] - {f_{min}}) + a_t^2\frac{{LM}}{2},\end{aligned} \) 
