Large-Scale Methods for Distributionally Robust Optimization
This work addresses scalable optimization under uncertainty for machine learning applications, offering incremental improvements in efficiency and theoretical guarantees.
The paper tackles distributionally robust optimization for convex losses with CVaR and χ² divergence uncertainty sets, achieving algorithms with gradient evaluations independent of dataset size and parameters, and showing 9–36 times efficiency gains over full-batch methods in experiments on MNIST and ImageNet.
We propose and analyze algorithms for distributionally robust optimization of convex losses with conditional value at risk (CVaR) and $χ^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 $χ^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 $χ^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.