I am trying to implement the Tree Parzen Estimator for hyperparameter optimization. I follow this paper https://papers.nips.cc/paper/4443-algorithms-for-hyper-parameter-optimization.pdf, in which section 4 is the relevant one.

I am confused about Section 4.2: "The Adaptive Parzen Estimator yields a model over X by placing density in the vicinity of K observations B = {x(1), ..., x(K)} ⊂ H".

• What is "Adaptive Parzen Estimator"? Is it similar to multivariate kernel density estimators?
• What is K? What K observations to pick?
• Given the way they deal with discrete variables (bottom of the page), this seems to not model dependencies between discrete variables and all other variables. Is that correct? When you have a multivariate KDE, obviously it models dependencies between variables. But not when you just increase probability of some discrete value according to how many times it has been seen. Or am I mistaken?

If this technique is first defined in this paper, it seems underspecified to me. Maybe someone with some knowledge about this technique can fill the holes?

2. Since $$\mathcal{B} \subset \mathcal{H}$$, it seems that they only use a subset of the history to do the kernel density estimation. In this case, $$K$$ would be the number of observations that are used for the kernel density estimation.
I might have answered your questions at this point, but this does not necessarily make things much clearer. E.g. it is still unclear whether balloon or pointwise estimators were used or how to sample $$\mathcal{B}$$ from $$\mathcal{H}$$. Of course, if we take a look at the reference implementation of TPE, these details can be found (spoiler: the bandwidth is the bounded maximum difference to the nearest neighbours). However, even Yoshua Bengio (last author) acknowledges that this should have been cited properly in the paper.