# Theoretical bound - regression error

The Bayes error rate is a theoretical bound that determines the lowest possible error rate for a classification problem, given some data. I was wondering whether an equivalent concept exists for the case of regression algorithms. My aim is to determine how far my regression algorithm's error is from that theoretical bound, as a way to assess how far am I from the best possible solution. Is there any way to obtain a bound of the lowest regression error for a given dataset?

• This is a great question. My initial thought was R-squared, which tells you how much of the variation is explained by the regression for a given set of features. Since the Bayes error rate gives a statistical lower bound on the error achievable for a given classification problem AND associated choice of features. Though the Bayes Error Rate is difficult to calculate (estimate), it has great universal utility for any classifier as you point out. So I started thinking about Bayesian Regression and it almost seems like you are looking for the Bayes Loss. – AN6U5 Jul 25 '15 at 21:29
• Thank you for your answer. The computation of R-squared requires predictions, so I am wondering whether a theoretical bound of R-squared can be estimated. I read a paper on the estimation of the Bayes error rate by means of an ensemble of classifiers; maybe something similar can be applied to R-squared (just a random thought here). I am not familiar with Bayesian regression. I will check that out. – Pablo Suau Jul 27 '15 at 9:04

I realize this question was asked more than a year ago, but I think one possibility is to use the bias-variance decomposition to calculate a lower bound on the error rate.

Essentially, the error rate is written as the sum of three terms, the bias, the variance, and the irreducible error. One good source for learning about these terms is An Introduction to Statistical Learning.

Assume that the true function ($f(x)$) lies within the family of functions that our machine learning model is capable of fitting, and take the limit as the amount of training data we have goes to infinity. Then, if our machine learning model has a finite number of parameters, both the bias and the variance will be zero. So, the actual error will simply be equal to the irreducible error.

As an example, suppose our true data is linear with Gaussian noise: $y \sim N(a + bx, \sigma^2)$. One of the the optimal estimators is obviously linear regression, $\hat{y} = \hat{a} + \hat{b}x$, and, as we add more training examples, the estimated coefficients $\hat{a}$ and $\hat{b}$ will approach $a$ and $b$, respectively. So, the best error (assuming squared loss) we could hope to achieve would be equal $\sigma^2$, the inherent error/irreducible noise associated with the data generation itself

In practice, computing the irreducible error is difficult (impossible?), since it requires knowledge of the true process for generating the data. But, this critique is also applicable to the Bayes error, since that requires knowledge of the true class probabilities.

• Thank you for the answer. I think that it makes much sense. – Pablo Suau Feb 1 '17 at 10:46

Yes, that would be the sum of the squares of distances of the response variable from the true or the actual regression line(provided you know it).