Regret-Optimal Wasserstein-Robust Linear Regression

AI summary

Overview

Research area: Statistical machine learning and optimization — specifically distributionally robust optimization (DRO), Wasserstein-robust estimation, and multivariate linear regression theory.

Technical level: Advanced. The paper relies on Bures–Wasserstein geometry of second-moment matrices, spectral perturbation theory (a Davis–Kahan–Wedin-type argument), convex duality, and Ky Fan variational principles. The high-level message is accessible, but the derivations are not.

Scope: A theoretical and algorithmic comparison of four estimators (ERM, Wasserstein DRO, minimax regret optimization, and spectral-norm regularization) for multivariate least-squares regression when the target distribution is an adversarial 2-Wasserstein perturbation of the observed source distribution.

What This Paper Is About

Wasserstein DRO picks the predictor that minimizes the worst-case risk over a ball of distributions around the observed data, but the quantity that actually matters is excess risk — the regret relative to the best predictor for the true, unknown target distribution. These two objectives are not the same, so a DRO decision can be robust in the wrong sense.

The paper asks a sharp question: for multivariate linear regression under an adversarial 2-Wasserstein perturbation of size ε, when does DRO make near-optimal decisions in terms of regret, and when can it be provably beaten by simple alternatives?

Key Contributions

1. An exact asymptotic characterization of robust estimation difficulty. The authors define a problem-specific condition number κ_P and prove that the local minimax robust regret satisfies R_ε^⋆(P) = κ_P ε² + o(ε²) as ε ↓ 0, with a closed-form formula κ_P = 1 + λ_max(A_P A_P^⊤ + Σ_E^P / λ_min(Σ_X^P)).

2. A non-asymptotic separation between estimators. For the well-conditioned class G(κ) = {P ∈ P*: κ_P ≤ κ}, they prove the minimax rate is Θ(κ ε²), attained by MRO and SNR, while ERM can have infinite regret and DRO is suboptimal by a dimension-dependent factor (for κ ≥ 2 and p ≥ m, its worst-case regret scales as √m · κ ε²).

3. A rank-adaptive guarantee for DRO. DRO does achieve the minimax rate when the residual second moment has bounded effective rank r_eff(Σ_E^P) = tr(Σ_E^P)/‖Σ_E^P‖_op, giving R_ε(DRO_ε, P) ≲ (√(min{p,r})(κ_P−1) + √(r(κ_P−1)) + κ_P) ε².

4. Tractable algorithms and finite-sample theory. An exact lifted convex reformulation of MRO, an accelerated proximal (FISTA-based) algorithm for SNR reaching objective gap δ in O(δ^{-1/2}) iterations per SVD, and high-probability finite-sample regret bounds under two sampling models with fourth-moment assumptions.

Main Findings

• The condition number controls local complexity. All four estimators — ERM, DRO, MRO, and SNR — attain the local rate κ_P ε² up to absolute multiplicative constants as ε ↓ 0. In the small-perturbation limit, the choice among them barely matters.

• For fixed ε > 0, the choice matters enormously. MRO and SNR achieve the minimax rate Θ(κ ε²) for every ε > 0 over G(κ). ERM's worst-case robust regret is ∞. DRO's is Θ((√(min{p,m})(κ−1) + √(m(κ−1)) + κ) ε²), which for κ ≥ 2 and p ≥ m reduces to Θ(√m κ ε²).

• DRO is rescued by low residual effective rank. The suboptimality is driven by independent residual noise spread across many response coordinates: such noise adds an additive constant to target risk and cancels from regret, yet can still distort DRO's decision. When m = O(1), or more generally when Σ_E^P has O(1) effective rank, DRO is minimax optimal. In the worst case, the effective rank can be as large as m.

• A regret stability lemma drives the upper bounds. For any A, P ∈ P* and Q ∈ P₂(R^d), |√R(A,P) − √R(A,Q)| ≤ (2√κ_P + ‖A‖_op) W₂(P,Q). Specialized to A = A_P, this gives R(A_P, Q) ≤ 4κ_P W₂(P,Q)². The operator-norm term explains precisely why the SNR penalty ‖A‖_op² is the right regularizer.

• A closed-form condition number with interpretable bounds. Theorem 2.2 yields 1 + max{‖A_P‖_op², λ_max(Σ_E^P)/λ_min(Σ_X^P)} ≤ κ_P ≤ 1 + ‖A_P‖_op² + λ_max(Σ_E^P)/λ_min(Σ_X^P). The additive 1 comes from response-only perturbations; the eigenvalue term comes from feature-only perturbations.

• Exact convex reformulation of MRO. Despite regret being convex in Σ (a seeming obstruction to maximizing over the ambiguity ball), the MRO objective equals inf_η D(A, η) for an explicit convex extended-value function D built from tr_p, the sum of the p largest eigenvalues, over the domain η > 1 + ‖A‖_op².

