{"389831":{"#nid":"389831","#data":{"type":"event","title":"PhD Thesis Defense: Cristobal Guzman","body":[{"value":"\u003Cp\u003EFinal doctoral examination and defense of dissertation of \u003Cstrong\u003ECristobal Guzman\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cbr \/\u003E\u003Cstrong\u003ETitle: Information, Complexity and Structure in Convex Optimization\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003ETime: Monday,\u0026nbsp;March 30, 9:00am\u003Cbr \/\u003ELocation: Academic Conference Room - Groseclose Building - Room 204\u003Cbr \/\u003EAdvisors: Prof. Arkadi Nemirovski and Prof. Sebastian Pokutta\u003Cbr \/\u003E\u003Cbr \/\u003ECommittee:\u003Cbr \/\u003EProf. Arkadi Nemirovski, School of Industrial and Systems Engineering\u003Cbr \/\u003EProf. Sebastian Pokutta, School of Industrial and Systems Engineering\u003Cbr \/\u003EProf. Shabbir Ahmed, School of Industrial and Systems Engineering\u003Cbr \/\u003EProf. Santosh Vempala, School of Computer Science\u003Cbr \/\u003EProf. Alexandre d\u0027Aspremont, Department d\u0027Informatique, Ecole Normale\u003Cbr \/\u003ESuperieure\u003Cbr \/\u003E\u003Cbr \/\u003EReader: Prof. Alexandre d\u0027Aspremont, Department d\u0027Informatique, Ecole\u003Cbr \/\u003ENormale Superieure\u003Cbr \/\u003E\u003Cbr \/\u003E\u003Cstrong\u003ESUMMARY\u003C\/strong\u003E: This thesis is focused on the limits of performance of large-scale\u003Cbr \/\u003Econvex optimization algorithms. Classical theory of oracle complexity,\u003Cbr \/\u003Efirst proposed by Nemirovski and Yudin in 1983, successfully established\u003Cbr \/\u003Ethe worst-case behavior of methods based on local oracles (a generalization\u003Cbr \/\u003Eof first-order oracle for smooth functions) for nonsmooth convex\u003Cbr \/\u003Eminimization, both in the large-scale and low-scale regimes; and the\u003Cbr \/\u003Ecomplexity of approximately solving linear systems of equations (equivalent\u003Cbr \/\u003Eto convex quadratic minimization) over Euclidean balls, under a\u003Cbr \/\u003Ematrix-vector multiplication oracle. Our work extends the applicability of\u003Cbr \/\u003Elower bounds in two directions: Worst-Case Complexity of Large-Scale Smooth\u003Cbr \/\u003EConvex Optimization: We generalize lower bounds on the complexity of\u003Cbr \/\u003Efirst-order methods for convex optimization, considering classes of convex\u003Cbr \/\u003Efunctions with Holder continuous gradients. Our technique relies on the\u003Cbr \/\u003Eexistence of a smoothing kernel, which defines a smooth approximation for\u003Cbr \/\u003Eany convex function via infimal convolution. As a consequence, we derive\u003Cbr \/\u003Elower bounds for ell_p\/ell_q-setups, where 1 \u0026lt;= p,q \u0026lt;= \\infty, and extend\u003Cbr \/\u003Eto its matrix analogue: Smooth (w.r.t. Schatten q-norm) convex minimization\u003Cbr \/\u003Eover matrices with bounded Schatten p-norm. The major consequences of this\u003Cbr \/\u003Eresult are the near-optimality of the Conditional Gradient method over\u003Cbr \/\u003Ebox-type domains (p=q=\\infty), and the near-optimality of Nesterov\u0027s\u003Cbr \/\u003Eaccelerated method over the cross-polytope (p=q=1).\u003Cbr \/\u003EThe thesis is available for public inspection in the School of\u003Cbr \/\u003EMathematics lounge (Skiles 236), the ARC lounge (Klaus 2222), the ISyE\u003Cbr \/\u003EPhD student lounge, and at the URL\u003Cbr \/\u003E\u003Cbr \/\u003E\u0026nbsp;\u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp;\u0026nbsp;\u003Ca href=\u0022http:\/\/www.aco.gatech.edu\/dissert\/guzman.html\u0022 target=\u0022_blank\u0022\u003Ehttp:\/\/www.aco.gatech.edu\/dissert\/guzman.html\u003C\/a\u003E\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Information, Complexity and Structure in Convex Optimization"}],"uid":"28077","created_gmt":"2015-03-23 16:36:53","changed_gmt":"2016-10-08 01:46:40","author":"Danielle Ramirez","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2015-03-30T10:00:00-04:00","event_time_end":"2015-03-30T12:00:00-04:00","event_time_end_last":"2015-03-30T12:00:00-04:00","gmt_time_start":"2015-03-30 14:00:00","gmt_time_end":"2015-03-30 16:00:00","gmt_time_end_last":"2015-03-30 16:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"221981","name":"Graduate Studies"}],"categories":[],"keywords":[{"id":"1808","name":"graduate students"},{"id":"100811","name":"Phd Defense"}],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1788","name":"Other\/Miscellaneous"}],"invited_audience":[{"id":"78771","name":"Public"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}}}