  Randomized algorithms that base iteration-level decisions on samples from
some pool are ubiquitous in machine learning and optimization. Examples include
stochastic gradient descent and randomized coordinate descent. This paper makes
progress at theoretically evaluating the difference in performance between
sampling with- and without-replacement in such algorithms. Focusing on least
means squares optimization, we formulate a noncommutative arithmetic-geometric
mean inequality that would prove that the expected convergence rate of
without-replacement sampling is faster than that of with-replacement sampling.
We demonstrate that this inequality holds for many classes of random matrices
and for some pathological examples as well. We provide a deterministic
worst-case bound on the gap between the discrepancy between the two sampling
models, and explore some of the impediments to proving this inequality in full
generality. We detail the consequences of this inequality for stochastic
gradient descent and the randomized Kaczmarz algorithm for solving linear
systems.
