  We introduce a new concept, data irrecoverability, and show that the
well-studied concept of data privacy is sufficient but not necessary for data
irrecoverability. We show that there are several regularized loss minimization
problems that can use perturbed data with theoretical guarantees of
generalization, i.e., loss consistency. Our results quantitatively connect the
convergence rates of the learning problems to the impossibility for any
adversary for recovering the original data from perturbed observations. In
addition, we show several examples where the convergence rates with perturbed
data only increase the convergence rates with original data within a constant
factor related to the amount of perturbation, i.e., noise.
