How do these and other variants compare to simple Hill Climbing with random restarts, because I feel that gradient descent, simulated annealling etc are just local searches within the local search space.
SA/RR are global optimization methods which come with very little (if any?) complexity guarantees.
Ah thanks, I thought I missed something. That makes total sense.
"SA/RR are global optimization methods"
RR is definitely global, but (depending on your cooling function I guess) I would say SA is not.