On the Sample Complexity of Robust Binary Hypothesis Testing

We study the sample complexity of robust binary hypothesis testing under three standard contamination models: varepsilon-additive (Huber), varepsilon-subtractive, and varepsilon-total variation (TV), denoted by n^*Hub(varepsilon), n^*Sub(varepsilon), and n^*TV(varepsilon), respectively. For subtractive contamination, we show that least favourable distributions exist and provide explicit formulas for the same, bringing this model in line with the classical Huber and TV models. Next we show that in all three models, sample complexity may be highly unstable in the contamination parameter varepsilon, increasing by polynomial factors even for o(varepsilon) perturbations. Similarly, there may be polynomial factor gaps between the sample complexities when varepsilon is known exactly versus when it is known up to o(varepsilon) error. Despite the instability of the sample complexity in all models, we show that the sample complexities across models are comparable up to constant-factor rescaling of varepsilon. Specifically, for any fixed δ0>0, the following hold for all distributions p and q: (i) n^*Hub(varepsilon) lesssim n^*TV(varepsilon) lesssim n^*Hub(2varepsilon), (ii) n^*Sub(varepsilon) lesssim n^*TV(varepsilon) lesssim n^*Sub((2+δ0)varepsilon), and (iii) n^*Sub(varepsilon) lesssim n^*Hub(varepsilon) lesssim n^*Sub((1+δ0)varepsilon), and the scaling constants are tight. Finally, we extend our results to adaptive versions of the contamination models.