# Provable Convex Co-clustering of Tensors

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Mar 2018.

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

- [ALMA: Alternating Minimization Algorithm for Clustering Mixture Multilayer Network](https://mlsanity.com/paper/2102.10226/) (2021)
- [Beyond the Signs: Nonparametric Tensor Completion via Sign Series](https://mlsanity.com/paper/2102.00384/) (2021)
- [Multiway Spherical Clustering via Degree-Corrected Tensor Block Models](https://mlsanity.com/paper/2201.07401/) (2022)
- [Sparse Subspace Clustering in Diverse Multiplex Network Model](https://mlsanity.com/paper/2206.07602/) (2022)
- [Jointly Modeling and Clustering Tensors in High Dimensions](https://mlsanity.com/paper/2104.07773/) (2021)
- [Optimal Variable Clustering for High-Dimensional Matrix Valued Data](https://mlsanity.com/paper/2112.12909/) (2021)
- [Randomly Projected Convex Clustering Model: Motivation, Realization, and Cluster Recovery Guarantees](https://mlsanity.com/paper/2303.16841/) (2023)
- [Signed Diverse Multiplex Networks: Clustering and Inference](https://mlsanity.com/paper/2402.10242/) (2024)
- [MultiwayPAM: Multiway Partitioning Around Medoids for LLM-as-a-Judge Score Analysis](https://mlsanity.com/paper/2603.10287/) (2026)
- [Nonparametric Trace Regression in High Dimensions via Sign Series Representation](https://mlsanity.com/paper/2105.01783/) (2021)
- [Data Understanding Survey: Pursuing Improved Dataset Characterization Via Tensor-based Methods](https://mlsanity.com/paper/2510.14161/) (2025)
- [Biconvex Biclustering](https://mlsanity.com/paper/2604.03936/) (2026)
- [Affinity Graph Connectivity in Convex Clustering](https://mlsanity.com/paper/2605.24673/) (2026)

## Abstract (arXiv)

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.