Provable Convex Co-clustering of Tensors

Abstract

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.

to appear in Journal of Machine Learning Research

References in corpus (1)

• Network Lasso: Clustering and Optimization in Large Graphs

Cited by in corpus (15)

• Dynamic Visualization and Fast Computation for Convex Clustering via Algorithmic Regularization
• Multi-way Graph Signal Processing on Tensors: Integrative analysis of irregular geometries
• Integrative Generalized Convex Clustering Optimization and Feature Selection for Mixed Multi-View Data
• Exact Clustering in Tensor Block Model: Statistical Optimality and Computational Limit
• A Sharp Blockwise Tensor Perturbation Bound for Orthogonal Iteration
• Splitting Methods for Convex Bi-Clustering and Co-Clustering
• ALMA: Alternating Minimization Algorithm for Clustering Mixture Multilayer Network
• Jointly Modeling and Clustering Tensors in High Dimensions
• Multiway Spherical Clustering via Degree-Corrected Tensor Block Models
• Clustering of Diverse Multiplex Networks
• Beyond the Signs: Nonparametric Tensor Completion via Sign Series
• Biclustering with Alternating K-Means
• Resistant convex clustering: How does the fusion penalty enhance resistantance?
• Nonparametric Trace Regression in High Dimensions via Sign Series Representation
• A Doubly-Enhanced EM Algorithm for Model-Based Tensor Clustering