{"665072":{"#nid":"665072","#data":{"type":"event","title":"ARC Colloquium: Rohan Ghuge (University of Michigan)","body":[{"value":"\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EAlgorithms \u0026amp; Randomness Center (ARC)\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003ERohan Ghuge (University of Michigan)\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EFebruary 13, 2023\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022Center\u0022\u003E\u003Cstrong\u003EPettit Microelectronics Building, Room 102 A\u0026amp;B - 2:00 pm\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E The Power of Adaptivity for Decision-Making under Uncertainty\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract:\u0026nbsp; \u003C\/strong\u003EIn this talk, we discuss the role of adaptivity in decision-making problems under uncertainty. The first part of the talk focuses on stochastic combinatorial optimization problems, while the second part deals with the K-armed dueling bandits problem.\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003ECombinatorial optimization captures many natural decision-making\u0026nbsp;problems such as matching, assortment optimization,\u0026nbsp;and submodular optimization. In many practical settings, we have to solve such combinatorial problems under uncertainty; specifically when we\u0026nbsp;only have partial knowledge about the input. Solutions to such\u0026nbsp;problems are sequential decision processes that make decisions one\u0026nbsp;by one \u0026ldquo;adaptively\u0026rdquo; (depending on prior observations). While such\u0026nbsp;adaptive solutions achieve the best objective, the inherently\u0026nbsp;sequential nature makes them undesirable in many applications. Specifically, we ask: \u003Cem\u003Ehow well can solutions with few adaptive rounds approximate fully-adaptive solutions? \u003C\/em\u003EWe study (and answer) this question for the stochastic submodular cover problem, where one needs to select a subset of stochastic items to cover a submodular function at minimum expected cost. This model captures many problems such as sensor placement with unreliable sensors, optimal decision tree, stochastic set cover, and correlated knapsack cover. We show how to obtain solutions that approximate fully-adaptive solutions using only a few \u0026ldquo;rounds\u0026rdquo; of adaptivity for the stochastic submodular cover problem. We study both independent and correlated settings, proving \u003Cem\u003Esmooth tradeoffs between the number of adaptive rounds and the solution quality\u003C\/em\u003E. We also present experimental results demonstrating that a few rounds of adaptivity suffice to obtain high-quality solutions in practice.\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EIn the second part of the talk, we discuss the K-armed dueling bandits problem, a variation of the multi-armed bandit problem where the feedback is in the form of noisy pairwise comparisons. This problem has applications in a wide-variety of domains like search ranking, recommendation systems and sports ranking where eliciting qualitative feedback is easy while real-valued feedback is not easily interpretable; thus, it has been a popular topic of research in the machine learning community. Previous works have only focused on the sequential setting where the learning policy adapts after every comparison. However, in many applications such as search ranking and recommendation systems, it is preferable to perform comparisons in a limited number of parallel batches. We \u003Cem\u003Eintroduce and study the batched dueling bandits problem\u003C\/em\u003E, for which we design algorithms with a \u003Cem\u003Esmooth trade-off between the number of batches and regret\u003C\/em\u003E. Our regret bounds match the best known sequential regret bounds (up to poly-logarithmic factors), using only a logarithmic number (in the time horizon) of batches.\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E---------------------------------------------------------------\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022http:\/\/rohanghuge.com\/\u0022\u003ESpeaker\u0026#39;s Webpage\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cem\u003EVideos of recent talks are available at: \u003C\/em\u003E\u003Ca href=\u0022https:\/\/smartech.gatech.edu\/handle\/1853\/46836\u0022\u003E\u003Cem\u003Ehttps:\/\/smartech.gatech.edu\/handle\/1853\/46836\u003C\/em\u003E\u003C\/a\u003E\u003Cem\u003E and \u003Ca href=\u0022http:\/\/arc.gatech.edu\/node\/121\u0022\u003Ehttp:\/\/arc.gatech.edu\/node\/121\u003C\/a\u003E \u003C\/em\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/mailman.cc.gatech.edu\/mailman\/listinfo\/arc-colloq\u0022\u003E\u003Cem\u003EClick here to subscribe to the seminar email list: arc-colloq@Klauscc.gatech.edu\u003C\/em\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"The Power of Adaptivity for Decision-Making under Uncertainty - Pettit 102 A\u0026B at 2:00 PM"}],"uid":"35702","created_gmt":"2023-01-25 12:41:38","changed_gmt":"2023-02-07 13:04:23","author":"mb121","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2023-02-13T14:00:00-05:00","event_time_end":"2023-02-13T15:00:00-05:00","event_time_end_last":"2023-02-13T15:00:00-05:00","gmt_time_start":"2023-02-13 19:00:00","gmt_time_end":"2023-02-13 20:00:00","gmt_time_end_last":"2023-02-13 20:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"}],"categories":[],"keywords":[],"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"},{"id":"78751","name":"Undergraduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}}}