  Distributionally robust supervised learning (DRSL) is emerging as a key
paradigm for building reliable machine learning systems for real-world
applications -- reflecting the need for classifiers and predictive models that
are robust to the distribution shifts that arise from phenomena such as
selection bias or nonstationarity. Existing algorithms for solving Wasserstein
DRSL -- one of the most popular DRSL frameworks based around robustness to
perturbations in the Wasserstein distance -- involve solving complex
subproblems or fail to make use of stochastic gradients, limiting their use in
large-scale machine learning problems. We revisit Wasserstein DRSL through the
lens of min-max optimization and derive scalable and efficiently implementable
stochastic extra-gradient algorithms which provably achieve faster convergence
rates than existing approaches. We demonstrate their effectiveness on synthetic
and real data when compared to existing DRSL approaches. Key to our results is
the use of variance reduction and random reshuffling to accelerate stochastic
min-max optimization, the analysis of which may be of independent interest.
