acceptodds
Under review as a conference paper at ICLR 2027

Distributionally robust linear regression through the lens of adversarial training

13 views

Abstract

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 in general and 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.

Primary area:
learning theory
Keywords:
Distributional robust optimization, regression, adversarial training

Reviews

Among:
Shape:
1234this paper, Top 32%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.50 over 4 reviews, above 68% of the others.
Reviewer_P1v4OpenReview ↗
Rating
3
Confidence
4
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper establishes a connection between adversarial training and Wasserstein distributionally robust optimization, which enables the error analysis for a slow rate n^{-1/2} and a fast rate n^{-1} based on Restricted eigenvalue condition (a classic analysis tool in statistics). The paper mainly focus on the linear regression.

Critical strengths
  1. Building a connection between two popular robust learning approaches, i.e., adversarial training and Wasserstein distributionally robust optimization. This connection is clean and insightful, as shown in Theorem 1.

  2. The authors provide both rigorous statistical analysis and numerical experiments.

  3. All insights.tools and technical details are well attributed and well organized, which is important in the current era.

Critical weaknesses

I do not see critical weakness for rejection.

Questions for authors
  1. Can the authors provide justifications for why to focus on the shrinking radius? I understand it is a standard assumption in relevant literature, but some justifications can be added to make the assumption valid.
  2. Can the authors discuss the possibility of extending the connection to nonlinear case?
3 comments

Thank you for the positive feedback. We appreciate it and try to address your questions bellow:

(Q1) Robustness versus regularization: Thank you for raising this important point. There is a dual use of the radius δ\delta in DRO that is crucial in this paper, so we are happy to clarify this. Indeed one can see it from two different perspectives:

  • Robustness perspective: On the one hand, we show in our paper that DRO is connected to adversarial attacks (p=∞p=\infty). So one can think of using DRO to defend the model against adversarial perturbations in input space. Here, one usually wants to guarantee δ\delta is of a similar magnitude as the attacks we want to defend against. And hence, a larger δ\delta might make the model more robust against such perturbations, but may also degrade generalisation in clean evaluation.

  • Regularization perspective: On the other hand, we connect DRO with Square-root lasso and other parameter shrinking methods. In this case, δ\delta is a tunable regularisation parameter akin to the regularization strength. Here our results show that one obtains near-oracle performance by shrinking δ∝1/n\delta \propto 1/\sqrt{n}. See also the adversarial training work [1] where the radius δ\delta is tuned for similar purposes. We will clarify this dual use in the paper.

(Q2) Extensions to the nonlinear case: That is an interesting question. There are extensions for adversarial linear regression to kernels [2] that should extend naturally to DRO linear regression as well. In the general nonlinear case, including neural networks, such extensions might not be possible, and there are some negative results showing it [3].

References:

[1] “Regularization properties of adversarially trained linear regression,” A. H. Ribeiro, D. Zachariah, F. Bach, and T. B. Schön. NeurIPS, 2023

[2] “Kernel Learning with Adversarial Features: Numerical Efficiency and Adaptive Regularization,” A. H. Ribeiro, D. Vävinggren, D. Zachariah, T. B. Schön, F. Bach. NeurIPS, 2025

[3] “Robustness Cannot be Reduced to Regularization: Studying Adversarial Training Beyond the Linear Case,” David A. R. Robin, Rafael Pinot, Yann Chevaleyre, arXiv:2606.21488, 2026

When we use adversarial training in practice, should we choose shrinking radius or fixed radius?

Our overall impression is that most of the times adversarial training is used in practice it focus on robustness. Hence, we would imagine that fixing the radius to a number that matches this level of robustness is the usual strategy.  However, the interpretation that the radius can work as a regularizer when you shrink it with the number of samples is also applicable for a linear model, as we highlight above.

Reviewer_HxpfOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
3
Presentation
2
Soundness
3(+1)
Read review
Paper summary

This paper studies linear regression under pp-Wasserstein distributionally robust optimization (DRO) for 2≤p≤∞2\leq p\leq\infty. The main result is a reformulation of the robust risk as an adversarial regression problem where each training sample has its own perturbation budget, subject to a shared constraint. This connects square-root Lasso (p=2p=2) and adversarial linear regression (p=∞p=\infty) in a single framework.

Using this reformulation, the authors prove non-asymptotic in-sample prediction error bounds of O(n−1/2)O(n^{-1/2}) and O(n−1)O(n^{-1}) under different assumptions. They also show that the ambiguity radius can be chosen without knowing the Gaussian noise variance, and characterize when the solution becomes a minimum-norm interpolator or the zero vector. Two optimization methods are presented, and synthetic experiments are used to check the theoretical rates, solution behavior, and computational costs.

