# Optimizing EI in the TPE algorithm

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?

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.