  Seeking to improve model generalization, we consider a new approach based on
distributionally robust learning (DRL) that applies stochastic gradient descent
to the outer minimization problem. Our algorithm efficiently estimates the
gradient of the inner maximization problem through multi-level Monte Carlo
randomization. Leveraging theoretical results that shed light on why standard
gradient estimators fail, we establish the optimal parameterization of the
gradient estimators of our approach that balances a fundamental tradeoff
between computation time and statistical variance. Numerical experiments
demonstrate that our DRL approach yields significant benefits over previous
work.
