{"290241":{"#nid":"290241","#data":{"type":"event","title":"DOS Seminar","body":[{"value":"\u003Cp\u003ETITLE:\u0026nbsp; Lower Complexity Bounds for Large-Scale Smooth Convex Optimization\u003C\/p\u003E\u003Cp\u003ESPEAKER:\u0026nbsp; Cristobal Guzman\u003C\/p\u003E\u003Cp\u003EABSTRACT:\u003C\/p\u003E\u003Cp\u003EWe prove lower bounds on the black-box oracle complexity of large-scale \u003Cbr \/\u003Esmooth convex minimization problems. These lower bounds work for unit balls \u003Cbr \/\u003Eof normed spaces under a technical smoothing condition, and arbitrary \u003Cbr \/\u003Esmoothness parameter of the objective with respect to this norm. As a \u003Cbr \/\u003Econsequence, we show a unified framework for the complexity of convex \u003Cbr \/\u003Eoptimization on \\ell^p-balls, for 2\u0026lt;=p\u0026lt;=\\infty. In particular, we prove \u003Cbr \/\u003Ethat the T-step Conditional Gradient algorithm as applied to minimizing \u003Cbr \/\u003Esmooth convex functions over the n-dimensional box with T\u0026lt;=n is nearly \u003Cbr \/\u003Eoptimal. \u003Cbr \/\u003E \u003Cbr \/\u003EOn the other hand, we prove lower bounds for the complexity of convex \u003Cbr \/\u003Eoptimization over \\ell^p-balls, for 1\u0026lt;=p\u0026lt;2, by combining a random subspace \u003Cbr \/\u003Emethod with the p=\\infty lower bounds. In particular, we establish the \u003Cbr \/\u003Ecomplexity of problem classes that contain the sparse recovery problem. \u003Cbr \/\u003E \u003Cbr \/\u003EThis is joint work with Arkadi Nemirovski \u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"DOS Seminar"}],"uid":"27187","created_gmt":"2014-04-14 09:19:49","changed_gmt":"2017-04-13 21:22:42","author":"Anita Race","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2014-04-16T17:00:00-04:00","event_time_end":"2014-04-16T18:00:00-04:00","event_time_end_last":"2014-04-16T18:00:00-04:00","gmt_time_start":"2014-04-16 21:00:00","gmt_time_end":"2014-04-16 22:00:00","gmt_time_end_last":"2014-04-16 22: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":"1795","name":"Seminar\/Lecture\/Colloquium"}],"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":""}}}