# How Big Should Your Data Really Be? Data-Driven Newsvendor: Learning One Sample at a Time

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Jul 2021.

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

- [Estimate-Then-Optimize versus Integrated-Estimation-Optimization versus Sample Average Approximation: A Stochastic Dominance Perspective](https://mlsanity.com/paper/2304.06833/) (2023)
- [Beyond IID: data-driven decision-making in heterogeneous environments](https://mlsanity.com/paper/2206.09642/) (2022)
- [VC Theory for Inventory Policies](https://mlsanity.com/paper/2404.11509/) (2024)
- [Learning and Decision-Making with Data: Optimal Formulations and Phase Transitions](https://mlsanity.com/paper/2109.06911/) (2021)
- [Speed Up the Cold-Start Learning in Two-Sided Bandits with Many Arms](https://mlsanity.com/paper/2210.00340/) (2022)
- [Bilevel Optimization for Feature Selection in the Data-Driven Newsvendor Problem](https://mlsanity.com/paper/2209.05093/) (2022)
- [LLM-SAA: LLM-persona Generated Distributions for Decision-making](https://mlsanity.com/paper/2602.06357/) (2026)
- [Survey of Data-driven Newsvendor: Unified Analysis and Spectrum of Achievable Regrets](https://mlsanity.com/paper/2409.03505/) (2024)
- [Autocorrelated Optimize-via-Estimate: Predict-then-Optimize versus Finite-sample Optimal](https://mlsanity.com/paper/2602.01877/) (2026)
- [Towards Optimal Inventory Control under Censored Demand: A Biased Sample-Average Approximation Approach](https://mlsanity.com/paper/2609.39397/) (2026)

## Abstract (arXiv)

We study the classical newsvendor problem in which the decision-maker must trade-off underage and overage costs. In contrast to the typical setting, we assume that the decision-maker does not know the underlying distribution driving uncertainty but has only access to historical data. In turn, the key questions are how to map existing data to a decision and what type of performance to expect as a function of the data size. We analyze the classical setting with access to past samples drawn from the distribution (e.g., past demand), focusing not only on asymptotic performance but also on what we call the transient regime of learning, i.e., performance for arbitrary data sizes. We evaluate the performance of any algorithm through its worst-case relative expected regret, compared to an oracle with knowledge of the distribution. We provide the first finite sample exact analysis of the classical Sample Average Approximation (SAA) algorithm for this class of problems across all data sizes. This allows to uncover novel fundamental insights on the value of data: it reveals that tens of samples are sufficient to perform very efficiently but also that more data can lead to worse out-of-sample performance for SAA. We then focus on the general class of mappings from data to decisions without any restriction on the set of policies and derive an optimal algorithm (in the minimax sense) as well as characterize its associated performance. This leads to significant improvements for limited data sizes, and allows to exactly quantify the value of historical information.