Regret-Optimal Wasserstein-Robust Regression

Wasserstein distributionally robust optimization (DRO) is a prominent paradigm for robust decision-making in the face of distributional uncertainty. Given a nominal data distribution, DRO selects a decision which minimizes the risk for a worst-case data distribution within a prescribed Wasserstein radius $\varepsilon$ of the nominal distribution. In this paper, we investigate the quality of DRO decisions when evaluated on a worst-case distribution within a 2-Wasserstein $\varepsilon$-neighborhood of the nominal distribution, as measured by excess risk or ex-ante regret. Beginning with multivariate linear regression and extending to ridge regression, we first identify the asymptotic complexity of robust decision-making in the $\varepsilon \to 0$ limit, characterized by a problem-specific condition number $\kappa$. In this regime, a wide spectrum of simple algorithms, including DRO, achieve the instance-optimal rate of $O(\kappa \varepsilon^2)$. For fixed $\varepsilon > 0$, we prove that DRO still achieves the minimax rate if the problem is of an appropriate ``low rank''. On the other hand, we identify significant failure modes where DRO is provably suboptimal by dimension-dependent factors. To resolve this, we introduce a new condition number reduction (CNR) procedure which achieves the optimal rate and admits tractable approximation algorithms. We support these theoretical results with numerical experiments comparing the performance of various estimators including DRO and CNR.