# Oracle Inequality : In basic terms

I'm going through a paper that uses oracle inequality to prove something but I'm unable to understand what it is even trying to do. When I searched online about 'Oracle Inequality', some sources directed me to the article "Candes, Emmanuel J. 'Modern statistical estimation via oracle inequalities.' " which can be found here https://statweb.stanford.edu/~candes/papers/NonlinearEstimation.pdf. But this book seems too heavy for me and I believe I lack some prerequisites.

My question is : How would you explain what an oracle inequality is to a non-math major (includes engineers)? Secondly how would you recommend them to go about the prerequisites/topics before trying to learn something like the above mentioned book.

I would highly recommend that someone who has a concrete grasp and good amount of experience in high-dimension statistics should answer this.

• Can anyone with more than 1k reputation please offer bounty on this question. That would really help. I don't think that the general CV users would be familiar with this concept since most users use stats for data analysis and not theoretical analysis, although as a community completely based on stats, I believe there must be someone who could adequately answer this. I believe the question hasn't received enough attention. – Wolcott Apr 14 '18 at 7:35
• I had thought about the same question – jeza Apr 23 '18 at 11:35
• The "definition" provided on p.22 of the link "An oracle inequality relates the performance of a real estimator with that of an ideal estimator which relies on perfect information supplied by an oracle, and which is not available in practice." Does not this convey the essence of the definition to you? – Mark L. Stone Apr 23 '18 at 15:43
• @Mark L. Stone for me, it does not – jeza Apr 23 '18 at 17:29
• Not even when you look at the example and discussion provided in the preceding few sentences, i.e., the statement and discussion of Theorem 4.1, as an example of an oracle inequality? In layman's terms: Gee, we don't know the optimal value (provided by an oracle) of the shrinkage factor we should use. But knowing that optimal value of shrinkage factor could improve the MSE by no more than 2 vs. not having the optimal shrinkage factor from the oracle. – Mark L. Stone Apr 23 '18 at 17:44

I'll try to explain it in linear case. Consider the linear model $$Y_i=\sum_{j=1}^{p} \beta_jX_{i}^{(j)}+\epsilon_i, i=1,...,n.$$ When $p \leq n$ (number of independent variables less or equal then number of observation) and design matrix has full rank, the least squared estimator of $b$ is $$\hat{b}=(X^TX)^{-1}X^TY$$ and prediction error is $$\dfrac{\| X(\hat{b}-\beta^0) \|_2^2}{\sigma^2}$$ from which we can deduce $$\dfrac{ \mathbb{E} \| X(\hat{b}-\beta^0) \|_2^2}{n}=\dfrac{\sigma^2}{n}p.$$ It means that each parameter $\beta_j^0$ is estimated with squared accuracy $\sigma^2/n, j=1,...,p.$ So your overall squared accuracy is $(\sigma^2/n)p.$
Now what if the number of observations are less then number of independent variables $(p>n)$? We "believe" that not all of our independent variables play a role in explaining $Y$, so only a few, say $k$, of them are non-zero. If we would know which variables are non-zero, we could neglect all other variables and by above argument, overall squared accuracy would be $(\sigma^2/n)k.$
Because the set of nonzero variables are unknown, we need some regularization penalty(for example $l_1$) with regularization parameter $\lambda$ (which controls the number of variables). Now you want to get results similar to discussed above, you want to estimate squared accuracy. The problem is your optimal estimator $\hat{\beta}$ is now depend on $\lambda$. But the great fact is that with proper choice for $\lambda$ you can get an upper bound of prediction error with high probability, that is the "oracle inequality" $$\dfrac{\| X(\hat{\beta}-\beta^0) \|_2^2}{n} \leq const.\dfrac{\sigma^2\log p}{n}k.$$ Note an additional factor $\log p$, which is the price for not knowing set of non-zero variables. "$const.$" depend only on $p$ or $n$.
• $\dfrac{\| X(\hat{b}-\beta^0) \|_2^2}{\sigma^2}$ has the chi-square distribution with p degrees of freedom so its expectation is $(\sigma^2/n)p$. Last inequality is an oracle inequality. Proof is not so trivial, i can recommend this book: Statistics for High-Dimensional Data: Methods, Theory and Applications, chapter 6. – Dato Gogolashvili Jan 4 '19 at 19:52