First-Order Methods for Distributionally Robust Constrained Optimization

Abstract

We consider constrained optimization problems in which input data are affected by estimation errors. In such settings, Wasserstein distributionally robust optimization provides a principled framework to mitigate model risk by optimizing against worst-case distributions within Wasserstein ambiguity sets. However, the numerical resolution of the resulting problems remains challenging, especially in constrained and combinatorial settings. In this paper, we propose a tractable stochastic approach based on two key ingredients: (i) an entropic regularization of the distributionally robust value function, which makes it possible to compute stochastic gradient estimators, and (ii) the combination of these estimators with a stochastic Frank-Wolfe algorithm, allowing us to optimize the regularized robust objective while naturally handling constraints. We illustrate the method, and its interests against empirical risk minimization, on two classical optimization problems, the minimum quadratic spanning tree and the traffic assignment problems. Our approach provides a general, practical way to address Wasserstein distributionally robust formulations in the presence of constraints.