Calculate boundary for MAE given RMSE E.g. from the Netflix prize I know that the best RMSE =  0.8563 where the test dataset has a size of n=1,408,789.
Can I calculate a boundary for the MAE. If not, why can't I calculate a boundary?
I started like that:
RMSE = $\sqrt{\frac{\sum_{i=1}^{n}(y_{i}-\hat y_{i})^2}{n}}=0.8563$
Now I want to calculate the MAE or a boundary for the MSE:
MAE = $\frac{1}{n}\sum_{i=1}^{n}{|y_{i}-\hat y_{i}|}$
I know that:
$\sum_{i=1}^{n}(y_{i}-\hat y_{i})^2=RMSE^2*n$
from the first formula.
Is it possible to determine a boundary for the MAE e.g. MAE < 1?
 A: Eliminating the n-part in both metrics we can express them as p-norms or $L^p$-norms.


*

*$\sqrt{n}*RMSE = 2-norm$

*$n*MAE=1-norm$


So we can utilize that
$\|x\|_{p+a} \leq \|x\|_{p}$ for any vector x and real numbers p ≥ 1 and a ≥ 0.
So
$\sqrt{n}*0.8563=\sqrt{n} * RMSE<n*MAE$ 
=>
$MAE > \frac{0.8563}{\sqrt{n}} = \frac{0.8563}{\sqrt{1,408,789}}=0.0007214446$
which is the lower bound.
Given that $E[X^2] \geq E[X]^2$ (many thanks @Innuo), setting $X=(|y_i-\hat{y}_i|)$ leads us to 
$RMSE^2 \geq MAE^2$ => $RMSE \geq MAE$
So the RMSE is actually the upper bound for MAE.
So my estimate for MAE is $[0.0007214446,0.8563]$ given RMSE=0.8563 and the model which has been used to calculate the specific RMSE.
The general model-independent boundaries of course remain [0,4], where the upper bound has been derived from the fact that $y_i,\hat{y}_i$ is an integer in the range from 1 to 5 (according to the rules of the netflix contest).
with 
$\frac{1}{n}*\sum_{i=1}^{n}|5-1|=\frac{n}{n}4=4$
assuming that the model is smart enough to not predict ratings out of range.
