Derivation of the conditional median for linear regression in “The elements of statistical learning ”

Question

My question is about "The elements of statistical learning" book. I would like to know how to prove that the use of the $L_1$ loss $$L_1: E\bigg[|Y-f(X)|\bigg]$$ leads to have conditional median $\hat{f}(x)=median(Y|X=x)$ as solution to the $EPF(f)$ criterion minimisation in eq(2.11): $$EPF(f)= E_X\bigg[E_{Y|X}\big[(Y-f(X))^2|X\big]\bigg]$$

Answer 1

First, I think you misspelled something in the question. In your case it should be $$ EPE(f)=\mathbb{E}(\vert Y-f(X)\vert). $$ What you want to show is that $$ \text{argmin}_{f \text{ measurable}}EPE(f)=\left(X\mapsto\text{median}(Y\vert X)\right) $$ This is in fact equivalent to showing that the median is the best constant approximation in the $L^1$-norm, i.e. that

$$ \text{argmin}_{c}\mathbb{E}(\vert X-c\vert) = c^* $$ where $$ c^*=\inf\{t:F_X(t)\geq 0.5\} $$ is the median of $X$ defined via the generalized inverse of the cdf $F_X(\cdot)$ of $X$.This can be easily shown as follows: First assume that $c>c^*$, then

\begin{align} \mathbb{E}(\vert X-c\vert)&=\mathbb{E}((X-c)\chi_{\{X>c\}})-\mathbb{E}((X-c)\chi_{\{X\in(c^*,c]\}})-\mathbb{E}((X-c)\chi_{\{X\leq c^*\}})\\ &=\mathbb{E}((X-c^*)\chi_{\{X>c\}})-(c-c^*)\mathbb{P}(X>c)\\ &\quad\quad + \mathbb{E}((X-c^*)\chi_{\{X\in(c^*,c]\}})-2\mathbb{E}(X\chi_{\{X\in(c^*,c]\}})+(c+c^*)\mathbb{P}(X\in (c^*,c])\\ &\quad\quad-\mathbb{E}((X-c^*)\chi_{\{X\leq c^*\}})+(c-c^*)\mathbb{P}(X\leq c^*) \end{align} Now we bound $$ -2\mathbb{E}(X\chi_{\{X\in (c^*,c]\}})\geq -2c\mathbb{P}(X\in (c^*,c]). $$ Hence, we get \begin{align} \mathbb{E}(\vert X-c\vert)&\geq \mathbb{E}(\vert X-c^*\vert)+(c-c^*)\left(\mathbb{P}(X\leq c^*)-P(X>c)-\mathbb{P}(X\in (c^*,c])\right)\\ &=\mathbb{E}(\vert X-c^*\vert)+(c-c^*)(2\mathbb{P}(X\leq c^*)-1)\\ &\geq \mathbb{E}(\vert X-c^*\vert), \end{align} where we used that $c>c^*$ and $2\mathbb{P}(x\leq c^*)\geq 1$ by the definition of $c^*$. Analogously it can be shown that the same thing holds for $c<c^*$. Hence, we can conclude that the median is in fact the constant RV that approximates $X$ the best in $L^1$.

Finally this can be used to show the final result:

\begin{align} EPE(f)&=\mathbb{E}(\vert Y-f(X)\vert)\\ &=\mathbb{E}(\mathbb{E}(\vert Y-f(X)\vert\vert X))\\ &\geq \mathbb{E}(\vert Y-\text{median}(Y\vert X)\vert\vert X)\\ &=EPE(\text{median}(Y\vert X)) \end{align}

Answer 2

INTUITION This part is taken from this answer.

Assume that $S$ is a finite set, with say $k$ elements. Line them up in order, as $s_1<s_2<\cdots <s_k$.

If $k$ is even there are (depending on the exact definition of median) many medians. $|x-s_i|$ is the distance between $x$ and $s_i$, so we are trying to minimize the sum of the distances. For example, we have $k$ people who live at various points on the $x$-axis. We want to find the point(s) $x$ such that the sum of the travel distances of the $k$ people to $x$ is a minimum.

