{"43055":{"#nid":"43055","#data":{"type":"event","title":"Graphical Model Selection: Polynomial-time Schemes","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003ETITLE:\u003C\/strong\u003E Graphical model selection in high dimensions: Polynomial-time schemes and information-theoretic limits \n\u003C\/p\u003E\n\u003Cp\u003E\u003Cstrong\u003ESPEAKER:\u003C\/strong\u003E Professor Martin Wainwright\n\u003C\/p\u003E\n\u003Cp\u003E\u003Cstrong\u003EABSTRACT:\u003C\/strong\u003E\n\u003C\/p\u003E\n\u003Cp\u003EUndirected graphical models or Markov random fields (MRF) provide a framework for capturing statistical dependencies among large collections of random variables, and are used in many application domains (e.g., spatial statistics, statistical image analysis, social network analysis).  The problem of graphical model selection is to recover the edge structure of the graph based on a set of samples from the unknown model.  In general, it is a challenging problem due to the exponential explosion in the number of possible graphs.\n\u003C\/p\u003E\n\u003Cp\u003EWe analyze different methods for graphical model selection under high-dimensional scaling, in which the graph size $p$, maximum degree $d$ and sample size $n$ are all allowed to scale.  For discrete graphical models over binary variables, we present a polynomial-time algorithm based on $ell_1$-regularized logistic regression, and show that under mild conditions, it can reliably recover the graph structure with $n = Omega(d3 log p)$ samples.  We also analyze the information-theoretic limits of the problem, and prove that no method can succeed with fewer than $n = O(d log p)$ samples.\n\u003C\/p\u003E\n\u003Cp\u003EBased on joint work with John Lafferty, Pradeep Ravikumar, and Prasad Santhanam. \u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":[{"value":"Graphical model selection in high dimensions: Polynomial-time schemes and information-theoretic limits","format":"limited_html"}],"field_summary_sentence":[{"value":"Graphical Model Selection"}],"uid":"27187","created_gmt":"2009-10-12 20:36:55","changed_gmt":"2016-10-08 01:47:21","author":"Anita Race","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2009-01-29T10:00:00-05:00","event_time_end":"2009-01-29T11:00:00-05:00","event_time_end_last":"2009-01-29T11:00:00-05:00","gmt_time_start":"2009-01-29 15:00:00","gmt_time_end":"2009-01-29 16:00:00","gmt_time_end_last":"2009-01-29 16:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"1242","name":"School of Industrial and Systems Engineering (ISYE)"}],"categories":[],"keywords":[{"id":"5470","name":"Graphical model"}],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cstrong\u003ENicoleta Serban\u003C\/strong\u003E\u003Cbr \/\u003EISyE\u003Cbr \/\u003E\u003Ca href=\u0022mailto:nserban@isye.gatech.edu\u0022\u003EContact Nicoleta Serban\u003C\/a\u003E\u003Cbr \/\u003E\u003Cstrong\u003E404-385-7255\u003C\/strong\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}}}