Privacy Aware Learning

We study statistical risk minimization problems under a privacy model in which the data is kept confidential even from the learner. In this local privacy framework, we establish sharp upper and lower bounds on the convergence rates of statistical estimation procedures. As a consequence, we exhibit a precise tradeoff between the amount of privacy the data preserves and the utility, as -measured by convergence rate, of any statistical estimator or learning procedure. Categories and Subject Descriptors: G.1.6 [Numerical Analysis]: Optimization Convex programming; gradient methods; G.8 [Probability and Statistics]: Nonparametric statistics; H.1.1 [Models and Principles]: Systems and information Theory Information theory; 1.2.6 [Artificial Intelligence]: Learning-Parameter learning; K.4.1 [Computers and Society]: Public Policy issue - Privacy