Thanks for the links – they are very helpful. I also found this paper 1 that studied this question, and from the abstract:

Stochastic gradient methods for machine learning and optimization problems are usually analyzed assuming data points are sampled with replacement. In con- trast, sampling without replacement is far less understood, yet in practice it is very common, often easier to implement, and usually performs better.