“K-Means: A Nonconvex Problem with Fast and Provable Algorithms”

Speaker: Hamed Hassani
Assistant Professor of Electrical and Systems Engineering at the University of Pennsylvania

Add to calendar: iCalendar  •  Google Calendar  •  Outlook  •  Outlook Online  •  Yahoo! Calendar

Abstract: Non-convex optimization problems are ubiquitous and arise in many modern applications of statistics and machine learning. It is well known that finding a local optimum of a non-convex problem is NP-hard in general, and hence, most of the non-convex optimization procedures can only ensure convergence to stationary points without any guarantees. In some exceptional cases, such as K-means clustering, the geometric structure of the problem can be exploited to design efficient algorithms with guarantees on the quality of the solution. Such a geometric structure is usually captured in the “seeding” step of K-means algorithms. Seeding - the task of finding initial cluster centers - is critical in obtaining high-quality clusterings for K-Means. In this talk, I will discuss fast and scalable seeding methods that produce provably good clusterings without any assumptions on the data. I will then demonstrate analytically that such methods allow for a favourable trade-off between solution quality and computational cost, speeding up the state-of-the-art algorithms by up to several orders of magnitude. I will conclude with discussing experimental results and future directions.

Bio: Hamed Hassani is currently an assistant professor of Electrical and Systems Engineering department at the University of Pennsylvania. Prior to that, he was a research fellow at Simons Institute for the Theory of Computing (UC Berkeley), and a post-doctoral researcher in the Computer Science department at ETH Zurich. He received a Ph.D. degree in Computer and Communication Sciences from EPFL, Lausanne. Hamed’s fields of interest include information theory, machine learning, and theory and applications of graphical models. He is the recipient of the 2014 IEEE Information Theory Society Thomas M. Cover Dissertation Award. His co-authored paper at ISIT 2015 received the IEEE Jack Keil Wolf ISIT Student Paper Award.

.