There are two kinds of convergence proofs - the ones that get you a 1/k or 1/k^2 rate, and the ones that get you "linear" or "superlinear" convergence (which is

There are two kinds of convergence proofs - the ones that get you a 1/k or 1/k^2 rate, and the ones that get you "linear" or "superlinear" convergence (which is optimization jargon for exponential/superexponential decay of the error). The latter require way too strong of assumptions to be that useful in practice, and we generally think of them as just "local" convergence theorems - i.e. the assumptions they make start to be true when you get close enough to the minimum, and the fast convergence kicks in at that point. Which is nice, but getting close enough in the first place is often 99% of the problem!