  Distributionally robust optimization (DRO) problems are increasingly seen as
a viable method to train machine learning models for improved model
generalization. These min-max formulations, however, are more difficult to
solve. We therefore provide a new stochastic gradient descent algorithm to
efficiently solve this DRO formulation. Our approach applies gradient descent
to the outer minimization formulation and estimates the gradient of the inner
maximization based on a sample average approximation. The latter uses a subset
of the data in each iteration, progressively increasing the subset size to
ensure convergence. Theoretical results include establishing the optimal manner
for growing the support size to balance a fundamental tradeoff between
stochastic error and computational effort. Empirical results demonstrate the
significant benefits of our approach over previous work, and also illustrate
how learning with DRO can improve generalization.
