A Caltech Library Service

Fast Distributionally Robust Learning with Variance Reduced Min-Max Optimization

Yu, Yaodong and Lin, Tianyi and Mazumdar, Eric and Jordan, Michael I. (2021) Fast Distributionally Robust Learning with Variance Reduced Min-Max Optimization. . (Unpublished)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


Distributionally robust supervised learning (DRSL) is emerging as a key paradigm for building reliable machine learning systems for real-world applications -- reflecting the need for classifiers and predictive models that are robust to the distribution shifts that arise from phenomena such as selection bias or nonstationarity. Existing algorithms for solving Wasserstein DRSL -- one of the most popular DRSL frameworks based around robustness to perturbations in the Wasserstein distance -- involve solving complex subproblems or fail to make use of stochastic gradients, limiting their use in large-scale machine learning problems. We revisit Wasserstein DRSL through the lens of min-max optimization and derive scalable and efficiently implementable stochastic extra-gradient algorithms which provably achieve faster convergence rates than existing approaches. We demonstrate their effectiveness on synthetic and real data when compared to existing DRSL approaches. Key to our results is the use of variance reduction and random reshuffling to accelerate stochastic min-max optimization, the analysis of which may be of independent interest.

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Yu, Yaodong0000-0003-0540-8526
Lin, Tianyi0000-0002-5323-1852
Mazumdar, Eric0000-0002-1815-269X
Jordan, Michael I.0000-0001-8935-817X
Additional Information:Yaodong Yu, Tianyi Lin and Eric Mazumdar contributed equally to this work. This work was supported in part by the Mathematical Data Science program of the Office of Naval Research under grant number N00014-18-1-2764.
Funding AgencyGrant Number
Office of Naval Research (ONR)N00014-18-1-2764
Record Number:CaltechAUTHORS:20210903-213710817
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:110724
Deposited By: George Porter
Deposited On:07 Sep 2021 16:00
Last Modified:07 Sep 2021 19:36

Repository Staff Only: item control page