Asymptotic Theory of Geometric and Adaptive $k$-Means Clustering

• URL: http://arxiv.org/abs/2202.13423v2
• Date: Fri, 27 Jun 2025 23:01:38 GMT
• Title: Asymptotic Theory of Geometric and Adaptive $k$-Means Clustering
• Authors: Adam Quinn Jaffe,
• Abstract summary: We revisit Pollard's classical result on consistency for $k$-means clustering in Euclidean space.<n>We show that all clustering procedures described above are strongly consistent.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We revisit Pollard's classical result on consistency for $k$-means clustering in Euclidean space, with a focus on extensions in two directions: first, to problems where the data may come from interesting geometric settings (e.g., Riemannian manifolds, reflexive Banach spaces, or the Wasserstein space); second, to problems where some parameters are chosen adaptively from the data (e.g., $k$-medoids or elbow-method $k$-means). Towards this end, we provide a general theory which shows that all clustering procedures described above are strongly consistent. In fact, our method of proof allows us to derive many asymptotic limit theorems beyond strong consistency. We also remove all assumptions about uniqueness of the set of optimal cluster centers.

Related papers

• Near-Optimal Clustering in Mixture of Markov Chains [74.3828414695655]
  We study the problem of clustering $T$ trajectories of length $H$, each generated by one of $K$ unknown ergodic Markov chains over a finite state space of size $S$.<n>We derive an instance-dependent, high-probability lower bound on the clustering error rate, governed by the weighted KL divergence between the transition kernels of the chains.<n>We then present a novel two-stage clustering algorithm.
  arXiv  Detail & Related papers  (2025-06-02T05:10:40Z)
• Self-Supervised Graph Embedding Clustering [70.36328717683297]
  K-means one-step dimensionality reduction clustering method has made some progress in addressing the curse of dimensionality in clustering tasks. We propose a unified framework that integrates manifold learning with K-means, resulting in the self-supervised graph embedding framework.
  arXiv  Detail & Related papers  (2024-09-24T08:59:51Z)
• Disentangled Representation Learning with the Gromov-Monge Gap [65.73194652234848]
  Learning disentangled representations from unlabelled data is a fundamental challenge in machine learning. We introduce a novel approach to disentangled representation learning based on quadratic optimal transport. We demonstrate the effectiveness of our approach for quantifying disentanglement across four standard benchmarks.
  arXiv  Detail & Related papers  (2024-07-10T16:51:32Z)
• Correspondence-Free Non-Rigid Point Set Registration Using Unsupervised Clustering Analysis [28.18800845199871]
  We present a novel non-rigid point set registration method inspired by unsupervised clustering analysis. Our method achieves high accuracy results across various scenarios and surpasses competitors by a significant margin.
  arXiv  Detail & Related papers  (2024-06-27T01:16:44Z)
• GCC: Generative Calibration Clustering [55.44944397168619]
  We propose a novel Generative Clustering (GCC) method to incorporate feature learning and augmentation into clustering procedure. First, we develop a discrimirative feature alignment mechanism to discover intrinsic relationship across real and generated samples. Second, we design a self-supervised metric learning to generate more reliable cluster assignment.
  arXiv  Detail & Related papers  (2024-04-14T01:51:11Z)
• Deep Embedding Clustering Driven by Sample Stability [16.53706617383543]
  We propose a deep embedding clustering algorithm driven by sample stability (DECS) Specifically, we start by constructing the initial feature space with an autoencoder and then learn the cluster-oriented embedding feature constrained by sample stability. The experimental results on five datasets illustrate that the proposed method achieves superior performance compared to state-of-the-art clustering approaches.
  arXiv  Detail & Related papers  (2024-01-29T09:19:49Z)
• Stable Cluster Discrimination for Deep Clustering [7.175082696240088]
  Deep clustering can optimize representations of instances (i.e., representation learning) and explore the inherent data distribution. The coupled objective implies a trivial solution that all instances collapse to the uniform features. In this work, we first show that the prevalent discrimination task in supervised learning is unstable for one-stage clustering. A novel stable cluster discrimination (SeCu) task is proposed and a new hardness-aware clustering criterion can be obtained accordingly.
  arXiv  Detail & Related papers  (2023-11-24T06:43:26Z)
• Curvature-Independent Last-Iterate Convergence for Games on Riemannian Manifolds [77.4346324549323]
  We show that a step size agnostic to the curvature of the manifold achieves a curvature-independent and linear last-iterate convergence rate. To the best of our knowledge, the possibility of curvature-independent rates and/or last-iterate convergence has not been considered before.
  arXiv  Detail & Related papers  (2023-06-29T01:20:44Z)
