Large-Scale Methods for Distributionally Robust Optimization
arXiv:2010.05893
Abstract
We propose and analyze algorithms for distributionally robust optimization of convex losses with conditional value at risk (CVaR) and 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 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 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.
arXiv comment63 pages, NeurIPS 2020
References in corpus (11)
- Rényi Divergence and Kullback-Leibler Divergence
- Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes
- Distributionally Robust Neural Networks for Group Shifts: On the Importance of Regularization for Worst-Case Generalization
- Robust Wasserstein Profile Inference and Applications to Machine Learning
- Fairness Without Demographics in Repeated Loss Minimization
- Learning with Average Top-k Loss
- Robust Optimization for Fairness with Noisy Protected Groups
- Minimizing the Maximal Loss: How and Why?
- Ordered SGD: A New Stochastic Optimization Framework for Empirical Risk Minimization
- Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization via Information Theory
- Adaptive Sampling for Stochastic Risk-Averse Learning