  Stochastic gradient methods for machine learning and optimization problems
are usually analyzed assuming data points are sampled \emph{with} replacement.
In practice, however, sampling \emph{without} replacement is very common,
easier to implement in many cases, and often performs better. In this paper, we
provide competitive convergence guarantees for without-replacement sampling,
under various scenarios, for three types of algorithms: Any algorithm with
online regret guarantees, stochastic gradient descent, and SVRG. A useful
application of our SVRG analysis is a nearly-optimal algorithm for regularized
least squares in a distributed setting, in terms of both communication
complexity and runtime complexity, when the data is randomly partitioned and
the condition number can be as large as the data size per machine (up to
logarithmic factors). Our proof techniques combine ideas from stochastic
optimization, adversarial online learning, and transductive learning theory,
and can potentially be applied to other stochastic optimization and learning
problems.
