{"582458":{"#nid":"582458","#data":{"type":"event","title":"ARC Colloquium: Constantinos Daskalakis (MIT)","body":[{"value":"\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EAlgorithms \u0026amp; Randomness Center (ARC)\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EConstantinos Daskalakis (MIT)\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EMonday, March 6, 2017\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EKlaus 1116 East - 11:00 am\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003ETitle:\u0026nbsp;\u003C\/strong\u003E\u003Cem\u003ETen Steps of EM Suffice for Mixtures of Two Gaussians\u003C\/em\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cbr \/\u003E\r\n\u003Cstrong\u003EAbstract\u003C\/strong\u003E:\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;The Expectation-Maximization (EM) algorithm is a widely used method for maximum likelihood estimation in models with latent variables. For estimating mixtures of Gaussians, its iteration can be viewed as a soft version of the k-means clustering algorithm. Despite its wide use and applications, there are essentially no known convergence guarantees for this method. We provide global convergence guarantees for\u0026nbsp; mixtures of two Gaussians with known covariance matrices. We show that EM converges geometrically to the correct mean vectors, and provide simple, closed-form expressions for the convergence rate. As a simple illustration, we show that, in one dimension, ten steps of the EM algorithm initialized at infinity result in less than 1% error estimation of the means.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E(Joint work with Christos Tzamos and Manolis Zampetakis.)\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EBio: \u0026nbsp;\u003C\/strong\u003EConstantinos Daskalakis is the x-window consortium associate professor of computer science at MIT. He holds a diploma in electrical and computer engineering from the National Technical University of Athens, and a Ph.D. in electrical engineering and computer sciences from UC-Berkeley. His research interests lie in theoretical computer science and its interface with economics and probability. Daskalakis has been honored with the 2007 Microsoft Graduate Research Fellowship, the 2008 ACM Doctoral Dissertation Award, the Game Theory and Computer Science Prize from the Game Theory Society, the 2010 Sloan Fellowship in Computer Science, the 2011 SIAM Outstanding Paper Prize, the 2011 Ruth and Joel Spira Award for Distinguished Teaching, the 2012 Microsoft Research Faculty Fellowship, and the 2015 Research and Development Award by the Vatican Giuseppe Sciacca Foundation. He is also a recipient of Best Paper awards at the ACM Conference on Economics and Computation in 2006 and in 2013.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E---------------------------------------------------------\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022http:\/\/people.csail.mit.edu\/costis\/\u0022\u003ESpeaker\u0026#39;s webpage\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003EVideos of recent talks are available at: \u003Ca href=\u0022https:\/\/smartech.gatech.edu\/handle\/1853\/46836\u0022\u003Ehttps:\/\/smartech.gatech.edu\/handle\/1853\/46836\u003C\/a\u003E\u003Cbr \/\u003E\r\n\u003Cbr \/\u003E\r\n\u003Ca href=\u0022https:\/\/mailman.cc.gatech.edu\/mailman\/listinfo\/arc-colloq\u0022\u003EClick here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu \u003C\/a\u003E\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":" Ten Steps of EM Suffice for Mixtures of Two Gaussians  (Klaus 1116 E at 11am)"}],"uid":"27466","created_gmt":"2016-10-12 18:03:02","changed_gmt":"2017-04-13 21:14:21","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2017-03-06T11:00:00-05:00","event_time_end":"2017-03-06T12:00:00-05:00","event_time_end_last":"2017-03-06T12:00:00-05:00","gmt_time_start":"2017-03-06 16:00:00","gmt_time_end":"2017-03-06 17:00:00","gmt_time_end_last":"2017-03-06 17:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"}],"categories":[],"keywords":[{"id":"111051","name":"Algorithm and Randomness Center"},{"id":"4265","name":"ARC"}],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[{"id":"78761","name":"Faculty\/Staff"},{"id":"78771","name":"Public"},{"id":"78751","name":"Undergraduate students"},{"id":"174045","name":"Graduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003EEric Vigoda\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}}}