We propose and analyze algorithms for distributionally robust optimization of convex losses with conditional value at risk (CVaR) and $\chi^2$ divergence uncertainty sets. We prove that our algorithms require a number of gradient evaluations independent of training set size and number of parameters, making them suitable for large-scale applications. For $\chi^2$ uncertainty sets these are the first such guarantees in the literature, and for CVaR our guarantees scale linearly in the uncertainty level rather than quadratically as in previous work. We also provide lower bounds proving the worst-case optimality of our algorithms for CVaR and a penalized version of the $\chi^2$ problem. Our primary technical contributions are novel bounds on the bias of batch robust risk estimation and the variance of a multilevel Monte Carlo gradient estimator due to [Blanchet & Glynn, 2015]. Experiments on MNIST and ImageNet confirm the theoretical scaling of our algorithms, which are 9-36 times more efficient than full-batch methods.

Summary and Contributions: The paper studies the use of batch stochastic gradient methods to solve large scale DRO problems. In these scenarios, we face two problems: (1) Stochastic gradient estimates of DRO problems are biased; (2) Due to the size of large-scale problems, the convergence rate of the methods used to tackle them should not depend on either the number of parameters d or number of training examples N. The authors tackled problem (1) by defining a surrogate objective for which the gradient estimates are unbiased. Then, by carefully bounding the difference between the true and surrogate objectives as a function of the batch size n, the authors are able to give optimality bounds for the true cost by optimizing the surrogate cost, using a large enough batch size. Moreover, for some classes of robust risks, the authors also bound the variance of the gradient estimates. This allows them to use an accelerated version of the stochastic gradient method which achieves tighter convergence bounds.

We propose and analyze algorithms for distributionally robust optimization of convex losses with conditional value at risk (CVaR) and \chi 2 divergence uncertainty sets. We prove that our algorithms require a number of gradient evaluations independent of training set size and number of parameters, making them suitable for large-scale applications. For \chi 2 uncertainty sets these are the first such guarantees in the literature, and for CVaR our guarantees scale linearly in the uncertainty level rather than quadratically as in previous work. We also provide lower bounds proving the worst-case optimality of our algorithms for CVaR and a penalized version of the \chi 2 problem. Our primary technical contributions are novel bounds on the bias of batch robust risk estimation and the variance of a multilevel Monte Carlo gradient estimator due to [Blanchet & Glynn, 2015].