Working under a model of privacy in which data remains private even from the statistician, we study the tradeoff between privacy guarantees and the utility of the resulting statistical estimators. By combining new bounds on certain information-theoretic quantities with standard minimax techniques, we provide a characterization of statistical rates under local privacy constraints, exhibiting a precise tradeoff between the amount of privacy the data preserves and the utility of any statistical estimator or learning procedure. As specific examples, our framework allows a treatment of several canonical problem families: mean estimation, fixed-design regression models, multinomial probability estimation, convex risk minimization, and non-parametric density estimation.
-- Joint work with Michael Jordan and Martin Wainwright --