Convergence Rate for the Last Iterate of Stochastic Gradient Descent Schemes

We study the convergence rate for the last iterate of stochastic gradient descent (SGD) and stochastic heavy ball (SHB) in the parametric setting when the objective function F is globally convex or non-convex whose gradient is γ-H"older. Using only discrete Gronwall's inequality without Robbins-Siegmund theorem, we recover results for both SGD and SHB: mins≤ t |nabla F(ws)|2 = o(tp-1) for non-convex objectives and F(wτ wedge t) - F_* = o(t2γ/(1+γ) · max(p-1,-2p+1)-ε) for β ∈ (0, 1), τ := inf t > 0 : F(wt) = F_*, and mins ≤ t F(ws) - F_* = o(tp-1) for convex objectives F whose minimum is F_*. In addition, we proved that SHB with constant momentum parameter β ∈ (0, 1) attains a convergence rate of F(wt) - F_* = O(tmax(p-1,-2p+1) log2 fractδ) with probability at least 1-δ when F is convex and γ = 1 and step size αt = Theta(t-p) with p ∈ (frac12, 1).