Skip to main content
Back to timeline
arXivSource publication:

Ensembles of random-partition models under covariate shift: with enough trees, the Mondrian kernel regains minimax-optimal rates

Synopsis

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.

Interpretation

Covariate-shift analysis for random-partition kernel estimators now has discrepancy measures indexed by ensemble size, making ensemble size an explicit variable in the risk bound. Earlier severity measures targeted single learners such as nearest-neighbor, dyadic-tree and top-hat kernel estimators and were shown to control minimax rates; ensembles such as random forests, built from piecewise-constant local averages over random partitions, had no corresponding theory. For a class of shifts where the target is uniform on the unit cube and the source has polynomial density, the integrated shift discrepancy for a single Mondrian tree can be infinite, yet a sufficiently large ensemble of Mondrian kernel estimators still attains minimax-optimal convergence rates.

Ensembling helps because it pools independent training points near the test point, widening the sample available to the local average. Cells of a single Mondrian tree are small because of the memorylessness of the STIT tessellation, so too few training points feed the local average to withstand severe shift. The bias term in the risk bound grows only logarithmically in ensemble size, so the bound applies to moderate-to-large finite ensembles; the analysis covers independently realized STIT tessellations with partitions independent of the training data.

More severe covariate shifts require larger ensembles to reach minimax-optimal convergence rates. Prior empirical reports showed only that ensembles degrade less under shift, without a quantitative link between ensemble size and shift severity. On the polynomial-density class of shifts, a sufficiently large ensemble is needed to bring the integrated shift discrepancy to the required level with high probability, which is what guarantees the rate.

Perspective

The analysis covers purely random partition ensembles whose partitions are independent of the training data and independently generated, with a Hölder-continuous regression function, nested compact source and target supports, and bounded second-moment label noise; explicit rates are given for STIT tessellations, and the numerical example is limited to one-dimensional Mondrian partitions under a polynomial-density class of shifts.

The bias bound grows only logarithmically in ensemble size, so it suits moderate-to-large finite ensembles rather than arbitrarily large ones; the authors note that the large-ensemble limit corresponds to the Laplace kernel, whose robustness to covariate shift is not known. The integrated shift discrepancy for a single Mondrian tree can be infinite, and controlling it with high probability requires a sufficiently large ensemble, a guarantee that relies on truncation to handle the low-probability event.