• A One-shot Framework for Distributed Clustered Learning in Heterogeneous Environments [54.172993875654015]
  The paper proposes a family of communication efficient methods for distributed learning in heterogeneous environments. One-shot approach, based on local computations at the users and a clustering based aggregation step at the server is shown to provide strong learning guarantees. For strongly convex problems it is shown that, as long as the number of data points per user is above a threshold, the proposed approach achieves order-optimal mean-squared error rates in terms of the sample size.
  arXiv  Detail & Related papers  (2022-09-22T09:04:10Z)
• The Dynamics of Riemannian Robbins-Monro Algorithms [101.29301565229265]
  We propose a family of Riemannian algorithms generalizing and extending the seminal approximation framework of Robbins and Monro. Compared to their Euclidean counterparts, Riemannian algorithms are much less understood due to lack of a global linear structure on the manifold. We provide a general template of almost sure convergence results that mirrors and extends the existing theory for Euclidean Robbins-Monro schemes.
  arXiv  Detail & Related papers  (2022-06-14T12:30:11Z)
• First-Order Algorithms for Min-Max Optimization in Geodesic Metric Spaces [93.35384756718868]
  min-max algorithms have been analyzed in the Euclidean setting. We prove that the extraiteient (RCEG) method corrected lastrate convergence at a linear rate.
  arXiv  Detail & Related papers  (2022-06-04T18:53:44Z)
• No More Than 6ft Apart: Robust K-Means via Radius Upper Bounds [17.226362076527764]
  Centroid based clustering methods such as k-means, k-medoids and k-centers are heavily applied as a go-to tool in exploratory data analysis. In many cases, those methods are used to obtain representative centroids of the data manifold for visualization or summarization of a dataset. We propose to remedy such a scenario by introducing a maximal radius constraint $r$ on the clusters formed by centroids.
  arXiv  Detail & Related papers  (2022-03-04T18:59:02Z)
• Gradient Based Clustering [72.15857783681658]
  We propose a general approach for distance based clustering, using the gradient of the cost function that measures clustering quality. The approach is an iterative two step procedure (alternating between cluster assignment and cluster center updates) and is applicable to a wide range of functions.
  arXiv  Detail & Related papers  (2022-02-01T19:31:15Z)
• Classification of (2+1)D invertible fermionic topological phases with symmetry [2.74065703122014]
  We classify invertible fermionic topological phases of interacting fermions with symmetry in two spatial dimensions for general fermionic symmetry groups $G_f$. Our results also generalize and provide a different approach to the recent classification of fermionic symmetry-protected topological phases by Wang and Gu.
  arXiv  Detail & Related papers  (2021-09-22T21:02:07Z)
• Local versions of sum-of-norms clustering [77.34726150561087]
  We show that our method can separate arbitrarily close balls in the ball model. We prove a quantitative bound on the error incurred in the clustering of disjoint connected sets.
  arXiv  Detail & Related papers  (2021-09-20T14:45:29Z)
• You Never Cluster Alone [150.94921340034688]
  We extend the mainstream contrastive learning paradigm to a cluster-level scheme, where all the data subjected to the same cluster contribute to a unified representation. We define a set of categorical variables as clustering assignment confidence, which links the instance-level learning track with the cluster-level one. By reparametrizing the assignment variables, TCC is trained end-to-end, requiring no alternating steps.
  arXiv  Detail & Related papers  (2021-06-03T14:59:59Z)
• Global Riemannian Acceleration in Hyperbolic and Spherical Spaces [0.0]
  Research on the acceleration phenomenon on Euclidian curvature by the first global firstorder method. First order method achieves the same rates as in Euclidean gradient as accelerated gradient descent.
  arXiv  Detail & Related papers  (2020-12-07T12:09:30Z)
• Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
  Existing scalable hierarchical clustering methods sacrifice quality for speed. We present a scalable, agglomerative method for hierarchical clustering that does not sacrifice quality and scales to billions of data points.
  arXiv  Detail & Related papers  (2020-10-22T15:58:35Z)
• Curvature-Dependant Global Convergence Rates for Optimization on Manifolds of Bounded Geometry [6.85316573653194]
  We give curvature-dependant convergence rates for weakly convex functions defined on a manifold of 1-bounded geometry. We compute these bounds explicitly for some manifold commonly used in the optimization literature. We present self-contained proofs of fully general bounds on the norm of the differential of the exponential map.
  arXiv  Detail & Related papers  (2020-08-06T08:30:35Z)
• Robust $k$-means Clustering for Distributions with Two Moments [4.21934751979057]
  We consider the robust algorithms for the $k$-means clustering problem where a quantizer is constructed based on $N$ independent observations. Our main results are median of means based non-asymptotic excess distortion bounds that hold under the two bounded moments assumption in a general separable Hilbert space.
  arXiv  Detail & Related papers  (2020-02-06T16:36:53Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.