Our upcoming event for the Statistics Department Colloquium Series is scheduled for this Monday, October 31st from 12:00 – 1:00pm (ET) and will be an in-person presentation Science Center Rm. 316. The speaker will be Kyra Gan who is a current postdoc in Statistical Reinforcement Learning lab with Susan Murphy at Harvard University. She is joining Cornell Tech as an Assistant Professor in ORIE starting July 2023.
Title: Greedy Approximation Algorithms for Active Sequential Hypothesis Testing
Abstract: In the problem of active sequential hypothesis testing (ASHT), a learner seeks to identify the true hypothesis from among a known set of hypotheses. The learner is given a set of actions and knows the random distribution of the outcome of any action under any true hypothesis. Given a target error δ>0, the goal is to sequentially select the fewest number of actions so as to identify the true hypothesis with probability at least 1 - δ. Motivated by applications in which the number of hypotheses or actions is massive (e.g., genomics-based cancer detection), we propose efficient (greedy, in fact) algorithms and provide the first approximation guarantees for ASHT, under two types of adaptivity. Both of our guarantees are independent of the number of actions and logarithmic in the number of hypotheses. We numerically evaluate the performance of our algorithms using both synthetic and real-world DNA mutation data, demonstrating that our algorithms outperform previously proposed heuristic policies by large margins.
LOCATION:Science Center, Room 316 STATUS:CONFIRMED DTSTART:20221031T160000Z DTEND:20221031T170000Z END:VEVENT END:VCALENDAR