Comment by mjburgess

The more dimensions, the simpler the surface. With enough dimensionality, everything is a straight line. I'd expect "random direction" grad desc to improve the more dimensionality the data has, as in that space, the data surface itself is simple.