Re: [theory students] Theory Seminar Nov 12: "How fast can you find a good hypothesis" by Anders Aamand (University of Copenhagen) and Justin Chen (MIT)

[Sandeep Silwal <silwal@xxxxxxxxxxx>]

Happening today! See you at 2:30 pm in Morgridge 3610!

On Nov 11, 2025, at 8:08âAM, Sandeep Silwal <silwal@xxxxxxxxxxx> wrote:

Hi everyone

Just a reminder about tomorrowâs talk! I realized some interested people may not be in the mailing list so here are also instructions about how to join! Please sign up at https://lists.cs.wisc.edu/mailman/listinfo/theory-seminar if you are interested. 

If you would like to meet with the speakers, please sign up here (https://docs.google.com/spreadsheets/d/1QB_6IxmT5pNlj_5BkCNJgP5jab4_olmj8UZFKOkZU2g/edit?gid=0#gid=0).

Details: Wed Nov 12 at 2:30-3:30pm, Morgridge Hall  3610 

Title: How fast can you find a good hypothesis? 

Abstract: In the hypothesis selection problem, we are given a finite set of candidate distributions (hypotheses), H_1, . . . , H_n, and samples from an unknown distribution P. Our goal is to find a hypothesis H_i whose total variation distance to P is comparable to that of the nearest hypothesis in H. Specifically, if the minimum distance is OPT, we aim to output an H_i such that, with probability at least 1 â Î, its total variation distance to P is at most C Â OPT + Î. Key aspects of this problem remain unresolved, especially regarding the computational efficiency of statistically optimal hypothesis selection. In this talk, we will highlight recent progress on two questions: (a) Does there exists an algorithm that simultaneously runs in near-linear time, achieves the best possible approximation factor, and succeeds with high probability? Intriguingly, such algorithms exist if we relax any one of these criteria. (b) Can the approximation factor be improved in expectation (similarly, if we are allowed to output a mixture of the hypotheses)? This question is closely related to the challenge of achieving the optimal approximation for improper hypothesis selection in finite time on real-valued domains. This talk is based joint work by Anders Aamand, Maryam Aliakbarpour, Justin Y. Chen, and Sandeep Silwal.

Thanks!

Sandeep

On Nov 9, 2025, at 8:06âAM, Sandeep Silwal <silwal@xxxxxxxxxxx> wrote:

Hi everyone,

This week we have two visitors giving a joint talk on Wednesday, Nov 12! The visitors are Anders Aamand (University of Copenhagen) and Justin Chen (MIT). If you would like to meet with them, please sign up here (https://docs.google.com/spreadsheets/d/1QB_6IxmT5pNlj_5BkCNJgP5jab4_olmj8UZFKOkZU2g/edit?gid=0#gid=0).

Details: Wed Nov 12 at 2:30-3:30pm, Morgridge Hall  3610 

Title: How fast can you find a good hypothesis? 

Abstract: In the hypothesis selection problem, we are given a finite set of candidate distributions (hypotheses), H_1, . . . , H_n, and samples from an unknown distribution P. Our goal is to find a hypothesis H_i whose total variation distance to P is comparable to that of the nearest hypothesis in H. Specifically, if the minimum distance is OPT, we aim to output an H_i such that, with probability at least 1 â Î, its total variation distance to P is at most C Â OPT + Î. Key aspects of this problem remain unresolved, especially regarding the computational efficiency of statistically optimal hypothesis selection. In this talk, we will highlight recent progress on two questions: (a) Does there exists an algorithm that simultaneously runs in near-linear time, achieves the best possible approximation factor, and succeeds with high probability? Intriguingly, such algorithms exist if we relax any one of these criteria. (b) Can the approximation factor be improved in expectation (similarly, if we are allowed to output a mixture of the hypotheses)? This question is closely related to the challenge of achieving the optimal approximation for improper hypothesis selection in finite time on real-valued domains. This talk is based joint work by Anders Aamand, Maryam Aliakbarpour, Justin Y. Chen, and Sandeep Silwal.

See you there!

Sandeep