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 ε. We first identify the asymptotic complexity of robust decision-making in the ε→0 limit, characterized by a problem-specific condition number κ. Here, a wide spectrum of simple algorithms, including DRO, achieve the instance-optimal rate of O(κε2). For fixed ε>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. 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. We support these theoretical results with numerical experiments separating the performance of MRO and SNR from DRO.
Figures & tables
Estimator A^
ERM
DROε
MROε
SNRε
Robust regret
∞
(min{p,m}κ+mκ)ε2
κε2
κε2
Minimax optimal?
×
×
✓
✓
Computation
Closed form
Convex reformulation
(New) convex reformulation
Accelerated proximal gradient method (FISTA)
Table 1: Worst-case robust regret Rε(A^,G(κ)) for our running estimators, up to absolute multiplicative constants, for ε>0 and κ≥2 . Computation uses second-moment matrices.
σk⋆>τk⋆≥σk⋆+1,τk=∑i=1kσi/(k+2α).
Algorithm 2 ProxSpecSq : proximal map of α∥⋅∥op2
Figure 1: Target population regret R(A^[Ps,n],P) for Settings A (left) and B (right). Solid curves show finite-sample averages, while dashed curves show population benchmarks. For Setting B, the dashed vertical line marks the corruption budget ε=1 .
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
Figure 2: Target population regret R(A^[Ps,n],Pr) for Setting C, as a function of the target residual effective rank r=reff(ΣEPr) .
Distributionally robust optimization (DRO) studies parameter estimation under uncertainty in the underlying probability distribution and has emerged as a principled framework for analyzing robustness and generalization. In particular, Wasserstein DRO, with distributional uncertainty induced by the Wasserstein distance, generalizes several popular regularizers. This paper studies Wasserstein DRO linear regression, unifying square-root Lasso and adversarial linear regression as important special cases. We prove that many properties of these two special cases carry over to this general method. In particular, we show (i) deterministic and non-asymptotic in-sample error bounds O(n−1/2) in general and O(n−1) under design matrix and sparsity conditions; (ii) insensitivity to the noise level, also known as the pivotal property; and (iii) solution equivalences for small and large ambiguity sets. The key proof step is to recast the method into a quadratic form, mimicking adversarial linear regression. We also show that the method can be solved efficiently, and we validate our findings through numerical simulations.
Elis Stefansson, David Vävinggren, Antônio H. Ribeiro
Uppsala University, Sweden · Science for Life Laboratory, Sweden
Distributionally robust optimization (DRO) is widely used for decision-making under uncertainty, but its adversarial focus on worst-case loss can lead to overly conservative policies. To mitigate this, we study ex-ante Distributionally Robust Regret Optimization (DRRO) with Wasserstein ambiguity sets, designed to balance robustness with upside potential. We develop a theory of Wasserstein DRRO (WDRRO) paralleling Wasserstein DRO. Under smoothness and regularity, WDRRO selects among ERM optima by a first-order gradient-discrepancy rule. If the ERM optimizer is unique, first-order sensitivity vanishes and a second-order expansion governs deviations. For convex quadratics ERM and DRRO coincide for any radius. We then study regimes where these assumptions fail: nondifferentiable max-affine losses, discrete references, and larger radii, where WDRRO can differ from ERM and WDRO. We show that computing WDRRO regret is NP-hard even without bilinear terms. Nevertheless, we develop exact algorithms, a tractable convex relaxation with guarantees, and experiments showing tightness and loss-dependent behavior.
Lukas-Benedikt Fiechtner, Jose Blanchet
Institute of Computational and Mathematical Engineering Stanford University · Institute of Computational and Mathematical Engineering Department of Management Science and Engineering Stanford University
We study distributionally robust optimization (DRO) for robust inference when the worst-case distribution is continuous, leading to significant computational challenges due to the infinite-dimensional nature of the optimization problem. Unlike traditional discrete DRO approaches, which often suffer from scalability issues, limited generalization, and costly worst-case inference, our framework exploits Brenier's theorem to characterize the least favorable distribution as the pushforward of a transport map from a continuous reference measure. This characterization motivates our study of the minimax problem in Wasserstein space. We propose an iterative algorithmic framework with multiple variants and establish global convergence guarantees under mild assumptions, deriving complexity bounds in terms of subgradient evaluations and inexact Jordan-Kinderlehrer-Otto updates. Numerical results with neural network-based transport maps demonstrate that the proposed method enables both stable training of robust classifiers and effective worst-case inference for classification tasks.
Linglingzhi Zhu, Yunqin Zhu, Yao Xie
1H. Milton Stewart School of Industrial and Systems Engineering Georgia Institute of Technology