Position: Ph.D. Candidate

Current Institution: George Washington University


Convergence rate of stochastic k-means

Clustering, the science (or art) of grouping data automatically, is crucial to many applications, ranging from grouping genes with similar expressions to segmenting forest cover types obtained by satellite images. Modern clustering algorithms face challenges from large-scale datasets. For this purpose, stochastic k-means, a scalable version of the k-means algorithm, was proposed (Bottou-Bengio 98, Sculley 10) and has become increasingly popular for general-purpose large-scale clustering. On the other hand, most of its properties, such as convergence speed and solution quality, lacked formal guarantees, limiting its reliability to practitioners.

I will present our recent results addressing this gap between theory and practice. By exploiting the connection between stochastic k-means and stochastic gradient descent and using recent insights on non-convex stochastic optimization, we show, for the first time, that starting with any initial choice of k centers, the algorithm converges to a local optimum at a linear rate, in expectation. In addition, we show that if the dataset has an underlying “clusterable” structure, then initializing stochastic k-means with a simple and scalable seeding algorithm guarantees expected convergence to an optimal k-means solution at linear rate, with high probability.

Cheng is a PhD candidate at George Washington University, working on machine learning with Professor Claire Monteleoni. Her recent research directions include rigorously justifying the empirical success of popular clustering heuristics, such as k-means and linkage-based algorithms, developing scalable clustering algorithms via sampling, and the analysis of non-convex problems emerging from unsupervised learning. On the applied side, she has used machine learning algorithm to detect patterns of climate extremes from raw climate data. Cheng received her B.S. in Mathematics also from George Washington University in May 2012. In the preceding fall, she returned from studying abroad and serendipitously took Claire’s class in machine learning, which turned out to be a perfectly interdisciplinary field that accommodates her diverse interests, and now she is entering her 5th year exploring it. She was the recipient of the 2013 Louis P. Wagman Endowment Fellowship and the 2015-2016 Engineer Alumni Association scholarship from the GWU School of Engineering and Applied Science.