Critical strengths
  1. A useful connection between Wasserstein DRO and adversarial training.

Theorem 1 is the strongest part of the paper. The robust quadratic form in Eq. (6) gives an exact connection between Wasserstein DRO and adversarial regression for the full range 2≤p≤∞2\leq p\leq\infty. The interpretation of sample-dependent perturbation budgets with a shared constraint is quite clear. More importantly, this formulation makes it possible to study the whole family using similar proof techniques.

  1. The theoretical results go beyond the two known special cases.

The error bounds and pivotal property extend known results for square-root Lasso and adversarial linear regression. I also find the results in Section 6 interesting, particularly Theorem 5, which shows that the interpolation threshold is the same for all p>2p>2, while p=2p=2 behaves differently. This gives a clearer picture of how the ambiguity radius affects the solution.

Critical weaknesses
  1. The theoretical guarantees need some clarification and correction.

In Theorem 2, the constant cc is defined through ∥v∥∞≤c∥v∥\|v\|_\infty\leq c\|v\|. However, the proof in Appendix C.1, around Eq. (A.9), uses the opposite inequality, ∥v∥≤c∥v∥∞\|v\|\leq c\|v\|_\infty. For example, with the Euclidean norm, the first inequality holds with c=1c=1, while the second generally requires a factor of d\sqrt d. This affects the claimed choice of KK and the high-probability guarantee for general norms.

The stated O(n−1)O(n^{-1}) rate also needs clearer qualification when the dimension or sparsity grows, since the explicit bound in Theorem 3 contains an s2s^2 term and the chosen radius depends on log⁡d\log d.

  1. The experiments do not show why an intermediate value of pp would be useful.

The main motivation is to study the whole range between square-root Lasso and adversarial linear regression. However, in Figure 2, the results for p=2,3,6,∞p=2,3,6,\infty are almost identical. The experiments confirm the theoretical rates, but they tell us little about when one value of pp should be preferred over another.

The experiments are also limited to synthetic data, with d=2d=2 or d=10d=10 in the convergence studies. There is no evaluation of held-out prediction performance under distribution shifts, which would help demonstrate the practical value of the DRO formulation. The solver comparison is useful, but it mainly compares the two proposed implementations.

Questions for authors
  1. Clarification: In Theorem 2, the definition of the norm-equivalence constant cc seems inconsistent with the inequality used in Appendix C.1. Which inequality is intended? Does correcting it change the stated condition K>2cπK>2c\sqrt{\pi} for general norms?

  2. Experimental evidence: Is there a setting where choosing 2<p<∞2<p<\infty gives a clear advantage over either p=2p=2 or p=∞p=\infty? The current experiments show very similar prediction errors across these values. A comparison under distribution shift or different noise conditions would help establish whether the intermediate cases offer something useful beyond the theoretical connection.

4 comments
AuthorsOpenReview ↗

Comment 1/3

Thanks for the valuable feedback. We address your questions and concerns below. We believe that this significantly improves the paper.

(W1 & Q1) Normalization constant cc: Thanks for seeing this. We rephrase the theorem. Particularly, the last part scaling with log(d)log(d) is true for the case when we have the infinity norm.

(Please see the next comment for continuation of this answer.)

AuthorsOpenReview ↗

Comment 2/3

(Continuation of the previous comment.)

(W2 & Q2) Concerning benefits of 2<p<∞2<p<\infty and the nature of the evaluations:

Concerning benefits of 2<p<∞2<p<\infty: Thanks for the comment. Indeed we did not focus on this aspect. Our motivation for studying the full range 2≤p≤∞2 \leq p \leq \infty was primarily to develop a unified understanding of DRO. Considering this range allows us to connect important properties previously studied separately for p=2p=2 and p=∞p=\infty. The interest in intermediate values of pp lies in what they reveal about these connections, without presupposing that they are preferable in practice.

Nonetheless, we agree that it is a valuable question: how one chooses pp given that many of them have similar properties. While we don’t have a definitive answer, we believe we can use our theory to provide insight to this question. Particularly, Theorem 2 provides a clear interpretation of the role of pp. When p=∞p=\infty, all samples have the same perturbation budget δ\delta. Thus we model an adversary that is uniform over the data. When p=2p=2, we instead allow an uneven perturbation budget over the data samples. Thus, the adversary can focus more of its adversarial budget for data samples that are particularly good to perturb to degrade performance. Going from p=2p=2 to p=∞p=\infty allows us to vary between the two extremes.

While we do not have a universal rule on how to pick such a pp, a simple experiment highlights the tradeoffs. The experiment is based on adding outliers to a simple linear regression setup

