Precise Convergence Speed of Clipped SGD

We present a tightened convergence analysis of clipped gradient descent on $(L_0,L_1)$-smooth functions, with quantitative constants. Building on the ideas of Koloskova et al (2023), we refactor several case disjunctions to reveal the central role of a control of the bias derived from fundamental properties of ${\mathrm{\ell }}_2$-projection, simplifying proofs. We also extend the domain of validity from $\eta \le 1\mathrm{/}(9\beta )$ to $\eta <1\mathrm{/}\beta$ where $\beta =L_0+c{L}_1$ for clipping constant $c$, which matches the more traditional analysis of smooth functions. We strengthen the convergence criterion from $({\min }_{t<T}\mathbb{E}[\parallel \mathrm{\nabla }f(x_t){\parallel }_2])$ to $(\frac{1}{T}{\sum }_{t<T}\mathbb{E}[\parallel \mathrm{\nabla }f(x_t){\parallel }_2])$ with matching speed, and lower the final achievable loss from $\mathcal{O}(\min ({\sigma }^2\mathrm{/}c,\sigma ))$ to the more precise $6\min ({\sigma }^2\mathrm{/}c,3\sigma )$.