Nesterov's method attains super-linear convergence on Convex functions. They don't really (if I remember right) work otherwise; but then this is okay, since Convex problems are really the only ones we can solve in poly-time (esp. if P/=NP and UGC is true).

SA/RR are global optimization methods which come with very little (if any?) complexity guarantees.