y_i = x_i^\top \beta^* + \varepsilon_i + M S_i C_i, \end{aligned}$$ where $x_i \sim N(0,I_{30})$, $\beta^* = (3,3,3,3,3,0,0,\dots,0)$, $\varepsilon_i \sim N(0,\sigma^2)$ with $\sigma=0.5$, $S_i$ is a random sign, $C_i \sim \mathrm{Bernoulli}(\tau)$, and $M>0$ is a constant. Here, $\tau$ controls the outlier frequency while $M$ controls the spike size of the outliers. We let $\tau \in \{1\\%,10\\%\}$ and $M \in \{5\sigma,20\sigma\}$ with results shown in the table below. The table shows the minimum in-sample error over $n=60$ samples by taking the optimal $\delta$ for each $p$ (avoids picking $\delta$ that is suboptimal for other values of $p$). | $M$ | $\tau$ | $p = 2$ | $p = 3$ | $p = 6$ | $p = \infty$ | |------:|----:|-----------:|-------:|-----------:|-----------:| | $5\sigma$ | 1% | **0.0615** | 0.0670 | 0.0698 | 0.0715 | | $5\sigma$ | 10% | 0.1930 | 0.1471 | **0.1449** | 0.1451 | | $20\sigma$ | 1% | 0.2183 | 0.0980 | 0.0930 | **0.0915** | | $20\sigma$ | 10% | 2.2864 | 1.2276 | 0.9168 | **0.8064** | In particular,, we see that for infrequent and small-magnitude outliers (first row), $p=2$ is optimal, while for more frequent and large-magnitude outliers (last row), $p=\infty$ is optimal, even though the performance for all $p$ degrades as we increase outliers. For intermediate setups (the two middle rows), intermediate $p=3$ and $p=6$ are slightly optimal or close to optimal. We did not find any case where these two $p$ are significantly better than both $p=2$ and $p=\infty$, but this could be invested more extensively in future work for other experiments. The reason why $p=2$ degrades more with outliers than $p=\infty$ can intuitively be understood as follows. Large outliers create large residuals. Due to the quadratic cost, large residuals become much larger when squared and are also more beneficial to perturb (steeper increase in error). Since $p=2$ can more adaptively pick which data to perturb (varying budget), it can focus its perturbation budget more on the outliers, creating larger errors compared to $p=\infty$, where the perturbation budget on each sample is fixed. This sensitivity to large residuals can also be seen in the difference of their objective functions: $$\begin{aligned} V_{2,\delta}(\beta) &= \frac{1}{n}\sum_{i=1}^n (x_i^\top \beta-y_i)^2+2\delta\lVert\beta\rVert_{\ast} \sqrt{\frac{1}{n}\sum_{i=1}^n (x_i^\top \beta-y_i)^2} + \delta^2\lVert\beta\rVert_{\ast}^2, \newline V_{\infty,\delta}(\beta) &= \frac{1}{n}\sum_{i=1}^n (x_i^\top\beta-y_i)^2 + 2\delta\lVert\beta\rVert_{\ast} \frac{1}{n}\sum_{i=1}^n \lvert x_i^\top\beta-y_i\rvert + \delta^2\lVert\beta\rVert_{\ast}^2. \end{aligned}$$ Here, the middle term for $V_{2,\delta}$ has the residuals squared while $V_{\infty,\delta}$ only has the absolute deviation. Thus, large residuals will affect $V_{2,\delta}$ more, which causes degradation for outliers when outliers are misleading (as in our experiment). Moreover, since the ambiguity sets decrease for larger $p$, we also have in general that $V_{2,\delta}(\beta) \geq V_{p,\delta}(\beta) \geq V_{\infty,\delta}(\beta)$, indicating that an intermediate $2<p<\infty$ can be optimal when a mix of characteristics of $p=2$ and $p=\infty$ is desirable. **(Please see the next comment for continuation of this answer.)**
AuthorsOpenReview ↗

Comment 3/3

(Continuation of the previous comment.)

The nature of the evaluations: Thanks for this comment. We thought this to be a reasonable amount of validation for a theoretical paper and provided reasonable confirmation of the results. We agree that considering distribution shifts is an interesting future direction. Concerning the numerical solvers, we mainly want to show that we can tractably solve the general DRO linear regression 2≤p≤∞2 \leq p \leq \infty (which has not been done before as far as we know) with two proposed novel solvers, where one of them (the η\eta-solver) can be significantly faster in some instances.

Thank you for the detailed response. The clarification about the norm constant addresses my main theoretical concern. The additional experiment is also helpful in showing how different values of pp behave under outliers, although the advantage of intermediate values is still somewhat limited. Overall, the response has addressed most of my concerns and improved my confidence in the paper. I will raise my rating from 2 to 3 .

