# Learning and Decision-Making with Data: Optimal Formulations and Phase Transitions

arXiv: https://arxiv.org/abs/2109.06911 · HTML: https://mlsanity.com/paper/2109.06911/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 49 references that are in the map.
- First posted on arXiv 14 Sep 2021.

## Builds on (most cited first, 14 of 14)

- [Smart "Predict, then Optimize"](https://mlsanity.com/paper/1710.08005/) (2017)
- [Distributionally Robust Stochastic Optimization with Wasserstein Distance](https://mlsanity.com/paper/1604.02199/) (2016)
- [Statistics of Robust Optimization: A Generalized Empirical Likelihood Approach](https://mlsanity.com/paper/1610.03425/) (2016)
- [Wasserstein Distributionally Robust Optimization: Theory and Applications in Machine Learning](https://mlsanity.com/paper/1908.08729/) (2019)
- [Variance-based regularization with convex objectives](https://mlsanity.com/paper/1610.02581/) (2016)
- [Data-Driven Robust Optimization](https://mlsanity.com/paper/1401.0212/) (2013)
- [From Data to Decisions: Distributionally Robust Optimization is Optimal](https://mlsanity.com/paper/1704.04118/) (2017)
- [Recovering Best Statistical Guarantees via the Empirical Divergence-based Distributionally Robust Optimization](https://mlsanity.com/paper/1605.09349/) (2016)
- [Robust Sample Average Approximation](https://mlsanity.com/paper/1408.4445/) (2014)
- [Wasserstein Distributionally Robust Optimization and Variation Regularization](https://mlsanity.com/paper/1712.06050/) (2017)
- [How Big Should Your Data Really Be? Data-Driven Newsvendor: Learning One Sample at a Time](https://mlsanity.com/paper/2107.02742/) (2021)
- [Calibration of Distributionally Robust Empirical Optimization Models](https://mlsanity.com/paper/1711.06565/) (2017)
- [Efficient Learning of a Linear Dynamical System with Stability Guarantees](https://mlsanity.com/paper/2102.03664/) (2021)
- [Topological Linear System Identification via Moderate Deviations Theory](https://mlsanity.com/paper/2103.03805/) (2021)

## Built on by (most cited first, 7 of 7)

- [Integrated Conditional Estimation-Optimization](https://mlsanity.com/paper/2110.12351/) (2021)
- [Holistic Robust Data-Driven Decisions](https://mlsanity.com/paper/2207.09560/) (2022)
- [Distributionally Robust Bayesian Optimization with varphi-divergences](https://mlsanity.com/paper/2203.02128/) (2022)
- [Certified Robust Neural Networks: Generalization and Corruption Resistance](https://mlsanity.com/paper/2303.02251/) (2023)
- [Smoothed f-Divergence Distributionally Robust Optimization](https://mlsanity.com/paper/2306.14041/) (2023)
- [Towards Optimal Offline Reinforcement Learning](https://mlsanity.com/paper/2503.12283/) (2025)
- [Optimal Confidence Intervals via Moderate Deviations Theory](https://mlsanity.com/paper/2305.14496/) (2023)

## Abstract (arXiv)

We study the problem of designing optimal learning and decision-making formulations when only historical data is available. Prior work typically commits to a particular class of data-driven formulation and subsequently tries to establish out-of-sample performance guarantees. We take here the opposite approach. We define first a sensible yard stick with which to measure the quality of any data-driven formulation and subsequently seek to find an optimal such formulation. Informally, any data-driven formulation can be seen to balance a measure of proximity of the estimated cost to the actual cost while guaranteeing a level of out-of-sample performance. Given an acceptable level of out-of-sample performance, we construct explicitly a data-driven formulation that is uniformly closer to the true cost than any other formulation enjoying the same out-of-sample performance. We show the existence of three distinct out-of-sample performance regimes (a superexponential regime, an exponential regime and a subexponential regime) between which the nature of the optimal data-driven formulation experiences a phase transition. The optimal data-driven formulations can be interpreted as a classically robust formulation in the superexponential regime, an entropic distributionally robust formulation in the exponential regime and finally a variance penalized formulation in the subexponential regime. This final observation unveils a surprising connection between these three, at first glance seemingly unrelated, data-driven formulations which until now remained hidden.