Source-linked AI summary
From Data to Decisions: Distributionally Robust Optimization is Optimal
Bart P. G. Van Parys, Peyman Mohajerin Esfahani, Daniel Kuhn
TL;DR
The paper studies static decision problems under uncertainty and develops data-driven stochastic programming that jointly adapts estimation and optimization. Using Sanov’s theorem, it proves a unique meta-optimization solution and characterizes the optimal predictor through worst-case expectations over nearby distributions.
Problem
Static decision problems under uncertainty require data-driven procedures when the decision-maker cannot observe the uncertainty distribution.
Method
The paper develops data-driven stochastic programming that avoids decoupling estimation and optimization, using Sanov’s theorem to solve a meta-optimization problem over predictor-prescriptor pairs.
Results
The meta-optimization problem has a unique optimal solution, and the optimal predictor uses worst-case expected costs over distributions within a given relative entropy distance.
Takeaways & Limitations
The optimal data-driven predictor is characterized by a distributionally robust worst-case expectation over distributions near the empirical distribution.
Takeaways & Limitations
For the continuous-state-space extension, feasibility of the proposed pair in the meta-optimization problem remains open, although it is essentially optimal.
Abstract
from arXiv · showhide
We study stochastic programs where the decision-maker cannot observe the distribution of the exogenous uncertainties but has access to a finite set of independent samples from this distribution. In this setting, the goal is to find a procedure that transforms the data to an estimate of the expected cost function under the unknown data-generating distribution, i.e., a predictor, and an optimizer of the estimated cost function that serves as a near-optimal candidate decision, i.e., a prescriptor. As functions of the data, predictors and prescriptors constitute statistical estimators. We propose a meta-optimization problem to find the least conservative predictors and prescriptors subject to constraints on their out-of-sample disappointment. The out-of-sample disappointment quantifies the probability that the actual expected cost of the candidate decision under the unknown true distribution exceeds its predicted cost. Leveraging tools from large deviations theory, we prove that this meta-optimization problem admits a unique solution: The best predictor-prescriptor pair is obtained by solving a distributionally robust optimization problem over all distributions within a given relative entropy distance from the empirical distribution of the data.
1. Introduction
The paper formulates data-driven stochastic programming as a meta-optimization over predictor-prescriptor pairs, seeking the least conservative estimates that control out-of-sample disappointment. Using large deviations theory, it proves that the unique optimum is a relative-entropy distributionally robust solution centered at the empirical distribution.
- The paper studies stochastic programs where the distribution of uncertainty is unobserved but finite independent samples are available.
- A predictor estimates a feasible decision’s expected cost from data, while its prescriptor selects a decision minimizing that estimate.
- The proposed meta-optimization searches over predictor-prescriptor pairs for the least conservative prescriptor whose out-of-sample disappointment decays at a prescribed exponential rate.Out-of-sample disappointment is the probability that actual expected cost exceeds predicted cost.
- By Sanov’s theorem, the meta-optimization has a unique optimal solution for any given stochastic program.
- The optimal predictor estimates expected cost by worst-case expectation over distributions within a relative entropy distance of the empirical distribution.
- The ambiguity-set radius equals the desired exponential decay rate of out-of-sample disappointment, rather than serving as a prescribed-confidence region for the unknown distribution.The resulting predictor also has a dual representation as a one-dimensional convex optimization problem.
2. Data-driven stochastic programming
Data-driven stochastic programming uses samples to construct predictors of expected costs and prescriptors of near-optimal decisions when the true distribution is unknown. The paper studies out-of-sample disappointment and shows that optimizing this guarantee leads to distributionally robust optimization.
- Problem setting: Stochastic programs minimize the expected cost of a decision under an uncertain parameter governed by an unknown distribution.The model assumes a cost function continuous in the decision, a compact feasible set, and initially a finite scenario space.
- Prediction and prescription: A predictor estimates the expected cost of a fixed decision, whereas a prescriptor identifies a decision minimizing expected cost across feasible decisions.The true predictor and prescriptor depend on the unknown distribution and therefore cannot be computed directly.
- Data-driven estimators: Independent samples provide increasingly reliable information about the unknown distribution, motivating empirical and other data-driven estimators.The empirical distribution records state frequencies and is the maximum likelihood estimator under the finite-scenario model.
- Out-of-sample performance: Training-data optimization can produce disappointing test performance, even when training and test data are independently sampled from the same distribution.The paper relates this phenomenon to overfitting, the optimizer’s curse, and error maximization in different fields.
- Optimal data-driven solutions: The proposed framework seeks least conservative predictors and prescriptors whose out-of-sample disappointment decays at a prescribed exponential rate.The resulting closed-form strong solutions have a distributionally robust optimization interpretation.
- Optimal data-driven solutions: The optimal distributionally robust formulation uses a relative entropy ambiguity set whose radius is tied to the desired decay rate rather than serving as a confidence region.The approach optimizes out-of-sample performance implicitly through the ambiguity set.
3. Large deviation principles
Large deviations theory characterizes how empirical distributions depart from the data-generating model using relative entropy. These bounds support asymptotic and finite-sample guarantees for atypical empirical-distribution events.
- Large deviation principles: Large deviations theory bounds the exponential rate at which probabilities of atypical empirical-distribution events decay with sample size.The relevant rate is expressed through relative entropy between estimator realizations and the data-generating model.
- Relative entropy: Relative entropy is the paper’s distance measure and is also known as information for discrimination, cross-entropy, information gain, or Kullback-Leibler divergence.It is nonnegative, equals zero only for identical distributions, and has convexity and lower-semicontinuity properties.
- Weak LDP: The weak large deviation principle gives upper and lower bounds based on minimizing relative entropy over an event and its interior.The empirical distributions satisfy these bounds under independent sampling, with an additional positivity condition for the lower bound.
- Weak LDP: For nontrivial events excluding the true model and having nonempty interior, relative entropy determines the exponential decay rate of atypical empirical distributions.For I-continuous sets, the rate is the relative entropy distance from the true model to the event set.
- Strong LDP: The strong large deviation principle extends the framework to finite-sample guarantees without requiring the true model to have strictly positive probabilities.Most results in the paper rely on the weak large deviation principle, while the strong version supplies finite-sample bounds.
4. Distributionally robust predictors and prescriptors are optimal
The paper identifies relative-entropy distributionally robust predictors and prescriptors as optimal solutions to meta-optimization problems balancing reliability and conservatism. These procedures provide asymptotic and finite-sample guarantees, including trustworthy prescriptions independent of any particular dataset.
- Meta-optimization: Large deviations theory is used to identify least-conservative predictors and prescriptors whose out-of-sample disappointment decays at a prescribed rate.The resulting procedures solve the vector optimization problems defining the reliability-conservatism trade-off.
- Comparison with alternative predictors: The distributionally robust predictor differs from reverse and restricted alternatives because those alternatives may ignore models that could have generated unobserved outcomes.The proposed predictor hedges over models without requiring the true distribution to be absolutely continuous with respect to the empirical distribution.
- Predictor optimality: As r increases, ˆc_r becomes more reliable but more conservative, and the paper shows it strikes an optimal balance between these effects.The predictor is feasible and continuous on X × P.
- Predictor optimality: The distributionally robust predictor ˆc_r is strongly optimal: lowering predicted cost for any estimator realization necessarily increases disappointment to first order in the exponent.This establishes optimality among continuous functions of the empirical distribution.
- Finite-sample guarantees: The predictor and prescriptor also satisfy finite-sample guarantees that hold under any model P and are independent of a particular dataset.The paper states that these guarantees support trustworthy predictions and prescriptions before the data is observed.
- Prescriptor optimality: The corresponding prescriptor ˆx_r is feasible and strongly optimal, with out-of-sample disappointment decaying at least at rate r.It therefore provides trustworthy prescriptions under the paper’s asymptotic guarantees.
5. Extension to continuous state spaces
The paper extends its distributionally robust predictor-prescriptor framework from finite to compact continuous state spaces. Under continuity and compactness assumptions, the predictor remains continuous and the main optimality results largely carry over, with important finite-sample and prescriptor caveats.
- Setting: Compact continuous state spaces replace finite uncertainty sets, while distributions are equipped with the weak topology.The state space may have infinite cardinality, and the distribution family is compact in the weak topology.
- Limitations: The strong large deviations principle has no continuous counterpart, so the finite-sample guarantees from the finite-state case do not generalize.The continuous extension preserves asymptotic results but not those finite-sample guarantees.
- Predictors and prescriptors: Joint continuity of the cost on compact X × Ξ makes the model-based predictor continuous and guarantees an optimizing prescriptor exists.The model-based prescriptor is selected from arg min_x∈X c(x,P).
- Predictors and prescriptors: The distributionally robust predictor has a continuous extension, which ensures a quasi-continuous prescriptor can be chosen.This establishes validity of the continuous-state predictor-prescriptor construction.
- Optimality: The relative-entropy distributionally robust predictor remains the unique strong solution of the predictor meta-optimization problem for r > 0.The result follows using a weak large deviations principle adapted to the continuous setting.
- Optimality: The predictor-prescriptor pair is essentially optimal, but feasibility requires shifting the predictor upward by any ϵ > 0, and exact feasibility remains open.The shifted pair is feasible, while the unshifted pair is preferred to every feasible solution even if it may itself be infeasible.
Appendix A: Proofs
The appendix proves the paper’s finite-state technical results using empirical-distribution counting, relative-entropy bounds, and continuity arguments. It also establishes equivalent formulations and finite-sample measurability properties for the distributionally robust constructions.
- Large-deviation bounds: The proofs analyze empirical distributions generated by finite sample paths and bound the number of possible empirical distributions by (T + 1)^d.These counting bounds support the large-deviation estimates used later.
- Large-deviation bounds: Relative-entropy estimates yield asymptotic upper and lower bounds for empirical-distribution events.The upper bound is obtained by taking a limit superior, while the lower bound uses continuity and density arguments.
- Finite-sample properties: A finite-sample bound holds for every measurable set D and does not require additional structural properties of D.This is stated explicitly after the large-deviation inequalities are established.
- Auxiliary optimization: The robust predictor’s auxiliary optimization has an attained minimizer and inherits continuity and convexity properties needed for the formulation.The proof uses lower semicontinuity, first-order optimality, Jensen’s inequality, and growth of the objective.
- Continuity arguments: Compactness and continuity establish continuity of expected cost and support existence of minimizers in the model-based problem.Uniform continuity of the cost combines with weak convergence of distributions.
- Equivalent robust formulation: The appendix proves an equivalent representation of the distributionally robust predictor using a mixture distribution and a worst-case scenario.The two formulations provide matching upper and lower bounds through absolute-continuity and Radon–Nikodym arguments.