Ensembles of random-partition models under covariate shift: with enough trees, the Mondrian kernel regains minimax-optimal rates
Theory on covariate shift for random-partition kernel estimators previously covered only single learners such as nearest neighbors, dyadic trees and top-hat kernels, leaving unexplained why ensembles are more robust. This work extends covariate-shift severity measures to ensembles of random partitions and shows that, for a class of severe shifts with polynomial density, the discrepancy for a single Mondrian tree can be infinite while a sufficiently large ensemble of Mondrian kernel estimators still attains minimax-optimal convergence rates. The results also indicate that more severe shifts require larger ensembles.