More Like this

1. Provable Convex Co-clustering of Tensors

   Chi, Eric C; Gaines, Brian J; Sun, Will Wei; Zhou, Hua; Yang, Jian (October 2020, Journal of machine learning research)

   null (Ed.)

   Cluster analysis is a fundamental tool for pattern discovery of complex heterogeneous data. Prevalent clustering methods mainly focus on vector or matrix-variate data and are not applicable to general-order tensors, which arise frequently in modern scientific and business applications. Moreover, there is a gap between statistical guarantees and computational efficiency for existing tensor clustering solutions due to the nature of their non-convex formulations. In this work, we bridge this gap by developing a provable convex formulation of tensor co-clustering. Our convex co-clustering (CoCo) estimator enjoys stability guarantees and its computational and storage costs are polynomial in the size of the data. We further establish a non-asymptotic error bound for the CoCo estimator, which reveals a surprising ``blessing of dimensionality" phenomenon that does not exist in vector or matrix-variate cluster analysis. Our theoretical findings are supported by extensive simulated studies. Finally, we apply the CoCo estimator to the cluster analysis of advertisement click tensor data from a major online company. Our clustering results provide meaningful business insights to improve advertising effectiveness. 

   more » « less
2. A* for Bounding Shortest Paths in the Graphs of Convex Sets

   https://doi.org/10.1609/icaps.v35i1.36127  

   Sundar, Kaarthik; Rathinam, Sivakumar (September 2025, Proceedings of the International Conference on Automated Planning and Scheduling)

   We present a novel algorithm that fuses the existing convex-programming based approach with heuristic information to find optimality guarantees and near-optimal paths for the Shortest Path Problem in the Graph of Convex Sets (SPP-GCS). Our method, inspired by A* initiates a best-first-like procedure from a designated subset of vertices and iteratively expands it until further growth is neither possible nor beneficial. Traditionally, obtaining solutions with bounds for an optimization problem involves solving a relaxation, modifying the relaxed solution to a feasible one, and then comparing the two solutions to establish bounds. However, for SPP-GCS, we demonstrate that reversing this process can be more advantageous, especially with Euclidean travel costs. In other words, we initially employ A* to find a feasible solution for SPP-GCS, then solve a convex relaxation restricted to the vertices explored by A* to obtain a relaxed solution, and finally, compare the solutions to derive bounds. We present numerical results to highlight the advantages of our algorithm over the existing approach in terms of the sizes of the convex programs solved and computation time. 

   more » « less
3. Convex clustering with metric learning

   https://doi.org/j.patcog.2018.04.019  

   Sui, Xiaopeng Lucia; Xu, Li; Qian, Xiaoning; Liu, Tie (September 2018, Pattern recognition)

   The convex clustering formulation of Chi and Lange (2015) is revisited. While this formulation can be precisely and efficiently solved, it uses the standard Euclidean metric to measure the distance between the data points and their corresponding cluster centers and hence its performance deteriorates significantly in the presence of outlier features. To address this issue, this paper considers a formulation that combines convex clustering with metric learning. It is shown that: (1) for any given positive definite Mahalanobis distance metric, the problem of convex clustering can be precisely and efficiently solved using the Alternating Direction Method of Multipliers; (2) the problem of learning a positive definite Mahalanobis distance metric admits a closed-form solution; (3) an algorithm that alternates between convex clustering and metric learning can provide a significant performance boost over not only the original convex clustering formulation but also the recently proposed robust convex clustering formulation of Wang et al. (2017). 

   more » « less
4. Identifiability of Nonparametric Mixture Models and Bayes Optimal Clustering

   https://doi.org/10.1214/19-AOS1887  

   Aragam, B.; Dan, C.; Xing, E.; Ravikumar, P. (April 2020, The annals of statistics)

   Motivated by problems in data clustering, we establish general conditions under which families of nonparametric mixture models are identifiable, by introducing a novel framework involving clustering overfitted parametric (i.e. misspecified) mixture models. These identifiability conditions generalize existing conditions in the literature, and are flexible enough to include for example mixtures of Gaussian mixtures. In contrast to the recent literature on estimating nonparametric mixtures, we allow for general nonparametric mixture components, and instead impose regularity assumptions on the underlying mixing measure. As our primary application, we apply these results to partition-based clustering, generalizing the notion of a Bayes optimal partition from classical parametric model-based clustering to nonparametric settings. Furthermore, this framework is constructive so that it yields a practical algorithm for learning identified mixtures, which is illustrated through several examples on real data. The key conceptual device in the analysis is the convex, metric geometry of probability measures on metric spaces and its connection to the Wasserstein convergence of mixing measures. The result is a flexible framework for nonparametric clustering with formal consistency guarantees. 

   more » « less
5. Statistically Optimal K-means Clustering via Nonnegative Low-rank Semidefinite Programming

   Zhuang, Yubo; Chen, Xiaohui; Yang, Yun; Zhang, Y Richard (May 2024, The Twelfth International Conference on Learning Representations (2024 ICLR))

   K-means clustering is a widely used machine learning method for identifying patterns in large datasets. Recently, semidefinite programming (SDP) relaxations have been proposed for solving the K-means optimization problem, which enjoy strong statistical optimality guarantees. However, the prohibitive cost of implementing an SDP solver renders these guarantees inaccessible to practical datasets. In contrast, nonnegative matrix factorization (NMF) is a simple clustering algorithm widely used by machine learning practitioners, but it lacks a solid statistical underpinning and theoretical guarantees. In this paper, we consider an NMF-like algorithm that solves a nonnegative low-rank restriction of the SDP-relaxed K-means formulation using a nonconvex Burer--Monteiro factorization approach. The resulting algorithm is as simple and scalable as state-of-the-art NMF algorithms while also enjoying the same strong statistical optimality guarantees as the SDP. In our experiments, we observe that our algorithm achieves significantly smaller mis-clustering errors compared to the existing state-of-the-art while maintaining scalability. 

   more » « less