A Chernoff-Stein Lemma for adversarial hypothesis testing

Eeshan Modak
Agniv Bandyopadhyay
Friday, 17 Feb 2023, 16:00 to 17:00
In the composite hypothesis testing setting, the detector receives n i.i.d. samples either from a distribution  p∈P or from a distribution q∈Q. It then decides the correct set from which the samples were drawn.
Brandao, Harrow, Lee and Peres [BHLP] considered an adaptive generalization of this problem where the choice of p∈P and q∈Q can change in each sample in some way that depends arbitrarily on the previous samples. Initially, one might think that this might confuse the detector and worsen the optimal error exponent. But, [BHLP] showed that the exponent remains the same and a simple maximum likelihood ratio test achieves it.
Link to the paper: https://arxiv.org/abs/1308.6702