Abstract
We develop a martingale-based approach to constructing decision trees that efficiently approximate a target variable through recursive conditioning. We introduce MinimaxSplit, a novel splitting criterion that minimizes the worst-case variance at each step, and analyze its cyclic variant, proving an exponential error decay rate under mild conditions. Our analysis builds upon partition-based martingale approximations, providing new insights into their convergence behavior. Unlike traditional variance-based methods, MinimaxSplit avoids end-cut preference and performs well in noisy settings. We derive empirical risk bounds and also explore its integration into random forests.
