  We propose matrix norm inequalities that extend the Recht-R\'e (2012)
conjecture on a noncommutative AM-GM inequality by supplementing it with
another inequality that accounts for single-shuffle, which is a widely used
without-replacement sampling scheme that shuffles only once in the beginning
and is overlooked in the Recht-R\'e conjecture. Instead of general positive
semidefinite matrices, we restrict our attention to positive definite matrices
with small enough condition numbers, which are more relevant to matrices that
arise in the analysis of SGD. For such matrices, we conjecture that the means
of matrix products corresponding to with- and without-replacement variants of
SGD satisfy a series of spectral norm inequalities that can be summarized as:
"single-shuffle SGD converges faster than random-reshuffle SGD, which is in
turn faster than with-replacement SGD." We present theorems that support our
conjecture by proving several special cases.
