Computer Science > Machine Learning
Title:How Much Distribution Shift Can a Clustering Withstand? Exact Split and Merge Certificates for Structured Transports
Abstract:In clustering, the distribution of the population being clustered is often uncertain or changes over time, so the true distribution may shift away from the nominal distribution used to form the clustering. Once the clustering is committed and each member is assigned to a cluster, such shifts may change the distribution of each cluster. They can make a cluster too spread out for one representative at a given resolution, motivating a split, or bring distinct clusters close enough to share a representative at that resolution, motivating a merge. We make these split and merge events precise using a local stability criterion built on the phase-transition analysis in deterministic annealing. This notion of stability enables us to quantify how robust a clustering is against such events. Furthermore, motivated by applications in which uncertainty and population change are structured, we study shifts whose displacements are restricted to a prescribed subspace. The smallest structured shifts that reach the respective thresholds define the split and merge radii, for which we obtain exact semidefinite programming (SDP) reformulations. The split SDP has only two scalar decision variables. These convex reformulations enable us to combine the radii into a robustness certificate for the full clustering that gives the size of the smallest structured shift that reaches any monitored split or merge threshold.
| Subjects: | Machine Learning (cs.LG) |
|---|---|
| Cite as: | arXiv:2611.22000 [cs.LG] |
| (or arXiv:2611.22000v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2611.22000 arXiv-issued DOI via DataCite (pending registration) |
Submission history
Access Paper:
- HTML (experimental)
Additional Features
- Audio Summary
Current browse context:
References & Citations
- Google Scholar
- Semantic Scholar
BibTeX formatted citation
Bookmark
Bibliographic and Citation Tools
Code, Data and Media Associated with this Article
Demos
Recommenders and Search Tools
arXivLabs: experimental projects with community collaborators
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.