BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Engineering Systems and Design (ESD)//NONSGML Events//EN
CALSCALE:GREGORIAN
X-WR-CALNAME:Engineering Systems and Design (ESD) - Events
X-ORIGINAL-URL:https://esd.sutd.edu.sg/news-events/event/
X-WR-CALDESC:Engineering Systems and Design (ESD) - Events
BEGIN:VEVENT
UID:20210914T0239Z-1631587189.2855-EO-25770-1@10.1.1.165
STATUS:CONFIRMED
DTSTAMP:20211021T140735Z
CREATED:20210914T022726Z
LAST-MODIFIED:20210915T021212Z
DTSTART;TZID=Asia/Singapore:20210921T160000
DTEND;TZID=Asia/Singapore:20210921T170000
SUMMARY: Vincent Y.F. Tan (National University of Singapore) – Probabilisti
c Sequential Shrinking: A Best Arm Identification Algorithm for Stochastic
Bandits with Corruptions
DESCRIPTION: We consider a best arm identification (BAI) problem for stocha
stic bandits with adversarial corruptions in the fixed-budget setting of T
steps. We design a randomized algorithm\, Probabilistic Sequential Shrinkin
g(u) (PSS(u)). When the amount of corruption per step (CPS) is below a thre
shold\, PSS(u) identifies the best arm with probability tending to 1 as T g
rows.
X-ALT-DESC;FMTTYPE=text/html: #### Probabilistic Sequential Shrinking: A Bes
t Arm Identification Algorithm for Stochastic Bandits with Corruptions

Sep 21\, 2021 04:00 PM Singapore (**Registration will open at 03:50 PM.**)

Join Zoom Meeting:

https://sutd-edu.zoom.us/j/95872191837?pwd=OXZ6MDdVWlVYNmdEQUNYbzZpcW9
0UT09

**Meeting ID:** 958 7219 1837

**Pas
scode:** 4%Y.+Z2k

#### Abstract

We consider a best arm iden
tification (BAI) problem for stochastic bandits with adversarial corruption
s in the fixed-budget setting of T steps. We design a randomized algorithm\
, Probabilistic Sequential Shrinking(u) (PSS(u)). When the amount of corrup
tion per step (CPS) is below a threshold\, PSS(u) identifies the best arm w
ith probability tending to 1 as T grows. Otherwise\, the optimality gap of
the identified item degrades gracefully with the CPS. We argue that such a
bifurcation is necessary. The injection of randomization is shown to be ess
ential to mitigate the impact of corruption. To demonstrate this\, we desig
n two attack strategies. We apply them to a deterministic analogue of PSS(u
) known as Successive Halving (SH). The attack strategy results in a high f
ailure probability for SH\, but PSS(u) remains robust. We show that when th
e CPS is sufficiently large\, no algorithm can achieve a BAI probability te
nding to 1 as T grows.

The paper can be found at: http:
//proceedings.mlr.press/v139/zhong21a.html

#### About the Speaker

Vincent Y. F. Tan is currently a Dean’s Chair Associate Professor in th
e Department of Electrical and Computer Engineering (ECE) and the Departmen
t of Mathematics at the National University of Singapore (NUS). He received
the B.A. and M.Eng. degrees in Electrical and Information Sciences from Ca
mbridge University in 2005 and the Ph.D. degree in Electrical Engineering a
nd Computer Science (EECS) from the Massachusetts Institute of Technology i
n 2011. His research interests include network information theory\, machine
learning\, and statistical signal processing. He is currently an Editor of
the IEEE Transactions on Signal Processing and the IEEE Transactions on In
formation Theory.

*For more information about the ESD Seminar\, pl
ease email esd_invite@sutd.edu.sg*

CATEGORIES:ESD Research Seminar Series,Special Seminars
ORGANIZER;CN="SUTDPillarAdministrator":MAILTO:pillar-webmaster@sutd.edu.sg
URL;VALUE=URI:https://esd.sutd.edu.sg/news-events/research-seminar-series/v
incent-tan-national-university-of-singapore-probabilistic-sequential-shrink
ing-a-best-arm-identification-algorithm-for-stochastic-bandits-with-corrupt
ions/
END:VEVENT
BEGIN:VTIMEZONE
TZID:Asia/Singapore
BEGIN:STANDARD
TZOFFSETFROM:+0800
TZOFFSETTO:+0800
DTSTART:20210322T200000
TZNAME:SGT
END:STANDARD
END:VTIMEZONE
END:VCALENDAR