{"641931":{"#nid":"641931","#data":{"type":"event","title":"ARC Colloquium: Zhao Song (Princeton \u0026 Institute for Advanced Study)","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\u003EZhao Song (Princeton \u0026amp; Institute for Advanced Study)\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EMonday, November 14, 2020\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EVirtual via Bluejeans - 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: \u003C\/strong\u003EFaster Optimization : From Linear Programming to Deep Learning\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract: \u003C\/strong\u003EMany important real-life problems, in both convex and non-convex settings, can be solved using path-following optimization methods. The running time of optimization algorithms is typically governed\u0026nbsp;by two components -- the number of iterations and the cost-per-iteration. For decades, the vast majority of research effort was dedicated to improving the number of iterations required for convergence. A recent line of work of ours shows that the\u0026nbsp;\u003Cem\u003Ecost-per-iteration\u003C\/em\u003E\u0026nbsp;can be dramatically\u0026nbsp;improved using a careful combination of dynamic data structures with `robust\u0026#39; variants of the optimization method. A central ingredient is the use of randomized linear algebra for dimensionality\u0026nbsp;reduction (e.g.,\u0026nbsp; linear sketching) for fast maintenance of dynamic matrix problems.\u0026nbsp;This framework\u0026nbsp;recently led to many breakthroughs on decade-old optimization problems.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EIn this talk, I will present the framework\u0026nbsp;underlying these breakthroughs, focusing on faster\u0026nbsp;algorithms for linear programming and deep learning. We will first present how to use the above\u0026nbsp;idea to speed up general LP solvers by providing an n^omega + n^{2+1\/18} time algorithm.\u0026nbsp;We then show how to apply similar ideas in the *non-convex*\u0026nbsp;setting of deep learning. We provide both a theoretical result of a near-linear training algorithm for (overparametrized) neural networks, and an experimental application of LP techniques to speed up neural network training in practice.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E----------------------------------\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/www.ias.edu\/scholars\/zhao-song\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=\u0022http:\/\/arc.gatech.edu\/node\/121\u0022\u003Ehttp:\/\/arc.gatech.edu\/node\/121\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/mailman.cc.gatech.edu\/mailman\/listinfo\/arc-colloq\u0022\u003EClick here to subscribe to the seminar email list: arc-colloq@Klauscc.gatech.edu \u003C\/a\u003E\u003C\/p\u003E\r\n","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Faster Optimization : From Linear Programming to Deep Learning - Virtual via Bluejeans at 11:00am"}],"uid":"27544","created_gmt":"2020-12-08 13:53:30","changed_gmt":"2020-12-08 13:53:30","author":"Francella Tonge","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2020-12-14T11:00:00-05:00","event_time_end":"2020-12-14T12:00:00-05:00","event_time_end_last":"2020-12-14T12:00:00-05:00","gmt_time_start":"2020-12-14 16:00:00","gmt_time_end":"2020-12-14 17:00:00","gmt_time_end_last":"2020-12-14 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":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[{"id":"78761","name":"Faculty\/Staff"},{"id":"177814","name":"Postdoc"},{"id":"174045","name":"Graduate students"},{"id":"78751","name":"Undergraduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}}}