Differentially Private Learning with Kernels

In this paper, we consider the problem of differentially private learning where access to the training features is through a kernel function only. As mentioned in \citet{CMS11}, the problem seems to be intractable for general kernel functions in the standard learning model of releasing different private predictor.We study this problem in three simpler but practical settings. We first study an interactive model where the user sends its test points to a {\em trusted learner} (like search engines) and expects accurate but differentially private predictions. In the second model, the learner has access to a subset of the unlabeled test set using which it releases a predictor, which preserves privacy of the training data. \cite{HapMap} is an example of such publicly available test set.

Our third model is similar to the traditional model, where learner is oblivious to the test set but the kernels are restricted to functions over vector spaces. For each of the models, we derive differentially private learning algorithms with provable «utility» or error bounds. Moreover, we show that our methods can also be applied to the traditional model where they demonstrate better dimensionality dependence when compared to the methods of \cite{ Rubinstein09, CMS11}. Finally, we provide experimental validation of our methods.