Theoretical bound - regression error
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.