Tree-structured Parzen Estimator

Represent valid configurations with a conditional generative tree so that some variables are active only for particular parent choices. Given observed configurations and losses to minimize, choose a loss threshold at a quantile gamma and fit l(x) from observations below that threshold and g(x) from the remainder. The model uses p(x|y)=l(x) below the threshold and g(x) otherwise, with p(x)=gamma*l(x)+(1−gamma)*g(x). Under this construction, expected nonnegative improvement E[max(y*−y,0)] is proportional, across configurations, to [gamma+(1−gamma)*g(x)/l(x)]^−1 wherever the relevant densities and expectation are defined. Draw candidate configurations from l, rank them by this expression, evaluate the selected candidate’s actual loss, and incorporate the observation into subsequent density estimates. The original estimator replaces continuous priors with adaptive Parzen mixtures around observed values and retains a prior component; bounded uniform variables use truncated Gaussian mixtures, log-uniform variables are modeled in log space, and categorical probabilities are reweighted by observed counts. The tree specifies conditional variable activation, not a decision tree that predicts loss. This is distinct from the separate Gaussian-process surrogate described in Section 3 of the same paper.