• SNR is the practical winner. It is convex, has a simple subgradient 2AΣ̃_X − 2Σ̃_YX + 2ε²‖A‖_op u vᵀ, shares MRO's minimax optimality, and is solvable by an accelerated proximal method.

• Synthetic experiments confirm the theory. Numerical experiments separate the performance of MRO and SNR from DRO as predicted. (The paper reports the qualitative separation; specific numerical values are outside the provided content.)

Methodology in Plain English

The authors reduce the entire problem to second moments. Least-squares risk depends on a distribution only through its second-moment matrix Σ_P, so a 2-Wasserstein ball around a distribution becomes a Bures ball around Σ_P — the set of matrices (Σ_P^{1/2} + Δ)(Σ_P^{1/2} + Δ)ᵀ with ‖Δ‖_F ≤ ε. This turns a problem over probability measures into a finite-dimensional matrix problem.

They define robust regret symmetrically, letting the reference law play either the source or the target role, so the analysis covers both directions of perturbation. For the ε → 0 regime, they compute the second-order sensitivity of regret to a Bures perturbation, separating feature and response perturbations to get the closed-form κ_P. For fixed ε, they prove a stability lemma bounding how fast square-root regret moves under W₂ perturbations, then plug the four estimators into it: MRO and SNR are analyzed directly via optimality, while ERM and DRO inherit bounds that depend on the worst condition number in a slightly enlarged ball.

Lower bounds come from explicit adversarial constructions. For ERM, a target with identically zero responses plus a source with a nearly collapsed feature forces the ERM solution to diverge even though κ_P = 1. For DRO, two constructions with λ_min(Σ_X^P) = ε² and independent residual noise across many response coordinates are analyzed via rotational symmetry and strong duality, showing that matching the optimal robust-risk value forces an inflated coefficient on the contracted feature. Computation is handled by convex reformulation (MRO) and accelerated proximal gradient (SNR), and finite-sample behavior is analyzed under adversarial corruption of i.i.d. target data and under i.i.d. source data with a perturbed population target.

Why This Matters

Impact on research. The paper reframes the evaluation of robust estimators: robust risk at the source is not a proxy for regret at the target, and the gap can be as large as a √m factor. It gives the DRO literature a precise, closed-form diagnostic (κ_P and the residual effective rank) for when DRO is trustworthy, and it identifies two computationally tractable alternatives that are always minimax optimal. It also connects to the regret-optimization literature (Agarwal and Zhang, 2022) and to second-order sensitivity analyses of Wasserstein DRO (Fiechtner and Blanchet, 2025, whose second-order coefficient specializes to the same condition number), while providing a self-contained Bures-geometric derivation and an explicit multivariate formula.

Real-world applications:

• Robust multivariate regression under distribution shift, where the deployment distribution differs adversarially from training data.
• Data poisoning and adversarial contamination of training sets, where the attacker perturbs the empirical law within a Wasserstein budget.
• Sequential state estimation and Kalman filtering, the application domain for which Shafieezadeh-Abadeh et al. (2018) developed Wasserstein DRO algorithms for exactly this multivariate linear regression setting.
• Multi-output prediction problems (multi-target regression, control with vector-valued outputs), where the paper shows the DRO-versus-MRO gap is largest and where scalar-response analyses cannot detect it.

Industry relevance. Teams that deploy Wasserstein-DRO-trained regressors for safety- or robustness-critical prediction now have a computable check: estimate κ_P and the effective rank of the residual second moment. If the residual covariance is high-rank and κ is meaningfully above 1, DRO's guarantee degrades by up to √m, and switching to SNR costs only a FISTA-based proximal solve.

Future Directions

• Convergence analysis for the MRO reformulation. The authors explicitly defer a complete convergence analysis of subgradient methods on the lifted convex objective D(A, η) to future work, justified by the fact that SNR shares MRO's minimax rate with far simpler computation.

• Extending beyond the non-degenerate case. The paper assumes Σ_X^P ≻ 0 and notes that the definition and non-asymptotic analysis can be adapted to singular Σ_X^P when the condition-number limit is finite (which occurs when the optimal risk is zero); this edge case is omitted.

• Tighter DRO characterizations. The rank-adaptive bound depends on the residual effective rank, which can be as large as m in the worst case. Whether intermediate regimes admit sharper, structure-adaptive DRO guarantees — or simple corrections that recover optimality — remains open.

• From population to practice. The finite-sample results cover two specific models (adversarially corrupted i.i.d. target data, and i.i.d. source data with a perturbed population target) under fourth-moment assumptions. Broader sampling models, heavy-tailed regimes, and empirical behavior of the MRO solver on real data are natural next steps.

Target Audience

Researchers and graduate students in statistical learning theory, distributionally robust optimization, and convex optimization who work on robustness to distribution shift. It is most valuable to readers already comfortable with Wasserstein DRO duality and matrix analysis, and to practitioners who use Wasserstein-robust regression and need to know when DRO's decision is actually the right one. Readers seeking an introductory treatment of DRO should look elsewhere first.

Authors’ 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.