{"625117":{"#nid":"625117","#data":{"type":"event","title":"TRIAD Lecture Series by Yuxin Chen from Princeton (1\/5)","body":[{"value":"\u003Cp\u003ETitle of this talk: \u0026nbsp;The power of nonconvex optimization in solving random quadratic systems of equations\u003C\/p\u003E\r\n\r\n\u003Cp\u003EAbstract: \u0026nbsp;We consider the fundamental problem of solving random quadratic systems of equations in n variables,\u0026nbsp;which spans many applications ranging from the century-old phase retrieval problem to various latent-variable\u0026nbsp;models in machine learning. A growing body of recent work has demonstrated the effectiveness of convex\u0026nbsp;relaxation --- in particular, semidefinite programming --- for solving problems of this kind. However, the\u003Cbr \/\u003E\r\ncomputational cost of such convex paradigms is often unsatisfactory, which limits applicability to\u0026nbsp;large-dimensional data.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EThis talk follows another route: by formulating the problem into nonconvex programs, we attempt to optimize the\u0026nbsp;nonconvex objectives directly. We demonstrate that for certain unstructured models of quadratic systems,\u0026nbsp;nonconvex optimization algorithms return the correct solution in linear time, as soon as the ratio between the\u0026nbsp;number of equations and unknowns exceeds a fixed numerical constant. We extend the theory to deal with noisy systems, and prove that our algorithms achieve a minimax optimal statistical accuracy. Numerical evidence\u0026nbsp;suggests that the computational cost of our algorithm is about four times that of solving a least-squares\u0026nbsp;problem of the same size.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EThis is joint work with Emmanuel Candes.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EBio: Yuxin Chen is currently an assistant professor in the Department of Electrical Engineering at Princeton\u0026nbsp;University. Prior to joining Princeton, he was a postdoctoral scholar in the Department of Statistics at\u0026nbsp;Stanford University, and he completed his Ph.D. in Electrical Engineering at Stanford University. His research interests include high-dimensional statistics, convex and nonconvex optimization, statistical learning, and\u003Cbr \/\u003E\r\ninformation theory. He received the 2019 AFOSR Young Investigator Award.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":[{"value":"\u003Cp\u003EThis is one of a series of talks that are given by Professor Chen. The full list of his talks is as follows:\u003Cbr \/\u003E\r\nWednesday, August 28, 2019; 11:00 am - 12:00 pm; Groseclose 402\u003Cbr \/\u003E\r\nThursday, August 29, 2019; 11:00 am - 12:00 pm; Groseclose 402\u003Cbr \/\u003E\r\nTuesday, September 3, 2019; 11:00 am - 12:00 pm; Main - Executive Education Room 228\u003Cbr \/\u003E\r\nWednesday, September 4, 2019; 11:00 am - 12:00 pm; Main - Executive Education Room 228\u003Cbr \/\u003E\r\nThursday, September 5, 2019; 11:00 am - 12:00 pm; Groseclose 402\u003C\/p\u003E\r\n\r\n\u003Cp\u003ECheck https:\/\/triad.gatech.edu\/events for more information.\u003C\/p\u003E\r\n\r\n\u003Cp\u003ETitle of this talk:\u0026nbsp; The power of nonconvex optimization in solving random quadratic systems of equations\u003C\/p\u003E\r\n\r\n\u003Cp\u003EAbstract:\u0026nbsp; We consider the fundamental problem of solving random quadratic systems of equations in n variables, which spans many applications ranging from the century-old phase retrieval problem to various latent-variable models in machine learning. A growing body of recent work has demonstrated the effectiveness of convex relaxation --- in particular, semidefinite programming --- for solving problems of this kind. However, the computational cost of such convex paradigms is often unsatisfactory, which limits applicability to large-dimensional data.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EThis talk follows another route: by formulating the problem into nonconvex programs, we attempt to optimize the nonconvex objectives directly. We demonstrate that for certain unstructured models of quadratic systems, nonconvex optimization algorithms return the correct solution in linear time, as soon as the ratio between the number of equations and unknowns exceeds a fixed numerical constant. We extend the theory to deal with noisy systems and prove that our algorithms achieve a minimax optimal statistical accuracy. Numerical evidence suggests that the computational cost of our algorithm is about four times that of solving a least-squares the problem of the same size.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EThis is joint work with Emmanuel Candes.\u003C\/p\u003E\r\n","format":"limited_html"}],"field_summary_sentence":[{"value":"This is one of a series of talks that are given by Professor Chen."}],"uid":"34963","created_gmt":"2019-08-25 17:15:21","changed_gmt":"2019-08-29 12:48:44","author":"Xiaoming Huo","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2019-08-28T12:00:00-04:00","event_time_end":"2019-08-28T13:00:00-04:00","event_time_end_last":"2019-08-28T13:00:00-04:00","gmt_time_start":"2019-08-28 16:00:00","gmt_time_end":"2019-08-28 17:00:00","gmt_time_end_last":"2019-08-28 17:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"related_links":[{"url":"http:\/\/www.princeton.edu\/~yc5\/slides\/Gatech2019_TWF.pdf","title":"Talk Slides at Speaker\u0027s web site"}],"groups":[{"id":"602673","name":"TRIAD "}],"categories":[],"keywords":[{"id":"92811","name":"data science"}],"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"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}}}