where we denote with \(\hat{\mathbb {P}}_T\)  the empirical distribution of the observed data points,
\(\hat{\mathbb {P}}_T(i) := \frac{1}{T}\sum _{t=1}^T \mathbb {1}_{\xi _t = i}\)  for all \(i \in \Sigma \) .
This formulation is well known in the optimization community as the Sample Average Approximation (SAA) [1]}. When applied to the machine learning problem discussed in Example REF  this approach reduces to the well known Empirical Risk Minimization (ERM) principle [2]}.
SAA and ERM are motivated by the fact that the historical empirical cost is the simplest and perhaps most natural substitution for the unknown actual cost.
However, this naive substitution is well documented to yield decisions which are prone to adverse overfitting effects and may suffer disappointing out-of-sample performance. It is particularly pronounced in machine learning, where it is known as “overfitting”. In decision analysis, [3]} refer to it as the “optimizer's curse”, and in finance, [4]} call it the “error maximization effect” of portfolio optimization.
This is perhaps not unsurprising as the empirical mean \(c(x, \hat{\mathbb {P}}_T)\)  indeed enjoys desirable properties as an estimator for the unknown cost \(c(x, \mathbb {P})\)  but is not necessarily tailored for use in a subsequent optimization problem.
The observation that good estimators for prediction do not generally translate to good estimators for prescription recently spurred interest into “optimization aware” estimation approaches [5]}. To guard against this overfitting effect, two alternative approaches to simple ERM/SAA have sparked interest in the past years: regularized formulations and distributionally robust formulations.
