Optimality of Spectral Clustering for Gaussian Mixture Models

Seminar: 
Number Theory
Event time: 
Friday, November 15, 2019 - 11:00am
Location: 
Room 107, 24 Hillhouse Avenue
Speaker: 
Harry Zhou
Speaker affiliation: 
Henry Ford II Professor of Statistics and Data Science - Yale University
Event description: 

Abstract:

Spectral clustering is one of the most popular algorithims to group high dimensional data.  It is easy to implement and computationally efficient.  Despite its popularity and successful applications, its theoretical properties have not been fully understood.  The spectral clustering algorithm is often used as a consistent initializer for more sophisticated clustering algorithims such as EM.  However, in this talk, we show that spectral clustering is actually already optimal for the Gaussian Mixture Models, when the number of clusters of is fixed and consistent clustering is possible.  Contrary to that the spectral gap conditions are widely assumed in literature to analyze spectral clustering, these conditions are not needed in this work to establish its optimality.