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.

该文主要研究了基于 CVaR 和 chi-squared 分布的鲁棒优化问题，并提出了一种新的算法以及相应的优化方案。研究结果表明，该算法不仅适用于大规模应用，而且在实验中的效率比全样本方法高 9~36 倍。