Appendix 1 Proofs

In this section, we present the proof of Theorem 1. Proof. Next, we prove the correctness of Algorithm 1. This proves the correctness of Algorithm 1. Finally, we consider the complexity of Algorithm 1. In Theorem 1, we demonstrated that MABSplit scales logarithmically in dataset size. Appendix Figure 1 (a) demonstrates the number of data points queried by MABSplit for a single node split, i.e., a single call to MABSplit, as the dataset size increases, for various subset sizes of For each sample size, a sample is drawn with replacement from the original MNIST dataset.