  A recent line of ground-breaking results for permutation-based SGD has
corroborated a widely observed phenomenon: random permutations offer faster
convergence than with-replacement sampling. However, is random optimal? We show
that this depends heavily on what functions we are optimizing, and the
convergence gap between optimal and random permutations can vary from
exponential to nonexistent. We first show that for 1-dimensional strongly
convex functions, with smooth second derivatives, there exist optimal
permutations that offer exponentially faster convergence compared to random.
However, for general strongly convex functions, random permutations are
optimal. Finally, we show that for quadratic, strongly-convex functions, there
are easy-to-construct permutations that lead to accelerated convergence
compared to random. Our results suggest that a general convergence
characterization of optimal permutations cannot capture the nuances of
individual function classes, and can mistakenly indicate that one cannot do
much better than random.
