Drago: Primal-Dual Coupled Variance Reduction for Faster Distributionally Robust Optimization
Abstract
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.
Cite
Text
Mehta et al. "Drago: Primal-Dual Coupled Variance Reduction for Faster Distributionally Robust Optimization." Neural Information Processing Systems, 2024. doi:10.52202/079017-4283Markdown
[Mehta et al. "Drago: Primal-Dual Coupled Variance Reduction for Faster Distributionally Robust Optimization." Neural Information Processing Systems, 2024.](https://mlanthology.org/neurips/2024/mehta2024neurips-drago/) doi:10.52202/079017-4283BibTeX
@inproceedings{mehta2024neurips-drago,
title = {{Drago: Primal-Dual Coupled Variance Reduction for Faster Distributionally Robust Optimization}},
author = {Mehta, Ronak and Diakonikolas, Jelena and Harchaoui, Zaid},
booktitle = {Neural Information Processing Systems},
year = {2024},
doi = {10.52202/079017-4283},
url = {https://mlanthology.org/neurips/2024/mehta2024neurips-drago/}
}