𝑘-Variance: A Clustered Notion of Variance

𝑘-Variance: A Clustered Notion of Variance Solomon, Justin; Greenewald, Kristjan; Nagaraja, Haikady We introduce 𝑘-variance, a generalization of variance built on the machinery of random bipartite matchings. 𝑘-variance measures the expected cost of matching two sets of 𝑘 samples from a distribution to each other, capturing local rather than global information about a measure as 𝑘 increases; it is easily approximated stochastically using sampling and linear programming. In addition to defining 𝑘-