{"618789":{"#nid":"618789","#data":{"type":"event","title":"ARC Colloquium: Ravi Kannan (MSR)","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\u003ERavi Kannan (MSR)\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EMonday, March 25, 2019\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EKlaus 1116E - 11:00 am\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003ETitle:\u0026nbsp; \u003C\/strong\u003EA General Algorithm for Unsupervised Learning problems\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract:\u0026nbsp; \u003C\/strong\u003EThe following simply-stated geometric problem includes as special cases the core problems of a\u0026nbsp; number\u0026nbsp; of\u0026nbsp; areas\u0026nbsp; in\u0026nbsp; Unsupervised\u0026nbsp; Learning,\u0026nbsp; including,\u0026nbsp; Topic\u0026nbsp; Modeling,\u0026nbsp; Non-negative\u0026nbsp; Matrix Factorization, Clustering, Stochastic Block Models and Overalapping Communities Detection:\u003C\/p\u003E\r\n\r\n\u003Cp\u003EThere is an unknown polytope \u003Cem\u003EK\u003C\/em\u003E\u0026nbsp; \u0026isin; \u003Cstrong\u003ER\u003C\/strong\u003E\u003Cem\u003E\u003Csup\u003Ed\u003C\/sup\u003E\u003C\/em\u003E with\u003Cem\u003E k\u003C\/em\u003E vertices.\u0026nbsp; We are given n data points, each aperturbation of some point in \u003Cem\u003EK.\u003C\/em\u003E\u0026nbsp; The problem is to find \u003Cem\u003EK\u003C\/em\u003E, i.e., its vertices (approximately).\u0026nbsp; [The perturbations are large; indeed, many data points lie outside\u003Cem\u003E K\u003C\/em\u003E.]\u003C\/p\u003E\r\n\r\n\u003Cp\u003EOur main result is an algorithm which solves this general problem under two natural assumptions.\u0026nbsp; Our assumptions are technically different,\u0026nbsp; but similar in spirit to existing models for the special cases.\u0026nbsp; We assume separation between the vertices of\u003Cem\u003E K\u003C\/em\u003E\u0026nbsp; and the existence of \u0026ldquo;pure\u0026rdquo; data points whose unperturbed versions are close to the vertices of \u003Cem\u003EK\u003C\/em\u003E.\u0026nbsp; Notably we do not assume any stochastic\u0026nbsp; model\u0026nbsp; of\u0026nbsp; data.\u0026nbsp;\u0026nbsp; Our\u0026nbsp; algorithm\u0026nbsp; has\u0026nbsp; better\u0026nbsp; complexity\u0026nbsp; than\u0026nbsp; known\u0026nbsp; algorithms\u0026nbsp; for\u0026nbsp; the special cases when the input matrix\u003Cstrong\u003E A\u003C\/strong\u003E is sparse and k is relatively small compared to \u003Cem\u003En, d\u003C\/em\u003E.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EThe algorithm is simply stated, but the proof of correctness is involved.\u0026nbsp; It draws on tools in Numerical Analysis, especially perturbation of singular spaces of matrices.\u0026nbsp; Here is a description of our algorithm:\u0026nbsp; It has \u003Cem\u003Ek\u003C\/em\u003E stages; in each stage, it picks a certain random vector \u003Cem\u003Eu\u003C\/em\u003E, finds the \u003Cem\u003Em\u003C\/em\u003E largest\u003Cem\u003E u \u0026middot; x \u003C\/em\u003Eover data points\u003Cem\u003E x\u003C\/em\u003E and outputs the average of these data points as an approximation to a new vertex of \u003Cem\u003EK\u003C\/em\u003E.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EJoint Work with C. Bhattacharyya\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E----------------------------------\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/simons.berkeley.edu\/people\/ravi-kannan\u0022\u003ESpeaker\u0026#39;s Webpage\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cem\u003EVideos of recent talks are available at: \u003C\/em\u003E\u003Ca href=\u0022https:\/\/smartech.gatech.edu\/handle\/1853\/46836\u0022\u003E\u003Cem\u003Ehttps:\/\/smartech.gatech.edu\/handle\/1853\/46836\u003C\/em\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/mailman.cc.gatech.edu\/mailman\/listinfo\/arc-colloq\u0022\u003E\u003Cem\u003EClick here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu \u003C\/em\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"A General Algorithm for Unsupervised Learning problems - Klaus 1116 East at 11 am"}],"uid":"27544","created_gmt":"2019-03-05 14:33:45","changed_gmt":"2019-03-19 12:35:05","author":"Francella Tonge","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2019-03-25T12:00:00-04:00","event_time_end":"2019-03-25T13:00:00-04:00","event_time_end_last":"2019-03-25T13:00:00-04:00","gmt_time_start":"2019-03-25 16:00:00","gmt_time_end":"2019-03-25 17:00:00","gmt_time_end_last":"2019-03-25 17:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1789","name":"Conference\/Symposium"}],"invited_audience":[{"id":"78761","name":"Faculty\/Staff"},{"id":"177814","name":"Postdoc"},{"id":"78771","name":"Public"},{"id":"174045","name":"Graduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}}}