Imagine that the $s_i$ are points on the $x$-axis. For clarity, take $k=7$. Start from well to the left of all the $s_i$, and take a tiny step, say of length $\epsilon$, to the right. Then you have gotten $\epsilon$ closer to every one of the $s_i$, so the sum of the distances has decreased by $7\epsilon$.

Keep taking tiny steps to the right, each time getting a decrease of $7\epsilon$. This continues until you hit $s_1$. If you now take a tiny step to the right, then your distance from $s_1$ increases by $\epsilon$, and your distance from each of the remaining $s_i$ decreases by $\epsilon$. So there is a decrease of $6\epsilon$, and an increase of $\epsilon$, for a net decrease of $5\epsilon$ in the sum.

This continues until you hit $s_2$. Now, when you take a tiny step to the right, your distance from each of $s_1$ and $s_2$ increases by $\epsilon$, and your distance from each of the five others decreases by $\epsilon$, for a net decrease of $3\epsilon$.

This continues until you hit $s_3$. The next tiny step gives an increase of $3\epsilon$, and a decrease of $4\epsilon$, for a net decrease of $\epsilon$.

This continues until you hit $s_4$. The next little step brings a total increase of $4\epsilon$, and a total decrease of $3\epsilon$, for an increase of $\epsilon$. Things get even worse when you travel further to the right. So the minimum sum of distances is reached at $s_4$, the median.

The situation is quite similar if $k$ is even, say $k=6$. As you travel to the right, there is a net decrease at every step, until you hit $s_3$. When you are between $s_3$ and $s_4$, a tiny step of $\epsilon$ increases your distance from each of $s_1$, $s_2$, and $s_3$ by $\epsilon$. But it decreases your distance from each of the three others, for no net gain. Thus any $x$ in the interval from $s_3$ to $s_4$, including the endpoints, minimizes the sum of the distances. In the even case, Some people prefer to say that any point between the two "middle" points is a median. So the conclusion is that the points that minimize the sum are the medians. Other people prefer to define the median in the even case to be the average of the two "middle" points. Then the median does minimize the sum of the distances, but some other points also do.

IN FORMULAS This is taken from this answer

Consider two $x_i$'s $x_1$ and $x_2$,

For $x_1\leq a\leq x_2$, $\sum_{i=1}^{2}|x_i-a|=|x_1-a|+|x_2-a|=a-x_1+x_2-a=x_2-x_1$

For $a\lt x_1$, $\sum_{i=1}^{2}|x_i-a|=x_1-a+x_2-a=x_1+x_2-2a\gt x_1+x_2-2x_1=x_2-x_1$

For $a\gt x_2$,$\sum_{i=1}^{2}|x_i-a|=-x_1+a-x_2+a=-x_1-x_2+2a\gt -x_1-x_2+2x_2=x_2 - x_1$

$\implies$for any two $x_i$'s the sum of the absolute values of the deviations is minimum when $x_1\leq a\leq x_2$ or $a\in[x_1,x_2]$.

When $n$ is odd, $$ \sum_{i=1}^n|x_i-a|=|x_1-a|+|x_2-a|+\cdots+\left|x_{\tfrac{n-1}{2}}-a\right| + \left|x_{\tfrac{n+1}{2}}-a\right|+\left|x_{\tfrac{n+3}{2}}-a|+\cdots+|x_{n-1}-a\right|+|x_n-a| $$ consider the intervals $[x_1,x_n], [x_2,x_{n-1}], [x_3,x_{n-2}], \ldots, \left[x_{\tfrac{n-1}{2}}, x_{\tfrac{n+3}{2}}\right]$. If $a$ is a member of all these intervals. i.e, $\left[x_{\tfrac{n-1}{2}},x_{\tfrac{n+3}{2}}\right],$

using the above theorem, we can say that all the terms in the sum except $\left|x_{\tfrac{n+1}{2}}-a\right|$ are minimized. So $$ \sum_{i=1}^n|x_i-a|=(x_n-x_1)+(x_{n-1}-x_2)+(x_{n-2}-x_3)+\cdots + \left(x_{\tfrac{n+3}{2}}-x_{\tfrac{n-1}{2}}\right) + \left|x_{\tfrac{n+1}{2}}-a\right| = \left|x_{\tfrac{n+1}{2}}-a \right|+\text{costant} $$

