Stochastic Constrained DRO with a Complexity Independent of Sample Size
This work addresses the challenge of efficient DRO training for robust models against distribution shifts, offering practical improvements for machine learning applications, though it appears incremental in method development.
The paper tackles the problem of solving Kullback-Leibler divergence constrained Distributionally Robust Optimization (DRO) for both non-convex and convex losses by proposing stochastic algorithms with complexity independent of sample size and constant batch size, achieving nearly optimal complexity bounds for stationary and optimal solutions.
Distributionally Robust Optimization (DRO), as a popular method to train robust models against distribution shift between training and test sets, has received tremendous attention in recent years. In this paper, we propose and analyze stochastic algorithms that apply to both non-convex and convex losses for solving Kullback Leibler divergence constrained DRO problem. Compared with existing methods solving this problem, our stochastic algorithms not only enjoy competitive if not better complexity independent of sample size but also just require a constant batch size at every iteration, which is more practical for broad applications. We establish a nearly optimal complexity bound for finding an $ε$ stationary solution for non-convex losses and an optimal complexity for finding an $ε$ optimal solution for convex losses. Empirical studies demonstrate the effectiveness of the proposed algorithms for solving non-convex and convex constrained DRO problems.