On approximations of data-driven chance constrained programs over Wasserstein balls

Zhi Chen, Daniel Kühn, Wolfram WiesemannOperations 2023 · DOI

TL;DR

This paper tackles the challenge of making optimal decisions when faced with uncertain parameters, using data to define the uncertainty. The authors propose and analyze three approximation methods for these "data-driven distributionally robust chance constrained programs," showing how they relate to each other and when they perform well or poorly. This work is crucial for building more reliable and efficient decision-making systems in fields like finance and operations research.

What Problem Does This Paper Address?

Imagine you need to make a decision today (like investing in a portfolio or planning a supply chain) that will be affected by uncertain future events. Traditionally, we might use "chance constrained programming" where we ensure certain outcomes happen with a high probability. However, this often requires knowing the exact probability distribution of the uncertain events, which is rarely the case in reality.

A more realistic approach is "distributionally robust optimization," where we acknowledge that our knowledge of the probability distribution is imperfect. Instead of a single distribution, we consider a set of "plausible" distributions. This paper focuses on a specific type of ambiguity set: a "Wasserstein ball," which defines plausible distributions as those within a certain "distance" (in a specific mathematical sense) from a known reference distribution.

The core problem is that these distributionally robust chance constrained programs (DRCCPs) are computationally very difficult to solve exactly, especially when derived from data. This paper addresses this by studying and comparing different approximation schemes that make these problems tractable while still providing guarantees. Specifically, they focus on data-driven DRCCPs, where the reference distribution is an empirical distribution learned from historical data.

Methods

The paper investigates three popular approximation schemes for DRCCPs over Wasserstein balls:

  1. Worst-Case Conditional Value-at-Risk (CVaR) Approximation: This method replaces the chance constraint with a bound on the CVaR of the violation. The authors show this provides a tight convex approximation and offers an intuitive interpretation related to "transportation savings" in the context of Wasserstein distance.
  2. Bonferroni Approximation: This approach decouples multiple safety conditions using Bonferroni's inequality (a form of the union bound). It's attractive because it often leads to simple linear inequalities.
  3. ALSO-X Approximation: This scheme traces Pareto efficient solutions to balance the objective value and the expected violation of safety conditions. It's designed to find feasible, though often suboptimal, solutions.

The authors analyze the theoretical properties of these approximations, including their relationships, conservativeness, and exactness under certain conditions. They also demonstrate their performance in data-driven settings.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and uses synthetic examples to illustrate its points, rather than relying on specific real-world datasets for training or evaluation.

Key Insights and Ideas

  • CVaR as a Tight Convex Approximation: The paper provides a theoretical justification for the popularity of the CVaR approximation, showing it's a tight convex approximation for certain underlying constraints.
  • Intuitive Interpretation of CVaR: The CVaR approximation can be understood as accounting for "transportation savings" when considering Wasserstein distance, complementing existing interpretations.
  • Incomparability of Approximations: Crucially, the paper demonstrates that the CVaR, Bonferroni, and ALSO-X approximations are generally incomparable. This means one approximation might be better (less conservative) than another for a specific problem instance, but there's no single "best" approximation that dominates all others across the board. This contrasts with some findings for other types of ambiguity sets.
  • Data-Driven Performance: The authors highlight that these approximations can perform arbitrarily poorly in data-driven settings, underscoring the importance of understanding their limitations when applied to real-world data.

Key Results

  • The paper establishes theoretical links between the CVaR approximation and exact reformulations of DRCCPs, providing a convex inner approximation.
  • It shows that the CVaR approximation can be interpreted as balancing transportation costs and savings within the Wasserstein distance framework.
  • Through theoretical analysis and examples, the paper demonstrates that the CVaR, Bonferroni, and ALSO-X approximations are generally incomparable. This means that for a given problem, one might be significantly better than another, but there's no universal hierarchy.
  • The paper also shows that these approximations can be arbitrarily poor in data-driven scenarios, emphasizing the need for careful selection and analysis.

Limitations and Future Work

  • Suboptimality in Data-Driven Settings: A significant limitation highlighted is that the approximations can yield arbitrarily suboptimal solutions in data-driven scenarios. This suggests that while these methods offer tractability, their quality can degrade significantly as the number of data samples or the Wasserstein radius changes.
  • Incomparability: The general incomparability of the approximations means that choosing the "best" one for a specific problem requires careful analysis or experimentation. There isn't a one-size-fits-all solution.
  • Future Work: The paper implicitly suggests future work in developing more robust or adaptive approximation strategies that can better handle the challenges of data-driven uncertainty. Further investigation into the conditions under which each approximation performs well would also be valuable. The paper also opens avenues for exploring how to tune parameters within these approximations (like scaling factors in CVaR or risk thresholds in Bonferroni) to improve their performance.

Summary updated

BibTeX
@inproceedings{chen2023approximations,
  author = {Zhi Chen and Daniel Kühn and Wolfram Wiesemann},
  title = {{On approximations of data-driven chance constrained programs over Wasserstein balls}},
  booktitle = {Operations},
  year = {2023},
  doi = {10.1016/j.orl.2023.02.008},
}
Figure