Appendix A Definitions from previous work

Recall the definitions of pseudodimension and Rademacher complexity, well-known measures for hypothesis-space complexity in statistical learning theory. U ({ 1, 1 }) are Rademacher variables. We will also need the definition of dispersion which, informally speaking, captures how amenable a non-Lipschitz function is to online learning. As noted in [Balcan et al., 2018b, 2020c], dispersion is We will present an example where an unlabeled point is closest to some labeled point of one class but closer to more points of another class on average. Now we have two cases 14 1. ζ (0, The example presented above captures some essential challenges of our setting in the following sense.