Reviewer_PvnROpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies p-Wasserstein DRO linear regression with square loss, which unifies square-root Lasso (p = 2) and adversarially trained linear regression (p = ∞) as special cases. The core result, Theorem 1, shows that the robust risk equals an adversarial linear regression in which each sample has its own perturbation budget tᵢ, subject to the overall constraint ‖t‖_p ≤ n^{1/p}δ. Building on this form, the authors prove a slow rate O(n^{-1/2}) in general and a fast rate O(n^{-1}) under a restricted eigenvalue (RE) condition, with a choice of δ that does not depend on the noise level (the pivotal property). They also give necessary and sufficient thresholds δ_L for the zero solution to be optimal and δ_S for the minimum-norm interpolator to be optimal in the overparametrized regime. Finally, they propose two solvers, a saddle-point solver based on disciplined saddle programming and an η-trick solver that iterates weighted ridge regressions, and validate the results on synthetic data.

Critical strengths
  1. The problem is clearly posed and naturally motivated. Both known special cases enjoy good properties such as pivotality, and the paper asks whether the whole family in p retains them, which is a clean question.
  2. Theorem 1 is simple and elegant. Its interpretation as adversarial regression with per-sample budgets is intuitive and allows proof techniques from the adversarial setting to carry over directly. Corollary 1 also recovers both special cases from the same form in a few lines.
  3. The theoretical results are fairly complete, covering slow and fast rates, the pivotal property, and characterizations of the solution at both ends of the δ range, the latter as necessary and sufficient conditions. I checked the proofs of Theorems 1–5 and Lemmas 1–8 step by step, and the main steps are correct.
  4. The small-δ result is novel. To my knowledge, the interpolation threshold for p = 2 (square-root Lasso) is new, and the observation that the threshold differs between p = 2 and p > 2, so that square-root Lasso starts interpolating earlier, is interesting and is confirmed in Figure 3.
  5. The paper is clearly written and the related work is thorough, with an honest account of the relation to prior results (Kuhn et al. 2019, Thm. 6; Zhang et al. 2024; Shafiee et al. 2026). The code is released, and all figures are vector graphics.
  6. The η-trick solver is practically useful: for p = 2 and p = ∞ it is orders of magnitude faster than the saddle-point solver, and the robust risks of the two solvers differ by only 10⁻⁶–10⁻⁸.
Critical weaknesses
  1. The technical contribution is somewhat incremental. Lemma 3 is a direct application of Shafiee et al. (2026), Theorem 4(ii), as the authors state, and Theorem 1 adds a standard concave-maximization duality step on top of it. The proofs in Section 5 closely follow Ribeiro et al. (2023) and Xie & Huo (2024); the Case 1/Case 2 split in the proof of Theorem 3 comes directly from Xie & Huo, Theorem 2.3. Section 6 follows Ribeiro et al. (2023), Theorem 1 and Proposition 3. I suggest stating more explicitly which steps are genuinely new technical difficulties when moving from p = 2 and p = ∞ to general p.
  2. The fast-rate bound is loose in its dependence on s, ‖β*‖, and σ, so the claim of recovering prior results holds only for the order in n. The s² in (11) arises because Case 2 in Appendix C.2 uses ‖Δ_S‖₁ ≤ s‖Δ_S‖₂. This is valid, but the tighter inequality ‖Δ_S‖₁ ≤ √s‖Δ_S‖₂ immediately reduces s² to s. In addition, B contains ‖β*‖₁ and C contains δ‖β*‖₁/σ (Appendix p. xii), so the bound is roughly of order s²‖β*‖₁² log d/(κ²n) and grows as σ → 0. By comparison, the known bound for square-root Lasso (Belloni et al. 2011) is of order σ²s log d/(κ²n), so for p = 2 the result here is weaker than the existing one. I suggest using √s, discussing the dependence on σ and ‖β*‖, and comparing the constants with those of Belloni et al. and Xie & Huo.
  3. The practical significance of intermediate values of p is unclear. All bounds are independent of p, the four curves in the experiments nearly coincide, and the conclusion acknowledges this. Although the paper is motivated by DRO and distributional robustness, it only evaluates in-sample error under a fixed design, with no distribution-shift, out-of-sample, or real-data experiments, and gives no guidance on when to choose 2 < p < ∞. An example in which different values of p behave clearly differently (e.g., heavy-tailed or heteroscedastic noise, or a shifted test distribution) would considerably strengthen the paper.
  4. The experiments are small and somewhat artificial. In the fast-rate experiment, d = 10 and s = 5 and λ_min(XᵀX/n) is bounded below, so the RE condition reduces to a full-rank condition and the high-dimensional sparse regime (d ≫ n) where RE actually matters is not tested. In the slow-rate experiment, d = 2 and the design matrix is constructed so that λ_min decays as 3/√n, and n only ranges over 4096–10240 (less than a factor of 3), which gives limited evidence for the slope. I suggest adding sparse experiments with d > n, a wider range of n, and fitted slopes.
  5. Several points in the solver section need clarification. Section 7 states that the appendix provides "implementation and convergence" details, but Appendix E.2 gives no convergence guarantee. The argument that the η-update minimizes G_δ(β, ·) relies on the existence of a saddle point and on the uniqueness of the minimizer in η, which is not stated explicitly. The η-trick solver is only implemented for ‖·‖ = ‖·‖∞, and the ϵ-smoothing in Algorithm 1 means that a smoothed problem is solved.

