Research map / Learning theory and algorithms / Clustering
Achieving Optimal Clustering in Gaussian Mixture Models with Anisotropic Covariance Structures
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Derives minimax lower bounds for clustering under homogeneous and heterogeneous anisotropic Gaussian mixtures and shows an adjusted Lloyd's (hard EM) algorithm with covariance estimation attains them within log n iterations.
Problem
Clustering under Gaussian mixture models whose covariance matrices are unknown and anisotropic, either shared across clusters or distinct per cluster; the fundamental limits and a rate-optimal polynomial-time procedure were previously unknown.
Approach
Replace the Euclidean distance in Lloyd's algorithm with Mahalanobis-type distances using iteratively re-estimated covariance matrices (a hard EM variant), and define anisotropic signal-to-noise ratios (SNR for shared covariance, SNR' via QDA for heterogeneous covariances) that govern the minimax exponent.
Key results
- On Fashion-MNIST T-shirt/Trouser (12,000 images, PCA to 50 dims), Algorithm 2 achieves 5.71% misclustering error versus 8.24% for vanilla Lloyd's.
- On the three-class Fashion-MNIST subset (18,000 images), Algorithm 2 achieves 3.97% error versus 5.64% for vanilla Lloyd's.
- In simulations, Algorithms 1 and 2 reach the theoretical minimax error exponents after about three iterations, while spectral and vanilla Lloyd's do not.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Algorithm 2 instead of vanilla Lloyd | Clustering on Fashion-MNIST with T-shirt/top and Trouser classes · Fashion-MNIST, T-shirt/top and Trouser | misclustering error: 8.24% -> 5.71% | Helped |
| Use Algorithm 2 instead of vanilla Lloyd | Clustering on Fashion-MNIST with three classes · Fashion-MNIST, T-shirt/top, Trouser, and Ankle boot | misclustering error: 5.64% -> 3.97% | Helped |
| Estimate and use covariance information in adjusted Lloyd’s algorithm | Clustering under anisotropic GMMs · Synthetic Model 1 and Model 2 | misclustering error | Helped |
Limitations
- Upper bounds require d = O(sqrt(n)) for the homogeneous model and d = O(1) for the heterogeneous model, stronger than prior isotropic results.
- Theory assumes well-conditioned covariance matrices (bounded eigenvalue ratio), which excludes ill-conditioned or degenerate covariances.
- Initialization must satisfy l(z0,z*)=o(n), requiring a decent starting point such as vanilla Lloyd's.
Experimental setup
Datasets: Fashion-MNIST
Benchmarks: Fashion-MNIST (T-shirt/Trouser, T-shirt/Trouser/Ankle boot subsets)
Metrics: misclustering error rate log misclustering error
Baselines: spectral clustering vanilla Lloyd's algorithm
Builds on: Lloyd's algorithm Lu and Zhou 2016 minimax clustering Gao et al. spectral clustering optimality Giraud and Verzelen-style sub-Gaussian mixture analysis hard EM
Closest papers by meaning
- A Spectral Algorithm for List-Decodable Covariance Estimation in Relative Frobenius Norm (NeurIPS 2023 · similarity 0.89)
- Clustering Semi-Random Mixtures of Gaussians (ICML 2018 · similarity 0.87)
- Learning Mixtures of Gaussian Processes through Random Projection (ICML 2024 · similarity 0.87)
- Generalization Performance of Ensemble Clustering: From Theory to Algorithm (ICML 2025 · similarity 0.86)
- Scalable Multiple Kernel Clustering: Learning Clustering Structure from Expectation (ICML 2024 · similarity 0.85)
- Sublinear Variational Optimization of Gaussian Mixture Models with Millions to Billions of Parameters (NeurIPS 2026 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.