Visit
Mon 11/29

Seminar @ Cornell Tech: Kyra Gan

Toward a Liquid Biopsy: Greedy Approximation Algorithms for Active Sequential Hypothesis Testing

This work addresses a set of problems that occur in the development of liquid biopsies via the lens of active sequential hypothesis testing (ASHT). In the problem of 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.

The goal is to sequentially select the fewest number of actions so as to identify the true hypothesis with sufficiently high probability. 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.

Speaker Bio

I am a fifth-year Ph.D. candidate in Operations Research at Tepper School of Business, Carnegie Mellon University. My advisors are Prof. Sridhar Tayur and Prof. Andrew Li. I also work closely with Prof. Zachary Lipton and Prof. Alan Scheller-Wolf, and I am part of the ACMI lab. Prior to joining CMU, I received my BA degrees in Mathematics (with the Ann Kirsten Pokora Prize) and Economics from Smith College in May 2017. I completed my first year of college at UCSD in June 2014. In general, I am interested in solving real-world medical problems. Specifically, I am interested in efficient algorithms in precision medicine, and my work lies in the intersection of optimization, machine learning, and medicine.