@inproceedings{
mehta2024drago,
title={Drago: Primal-Dual Coupled Variance Reduction for Faster Distributionally Robust Optimization},
author={Ronak Mehta and Jelena Diakonikolas and Zaid Harchaoui},
booktitle={The Thirty-eighth Annual Conference on Neural Information Processing Systems},
year={2024},
url={https://openreview.net/forum?id=ujk0XrNTQZ}
}
We consider the penalized distributionally robust optimization (DRO) problem with a closed, convex uncertainty set, a setting that encompasses learning using $f$-DRO and spectral/$L$-risk minimization. We present Drago, a stochastic primal-dual algorithm which combines cyclic and randomized components with a carefully regularized primal update to achieve dual variance reduction. Owing to its design, Drago enjoys a state-of-the-art linear convergence rate on strongly convex-strongly concave DRO problems witha fine-grained dependency on primal and dual condition numbers. The theoretical results are supported with numerical benchmarks on regression and classification tasks.
Drago: Primal-Dual Coupled Variance Reduction for Faster Distributionally Robust Optimization
Ronak Mehta Jelena Diakonikolas Zaid Harchaoui