{"390181":{"#nid":"390181","#data":{"type":"event","title":"PhD Thesis Defense - Cristobal Guzman","body":[{"value":"\u003Cp\u003ETITLE: Information, Complexity and Structure in Convex Optimization\u003C\/p\u003E\u003Cp\u003EABSTRACT:\u003C\/p\u003E\u003Cp\u003EThis thesis is focused on the limits of performance of large-scale convex optimization algorithms. Classical theory of oracle complexity, first proposed by Nemirovski and Yudin in 1983, successfully established the worst-case behavior of methods based on local oracles (a generalization of first-order oracle for smooth functions) for nonsmooth convex minimization, both in the large-scale and low-scale regimes; and the complexity of approximately solving linear systems of equations (equivalent to convex quadratic minimization) over Euclidean balls, under a matrix-vector multiplication oracle. \u003C\/p\u003E\u003Cp\u003EOur work extends the applicability of lower bounds in two directions: \u003C\/p\u003E\u003Cp\u003EWorst-Case Complexity of Large-Scale Smooth Convex Optimization: We generalize lower bounds on the complexity of first-order methods for convex optimization, considering classes of convex functions with Holder continuous gradients. Our technique relies on the existence of a smoothing kernel, which defines a smooth approximation for any convex function via infimal convolution. As a consequence, we derive lower bounds for ell_p\/ell_q-setups, where 1 \u0026lt;= p,q \u0026lt;= \\infty, and extend to its matrix analogue: Smooth (w.r.t. Schatten q-norm) convex minimization over matrices with bounded Schatten p-norm.\u003C\/p\u003E\u003Cp\u003EThe major consequences of this result are the near-optimality of the Conditional Gradient method over box-type domains (p=q=\\infty), and the near-optimality of Nesterov\u0027s accelerated method over the cross-polytope (p=q=1). \u003Cbr \/\u003E\u003C\/p\u003E\u003Cp\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;\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":"PhD Thesis Defense - Cristobal Guzman"}],"uid":"27187","created_gmt":"2015-03-24 15:22:12","changed_gmt":"2017-04-13 21:19:41","author":"Anita Race","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-30T10:00:00-04:00","event_time_end_last":"2015-03-30T10:00:00-04:00","gmt_time_start":"2015-03-30 14:00:00","gmt_time_end":"2015-03-30 14:00:00","gmt_time_end_last":"2015-03-30 14:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"1242","name":"School of Industrial and Systems Engineering (ISYE)"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1788","name":"Other\/Miscellaneous"}],"invited_audience":[{"id":"78751","name":"Undergraduate students"},{"id":"78761","name":"Faculty\/Staff"},{"id":"174045","name":"Graduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}}}