Optimizing EI in the TPE algorithm

Question

My question refers to the section "4.1 Optimizing EI in the TPE algorithm" on page 4 of the paper Algorithms for Hyperparameter Optimization (PDF).

The authors provide the following step, where $\gamma := p(y < y^*)$:

$$\ell(x) \int_{-\infty}^{y^*} (y^* - y) p(y)dy = \gamma y^* \ell(x) - \ell(x) \int_{-\infty}^{y^*}p(y)dy$$

However, this is where I arrive:

\begin{align} \ell(x) \int_{-\infty}^{y^*} (y^* - y) p(y)dy &= \left[ \ell(x) \int_{-\infty}^{y^*} y^* p(y)dy \right] - \left[ \ell(x) \int_{-\infty}^{y^*} y p(y)dy \right]\\ &= \left[y^* \ell(x) \int_{-\infty}^{y^*} p(y)dy \right] - \left[ \ell(x) \int_{-\infty}^{y^*} y p(y)dy \right]\\ &= y^* \ell(x) p(y < y ^*) - \left[ \ell(x) \int_{-\infty}^{y^*} y p(y)dy \right]\\ &= y^* \ell(x) \gamma - \left[ \ell(x) \int_{-\infty}^{y^*} y p(y)dy \right]\\ &= \gamma y^* \ell(x) - \ell(x) \int_{-\infty}^{y^*} y p(y)dy \\ \end{align}

The difference between my result and the authors' result is that I still have a $y$ in the remaining integral. I got $\int_{-\infty}^{y^*} y p(y)dy$ but the authors got $\int_{-\infty}^{y^*}p(y)dy$.

Why are they different?

Answer 1

That's a typo, it should indeed be $\gamma y^{*} \ell(x) - \ell(x)\int_{-\infty}^{y^*}y p(y) dy$ as you pointed out.

The reason this works is because the derivation can actually continue from the previous expression $\ell(x)\int_{-\infty}^{y^*}(y^*-y)p(y)dy$ as follows:

Let $$I := \int_{-\infty}^{y^*}(y^*-y)p(y)dy$$

Noting that $I$ doesn't depend on $x$.

Now substitute to get \begin{align*} EI_{y^*}(x) &= \frac{\ell(x)I}{\gamma\ell(x) + (1-\gamma)g(x)} \\ &= I \times \frac{1}{\gamma + (1-\gamma)\frac{g(x)}{\ell(x)}} \\ &= I \times \left(\gamma + (1-\gamma)\frac{g(x)}{\ell(x)}\right)^{-1} \end{align*} Since $I$ does not depend on $x$ it suffices to simply evaluate $\left(\gamma + (1-\gamma)\frac{g(x)}{\ell(x)}\right)^{-1}$ in order to determine the next candidate point to evaluate the fitness function.