Title: Locally private non-asymptotic testing of discrete distributions is faster using interactive mechanisms
Authors: Thomas Berrett - University of Warwick (United Kingdom) [presenting]
Cristina Butucea - CREST, ENSAE, IP Paris (France)
Abstract: Recent work on hypothesis testing under local differential privacy is presented. We find separation rates for testing multinomial or more general discrete distributions under the LDP constraint. The upper bounds are established by constructing efficient randomized algorithms and test procedures, in both the case where only non-interactive privacy mechanisms are allowed and also in the case where all sequentially interactive privacy mechanisms are allowed. We find that the separation rates are faster in the latter case. The lower bounds are based on general information theoretical bounds that allow us to establish the optimality of our algorithms among all pairs of privacy mechanisms and test procedures, in most usual cases. Considered examples include testing uniform, polynomially and exponentially decreasing distributions.