Regret-Optimal Wasserstein-Robust Linear Regression
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 ε. 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.
Related
- Feature Priming in Online Linear Regression: Sparse-Regret Lower Bounds and Tight Coordinatewise Rates
- Regret-Optimal Linear-Quadratic Control under Distributional Drift
- Nearly Minimax Optimal Regret for Adversarial Linear Bandits with Strong Corruptions
- Distributionally robust linear regression through the lens of adversarial training
- Doubly robust target inference for generalized linear regression with completely missing covariates
BibTeX
@misc{nietert2026regretoptimal,
title = {{Regret-Optimal Wasserstein-Robust Linear Regression}},
author = {Sloan Nietert and Daniel Kuhn},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.42109},
eprint = {2610.42109},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.42109},
}
RIS
TY - UNPB
TI - Regret-Optimal Wasserstein-Robust Linear Regression
AU - Sloan Nietert
AU - Daniel Kuhn
PY - 2026
DA - 2026/10/30
PB - arXiv
DO - 10.48550/arxiv.2610.42109
UR - https://arxiv.org/abs/2610.42109
AB - 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.
ER -