Locally-Adaptive Nonparametric Online Learning: Supplementary Material

Next, we consider two algorithms for the problem of prediction with expert advice over trees. The following lemma (whose proof is deferred to Appendix D) formally states this fact. Suppose that Algorithm 5 is run using predictions and updates provided by Algorithm 6. Suppose that Algorithm 5 is run using predictions and updates provided by AdaNormalHedge. We start by proving a master regret bound that can be specialized to various settings of interest. Combining terms completes the proof.