Speaker: |
Eeshan Modak (TIFR) |

Organiser: |
Varun Ramanathan |

Date: |
Friday, 22 Mar 2024, 14:30 to 15:30 |

Venue: |
A-201 (STCS Seminar Room) |

(Scan to add to calendar)

Consider the following problem: Given a set of probability distributions (p_1,p_2) and a sample access to an unknown target distribution p, find which hypothesis (p_1 or p_2) is closer to p in total variation (TV). In general this is not possible. However, we can output a p_i (from p_1 or p_2) such that TV(p_i,p) <= \beta OPT + \epsilon. Here OPT is the TV between p and the best candidate in our set. We will show a simple test for which \beta = 3 (which is in fact optimal). Time permitting, we will also see that if we are allowed to output a distribution not from the set (p_1, p_2), then we can get \beta = 2.