Wasserstein Distributionally Robust Regret Optimization

• URL: http://arxiv.org/abs/2504.10796v3
• Date: Sun, 20 Apr 2025 04:51:38 GMT
• Title: Wasserstein Distributionally Robust Regret Optimization
• Authors: Lukas-Benedikt Fiechtner, Jose Blanchet,
• Abstract summary: We provide a systematic analysis of Wasserstein DRRO, paralleling known results for Wasserstein DRO.<n>Under smoothness and regularity conditions, we show that Wasserstein DRRO coincides with Empirical Risk Minimization (ERM) up to first-order terms.<n>We show that the regret can be computed by maximizing two one-dimensional concave functions.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Distributionally Robust Optimization (DRO) is a popular framework for decision-making under uncertainty, but its adversarial nature can lead to overly conservative solutions. To address this, we study ex-ante Distributionally Robust Regret Optimization (DRRO), focusing on Wasserstein-based ambiguity sets which are popular due to their links to regularization and machine learning. We provide a systematic analysis of Wasserstein DRRO, paralleling known results for Wasserstein DRO. Under smoothness and regularity conditions, we show that Wasserstein DRRO coincides with Empirical Risk Minimization (ERM) up to first-order terms, and exactly so in convex quadratic settings. We revisit the Wasserstein DRRO newsvendor problem, where the loss is the maximum of two linear functions of demand and decision. Extending [25], we show that the regret can be computed by maximizing two one-dimensional concave functions. For more general loss functions involving the maximum of multiple linear terms in multivariate random variables and decision vectors, we prove that computing the regret and thus also the DRRO policy is NP-hard. We then propose a convex relaxation for these more general Wasserstein DRRO problems and demonstrate its strong empirical performance. Finally, we provide an upper bound on the optimality gap of our relaxation and show it improves over recent alternatives.

Related papers

• Outlier-Robust Wasserstein DRO [19.355450629316486]
  Distributionally robust optimization (DRO) is an effective approach for data-driven decision-making in the presence of uncertainty. We propose a novel outlier-robust WDRO framework for decision-making under both geometric (Wasserstein) perturbations and non-geometric (TV) contamination. We prove a strong duality result that enables tractable convex reformulations and efficient computation of our outlier-robust WDRO problem.
  arXiv  Detail & Related papers  (2023-11-09T18:32:00Z)
• On Generalization and Regularization via Wasserstein Distributionally Robust Optimization [0.1843404256219181]
  Wasserstein distributionally robust optimization (DRO) has gained prominence in operations research and machine learning.<n>We show that generalization bounds and regularization equivalence can be obtained in a significantly broader setting.
  arXiv  Detail & Related papers  (2022-12-12T05:48:07Z)
• Wasserstein Distributionally Robust Estimation in High Dimensions: Performance Analysis and Optimal Hyperparameter Tuning [0.0]
  We propose a Wasserstein distributionally robust estimation framework to estimate an unknown parameter from noisy linear measurements. We focus on the task of analyzing the squared error performance of such estimators. We show that the squared error can be recovered as the solution of a convex-concave optimization problem.
  arXiv  Detail & Related papers  (2022-06-27T13:02:59Z)
• Distributionally Robust Bayesian Optimization with $\varphi$-divergences [45.48814080654241]
  We consider robustness against data-shift in $varphi$-divergences, which subsumes many popular choices, such as the Total Variation, and the extant Kullback-Leibler divergence. We show that the DRO-BO problem in this setting is equivalent to a finite-dimensional optimization problem which, even in the continuous context setting, can be easily implemented with provable sublinear regret bounds.
  arXiv  Detail & Related papers  (2022-03-04T04:34:52Z)
• Fast Distributionally Robust Learning with Variance Reduced Min-Max Optimization [85.84019017587477]
  Distributionally robust supervised learning is emerging as a key paradigm for building reliable machine learning systems for real-world applications. Existing algorithms for solving Wasserstein DRSL involve solving complex subproblems or fail to make use of gradients. We revisit Wasserstein DRSL through the lens of min-max optimization and derive scalable and efficiently implementable extra-gradient algorithms.
  arXiv  Detail & Related papers  (2021-04-27T16:56:09Z)
• Wasserstein Distributionally Robust Inverse Multiobjective Optimization [14.366265951396587]
  We develop a distributionally robust inverse multiobjective optimization problem (WRO-IMOP) We show that the excess risk of the WRO-IMOP estimator has a sub-linear convergence rate. We demonstrate the effectiveness of our method on both a synthetic multiobjective quadratic program and a real world portfolio optimization problem.
  arXiv  Detail & Related papers  (2020-09-30T10:44:07Z)
• Finite-Sample Guarantees for Wasserstein Distributionally Robust Optimization: Breaking the Curse of Dimensionality [5.888646114353371]
  Wasserstein distributionally robust optimization aims to find robust and generalizable solutions by hedging against data perturbations in Wasserstein distance. Existing performance guarantees for generic loss functions are either overly conservative due to the curse of dimensionality, or plausible only in large sample complexitys. We develop a non-asymptotic framework for analyzing the out-of-sample performance for Wasserstein robust learning and the generalization bound for its related Lipschitz and gradient regularization problems.
  arXiv  Detail & Related papers  (2020-09-09T16:02:57Z)
• On Projection Robust Optimal Transport: Sample Complexity and Model Misspecification [101.0377583883137]
  Projection robust (PR) OT seeks to maximize the OT cost between two measures by choosing a $k$-dimensional subspace onto which they can be projected. Our first contribution is to establish several fundamental statistical properties of PR Wasserstein distances. Next, we propose the integral PR Wasserstein (IPRW) distance as an alternative to the PRW distance, by averaging rather than optimizing on subspaces.
  arXiv  Detail & Related papers  (2020-06-22T14:35:33Z)
• Projection Robust Wasserstein Distance and Riemannian Optimization [107.93250306339694]
  We show that projection robustly solidstein (PRW) is a robust variant of Wasserstein projection (WPP) This paper provides a first step into the computation of the PRW distance and provides the links between their theory and experiments on and real data.
  arXiv  Detail & Related papers  (2020-06-12T20:40:22Z)
• Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
  We consider the populationimation barycenter problem for random probability measures supported on a finite set of points and generated by an online stream of data. We employ the structure of the problem and obtain a convex-concave saddle-point reformulation of this problem. In the setting when the distribution of random probability measures is discrete, we propose an optimization algorithm and estimate its complexity.
  arXiv  Detail & Related papers  (2020-06-11T19:40:38Z)
• Approximation Schemes for ReLU Regression [80.33702497406632]
  We consider the fundamental problem of ReLU regression. The goal is to output the best fitting ReLU with respect to square loss given to draws from some unknown distribution.
  arXiv  Detail & Related papers  (2020-05-26T16:26:17Z)
• Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
  We show that families of algorithms fail to produce nearly optimal solutions with high probability. For the case of Boolean circuits, our results improve the state-of-the-art bounds known in circuit complexity theory.
  arXiv  Detail & Related papers  (2020-04-25T05:45:59Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.