Fréchet Regression with Mondrian Forests: Finite-Sample Guarantees and Ensemble Benefits

Fréchet random forests extend the power of classical random forests to general metric spaces, offering promising advantages over traditional methods, especially in high-dimensional settings. While forests have empirically outperformed individual trees in Fréchet regression, the theoretical basis for this improvement remains largely unexplored. This paper fills this gap by establishing non-asymptotic upper bounds for the prediction risk of Fréchet Mondrian forests, complementing the existing literature that primarily focuses on asymptotic analysis. We demonstrate that, under suitable regularity conditions, Fréchet Mondrian forests attain convergence rates comparable to their Euclidean counterparts. Moreover, under higher-order smoothness assumptions and with a sufficient number of trees, Fréchet forests achieve faster convergence than individual Fréchet trees, thereby providing a rigorous theoretical justification for the benefit of ensembles in non-Euclidean regression problems. The effectiveness of the proposed method is further corroborated through simulation studies across diverse settings, including probability distributions, symmetric positive-definite matrices, and spherical data.