Distributionally robust optimization (DRO) minimizes worst-case risk under distributional uncertainty, but its decisions can be suboptimal in terms of their excess risk, or regret. We study this gap for multivariate least-squares regression, assuming that the observed source law and unknown target law differ by an adversarial 2-Wasserstein perturbation of size $\varepsilon$.
Asymptotic complexity and the $\varepsilon \to 0$ limit
We first identify the asymptotic complexity of robust decision-making in the $\varepsilon \to 0$ limit, characterized by a problem-specific condition number $κ$.
Instance-optimal behavior for small $\varepsilon$
Here, a wide spectrum of simple algorithms, including DRO, achieve the instance-optimal rate of $O(κ\varepsilon^2)$.
Fixed $\varepsilon > 0$: when DRO is minimax
For fixed $\varepsilon > 0$, we prove that DRO still achieves the minimax rate if the problem has bounded residual effective rank.
On the other hand, we identify significant failure modes where DRO is provably suboptimal by dimension-dependent factors.
Minimax-rate alternatives and algorithms
Fortunately, we prove that two alternative procedures, minimax regret optimization (MRO) and spectral-norm regularization (SNR), attain the minimax rate. We derive an exact convex reformulation of MRO and an accelerated proximal algorithm for SNR, along with high-probability finite-sample guarantees.
Numerical experiments
We support these theoretical results with numerical experiments separating the performance of MRO and SNR from DRO.