Machine learning theory mostly analyses the learning performance of learning in the worst case over all data-generating distributions.
However, this framework is often too pessimistic.
In particular, for learning settings that use unlabeled data, such as semi-supervised and active learning, provable savings in label complexity are impossible without assumptions of niceness on the data generating distribution.
We propose Probabilistic Lipschitzness (PL), to model marginal-label relatedness of a distribution.
This notion is particularly useful for modeling niceness of distributions with deterministic labeling functions.
We present convergence rates for Nearest Neighbor learning under PL and summarize reductions in labeled sample complexity for learning with unlabeled data under PL.