Minor:

  • Figure 3 uses p ∈ {2, 3, 6, ∞} in the main text but {2, 3, 5, ∞} in Appendix F.3.
  • In the proof of Theorem 2, "E[f(ε)] = 6σ" should be ≤ (by Jensen's inequality); this does not affect the result.
  • The expression for V_{∞,δ} in Corollary 1 is missing the factor 1/n.
  • In Appendix B.1, the constraint for p = ∞ is written as ‖t‖ ≤ δ and should be ‖t‖∞ ≤ δ.
  • Typos: "This raise the natural question", "naturally generalize", "robust optimization forms coincides", "tailored specific for", and "iteratively alternative between" (twice).
Questions for authors
  1. Why is δ_S discontinuous at p = 2? It equals 1/(n min‖α‖∞) for all p > 2 but jumps to 1/(√n min‖α‖₂) at p = 2. Does this mean the set of minimizers is discontinuous in p at p = 2, and what is observed numerically as p decreases to 2?
  2. With √s instead of s, can the fast rate be improved to order s·δ²/κ²? Can a σ² dependence consistent with Belloni et al. (2011) be obtained?
  3. Is there a setting (e.g., heavy-tailed noise, heteroscedasticity, or distribution shift) in which 2 < p < ∞ clearly outperforms p = 2 or p = ∞?
  4. Does the η-trick solver have a convergence guarantee, and can it be extended to norms other than the ∞-norm?

Overall, I find this a clearly written and technically correct theoretical paper, and the unifying view offered by Theorem 1 is elegant.

3 comments
AuthorsOpenReview ↗

Comment 1/3

Thanks for the very detailed and valuable feedback. We address your questions and concerns below. We believe that your feedback significantly improves the paper.

(W1) Nature of the contribution: While we build on previous work, we believe the connections are not obvious. These results are scattered and use a diversity of different tools. We also find the conclusions that we draw are interesting and novel. In particular, the smart technical move is Theorem 1. While not hard to derive, it allows us to analyze DRO using tools and results that have not been used before.

(Q1) Interpolation difference: Thanks for the questions. To answer the first question, the reason δS\delta_S is strictly larger is because the subdifferential of the robust risk for an interpolator βˉ\bar{\beta} suddenly jumps and becomes a larger set as at p=2p=2, while remaining the same for all p>2p>2. This can be seen by (A.15) in the paper, where p=2p=2 results in T(βˉ)T(\bar{\beta}) having multiple solutions instead of a unique one, yielding a larger subdifferential since it is now a convex hull over multiple subdifferentials. This is crucial since βˉ\bar{\beta} is optimal if its subdifferential of the robust risk contains zero. A larger subdifferential will contain zero earlier, thus interpolation happens strictly earlier for p=2p=2. To answer the second question, we did a small numerical test where we let δ\delta be the average of δS(p=2)\delta_S(p=2) and δS(p>2)\delta_S(p>2) and checked if the minimizer β^p,δ\hat\beta_{p,\delta} converged to β^2,δ\hat\beta_{2,\delta}, indicating that the set of minimisers are in fact continuous, even though β^2,δ\hat\beta_{2,\delta} interpolates while β^p,δ\hat\beta_{p,\delta} does not. This was indeed the case. This is no contradiction: A non-interpolating solution can converge to an interpolation solution even though the former never interpolates.

(W2 & Q2) The fast-rate bound: Thanks for pointing this out. You are right and we will fix it. We also add a comment that the constants are weaker, although our numerical experiments are somehow very similar.

(W3 & Q3) Fixed design setting and benefits of 2<p<∞2<p<\infty:

Fixed design setting: Thanks for this comment. We focus on the fixed design setting with in-sample error, since it is an important design setting and we want to have a coherent story throughout the paper. We believe extensions to out-of-sample, distribution shifts and real-data experiments are readily possible and interesting future directions.

(Please see the next comment for continuation of this answer.)

AuthorsOpenReview ↗

Comment 2/3

(Continuation of the previous comment.)

Benefits of 2<p<∞2<p<\infty: Thanks for the comment. Indeed we did not focus on this aspect. Our motivation for studying the full range 2≤p≤∞2 \leq p \leq \infty was primarily to develop a unified understanding of DRO. Considering this range allows us to connect important properties previously studied separately for p=2p=2 and p=∞p=\infty. The interest in intermediate values of pp lies in what they reveal about these connections, without presupposing that they are preferable in practice.

Nonetheless, we agree that it is a valuable question: how one chooses pp given that many of them have similar properties. While we don’t have a definitive answer, we believe we can use our theory to provide insight to this question. Particularly, Theorem 2 provides a clear interpretation of the role of pp. When p=∞p=\infty, all samples have the same perturbation budget δ\delta. Thus we model an adversary that is uniform over the data. When p=2p=2, we instead allow an uneven perturbation budget over the data samples. Thus, the adversary can focus more of its adversarial budget for data samples that are particularly good to perturb to degrade performance. Going from p=2p=2 to p=∞p=\infty allows us to vary between the two extremes.

While we do not have a universal rule on how to pick such a pp, a simple experiment highlights the tradeoffs. The experiment is based on adding outliers to a simple linear regression setup

y_i = x_i^\top \beta^* + \varepsilon_i + M S_i C_i, \end{aligned}$$ where $x_i \sim N(0,I_{30})$, $\beta^* = (3,3,3,3,3,0,0,\dots,0)$, $\varepsilon_i \sim N(0,\sigma^2)$ with $\sigma=0.5$, $S_i$ is a random sign, $C_i \sim \mathrm{Bernoulli}(\tau)$, and $M>0$ is a constant. Here, $\tau$ controls the outlier frequency while $M$ controls the spike size of the outliers. We let $\tau \in \{1\\%,10\\%\}$ and $M \in \{5\sigma,20\sigma\}$ with results shown in the table below. The table shows the minimum in-sample error over $n=60$ samples by taking the optimal $\delta$ for each $p$ (avoids picking $\delta$ that is suboptimal for other values of $p$). | $M$ | $\tau$ | $p = 2$ | $p = 3$ | $p = 6$ | $p = \infty$ | |------:|----:|-----------:|-------:|-----------:|-----------:| | $5\sigma$ | 1% | **0.0615** | 0.0670 | 0.0698 | 0.0715 | | $5\sigma$ | 10% | 0.1930 | 0.1471 | **0.1449** | 0.1451 | | $20\sigma$ | 1% | 0.2183 | 0.0980 | 0.0930 | **0.0915** | | $20\sigma$ | 10% | 2.2864 | 1.2276 | 0.9168 | **0.8064** | In particular, we see that for infrequent and small-magnitude outliers (first row), $p=2$ is optimal, while for more frequent and large-magnitude outliers (last row), $p=\infty$ is optimal, even though the performance for all $p$ degrades as we increase outliers. For intermediate setups (the two middle rows), intermediate $p=3$ and $p=6$ are slightly optimal or close to optimal. We did not find any case where these two $p$ are significantly better than both $p=2$ and $p=\infty$, but this could be invested more extensively in future work for other experiments. The reason why $p=2$ degrades more with outliers than $p=\infty$ can intuitively be understood as follows. Large outliers create large residuals. Due to the quadratic cost, large residuals become much larger when squared and are also more beneficial to perturb (steeper increase in error). Since $p=2$ can more adaptively pick which data to perturb (varying budget), it can focus its perturbation budget more on the outliers, creating larger errors compared to $p=\infty$, where the perturbation budget on each sample is fixed. This sensitivity to large residuals can also be seen in the difference of their objective functions: $$\begin{aligned} V_{2,\delta}(\beta) &= \frac{1}{n}\sum_{i=1}^n (x_i^\top \beta-y_i)^2+2\delta\lVert\beta\rVert_{\ast} \sqrt{\frac{1}{n}\sum_{i=1}^n (x_i^\top \beta-y_i)^2} + \delta^2\lVert\beta\rVert_{\ast}^2, \newline V_{\infty,\delta}(\beta) &= \frac{1}{n}\sum_{i=1}^n (x_i^\top\beta-y_i)^2 + 2\delta\lVert\beta\rVert_{\ast} \frac{1}{n}\sum_{i=1}^n \lvert x_i^\top\beta-y_i\rvert + \delta^2\lVert\beta\rVert_{\ast}^2. \end{aligned}$$ Here, the middle term for $V_{2,\delta}$ has the residuals squared while $V_{\infty,\delta}$ only has the absolute deviation. Thus, large residuals will affect $V_{2,\delta}$ more, which causes degradation for outliers when outliers are misleading (as in our experiment). Moreover, since the ambiguity sets decrease for larger $p$, we also have in general that $V_{2,\delta}(\beta) \geq V_{p,\delta}(\beta) \geq V_{\infty,\delta}(\beta)$, indicating that an intermediate $2<p<\infty$ can be optimal when a mix of characteristics of $p=2$ and $p=\infty$ is desirable. **(Please see the next comment for continuation of this answer.)**
AuthorsOpenReview ↗

Comment 3/3

(Continuation of the previous comment.)

(W4) Additional experiments: Thanks for this comment. We thought it provided reasonable confirmation of the results, but we agree that the high-dimensional regime is interesting and something we want to include in the final version of the paper. We will also try to widen the range of n.The high-dimensional regime is also much more computationally demanding, and due to time constraints, we therefore do not yet have any preliminary results yet to show for now. But we will include it in the future version of the paper.

(W5 & Q4) The η\eta-trick solver: Thanks for pointing out these concerns. First, yes, we think the η\eta-trick solver can be extended to other norms. For example, the work [1] performs the η\eta-trick for the 2-norm, while [2] considers extensions to other norms. We mainly took the infinity-norm for simplicity. Concerning convergence, we build on the convergence result from [1]. There the result follows from basic regularity conditions plus the fact that this is a block coordinate descent algorithm. In our case, we would need to adapt the regularity conditions to be able to handle our problem, for instance using [3]. We did not focus on this since we already have a method with guaranteed convergence (the saddle-point solver) and the η\eta-trick solver was mainly implemented to show that one can solve the problem faster.

Minor fixes: Thanks for the minor corrections, we fix it in the paper.

References:

[1] “Efficient Optimization Algorithms for Linear Adversarial Training,” A. H. Ribeiro, T. B. Schön, D. Zachariah, F. Bach. AISTATS, 2025

[2] The “η-trick” or the effectiveness of reweighted least-squares – Machine Learning Research Blog. Francis Bach, 2019

[3] "Convergence of a Block Coordinate Descent Method for Nondifferentiable Minimization," P. Tseng. Journal of Optimization Theory and Applications, 2001

Reviewer_eNsROpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3(+1)
Soundness
3
Read review
Paper summary

This paper studies linear regression under pp-Wasserstein distributional robustness for 2≤p≤∞2\le p\le\infty, providing a unified framework for square-root Lasso and adversarial linear regression. The authors derive an equivalent robust quadratic formulation and establish slow and fast prediction error bounds, together with the pivotal property. They also characterize the solutions for small and large ambiguity radii, propose numerical optimization algorithms, and provide experiments to validate the theoretical results.

Critical strengths
  1. The paper provides a unified framework connecting square-root Lasso and adversarial linear regression through pp-Wasserstein DRO for 2≤p≤∞2\le p\le\infty.
  2. The equivalent robust quadratic formulation is mathematically interesting and facilitates the analysis of statistical properties across different values of pp.
  3. The characterization of solutions for small and large ambiguity radii provides additional insights into the behavior of the estimators.
Critical weaknesses

Although the paper extends existing results to the entire range 2≤p≤∞2\le p\le\infty, it does not clearly explain what is gained by considering intermediate values of pp. The theoretical convergence rates are independent of (p), and the numerical experiments also show nearly identical performance across different choices of$p$. Therefore, the statistical or practical advantages of intermediate values over the well-studied endpoint cases remain unclear, which limits the novelty and significance of the proposed generalization.

Questions for authors

1.Role of pp: What are the theoretical or practical advantages of choosing 2<p<∞2<p<\infty over the classical cases p=2p=2 and p=∞p=\infty? See also Critical Weaknesses.

2.RE condition: In Definition 1, the RE condition is attributed to Hastie et al. (2015). However, this condition was studied much earlier, notably by Bickel, Ritov, and Tsybakov (2009).

2 comments

Thanks for the valuable feedback. We believe that your comments improve the paper. We address your questions and concerns below:

(Q1) Role of pp: Thanks for the comment. Indeed we did not focus on this aspect. Our motivation for studying the full range 2≤p≤∞2 \leq p \leq \infty was primarily to develop a unified understanding of DRO. Considering this range allows us to connect important properties previously studied separately for p=2p=2 and p=∞p=\infty. The interest in intermediate values of pp lies in what they reveal about these connections, without presupposing that they are preferable in practice.

Nonetheless, we agree that it is a valuable question: how one chooses pp given that many of them have similar properties. While we don’t have a definitive answer, we believe we can use our theory to provide insight to this question. Particularly, Theorem 2 provides a clear interpretation of the role of pp. When p=∞p=\infty, all samples have the same perturbation budget δ\delta. Thus we model an adversary that is uniform over the data. When p=2p=2, we instead allow an uneven perturbation budget over the data samples. Thus, the adversary can focus more of its adversarial budget for data samples that are particularly good to perturb to degrade performance. Going from p=2p=2 to p=∞p=\infty allows us to vary between the two extremes.

While we do not have a universal rule on how to pick such a pp, a simple experiment highlights the tradeoffs. The experiment is based on adding outliers to a simple linear regression setup

y_i = x_i^\top \beta^* + \varepsilon_i + M S_i C_i, \end{aligned}$$ where $x_i \sim N(0,I_{30})$, $\beta^* = (3,3,3,3,3,0,0,\dots,0)$, $\varepsilon_i \sim N(0,\sigma^2)$ with $\sigma=0.5$, $S_i$ is a random sign, $C_i \sim \mathrm{Bernoulli}(\tau)$, and $M>0$ is a constant. Here, $\tau$ controls the outlier frequency while $M$ controls the spike size of the outliers. We let $\tau \in \{1\\%,10\\%\}$ and $M \in \{5\sigma,20\sigma\}$ with results shown in the table below. The table shows the minimum in-sample error over $n=60$ samples by taking the optimal $\delta$ for each $p$ (avoids picking $\delta$ that is suboptimal for other values of $p$). | $M$ | $\tau$ | $p = 2$ | $p = 3$ | $p = 6$ | $p = \infty$ | |------:|----:|-----------:|-------:|-----------:|-----------:| | $5\sigma$ | 1% | **0.0615** | 0.0670 | 0.0698 | 0.0715 | | $5\sigma$ | 10% | 0.1930 | 0.1471 | **0.1449** | 0.1451 | | $20\sigma$ | 1% | 0.2183 | 0.0980 | 0.0930 | **0.0915** | | $20\sigma$ | 10% | 2.2864 | 1.2276 | 0.9168 | **0.8064** | In particular, we see that for infrequent and small-magnitude outliers (first row), $p=2$ is optimal, while for more frequent and large-magnitude outliers (last row), $p=\infty$ is optimal, even though the performance for all $p$ degrades as we increase outliers. For intermediate setups (the two middle rows), intermediate $p=3$ and $p=6$ are slightly optimal or close to optimal. We did not find any case where these two $p$ are significantly better than both $p=2$ and $p=\infty$, but this could be invested more extensively in future work for other experiments. The reason why $p=2$ degrades more with outliers than $p=\infty$ can intuitively be understood as follows. Large outliers create large residuals. Due to the quadratic cost, large residuals become much larger when squared and are also more beneficial to perturb (steeper increase in error). Since $p=2$ can more adaptively pick which data to perturb (varying budget), it can focus its perturbation budget more on the outliers, creating larger errors compared to $p=\infty$, where the perturbation budget on each sample is fixed. This sensitivity to large residuals can also be seen in the difference of their objective functions: $$\begin{aligned} V_{2,\delta}(\beta) &= \frac{1}{n}\sum_{i=1}^n (x_i^\top \beta-y_i)^2+2\delta\lVert\beta\rVert_{\ast} \sqrt{\frac{1}{n}\sum_{i=1}^n (x_i^\top \beta-y_i)^2} + \delta^2\lVert\beta\rVert_{\ast}^2, \newline V_{\infty,\delta}(\beta) &= \frac{1}{n}\sum_{i=1}^n (x_i^\top\beta-y_i)^2 + 2\delta\lVert\beta\rVert_{\ast} \frac{1}{n}\sum_{i=1}^n \lvert x_i^\top\beta-y_i\rvert + \delta^2\lVert\beta\rVert_{\ast}^2. \end{aligned}$$ Here, the middle term for $V_{2,\delta}$ has the residuals squared while $V_{\infty,\delta}$ only has the absolute deviation. Thus, large residuals will affect $V_{2,\delta}$ more, which causes degradation for outliers when outliers are misleading (as in our experiment). Moreover, since the ambiguity sets decrease for larger $p$, we also have in general that $V_{2,\delta}(\beta) \geq V_{p,\delta}(\beta) \geq V_{\infty,\delta}(\beta)$, indicating that an intermediate $2<p<\infty$ can be optimal when a mix of characteristics of $p=2$ and $p=\infty$ is desirable. **(Q2) RE condition:** We just used it as a textbook reference, but agree that the original source is better. We fix it in the paper.

I appreciate the authors’ response and their careful answers to my questions. I have increased the presentation scores. However, I still believe my initial overall rating reflects my assessment of the paper, and therefore I would like to keep it.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.