Distributionally Robust Optimization using Cost-Aware Ambiguity Sets

Mathijs Schuurmans, Panagiotis PatrinosIEEE Control. Syst. Lett 2023

TL;DR

CADRO (Cost-Aware Distributionally Robust Optimization) is a new framework that slashes the "conservatism" of traditional robust optimization by tailoring the uncertainty set to the specific cost function at hand. By focusing only on the distribution shifts that actually hurt performance, CADRO provides tighter, more reliable cost estimates and better out-of-sample performance than standard methods.

What Problem Does This Paper Address?

In stochastic programming, we want to minimize an expected cost, but we rarely know the true probability distribution of the world. The standard approach, Sample Average Approximation (SAA), simply uses the empirical data as a proxy. However, SAA often suffers from the "optimizer's curse": it overfits to the specific data samples, leading to overly optimistic results that fail when deployed on new, unseen data.

Distributionally Robust Optimization (DRO) fixes this by optimizing against the worst-case distribution within a neighborhood of the empirical estimate, called an ambiguity set. The problem? Most ambiguity sets (like those based on Wasserstein distance or KL-divergence) are "cost-blind." They treat deviations in all directions equally. This often results in solutions that are far too conservative—preparing for "disasters" that have no real impact on the actual cost—making the resulting estimates practically useless for decision-making in data-sparse regimes.

Methods

The authors introduce CADRO, which builds an ambiguity set specifically designed to constrain the worst-case distribution along the direction where the expected cost increases most rapidly.

Key components include:

  • Data Partitioning: The available dataset is split into a training set and a calibration set.
  • Direction Selection: The training set is used to find a candidate solution and a corresponding "cost vector" $v$ that approximates the gradient of the cost function.
  • Calibration: The calibration set is used to determine a high-confidence upper bound ($\alpha$) on the expected cost in that specific direction.
  • Ambiguity Set Geometry: Instead of a multi-dimensional ball, the ambiguity set is a half-space (or polytope) in the space of probability distributions, defined by the constraint $\langle p, v \rangle \leq \alpha$.
  • Tractable Reformulation: The authors prove that this DRO problem can be reformulated into a standard convex optimization problem (or even a Linear Program if the costs are piecewise affine), making it computationally efficient.

Datasets

The paper evaluates the method using a Facility Location Problem benchmark.

  • Scenario: A bicycle-sharing service determining where to place stalls to minimize the distance users must travel from various points of interest.
  • Data: 100 independently drawn datasets of varying sizes ($m$ ranging from 10 to 1,000) were used to test the robustness and consistency of the estimators.
  • Comparison: CADRO was compared against SAA and three standard DRO variants: Total Variation (TV), Kullback-Leibler (KL), and Wasserstein-based DRO.

Key Insights and Ideas

  • Geometry Matters: The "aha moment" is that we don't need to be robust against every change in distribution—only those that align with our cost function. By "stretching" the ambiguity set in directions that don't matter and tightening it where they do, we get much better bounds.
  • The Power of the Ordered Mean Bound: The authors utilize a sophisticated "Ordered Mean Bound" (Proposition III.3) rather than simple concentration inequalities like Hoeffding’s. This allows for much sharper bounds at small sample sizes.
  • Consistency and Safety: Unlike many heuristics, CADRO is mathematically proven to be both a "high-confidence upper bound" (it won't underestimate the real-world cost) and a "consistent estimator" (it converges to the true optimal solution as you get more data).

Key Results

  • Reduced Conservatism: In the facility location tests, CADRO provided significantly tighter upper bounds on the cost compared to TV-DRO, KL-DRO, and Wasserstein-DRO, especially when data was scarce ($m < 100$).
  • Superior Out-of-Sample Performance: Not only were the estimates better, but the decisions (the chosen locations) resulted in lower actual realized costs when tested on the true distribution.
  • Efficiency: The cost estimates for CADRO converged to the true optimal value much faster than competing DRO methods as the sample size increased.

Limitations and Future Work

  • Finite Support Assumption: The current theory assumes the random variable has "finite support" (a finite number of possible outcomes). While many real-world problems fit this, extending the framework to continuous distributions is a primary goal for future work.
  • Data Splitting Heuristic: The performance depends on how the data is partitioned between training and calibration. While the authors provide a functional heuristic for this split, they note that more research could optimize this balance.
  • Directional Sensitivity: The method relies on the training set providing a "good enough" direction. If the initial training sample is extremely poor, the ambiguity set might be misaligned, though the statistical guarantees still hold.

Summary updated

Abstract

We present a novel framework for distributionally robust optimization (DRO), called cost-aware DRO (CADRO). The key idea of CADRO is to exploit the cost structure in the design of the ambiguity set to reduce conservatism. Particularly, the set specifically constrains the worst-case distribution along the direction in which the expected cost of an approximate solution increases most rapidly. We prove that CADRO provides both a high-confidence upper bound and a consistent estimator of the out-of-sample expected cost, and show empirically that it produces solutions that are substantially less conservative than existing DRO methods, while providing the same guarantees.
BibTeX
@article{schuurmans2023distributionally,
  author = {Mathijs Schuurmans and Panagiotis Patrinos},
  title = {{Distributionally Robust Optimization using Cost-Aware Ambiguity Sets}},
  journal = {IEEE Control. Syst. Lett.},
  year = {2023},
}
Figure