


The proof proceeds by dividing the analysis into two parts about \(n_0\) . For a detailed proof, see Appendix REF .

A few remarks are in order.


For Case I, the estimation error can decay as \(1/n\)  if \(c\)  is chosen such that \(2\mu _1 c>1.\)  However, if \(\mu _1\)  is not known, such a choice may not be feasible. Indeed, the error can decay much slower if \(c\)  is such that \(2\mu _1 c\)  is much smaller than \(1.\)  For Case II above, the estimation error decays as \(1/n^\alpha \)  where \(\alpha \)  can be chosen arbitrarily close to 1 when deciding the step size, and this choice does not depend on \(\mu _1\) . However, as \(\alpha \)  approaches 1, the first term grows in an unbounded manner.
An advantage with the larger stepsize \(c/k^\alpha \)  in Case II is that the initial error is forgotten exponentially fast, the corresponding rate is \(1/n^{\mu _1 c}\)  for the stepsize \(c/k\) .


The step size in Case II above is typically used in conjunction with iterate averaging [1]}, [2]}. We can also use iterate averaging in this setting, but we can show that it does not improve the error decay rate derived for Case II without employing iterate averaging. From a practical perspective, outputting the `last iterate' is often preferable over iterate averaging, especially when the latter does not improve the convergence rate appreciably.
