Statistical Seminar: Every Monday at 2:00 pm.
Time: 2:00 pm – 3:15 pm
Date: 28th of March 2022
Place: Amphi 200

Julien CHHOR et Flore SENTENAC (ENSAE-CREST) – “Robust estimation of discrete distributions under local differential privacy”

Abstract: Although robust learning and local differential privacy are both widely studied fields of research, combining the two settings is an almost unexplored topic. We consider the problem of estimating a discrete distribution in total variation from n contaminated data batches under a local differential privacy constraint. A fraction 1−ϵ of the batches contain k i.i.d. samples drawn from a discrete distribution p over d elements. To protect the users’ privacy, each of the samples is privatized using an α-locally differentially private mechanism.

The remaining ϵn batches are an adversarial contamination. The minimax rate of estimation under contamination alone, with no privacy, is known, up to a √ log(1/ϵ) factor. Under the privacy constraint alone, the minimax rate of estimation is also known. We characterize the minimax estimation rate under the two constraints up to a √ log(1/ϵ) factor, which is larger than the sum of the two separate rates. We provide a polynomial-time algorithm achieving this bound, as well as a matching information theoretic lower bound.

Organizers:
Cristina BUTUCEA (CREST), Alexandre TSYBAKOV (CREST), Karim LOUNICI (CMAP) , Jaouad MOURTADA (CREST)
Sponsors:
CREST-CMAP