Gradient descent can also jump out of a local minimum if the learning rate is large enough, so they're equal in that sense.

But it does make sense that a random walk would be more efficient in very high dimensional problems!