Learning in a Large Function Space: Privacy-Preserving Mechanisms for SVM Learning

Details Learning in a Large Function Space: Privacy-Preserving Mechanisms for SVM Learning Learning in a Large Function Space: Privacy-Preserving Mechanisms for SVM Learning

2009-11-30

arxiv.org/abs/0911.5708v1

Computer Science

Learning

21 pages, 1 figure

Scientific paper

Several recent studies in privacy-preserving learning have considered the trade-off between utility or risk and the level of differential privacy guaranteed by mechanisms for statistical query processing. In this paper we study this trade-off in private Support Vector Machine (SVM) learning. We present two efficient mechanisms, one for the case of finite-dimensional feature mappings and one for potentially infinite-dimensional feature mappings with translation-invariant kernels. For the case of translation-invariant kernels, the proposed mechanism minimizes regularized empirical risk in a random Reproducing Kernel Hilbert Space whose kernel uniformly approximates the desired kernel with high probability. This technique, borrowed from large-scale learning, allows the mechanism to respond with a finite encoding of the classifier, even when the function class is of infinite VC dimension. Differential privacy is established using a proof technique from algorithmic stability. Utility--the mechanism's response function is pointwise epsilon-close to non-private SVM with probability 1-delta--is proven by appealing to the smoothness of regularized empirical risk minimization with respect to small perturbations to the feature mapping. We conclude with a lower bound on the optimal differential privacy of the SVM. This negative result states that for any delta, no mechanism can be simultaneously (epsilon,delta)-useful and beta-differentially private for small epsilon and small beta.

Affiliated with

Also associated with

No associations

Rating

Learning in a Large Function Space: Privacy-Preserving Mechanisms for SVM Learning does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Learning in a Large Function Space: Privacy-Preserving Mechanisms for SVM Learning, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Learning in a Large Function Space: Privacy-Preserving Mechanisms for SVM Learning will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-444178