stat.MLOct 30, 2026

Regret-Optimal Wasserstein-Robust Linear Regression

Authors: Sloan Nietert, Daniel Kuhn

Organizations: EPFL

Abstract

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. We first identify the asymptotic complexity of robust decision-making in the ε→0\varepsilon \to 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)O(κ\varepsilon^2). For fixed ε>0\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. 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

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Distributionally robust linear regression through the lens of adversarial training

    Sep 30, 2026Elis Stefansson, David Vävinggren, Antônio H. RibeiroRobust RegressionDistributionally Robust Optimization

  2. Wasserstein Distributionally Robust Regret Optimization

    Apr 15, 2025Lukas-Benedikt Fiechtner, Jose BlanchetDistributionally Robust OptimizationRobust Optimization

  3. Distributionally Robust Optimization via Iterative Algorithms in Continuous Probability Spaces

    Dec 29, 2024Linglingzhi Zhu, Yunqin Zhu, Yao XieDistributionally Robust OptimizationWasserstein Distributionally Robust Optimization