Minimax Optimal Variable Clustering in G-Block Correlation Models via Cord
share
The goal of variable clustering is to partition a random vector X∈ R^p in sub-groups of similar probabilistic behavior. Popular methods such as hierarchical clustering or K-means are algorithmic procedures applied to observations on X, while no population-level target is defined prior to estimation. We take a different view in this paper, where we propose and investigate model based variable clustering. We identify variable clusters with a partition G of the variable set, which is the target of estimation. Motivated by the potential lack of identifiability of the G-latent models, which are currently used in problems involving variable clustering, we introduce the class of G-block correlation models and show that they are identifiable. The new class of models allows the unknown number of the clusters K to grow linearly with p, which itself can depend, and be larger, than the sample size. Moreover, the minimum size of a cluster can be as small as 1, and the maximum size can grow as p. In this context, we introduce MCord, a new cluster separation metric, tailored to G-block correlation models. The difficulty of any clustering algorithm is given by the size of the cluster separation required for correct recovery. We derive the minimax lower bound on MCord below which no algorithm can estimate the clusters exactly, and show that its rate is √(log(p)/n). We accompany this result by a simple, yet powerful, algorithm, CORD, and show that it recovers exactly the clusters of variables, with high probability, at the minimax optimal MCord separation rate. Our new procedure is available on CRAN and has computational complexity that is polynomial in p. The merits of our model and procedure are illustrated via a data analysis.
READ FULL TEXT