  Distributionally Robust Optimization (DRO), as a popular method to train
robust models against distribution shift between training and test sets, has
received tremendous attention in recent years. In this paper, we propose and
analyze stochastic algorithms that apply to both non-convex and convex losses
for solving Kullback Leibler divergence constrained DRO problem. Compared with
existing methods solving this problem, our stochastic algorithms not only enjoy
competitive if not better complexity independent of sample size but also just
require a constant batch size at every iteration, which is more practical for
broad applications. We establish a nearly optimal complexity bound for finding
an $\epsilon$ stationary solution for non-convex losses and an optimal
complexity for finding an $\epsilon$ optimal solution for convex losses.
Empirical studies demonstrate the effectiveness of the proposed algorithms for
solving non-convex and convex constrained DRO problems.
