Given the following minimization problem: $$ \text{argmin}_{\theta} \mathbb{E}_{(x,y)}[L(f_{\theta}(y),x)] $$ which can be rewritten as: $$ \text{argmin}_{\theta} \mathbb{E}_x \mathbb{E}_{(y|x)}[L(f_{\theta}(y),x)] \,. $$ Can I say that the minimum of the loss function L, being $\text{argmin}_{\theta} \mathbb{E}_{(y|x)}[L(f_{\theta}(y),x)]$ is preserved and thus $$ \text{argmin}_{\theta} \mathbb{E}_{(x,y)}[L(f_{\theta}(y),x)] = \text{argmin}_{\theta} \mathbb{E}_x ( \text{argmin}_{\theta} \mathbb{E}_{(y|x)}[L(f_{\theta}(y),x)] ) $$ ?

Thank you.

Basically I am trying to get the proof behind what is stated is section 2 of this article: https://arxiv.org/pdf/1803.04189.pdf

  • $\begingroup$ What do you actually mean by $\arg\min_\theta \mathbb{E}_x \arg\min_{\theta} (...)$? Once you choose a minimizer inside the expectation, what do you mean by averaging the minimizers and how can you choose a minimizer again? $\endgroup$
    – Steve
    Jun 9 at 9:33
  • 1
    $\begingroup$ Are you asking whether the solution $\theta$ to your original problem also has the property that for all $x$, $\theta$ solves the minimization problem conditioned on $x$? $\endgroup$
    – usul
    Jun 9 at 15:57
  • $\begingroup$ I am basically asking if $\text{argmin}_{\theta} \mathbb{E}_{(y|x)}[L(f_{\theta}(y),x)]$ is still a solution of $\text{argmin}_{\theta} \mathbb{E}_{(x,y)}[L(f_{\theta}(y),x)]$, with x and y as pair of input data $\endgroup$
    – emasasso
    Jun 10 at 13:11

Some issues. First, $\arg\min_\theta \mathbb E[L(f_\theta(y), x)|x]$ is a function of $x$, so it makes no sense with the outside $\arg\min$ at the RHS of your relationship. Second, even if we remove the outside $\arg\min$, we still can't interchange minimum with expectation without further assumptions.

However, it can be true (in some sense) if we are dealing with non-parametrized $f$. In that case, I would rather consider conditioning on $y$ instead of $x$, and suppose that $f^*(y) = \arg\min_f \mathbb E[L(f(y), x)|y]$, then it follows directly that, for any measurable $f$: $$\mathbb E[L(f(y), x)] = \mathbb E[\mathbb E[L(f(y), x)|y]] \geq \mathbb E[\mathbb E[L(f^*(y), x)|y]] = \mathbb E[L(f^*(y), x)]$$ which concludes: $$\min_{f}\mathbb E[L(f(y), x)] = \mathbb E[\min_f \mathbb E[L(f(y), x)|y]]$$ and $$\arg\min_f \mathbb E[L(f(y), x)|y]] \subset \arg\min_{f}\mathbb E[L(f(y), x)]$$

Note that this is closely related to Bayes estimator in decision theory. In our case, we can think of $x$ as a parameter with some distribution $\Lambda$, and $f(y)$ as an arbitrary estimator. $f_\Lambda(\cdot) = \arg\min_{f}\mathbb E[L(f(y), x)]$ is called Bayes estimator, and $\arg\min_f \mathbb E[L(f(y), x)|y]]$ is a way to find it (See Theorem 1.1 in Chapter 4 and related background in the very famous Theory of Point Estimation).


To be properly formulated, all occurrences of argmin should be replaced by min.

Then the hypothesized relation is false.

The RHS of the hypothesized relationship is obtained from $ \text{min}_{\theta} \mathbb{E}_x \mathbb{E}_{(y|x)}[L(f_{\theta}(y),x)] \,. $ by moving (part of the) minimization to between the expectations. I.e., interchanging minnmization with expectation (integration), which is not a valid operation.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.