TY - JOUR

T1 - Geometrizing rates of convergence under local differential privacy constraints

AU - Rohde, Angelika

AU - Steinberger, Lukas

N1 - Publisher Copyright:
© Institute of Mathematical Statistics, 2020

PY - 2020/10

Y1 - 2020/10

N2 - We study the problem of estimating a functional theta(P) of an unknown probability distribution P is an element of P in which the original iid sample X-1,..., X-n is kept private even from the statistician via an alpha-local differential privacy constraint. Let omega TV denote the modulus of continuity of the functional theta over P with respect to total variation distance. For a large class of loss functions l and a fixed privacy level alpha, we prove that the privatized minimax risk is equivalent to l(omega TV(n(-1/2))) to within constants, under regularity conditions that are satisfied, in particular, if theta is linear and P is convex. Our results complement the theory developed by Donoho and Liu (1991) with the nowadays highly relevant case of privatized data. Somewhat surprisingly, the difficulty of the estimation problem in the private case is characterized by omega TV, whereas, it is characterized by the Hellinger modulus of continuity if the original data X-1,..., X-n are available. We also find that for locally private estimation of linear functionals over a convex model a simple sample mean estimator, based on independently and binary privatized observations, always achieves the minimax rate. We further provide a general recipe for choosing the functional parameter in the optimal binary privatization mechanisms and illustrate the general theory in numerous examples. Our theory allows us to quantify the price to be paid for local differential privacy in a large class of estimation problems. This price appears to be highly problem specific.

AB - We study the problem of estimating a functional theta(P) of an unknown probability distribution P is an element of P in which the original iid sample X-1,..., X-n is kept private even from the statistician via an alpha-local differential privacy constraint. Let omega TV denote the modulus of continuity of the functional theta over P with respect to total variation distance. For a large class of loss functions l and a fixed privacy level alpha, we prove that the privatized minimax risk is equivalent to l(omega TV(n(-1/2))) to within constants, under regularity conditions that are satisfied, in particular, if theta is linear and P is convex. Our results complement the theory developed by Donoho and Liu (1991) with the nowadays highly relevant case of privatized data. Somewhat surprisingly, the difficulty of the estimation problem in the private case is characterized by omega TV, whereas, it is characterized by the Hellinger modulus of continuity if the original data X-1,..., X-n are available. We also find that for locally private estimation of linear functionals over a convex model a simple sample mean estimator, based on independently and binary privatized observations, always achieves the minimax rate. We further provide a general recipe for choosing the functional parameter in the optimal binary privatization mechanisms and illustrate the general theory in numerous examples. Our theory allows us to quantify the price to be paid for local differential privacy in a large class of estimation problems. This price appears to be highly problem specific.

KW - Local differential privacy

KW - minimax estimation

KW - moduli of continuity

KW - nonparametric estimation

KW - rate of convergence

KW - Nonparametric estimation

KW - Minimax estimation

KW - Rate of convergence

KW - Moduli of continuity

UR - http://www.scopus.com/inward/record.url?scp=85092301563&partnerID=8YFLogxK

U2 - 10.1214/19-AOS1901

DO - 10.1214/19-AOS1901

M3 - Article

VL - 48

SP - 2646

EP - 2670

JO - Annals of Statistics

JF - Annals of Statistics

SN - 0090-5364

IS - 5

ER -