Source-linked AI summary
Distributionally robust linear regression through the lens of adversarial training
Elis Stefansson, David Vävinggren, Antônio H. Ribeiro
TL;DR
Wasserstein DRO linear regression asks how robust and statistical properties of square-root Lasso and adversarial linear regression extend across Wasserstein orders. The paper derives an equivalent quadratic form and proves error-rate, pivotality, and radius-regime results for the general method. Its guarantees cover 2 ≤ p ≤ ∞, with the fast rate requiring additional conditions.
Problem
The paper asks whether properties known for the p=2 and p=∞ special cases also hold for other p-Wasserstein linear-regression methods.
Source: §1 · p. 2Method
The paper recasts Wasserstein DRO linear regression as an equivalent robust quadratic form that generalizes adversarial regression with jointly constrained sample perturbation budgets.
Source: §4 · p. 5Results
The method has deterministic in-sample error rates O(n^-1/2) generally and O(n^-1) under a restricted eigenvalue condition, is pivotal, and has characterized solutions for small and large ambiguity radii.
Source: §1 · p. 2, §5 · p. 5, §5.1 · p. 6Takeaways & Limitations
The results extend several square-root Lasso and adversarial-regression properties across the Wasserstein range 2 ≤ p ≤ ∞.
Source: §9 · p. 10The analysis is limited to Wasserstein DRO linear regression; the fast O(n^-1) rate additionally assumes a restricted eigenvalue condition and focuses on the infinity norm.
Source: §5.2 · p. 6, §9 · p. 10
Abstract
from arXiv · showhide
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.
1 Introduction
Wasserstein DRO linear regression minimizes squared loss under distributional uncertainty and asks whether properties known at the p=2 and p=∞ endpoints extend across 2 ≤ p ≤ ∞. The paper derives an equivalent robust-risk form and establishes error bounds and solution characterizations for the general method.
1 Introduction
- DRO minimizes expected loss under a worst-case distribution, with an ambiguity set represented by a radius-δ ball around the empirical distribution.Source: §1 · p. 1
- Square-root Lasso and adversarial linear regression are special cases associated with p = 2 and p = ∞, motivating the question of whether other p-Wasserstein methods share their properties.Source: §1 · pp. 1–2
- For 2 ≤ p ≤ ∞, Wasserstein DRO linear regression extends properties of square-root Lasso and adversarially trained linear regression, including pivotality, error rates, and small- and large-radius solution equivalences.The endpoint cases are p = 2 and p = ∞, respectively.Source: §1 · pp. 1–2
- The paper derives an equivalent robust-risk form and provides tailored numerical solvers, with numerical experiments validating the findings.Source: §1 · p. 2
- The paper proves deterministic, non-asymptotic in-sample error bounds of O(n^-1/2) generally and O(n^-1) under design-matrix and sparsity conditions.These generalize results previously known for square-root Lasso and adversarially trained linear regression.Source: §1 · p. 2
- The method characterizes solutions at both radius extremes: small δ gives minimum-norm interpolation in overparameterized settings, while large δ makes the zero solution optimal.Source: §1 · p. 2
2 Related work
Prior work connects DRO with regularization and adversarial training, but guarantees for Wasserstein linear regression have often focused on special cases or relied on assumptions unsuitable for square loss. This paper develops non-asymptotic deterministic guarantees across 2 ≤ p ≤ ∞ and a tractable reformulation for this setting.
Wasserstein DRO
- DRO is presented as a principled framework for accounting for distributional uncertainty in data.Source: §2 · p. 2
- Prior Wasserstein linear-regression studies mainly cover p = 1 or p = 2, whereas this work gives non-asymptotic guarantees for square loss uniformly over 2 ≤ p ≤ ∞.Source: §2 · p. 2
- The paper derives deterministic error bounds with explicit noise dependence and slow and fast rates uniformly in p, unlike cited generic bounds whose assumptions do not hold for square loss.The cited bounds may require Lipschitz loss or a compact domain; one cited p-independent slow rate is not applicable to square loss.Source: §2 · pp. 2–3
Connection between DRO and regularization
- Square-root Lasso and adversarial linear regression are endpoint cases of the broader method, whose error-rate and pivotal properties are extended across 2 ≤ p ≤ ∞.Source: §2 · p. 3
Tractable reformulations
- Existing finite convex-program reformulations assume losses that are finite maxima of concave functions, an assumption that does not hold for square loss.Source: §2 · p. 3
- For linear prediction models, a prior lower-dimensional dual form uses a possibly nonconvex univariate maximization; here that representation is unimodal for Wasserstein DRO linear regression and used in the solvers.The paper also considers the full range 2 ≤ p ≤ ∞, beyond cited convex forms for p = 2.Source: §2 · p. 3
3 Background
The background introduces Wasserstein DRO and its relationship to adversarial linear regression. It sets up the empirical ambiguity set and robust risk that the later equivalent-form analysis develops.
Wasserstein distance
- The p-Wasserstein distance measures distributional separation through transport cost, with the p=∞ case defined through an essential supremum.The transport cost reflects moving probability mass between points, and the infimum selects the least-cost coupling.Source: §3 · p. 3
Strong duality
- The DRO ambiguity set consists of distributions within Wasserstein radius δ of the empirical distribution, and its inner supremum is called the robust risk.Source: §3 · p. 4
- Strong duality gives an equivalent expression for the robust risk under the stated measurability and lower-bound condition on the loss.Source: §3 · p. 4
Wasserstein DRO linear regression
Adversarial linear regression
- The paper generalizes the adversarial linear-regression form to Wasserstein DRO as a step toward its later equivalent form.Source: §3 · p. 4
4 Equivalent form
The section recasts Wasserstein DRO linear regression's robust risk as a quadratic form. This form connects the general method to adversarial regression and recovers square-root Lasso and adversarial regression at the p=2 and p=∞ endpoints.
4 Equivalent form
- The robust risk has an equivalent quadratic form that underpins the paper's subsequent analytical properties.Source: §4 · p. 4
- The equivalent form acts like adversarial linear regression with sample-specific perturbation budgets constrained jointly by an overall p-norm budget.At p = ∞, the sample budgets become a fixed δ; for general 2 ≤ p ≤ ∞, they may vary across samples.Source: §4 · pp. 4–5
- At p = 2 the robust risk corresponds to square-root Lasso, while p = ∞ corresponds to adversarial linear regression.Source: §4 · p. 5
- The equality in the equivalent form holds for every 2 ≤ p ≤ ∞, extending earlier results that were limited to p = ∞ or compact sets.Source: §4 · p. 5
5 Error bounds
The section bounds average in-sample error for Wasserstein DRO linear regression and shows that its rate depends on the assumptions imposed. The tuning can be independent of the noise level, while a faster rate requires a restricted eigenvalue condition and a specified norm.
5 Error bounds
- The error target is average in-sample prediction error, bounded as a function of the ambiguity radius δ, which is tuned with sample size to obtain decay rates.The analysis treats the excess risk as the difference between expected risks at the estimated and true parameters.Source: §5 · p. 5, §5.1 · p. 5
- O(n^-1/2) holds generally, while O(n^-1) is available under a restricted eigenvalue condition with the infinity norm and sparsity assumptions.Both rates extend the corresponding results for square-root Lasso and adversarial linear regression.Source: §5 · p. 5, §5.2 · pp. 6–7
5.1 Slow rate of O(1/√n)
- The slow rate O(n^-1/2) requires no additional data assumptions and recovers the rates for square-root Lasso and adversarial linear regression at p = 2 and p = ∞.The tuning choice yielding this rate is independent of the noise level, so estimating that level is unnecessary.Source: §5 · p. 5, §5.1 · p. 6
5.2 Fast rate of O(1/n) under the restricted eigenvalue condition
- The fast rate O(n^-1) assumes a restricted eigenvalue condition, a sparse true parameter, and the infinity norm.The result applies across 2 ≤ p ≤ ∞ and recovers the corresponding special-case rates.Source: §5.2 · pp. 6–7
6 Small and large ambiguity balls
The paper characterizes Wasserstein DRO linear regression solutions at small and large ambiguity radii, extending radius-regime results beyond adversarial linear regression. In the overparametrized setting, sufficiently small radii yield minimum-norm interpolation, while sufficiently large radii yield the zero solution.
6 Small and large ambiguity balls
- These radius-regime characterizations extend results for adversarial linear regression to general p-Wasserstein regression and, notably, square-root Lasso.The authors describe the square-root Lasso result as novel to their knowledge.Source: §6 · p. 7
- For sufficiently large δ, the zero solution minimizes the robust risk; for sufficiently small δ, the minimum ∥·∥∗-norm interpolator does so when X has full row rank and n < d.The large-radius result gives an if-and-only-if condition, and the small-radius result also has a stated threshold condition.Source: §6 · pp. 7–8
- The interpolation threshold δS is shared by 2 < p ≤ ∞ and is higher for p = 2, so interpolation occurs sooner for square-root Lasso.The threshold is computable via a convex program.Source: §6 · p. 8
7 Numerical solvers
The paper presents two solvers for minimizing Wasserstein DRO linear-regression robust risk: a saddle-point formulation and an iterative η-trick method. The latter alternates efficient subproblems, while the experiments compare solver computation times and show predicted rate convergence.
7 Numerical solvers
- The saddle-point solver minimizes robust risk through a convex-concave saddle formulation, solved using disciplined saddle programming.Its objective is expressed as minβ supγ≥0 H(β, γ).Source: §7 · p. 8
- The η-trick solver alternates updates of t⋆, η, and β, with scalar optimization, closed-form weights, and weighted ridge regression, respectively.The paper reports that these subproblems can be solved quickly.Source: §7 · p. 8
- Figure 1 reports mean computation times over 10 repetitions for the saddle-point and η-trick solvers in the fast-rate experiment.The figure distinguishes the saddle-point solver with solid lines and the η-trick solver with dashed lines.Source: Figure 1 · p. 8
- Figure 2 compares fast and slow rates across p ∈ {2, 3, 6, ∞}, showing convergence toward O(n−1) and O(n−1/2), respectively.Curves average 10 runs and include ±1 standard deviation bands.Source: Figure 2 · p. 9
8 Numerical experiments
The simulations illustrate predicted fast and slow error rates, extreme ambiguity-radius behavior, and solver performance. The observed fast rate depends on a restricted eigenvalue condition, while correlated designs illustrate the slower-rate case.
8 Numerical experiments
- The rate simulations use 10 trials per (n, p) with ±1 standard deviation bands; the saddle-point solver is used for Figures 2 and 3.The experiments vary p over {2, 3, 6, ∞}.Source: §8 · p. 9
Fast rate.
- O(n−1) appears in the fast-rate experiment when the design satisfies the restricted eigenvalue condition; correlated designs can break that condition and yield O(n−1/2).The fast-rate setup uses independently sampled bounded design entries; the slow-rate setup uses correlated entries.Source: Fast rate · p. 9
- Figure 3 illustrates the extreme-radius outcomes in the overparametrized regime: the solution is zero for δ ≥ δL and interpolates for δ ≤ δS.The large-radius result is associated with Theorem 4 and the small-radius result with Theorem 5.Source: Figure 3 · p. 9, Fast rate · p. 9
- The η-trick solver is faster at larger sample sizes, with the largest gains for p = 2 and p = ∞, while both solvers achieve nearly identical prediction errors and robust-risk values.The solver comparison is from the fast-rate experiment.Source: Fast rate · p. 10
9 Conclusion
The conclusion summarizes Wasserstein DRO linear regression results for 2 ≤ p ≤ ∞, including error rates, pivotality, and radius-regime equivalences. The appendix supplies proofs and additional details, while the authors identify the study’s scope and possible extensions.
9 Conclusion
- For 2 ≤ p ≤ ∞, the paper reports a general O(n−1/2) error rate, an O(n−1) rate under a restricted eigenvalue condition, pivotality, and small- and large-radius solution equivalences.The robust risk is recast in an equivalent quadratic form, and simulations validate the theoretical findings.Source: §9 · p. 10
- The study is limited to Wasserstein DRO linear regression; other losses, nonparametric regression, and jointly growing d and n are future directions.The authors also note that their upper bounds have error rates independent of p, while cases with substantially different errors across p remain an open direction.Source: §9 · p. 10
Appendix
- The appendix provides additional material, particularly proofs, and follows the main-text section order..Source: Appendix · p. 13
A Background: Additional details
- For 1 ≤ p < 2, the appendix states that the robust risk is infinite for β ≠ 0.The stated reason is that the quadratic term grows faster than the p-power term.Source: A Background: Additional details · p. 14
B Equivalent forms: Proofs and additional details
- The equivalent-form proof reduces robust risk to scalar problems and uses strong duality for finite p; the p = ∞ case uses a dual-norm argument.The proof also fixes the response coordinate under the specified distance and expresses predictor deviations through the residual and βᵀu.Source: §B.1 · pp. 14–16
B.2 Proof of Corollary 1
The appendix proves that Wasserstein linear regression recovers square-root Lasso and adversarial linear regression as special cases, and establishes the slow-rate bound under the stated choice of ambiguity radius.
B.2 Proof of Corollary 1
- For p = 2, the formulation coincides with square-root Lasso when the dual norm is the 1-norm; for p = ∞, it coincides with adversarial linear regression.The proof also establishes convergence of V_p,δ(β) to V_∞,δ(β) as p tends to infinity.Source: §B.2 · p. 17
C.1 Slow rate: Proofs
- When K > 2c√π, choosing δ as specified yields the slow rate O(n^-1/2) with probability at least 1 − 4γ.The proof bounds the threshold δ̄ by O(1/√n) with probability at least 1 − 3γ.Source: §C.1 · p. 22
C.2 Fast rate: Proofs
The fast-rate proof combines case analysis with a restricted eigenvalue condition to obtain an O(1/n) rate. The appendix also uses a subdifferential rule for maxima to characterize when the zero vector minimizes robust risk.
C.2 Fast rate: Proofs
- Under the RE(s, 3) condition, bounded design entries, and the stated choice of δ, the proof obtains an O(1/n) rate with high probability, independently of p.The fast-rate result assumes Gaussian noise and a sparse β*; the probability bound is at least 1 − 5γ.Source: §C.2 · p. 25
D Small and large ambiguity balls: Proofs and additional details
- A subdifferential rule expresses the subdifferential of a maximum as the convex hull of the active functions’ subdifferentials.The proof invokes a generalized Danskin theorem for this rule.Source: §D.1 · pp. 25–26
D.1 Proof of Theorem 4
- The zero vector minimizes robust risk exactly when zero belongs to its subdifferential, which the proof computes using the generalized Danskin theorem.Source: §D.1 · pp. 25–26
D.2 Proof of Theorem 5
This section proves Theorem 5 by characterizing optimality conditions and procedures for computing and evaluating robust risk, and establishes design conditions for the fast-rate and slow-rate constructions. It also reports simulations supporting the corresponding $O(n^{-1})$ and $O(n^{-1/2})$ behavior.
D.2 Proof of Theorem 5
- Theorem 5’s optimality condition selects a dual maximizer with minimum ∞-norm for 2 < p ≤ ∞ and minimum 2-norm for p = 2.Lemma 8 links the primal subgradient condition to maximizing αᵀy subject to ∥Xᵀα∥ ≤ 1.Source: §D.2 · pp. 27–29
D.3 Computing δS via a convex program
- Compute δS by first maximizing αᵀy subject to ∥Xᵀα∥ ≤ 1, then minimizing the appropriate norm over the maximizers.If y ≠ 0 and the feasible set is strictly convex, the inner maximizer is unique and serves as ᾱ for any p.Source: §D.3 · p. 29
E Numerical solvers: Additional details
- Appendix E details two solvers that minimize robust risk and a third that evaluates it using one-dimensional subproblems.The minimization methods are the saddle-point solver and the η-trick solver; the evaluator exploits one-dimensional subproblems.Source: E Numerical solvers: Additional details · p. 30
E.1 Saddle-point formulation and solver
- For square-loss Wasserstein DRO with 2 ≤ p < ∞, Theorem 7 gives a saddle-point formulation with a convex-concave optimization objective.The formulation minimizes over β and maximizes over γ ≥ 0.Source: §E.1 · p. 30
E.2 η-trick solver
- For the ∞-norm Wasserstein cost, the η-trick solver alternates between weight updates and weighted ridge regression to minimize robust risk.The η-subproblem can be solved numerically or recovered explicitly from the maximizer in Theorem 1.Source: §E.2 · pp. 31, 33, 34
E.3 Fast robust risk evaluations
- For general δ > 0, 2 < p < ∞, and β ≠ 0, robust-risk evaluation reduces to unimodal inner subproblems and a convex outer minimization over λ.The inner supremum is solved numerically, and the outer problem is minimized with a scalar optimizer.Source: §E.3 · pp. 34–35
F Numerical experiments: Additional details
- The numerical-experiments appendix gives setup details for the fast-rate, slow-rate, and small- and large-δ simulations.These are additional details for the simulations in Section 8.Source: F Numerical experiments: Additional… · p. 35
F.1 Fast rate
- The fast-rate appendix reports that the design matrix satisfies the RE condition and provides additional simulations.Source: §F.1 · p. 35
- For independently uniform entries in [−1, 1], X satisfies RE(s, ℓ) with κ = 1/6 with arbitrarily high probability for sufficiently large n.Figure A.1 also shows the RE condition and δ ≥ ¯δ holding in the fast-rate simulations.Source: §F.1 · pp. 35–36, Figure A.1 · p. 36
- As n increases, e_q converges to a constant, making B and C converge to constants and yielding O(δ^2) = O(n^-1).Figure A.2 plots e_q across sample sizes; δ decreases as 1/√n.Source: §F.1 · p. 36, Figure A.2 · p. 37
F.2 Slow rate
- As n increases, the constructed columns’ correlation tends to 1, the RE condition fails, and the resulting rate is O(n^-1/2).Their smallest Gram-matrix eigenvalue is c0/√n, which tends to zero.Source: §F.2 · pp. 36–37
F.3 Small and large δ
In the small- and large-δ simulations, interpolation and zero estimates appear at the thresholds predicted by the theorems. The η-trick solver produces near-identical results to the saddle-point solver and is generally faster.
F.3 Small and large δ
- For p ∈{2, 3, 6, ∞}, error reaches numerical precision at δ ≤ δS, indicating interpolation; the transition is simultaneous for 2 < p ≤ ∞ and earlier for p = 2.The p = 2 threshold δS is larger than the shared threshold for 2 < p ≤ ∞.Source: §F.3 · pp. 37–38
F.4 Comparisons between the saddle-point solver and the η-trick solver
- The η-trick and saddle-point solvers produce near-identical results, with robust-risk error differences of 10^-6 to 10^-8.Figure A.3 compares error on the left and robust risk on the right.Source: Figure A.3 · p. 38, §F.4 · p. 38
- The η-trick solver is generally faster, by several orders of magnitude for p ∈{2, ∞}; both solvers are slower for p ∈{3, 6} because robust risk lacks a closed-form expression.Figure A.4 reports computation time and time ratio.Source: Figure A.4 · p. 38, §F.4 · p. 39
F.3 Small and large δ
- For large δ, ||β||∞ decreases when δ ≤ δL and becomes zero when δ ≥ δL; δL differs across p.Source: §F.3 · p. 38