# k-Variance: A Clustered Notion of Variance

arXiv: https://arxiv.org/abs/2012.06958 · HTML: https://mlsanity.com/paper/2012.06958/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Dec 2020.

## Built on by (most cited first, 11 of 11)

- [Measuring Generalization with Optimal Transport](https://mlsanity.com/paper/2106.03314/) (2021)
- [X-Boundary: Establishing Exact Safety Boundary to Shield LLMs from Multi-Turn Jailbreaks without Compromising Usability](https://mlsanity.com/paper/2502.09990/) (2025)
- [k-Mixup Regularization for Deep Learning via Optimal Transport](https://mlsanity.com/paper/2106.02933/) (2021)
- [Towards Bridging Generalization and Expressivity of Graph Neural Networks](https://mlsanity.com/paper/2410.10051/) (2024)
- [Input margins can predict generalization too](https://mlsanity.com/paper/2308.15466/) (2023)
- [A Critical Look at Targeted Instruction Selection: Disentangling What Matters (and What Doesn't)](https://mlsanity.com/paper/2602.14696/) (2026)
- [Centered plug-in estimation of Wasserstein distances](https://mlsanity.com/paper/2203.11627/) (2022)
- [Beyond External Monitors: Enhancing Transparency of Large Language Models for Easier Monitoring](https://mlsanity.com/paper/2502.05242/) (2025)
- [Differentially Private Wasserstein Barycenters](https://mlsanity.com/paper/2510.03021/) (2025)
- [Generalization of Graph Neural Networks through the Lens of Homomorphism](https://mlsanity.com/paper/2403.06079/) (2024)
- [Transductive Generalization via Optimal Transport and Its Application to Graph Node Classification](https://mlsanity.com/paper/2603.09257/) (2026)

## Abstract (arXiv)

We introduce k-variance, a generalization of variance built on the machinery of random bipartite matchings. K-variance measures the expected cost of matching two sets of k samples from a distribution to each other, capturing local rather than global information about a measure as k increases; it is easily approximated stochastically using sampling and linear programming. In addition to defining k-variance and proving its basic properties, we provide in-depth analysis of this quantity in several key cases, including one-dimensional measures, clustered measures, and measures concentrated on low-dimensional subsets of mathbb Rn. We conclude with experiments and open problems motivated by this new way to summarize distributional shape.