Drago: Primal-Dual Coupled Variance Reduction for Faster Distributionally Robust Optimization
This work addresses faster optimization for robust machine learning models, but it appears incremental as it builds on existing DRO methods with specific algorithmic improvements.
The paper tackles the problem of distributionally robust optimization (DRO) with convex uncertainty sets by introducing Drago, a stochastic primal-dual algorithm that achieves a state-of-the-art linear convergence rate, as demonstrated in numerical benchmarks on regression and classification tasks.
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 that 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 with a fine-grained dependency on primal and dual condition numbers. Theoretical results are supported by numerical benchmarks on regression and classification tasks.