Study finds better ways to reduce errors in robust linear regression
Regret-Optimal Wasserstein-Robust Linear Regression
Machine Learning
Summary
When making predictions with linear regression, the data used for training can differ slightly from the real-world data, causing mistakes. The authors studied methods to handle this difference, focusing on how to minimize regret, or extra errors, when the data shifts by a small amount. They found that the common DRO approach is good in some cases but can fail in others, especially for high-dimensional data. They proposed two alternative methods that work better across more situations and provided algorithms to implement them efficiently. Their work helps improve prediction accuracy when facing uncertain or changing data distributions.
What this means in practice
- •For data science teams: Improve robustness of linear regression models under data distribution shifts using the proposed minimax regret or spectral norm methods.
- •For machine learning engineers: Use the derived convex reformulation and accelerated algorithms to optimize regression models efficiently under uncertainty.
Authors
Sloan Nietert, Daniel Kuhn
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 $\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(κ\varepsilon^2)$. 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. 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.