On the Sample Complexity of Robust Binary Hypothesis Testing

arXiv:2605.24741v1 Announce Type: cross Abstract: We study the sample complexity of robust binary hypothesis testing under three standard contamination models: arepsilon-additive (Huber), arepsilon-subtractive, and arepsilon-total variation (TV), denoted by n^_{Hub}(arepsilon), n^{Sub}(arepsilon), and n^*{TV}(arepsilon), 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 arepsilon, increasing by polynomial factors even for o(arepsilon) perturbations. Similarly, there may be polynomial factor gaps between the sample complexities when arepsilon is known exactly versus when it is known up to o(arepsilon) 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 arepsilon. Specifically, for any fixed elta_0>0, the following hold for all distributions p and q: (i) n^_{Hub}(arepsilon) lesssim n^{TV}(arepsilon) lesssim n^*{Hub}(2arepsilon), (ii) n^_{Sub}(arepsilon) lesssim n^{TV}(arepsilon) lesssim n^*{Sub}((2+elta_0)arepsilon), and (iii) n^_{Sub}(arepsilon) lesssim n^{Hub}(arepsilon) lesssim n^*{Sub}((1+elta_0)arepsilon), and the scaling constants are tight. Finally, we extend our results to adaptive versions of the contamination models.

Source: arXiv cs.LG | 2026-05-26