Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It only takes a minute to sign up.
Sign up to join this community
This is a question from an old Ph.D Qualifying Exam.
Let $X,Y$ be two random variables. Find $g^{*}(X)$ so that $$\min_{g(x)}E(Y-g(X))^2=E(Y-g^{*}(X))^2$$
My attempt: If $g$ were a function of $Y$, then trivially $g(Y)=E(Y)$. However, since this is a function of $X$, I can't figure out how to approach this question. I guess this answer depends on the correlation between $X$ and $Y$. Does anyone have ideas?
Note: Normally for self-study questions we try to give hints rather than full solutions. However, in the present case you are dealing with a functional-optimisation problem where I think most students would not have any idea how to do any of this, without seeing a full solution for a few cases. In view of this, I have decided to give a full solution below.
Re-framing the optimisation problem: When you are undertaking optimisation in function spaces, half the battle is re-framing the problem in a way that brings it back to optimisation in the reals. In this case, this can be done by recognising that the functional argument is operating on $X$, but the loss is then with respect to $Y$. In this kind of case, with a bit of effort you can split your optimisation problem to turn it into a set of optimisations conditional on values of $x$, which reduces the problem to a standard optimisation problem dealing with real numbers (rather than a function).
Let's have a look at how to do this in the present case. You can apply the law-of-total-expectation to restate your optimisation problem as follows:
$$\underset{g \in \mathscr{G}}{\text{Minimise}} \quad F(g) = \int \limits_{\mathscr{X}} H(g(x),x) p_X(x) dx,$$
where $\mathscr{G}$ is some appropriately large function-space for the function $g$ (we will come back to this), and the inner-function $H$ is the conditional expectation:
$$H(g(x),x) \equiv \int \limits_{\mathscr{Y}} (y-g(x))^2 p_{Y|X}(y|x) dy.$$
Now, observe here that for a fixed argument value of $x$, the function $H(\text{ }\cdot \text{ }, x)$ depends on $g$ only through the individual value $g(x)$. Since you are choosing a function $g$ with argument value $x$ in your optimisation, this means that minimising the objective over the function-space is equivalent to minimising the inner function $H(g(x),x)$ for each individual $x$. Thus, substituting $w = g(x)$, your optimisation problem reduces to the non-linear programming problem:
$$\underset{w \in \mathbb{R}}{\text{Minimise}} \quad H(w,x) \quad \quad \quad \text{for all } x \in \mathscr{X}.$$
This means we can solve this optimisation problem by finding the point-wise optimised function $\hat{g}$ that minimises the above conditional expectation for each individual $x \in \mathscr{X}$.
One caveat on this: If we optimise in this way, we have to go back and check that the resulting optimised function $\hat{g}$ is within the allowable function-space in the initial optimisation problem. We have glossed over this in the above explanation, since it will turn out that the optimised function in this case is a well-known result that is usually considered to be within the scope of the optimisation. Nevertheless, the above reasoning should be read with the implicit caveat that it might not apply if the function space $\mathscr{G}$ is not sufficiently broad to encompass the point-wise optimised function $\hat{g}$. In that case the problem becomes much more complicated!
Solving the point-wise optimisation problem: To conduct our point-wise real optimisation we will use standard calculus techniques. For a fixed value of $x$ the derivative of $H$ with respect to our argument value is:
$$\begin{equation} \begin{aligned} \frac{\partial H}{\partial w}(w,x) &= \frac{\partial}{\partial w} \int \limits_{\mathscr{Y}} (y-w)^2 p_{Y|X}(y|x) dy \\[6pt] &= \int \limits_{\mathscr{Y}} \frac{\partial}{\partial w} (y-w)^2 p_{Y|X}(y|x) dy \\[6pt] &= -2 \int \limits_{\mathscr{Y}} (y-w) p_{Y|X}(y|x) dy \\[6pt] &= -2 \Bigg[ \int \limits_{\mathscr{Y}} y p_{Y|X}(y|x) dy - w \int \limits_{\mathscr{Y}} p_{Y|X}(y|x) dy \Bigg] \\[6pt] &= -2 \Bigg[ \mathbb{E}(Y|X=x) - w \Bigg]. \\[6pt] \end{aligned} \end{equation}$$
(Note that we have brought the derivative operator inside the integral in this working. This step can be justified by assuming that the support $\mathscr{Y}$ is not affected by the estimator $w = g(x)$, and the function $H$ has continuous partial derivatives.) For each fixed $x$ the function $H(w,x)$ is strictly convex in $w$, so the minimising point occurs at the unique critical point of the function, so we have:
$$0 = \frac{\partial H}{\partial w}(\hat{w},x) = -2 \Bigg[ \mathbb{E}(Y|X=x) - \hat{w} \Bigg] \quad \quad \implies \quad \quad \hat{w} = \mathbb{E}(Y|X=x).$$
Hence, our point-wise optimised function is:
$$\hat{g}(x) = \mathbb{E}(Y|X=x).$$
Assuming that this function is within the function-space for the initial optimisation problem (which it should be), we have found the optimising function. From this result we can see that the way to minimise squared-error-loss is to choose the conditional expectation of $Y$ given $X$ as estimator. This is a well-known result in estimation theory, but as you can see, the derivation requires a bit of knowledge of how to deal with functional optimisation problems.
Interpreting the question as @whuber did in his comment, here is a quite vague hint:
https://en.wikipedia.org/wiki/Law_of_total_expectation
Edit after the spoilers: graphical illustration of the application of the hint, as well as shorter version of Ben's answer:
Here are the two dependent random variables $X$ and $Y$. You can see the distribution of $Y$ "sliced" at some values of $X$.
The law of total expectation says, that if you want to integrate an expression of $X$ and $Y$, then you can first integrate it on each slice, and then integrate over the slices. Which is very handy in this case.
The expression of the question at a slice $x_0$ becomes $E((Y|X=x_0) - g(x_0))^2$, and it is well known (and mentioned by you in the question), that it is minimized by the average $g(x_0) = E(Y|X=x_0)$.
Since such $g$ minimizes the value of the expression at every slice, it minimizes the slice integral as well.
