BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1519
DTSTAMP:20250317T091122Z
SUMMARY:Semi-Bandit Learning for Monotone Stochastic Optimization
DESCRIPTION:Speaker: Arpit Agarwal (IIT Bombay)\n\nAbstract: \nStochastic o
 ptimization is a widely used approach for optimization under uncertainty\,
  where uncertain input parameters are modeled by random variables. Exact o
 r approximation algorithms have been obtained for several fundamental prob
 lems in this area. However\, a significant limitation of this approach is 
 that it requires full knowledge of the underlying probability distribution
 s. Can we still get good (approximation) algorithms if these distributions
  are unknown\, and the algorithm needs to learn them through repeated inte
 ractions? Particularly\, can we design an online learning algorithm whose 
 performance smoothly approaches the performance of an (offline) optimal al
 gorithm which has knowledge of these distributions?In this work\, we resol
 ve this question for a large class of "monotone" stochastic problems\, by 
 providing a generic online learning algorithm with \\sqrt{T log T} regret 
 relative to the best approximation algorithm (under known distributions). 
 Importantly\, our online algorithm works in a semi-bandit setting\, where 
 in each period\, the algorithm only observes samples from the r.v.s that w
 ere actually probed. Our framework applies to several fundamental problems
  in stochastic optimization such as prophet inequality\, Pandora's box\, s
 tochastic knapsack\, stochastic matchings and stochastic submodular optimi
 zation.In this talk\, I will first introduce the multi-armed bandits frame
 work and describe the popular algorithmic principle of "optimism in the fa
 ce of uncertainty". I will then give a brief introduction to stochastic op
 timization. Finally\, I will describe our result on conversion from offlin
 e to online semi-bandit algorithms for stochastic optimization.This talk i
 s based on a FOCS'24 paper with Rohan Ghuge and Viswanath Nagarajan- http
 s://arxiv.org/pdf/2312.15427.\nShort Bio:\nArpit Agarwal is an Assistant P
 rofessor at the CSE Department at IIT Bombay. His research lies in the are
 a of machine learning (ML) and artificial intelligence (AI). His focus is 
 on human-centered AI which includes learning from human feedback\, underst
 anding AI impact on individuals and society\, and designing socially respo
 nsible AI. Prior to joining IIT Bombay\, he was a researcher at FAIR Labs 
 (Meta). Before that he was a postdoctoral fellow at the Data Science Insti
 tute at Columbia University. He completed his PhD from the CIS Department 
 at University of Pennsylvania\, and masters from CSA Department at IISc Ba
 ngalore where he was the recipient of the Computer Society of India Medal.
 \n
URL:https://www.tcs.tifr.res.in/web/events/1519
DTSTART;TZID=Asia/Kolkata:20250318T160000
DTEND;TZID=Asia/Kolkata:20250318T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR