LabelRegimes

Corollary A.2. Suppose that the measure-smoothness assumption (Assumption 5.1) holds with parametersλ,Cλ,k k. Let us introduce the notation P0( . To conclude the proof of the lemma we apply Corollary A.2 to infer that with probability at least 1 δ/2wehave max Lemma B.2 implies that if we setk to be large enough, then all estimates for labels inTs(η(x)) will be smaller than1/2,thus thek-NN learner does not sufferanyregret on these labels, and we can handle this case easily inthe regret analysis. The setGδ(D) X contains those instances in the feature space for which we can compute an upper bound on the regret with anon-trivial term, since the error ofthek-NN regression estimate is small for the top-s Ts(η(x)). The next lemma provides a high-probability upper bound on the marginal probability measureµofX\Gδ(D).