Unifying Distributionally Robust Optimization via Optimal Transport Theory

José Blanchet, Daniel Kühn, Jiajin Li, Bahar TaşkesenarXiv 2023 · DOI · arXiv

Abstract

In recent years, two prominent paradigms have shaped distributionally robust optimization (DRO), modeling distributional ambiguity through $\phi$-divergences and Wasserstein distances, respectively. While the former focuses on ambiguity in likelihood ratios, the latter emphasizes ambiguity in outcomes and uses a transportation cost function to capture geometric structure in the outcome space. This paper proposes a unified framework that bridges these approaches by leveraging optimal transport (OT) with conditional moment constraints. Our formulation enables adversarial distributions to jointly perturb likelihood ratios and outcomes, yielding a generalized OT coupling between the nominal and perturbed distributions. We further establish key duality results and develop tractable reformulations that highlight the practical power of our unified approach.

Introduction

In data-driven decision-making, we often rely on an empirical distribution—the data we have actually observed. However, this data is rarely a perfect representation of reality. Distributionally Robust Optimization (DRO) protects against this "optimizer's curse" by finding a solution that performs well against the worst-case distribution within a certain "ambiguity set" around our data.

Historically, researchers have used two main tools to define these sets:

  1. $\phi$-divergences: These focus on likelihood re-weighting. They ask: "What if some data points are more or less likely than we thought?"
  2. Wasserstein distances: These focus on geometric perturbations. They ask: "What if the values of our data points are slightly shifted?"

Until now, these two paradigms were treated as separate mechanisms. Likelihood-based methods ignore the geometry of the data, while Wasserstein methods can be overly conservative because they struggle to "ignore" outliers. This paper addresses the lack of a principled, tractable way to combine both types of robustness.

A Unified "Lifted" Framework

The authors propose a "lifted" DRO framework that moves the problem from the original space of risk factors to a higher-dimensional space. This space includes both the outcomes and an auxiliary variable representing likelihood ratios.

The Core Innovation

They define a new OT discrepancy that incorporates conditional moment constraints. This allows an "adversary" to jointly perturb both the locations of data points and their relative weights. The paper mathematically proves that standard $\phi$-divergence DRO, Wasserstein DRO, and even Sinkhorn DRO (an entropy-regularized version of OT) are all special cases of this single lifted model.

Common $\phi$-divergences and their mathematical properties as utilized within the unified framework.

Strong Duality and Tractability

One of the biggest hurdles in DRO is solving the "inner" maximization (finding the worst-case distribution). The authors establish a strong duality theorem, transforming a complex infinite-dimensional problem into a manageable dual form. For common loss functions, such as the piecewise linear functions used in Support Vector Machines (SVMs), the problem reduces to a finite convex program (specifically, conic programming), which can be solved efficiently with standard optimization software.

Experimental Insights

The authors evaluated their framework using a synthetic SVM classification task with 100-dimensional feature vectors and training sets of 200 samples. Labels were generated using a noisy linear rule to simulate real-world data corruption.

  • The "Joint" Advantage: The most powerful insight is that you don't have to choose between re-weighting and shifting. By tuning an interpolation parameter ($\theta$), researchers can find a "sweet spot" that uses the strengths of both paradigms.
  • Graceful Degradation: Pure Wasserstein models often fail catastrophically if the uncertainty radius is set too large—they become too conservative. The joint model is much more stable; it can use re-weighting to handle outliers while using geometric shifts to exploit structural knowledge like sparsity.
  • Low-Data Efficiency: When the ratio of samples to features ($n/d_x$) was low, the joint model significantly outperformed the non-robust empirical SVM, showing it is particularly effective when data is scarce.

Limitations and Future Work

While the framework is powerful, the current proof for strong duality relies on the assumption that the support sets for the data and likelihood ratios are compact (bounded). Relaxing these conditions for more general cases remains a technical challenge. Additionally, while the problem is tractable, the "lifting" process adds auxiliary variables; future work could explore specialized algorithms to handle extremely large-scale datasets where generic conic solvers might slow down.

Summary updated

Abstract

In recent years, two prominent paradigms have shaped distributionally robust optimization (DRO), modeling distributional ambiguity through $ϕ$-divergences and Wasserstein distances, respectively. While the former focuses on ambiguity in likelihood ratios, the latter emphasizes ambiguity in outcomes and uses a transportation cost function to capture geometric structure in the outcome space. This paper proposes a unified framework that bridges these approaches by leveraging optimal transport (OT) with conditional moment constraints. Our formulation enables adversarial distributions to jointly perturb likelihood ratios and outcomes, yielding a generalized OT coupling between the nominal and perturbed distributions. We further establish key duality results and develop tractable reformulations that highlight the practical power of our unified approach.
BibTeX
@misc{blanchet2023unifying,
  author = {José Blanchet and Daniel Kühn and Jiajin Li and Bahar Taşkesen},
  title = {{Unifying Distributionally Robust Optimization via Optimal Transport Theory}},
  year = {2023},
  eprint = {2308.05414},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2308.05414},
}
Figure