To minimize also the term $\left|x_{\tfrac{n+1}{2}}-a \right|$ it is clear we have to choose $a=x_{\tfrac{n+1}{2}}$ to get $0$ but this is the definition of the median.

$\implies$ When $n$ is odd,the median minimizes the sum of absolute values of the deviations.

When $n$ is even, $$ \sum_{i=1}^n|x_i-a|=|x_1-a|+|x_2-a|+\cdots+|x_{\tfrac{n}{2}}-a|+|x_{\tfrac{n}{2}+1}-a|+\cdots+|x_{n-1}-a|+|x_n-a|\\ $$ If $a$ is a member of all the intervals $[x_1,x_n], [x_2,x_{n-1}], [x_3,x_{n-2}], \ldots, \left[x_{\tfrac{n}{2}},x_{\tfrac{n}{2}+1}\right]$, i.e, $a\in\left[x_{\tfrac{n}{2}},x_{\tfrac{n}{2}+1}\right]$,

$$ \sum_{i=1}^n|x_i-a|=(x_n-x_1)+(x_{n-1}-x_2)+(x_{n-2}-x_3)+\cdots + \left(x_{\tfrac{n}{2}+1}-x_{\tfrac{n}{2}}\right) $$

$\implies$ When $n$ is even, any number in the interval $[x_{\tfrac{n}{2}},x_{\tfrac{n}{2}+1}]$, i.e, including the median, minimizes the sum of absolute values of the deviations. For example consider the series:$2, 4, 5, 10$, median, $M=4.5$.

$$ \sum_{i=1}^4|x_i-M|=2.5+0.5+0.5+5.5=9 $$ If you take any other value in the interval $\left[x_{\tfrac{n}{2}},x_{\tfrac{n}{2} + 1} \right] =[4,5]$, say $4.1$ $$ \sum_{i=1}^4|x_i-4.1|=2.1+0.1+0.9+5.9=9 $$

Taking for example $4$ or $5$ yields the same result:

$$ \sum_{i=1}^4|x_i-4|=2+0+1+6=9 $$

$$ \sum_{i=1}^4|x_i-5|=3+1+0+5=9 $$

This is because when summing the distance from $a$ to the two middle points, you end up with the distance between them: $a-x_{\tfrac{n}{2}}+(x_{\tfrac{n}{2}+1}-a) = x_{\tfrac{n}{2}+1}-x_{\tfrac{n}{2}}$

For any value outside the interval $\left[x_{\tfrac{n}{2}},x_{\tfrac{n}{2}+1}\right]=[4,5]$, say $5.2$ $$ \sum_{i=1}^4|x_i-5.2|=3.2+1.2+0.2+4.8=9.4 $$

The question has other good answers but in my opinion these are the clearest.

Answer 3

Let's call $(Y - f(X))^2 = g(Y)$. Then, we know that, for continuous cases (for example) $$ E[g(Y)] = \int g(y) f_Y(y) dy $$

And we also know that $$ P(A, B) = P(A|B) P(B)$$ or, $$ f_{y, x}(y, x) = f_{y | x}(y | x) f_{x}(x) $$

Then, to derive $E_X \Big [ E_{Y|X} [g(Y) | X ] \Big ]$, we can do:

$$E_x \Big [ E_{Y|X} [g(Y) | X] \Big ] = E_x \Big [ \int_{Y} g(y) f_{y | x}(y | x) dy \Big] \\ \int_{X} \Big[ \int_{Y} g(y) f_{y | x}(y | x) dy \Big] f_{x}(x) dx $$

Which is:

$$ \int_{X} \int_{Y} g(y) f_{y | x}(y | x) f_{x}(x) dy dx $$ $$ \int_{X} \int_{Y} g(y) f_{y, x}(y, x) dy dx $$

$$ \int_{Y} g(y) \int_{X} f_{y, x}(y, x) dy dx $$

$$ \int_{Y} g(y) f_{y}(y) dy $$

that is the expectation of our $g(Y)$.