{"590507":{"#nid":"590507","#data":{"type":"event","title":"ARC Colloquium: Michael Cohen (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\u003EMichael Cohen (MIT)\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EMonday, May 1, 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\u003ENew Algorithms for Matrix Scaling Problems via Second-order Methods and Generalized Laplacian System Solvers\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract\u003C\/strong\u003E:\u003Cbr \/\u003E\r\nIn this paper, we study matrix scaling and balancing, which are fundamental problems in scientific computing, with a long line of work on them that dates back to the 1960s. We provide algorithms for both these problems that, ignoring logarithmic factors involving the dimension of the input matrix and the size of its entries, both run in time m log(k) log^2(1\/eps) where eps is the amount of error we are willing to tolerate. Here, k represents the ratio between the largest and the smallest entries of the optimal scalings. This implies that our algorithms run in nearly-linear time whenever k is quasi-polynomial, which includes, in particular, the case of strictly positive matrices.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EIn order to establish these results, we develop a new second-order optimization framework that enables us to treat both problems in a unified and principled manner. This framework identifies a certain generalization of linear system solving which we can use to efficiently minimize a broad class of functions, which we call second-order robust. We then show that in the context of the specific functions capturing matrix scaling and balancing, we can leverage and generalize the work on Laplacian system solving to make the algorithms obtained via this framework very efficient.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EWe also discuss an interior point method that runs in time, up to logarithmic factors, of m^{3\/2} log(1\/eps) for the case of matrix balancing and the doubly-stochastic variant of matrix scaling (with an additional log(log(k)) bound in a more general setting).\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EJoint work with Aleksander Madry, Dimitris Tsipras, and Adrian Vladu.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EArXiv posting:\u0026nbsp;\u003Ca href=\u0022https:\/\/arxiv.org\/abs\/1704.02310\u0022 target=\u0022_blank\u0022\u003Ehttps:\/\/arxiv.org\/abs\/1704.02310\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003EA similar approach (but not using the generalization of Laplacian solvers and hence obtaining somewhat different results) was developed independently by Zeyuan Allen-Zhu, Yuanzhi Li, Rafael Oliveira, and Avi Wigderson:\u0026nbsp;\u003Ca href=\u0022https:\/\/arxiv.org\/abs\/1704.02315\u0022 target=\u0022_blank\u0022\u003Ehttps:\/\/arxiv.org\/abs\/1704.02315\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E----------------------------------------------------------------\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/scholar.google.com\/citations?user=t3kDJHQAAAAJ\u0026amp;hl=en\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: \u003Ca href=\u0022https:\/\/smartech.gatech.edu\/handle\/1853\/46836\u0022\u003Ehttps:\/\/smartech.gatech.edu\/handle\/1853\/46836\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@cc.gatech.edu \u003C\/a\u003E\u003C\/em\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"New Algorithms for Matrix Scaling Problems via Second-order Methods and Generalized Laplacian System Solvers (Klaus 1116E at 11am)"}],"uid":"32895","created_gmt":"2017-04-17 16:07:25","changed_gmt":"2017-04-17 16:10:47","author":"Eric Vigoda","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2017-05-01T12:00:00-04:00","event_time_end":"2017-05-01T13:00:00-04:00","event_time_end_last":"2017-05-01T13:00:00-04:00","gmt_time_start":"2017-05-01 16:00:00","gmt_time_end":"2017-05-01 17:00:00","gmt_time_end_last":"2017-05-01 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":[],"invited_audience":[{"id":"78761","name":"Faculty\/Staff"},{"id":"78771","name":"Public"},{"id":"78751","name":"Undergraduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}}}