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.
Figures & tables
Figure 1 : Mean computation times over 10 repetitions for the saddle-point solver (solid) and the η -trick solver (dashed) in the fast-rate experiment.
Figure 2 : Fast rates (left) and slow rates (right) for p∈{2,3,6,∞} . Both show a clear convergence toward the predicted rates O(n−1) and O(n−1/2) , respectively. The curves are mean over 10 runs with ±1 standard deviation bands.
Figure 3 : Large δ (bottom) and small δ (top) in the overparametrized regime, with zero solution and interpolation for δ≥δL and δ≤δS , respectively.
Appendix figures & tables4 assets
Supplementary material from the paper’s appendix.
Appendix
Figure A.1 : Additional plots for the fast rate simulations in Section 8 showing that the conditions in Theorem 3 hold. Concretely, the left plot shows that the RE condition is satisfied for κ=1/6 (for all n ) since it indeed lower-bounds the minimum eigenvalue λmin(G) of G=XTX/n (see ( A.30 ) and the corresponding derivation for details). Moreover, the right plot shows that δ≥δˉ (which it should be with high probability). Therefore, the conditions in Theorem 3 hold. Both plots show median over 10 runs with shaded bands showing minimum and maximum across the repetitions.
Figure A.2 : Convergence for eq:=n1/q∥ε∥q in the fast rate simulations from Section 8 . We see that all eq quickly stabilizes toward a constant as n increases. Since eq converges to a constant, so do B and C in Theorem 3 . The plot shows the median over 10 repeats with shaded bands being the 10th-90th percentile range.
Figure A.3 : We plot the error of the saddle-point solver and the η -trick solver for the fast rate setup (left). We run 10 repeats and plot the mean with ±1 standard deviation bands. We also plot the robust risk for the obtained estimate for both solvers (right). Here we plot the median over 10 repeats with 10-90 percentiles. We note that both output near-identical results.
Figure A.4 : Computation time (left) and time ratio (right) of the saddle-point solver and the η -trick solver for the fast rate setup. We see that η -trick solver is, in general, faster, particularly for large n and p∈{2,∞} . Both methods are slower for p∈{3,6} , since the robust risk then lacks a closed-form expression. Both plots show mean over 10 runs.
Distributionally robust optimization (DRO) is widely used for decision-making under uncertainty, but its adversarial focus on worst-case loss can lead to overly conservative policies. To mitigate this, we study ex-ante Distributionally Robust Regret Optimization (DRRO) with Wasserstein ambiguity sets, designed to balance robustness with upside potential. We develop a theory of Wasserstein DRRO (WDRRO) paralleling Wasserstein DRO. Under smoothness and regularity, WDRRO selects among ERM optima by a first-order gradient-discrepancy rule. If the ERM optimizer is unique, first-order sensitivity vanishes and a second-order expansion governs deviations. For convex quadratics ERM and DRRO coincide for any radius. We then study regimes where these assumptions fail: nondifferentiable max-affine losses, discrete references, and larger radii, where WDRRO can differ from ERM and WDRO. We show that computing WDRRO regret is NP-hard even without bilinear terms. Nevertheless, we develop exact algorithms, a tractable convex relaxation with guarantees, and experiments showing tightness and loss-dependent behavior.
Lukas-Benedikt Fiechtner, Jose Blanchet
Institute of Computational and Mathematical Engineering Stanford University · Institute of Computational and Mathematical Engineering Department of Management Science and Engineering Stanford University
We propose a distributionally robust approach to learning hyperparameters for first-order methods in convex optimization. Given a dataset of problem instances, we minimize a Wasserstein distributionally robust version of the performance estimation problem (PEP) over algorithm parameters such as step sizes. Our framework unifies two extremes: as the robustness radius vanishes, we recover classical learning to optimize (L2O); as it grows, we recover worst-case optimal algorithm design via PEP. We solve the resulting problem with stochastic gradient descent, differentiating through the solution of an inner semidefinite program at each step. We prove high-probability bounds showing that the true risk of the learned algorithm is at most the in-sample L2O optimum plus a slack that shrinks with the sample size, and is no worse than the worst-case PEP bound. On unconstrained quadratic minimization, LASSO, and linear programming benchmarks, our learned algorithms achieve strong out-of-sample performance with certifiable robustness, outperforming both worst-case optimal and vanilla L2O baselines.
Vinit Ranjan, Jisun Park, Bartolomeo Stellato
Department of Operations Research and Financial Engineering, Princeton University. · Department of Operations Research and Financial Engineering, Princeton University, and Research Institute of Mathematics, Seoul National University. · Research Institute of Mathematics, Seoul National University.
We present an algorithm for the group distributionally robust (GDR) least squares problem. Given m groups, a parameter vector in Rd, and stacked design matrices and responses A and b, our algorithm obtains a (1+ε)-multiplicative optimal solution using O(min{rank(A),m}1/3ε−2/3) linear-system-solves of matrices of the form A⊤BA for block-diagonal B. Our technical methods follow from a recent geometric construction, block Lewis weights, that relates the empirical GDR problem to a carefully chosen least squares problem and an application of accelerated proximal methods. Our algorithm improves over known interior point methods for moderate accuracy regimes and matches the state-of-the-art guarantees for the special case of ℓ∞ regression. We also give algorithms that smoothly interpolate between minimizing the average least squares loss and the distributionally robust loss.
Naren Sarayu Manoj, Kumar Kshitij Patel
TTIC · Institute for Foundations of Data Science, Yale University