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.

  • 2
    $\begingroup$ 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. $\endgroup$
    – Wolcott
    Apr 14, 2018 at 7:35
  • 1
    $\begingroup$ I had thought about the same question $\endgroup$
    – jeza
    Apr 23, 2018 at 11:35
  • $\begingroup$ 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? $\endgroup$ Apr 23, 2018 at 15:43
  • 2
    $\begingroup$ @Mark L. Stone for me, it does not $\endgroup$
    – jeza
    Apr 23, 2018 at 17:29
  • 1
    $\begingroup$ 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. $\endgroup$ Apr 23, 2018 at 17:44

1 Answer 1


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$.

  • $\begingroup$ Strictly speaking, we don't need the number of observations to be less than the number of independent variables for all of the subsequent part to be correct. $\endgroup$
    – jbowman
    Apr 28, 2018 at 20:55
  • $\begingroup$ Can you explain how got the expectation equation (second to last equation) and the inequality (last equation)? $\endgroup$
    – user13985
    Dec 29, 2018 at 6:09
  • 1
    $\begingroup$ $ \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. $\endgroup$
    – D.G
    Jan 4, 2019 at 19:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.