Exact Clustering in Tensor Block Model: Statistical Optimality and Computational Limit

• Activity Number: 202 - SLDS Student Paper Awards
• Type: Topic-Contributed
• Date/Time: Tuesday, August 10, 2021 : 1:30 PM to 3:20 PM
• Sponsor: Section on Statistical Learning and Data Science
• Author(s): Rungang Han* and Yuetian Luo and Miaoyan Wang and Anru Zhang
• Companies: University of Wisconsin-Madison and University of Wisconsin-Madison and University of Wisconsin-Madison and University of Wisconsin-Madison
• Keywords: clustering; tensors; low-rank; block model

Abstract

High-order clustering aims to identify heterogeneous substructure in multiway dataset that arises commonly in neuroimaging, genomics, and social network studies. The non-convex and discontinuous nature of the problem poses significant challenges in both statistics and computation. In this paper, we propose a tensor block model and the computationally efficient methods, High-order Lloyd algorithm (HLloyd) and High-order spectral clustering (HSC), for high-order clustering in tensor block model. The convergence of the proposed procedure is established, and we show that our method achieves exact clustering under reasonable assumptions. We also give the complete characterization for the statistical-computational trade-off in high-order clustering based on three different signal-to-noise ratio regimes. Finally, we show the merits of the proposed procedures via extensive experiments on both synthetic and real datasets.