Exact Recovery of Clusters in Finite Metric Spaces Using Oracle Queries
Contributo in Atti di convegno
Data di Pubblicazione:
2021
Citazione:
Exact Recovery of Clusters in Finite Metric Spaces Using Oracle Queries / M. Bressan, N. Cesa Bianchi, S. Lattanzi, A. Paudice (PROCEEDINGS OF MACHINE LEARNING RESEARCH). - In: Proceedings of Thirty Fourth Conference on Learning Theory / [a cura di] M. Belkin, S. Kpotufe. - [s.l] : PMLR, 2021. - pp. 775-803 (( Intervento presentato al 34. convegno Conference on Learning Theory.
Abstract:
We investigate the problem of exact cluster recovery using oracle queries. Previous results show that clusters in Euclidean spaces that are convex and separated with a margin can be reconstructed exactly using only $O(log n)$ same-cluster queries, where $n$ is the number of input points. In this work, we study this problem in the more challenging non-convex setting. We introduce a structural characterization of clusters, called $(eta,gamma)$-convexity, that can be applied to any finite set of points equipped with a metric (or even a semimetric, as the triangle inequality is not needed). Using $(eta,gamma)$-convexity, we can translate natural density properties of clusters (which include, for instance, clusters that are strongly non-convex in $R^d$) into a graph-theoretic notion of convexity. By exploiting this convexity notion, we design a deterministic algorithm that recovers $(eta,gamma)$-convex clusters using $O(k^2 log n + k^2 (rac{6}{etagamma})^{dens(X)})$ same-cluster queries, where $k$ is the number of clusters and $dens(X)$ is the density dimension of the semimetric. We show that an exponential dependence on the density dimension is necessary, and we also show that, if we are allowed to make $O(k^2 + k log n)$ additional queries to a "cluster separation" oracle, then we can recover clusters that have different and arbitrary scales, even when the scale of each cluster is unknown.
Tipologia IRIS:
03 - Contributo in volume
Keywords:
Non-convex clusters; same-cluster queries; geodesic convexity
Elenco autori:
M. Bressan, N. Cesa Bianchi, S. Lattanzi, A. Paudice
Link alla scheda completa:
Link al Full Text:
Titolo del libro:
Proceedings of Thirty Fourth Conference on Learning Theory