Differentially Private Learning with Kernels

Prateek Jain, Abhradeep Thakurta
Proceedings of the 30th International Conference on Machine Learning, PMLR 28(3):118-126, 2013.

Abstract

In this paper, we consider the problem of differentially private learning where access to the training features is through a kernel function only. Existing work on this problem is restricted to translation invariant kernels only, where (approximate) training features are available explicitly. In fact, for general class of kernel functions and in general setting of releasing different private predictor (\w^*), the problem is impossible to solve \citeCMS11. In this work, we relax the problem setting into three different easier but practical settings. In our first problem setting, we consider an interactive model where the user sends its test set to a trusted learner who sends back differentially private predictions over the test points. This setting is prevalent in modern online systems like search engines, ad engines etc. In the second model, the learner sends back a differentially private version of the optimal parameter vector \w^* but requires access to a small subset of unlabeled test set beforehand. This also is a practical setting that involves two parties interacting through trusted third party. Our third model is similar to the traditional model, where learner is oblivious to the test set and needs to send a differentially private version of \w^*, but the kernels are restricted to efficiently computable functions over low-dimensional vector spaces. For each of the models, we derive differentially private learning algorithms with provable “utlity” or error bounds. Moreover, we show that our methods can also be applied to the traditional setting of \cite Rubinstein09, CMS11. Here, our sample complexity bounds have only O(d^1/3) dependence on the dimensionality d while existing methods require O(d^1/2) samples to achieve same generalization error.

Cite this Paper

BibTeX
@InProceedings{pmlr-v28-jain13, title = {Differentially Private Learning with Kernels}, author = {Jain, Prateek and Thakurta, Abhradeep}, booktitle = {Proceedings of the 30th International Conference on Machine Learning}, pages = {118--126}, year = {2013}, editor = {Dasgupta, Sanjoy and McAllester, David}, volume = {28}, number = {3}, series = {Proceedings of Machine Learning Research}, address = {Atlanta, Georgia, USA}, month = {17--19 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v28/jain13.pdf}, url = {https://proceedings.mlr.press/v28/jain13.html}, abstract = {In this paper, we consider the problem of differentially private learning where access to the training features is through a kernel function only. Existing work on this problem is restricted to translation invariant kernels only, where (approximate) training features are available explicitly. In fact, for general class of kernel functions and in general setting of releasing different private predictor (\w^*), the problem is impossible to solve \citeCMS11. In this work, we relax the problem setting into three different easier but practical settings. In our first problem setting, we consider an interactive model where the user sends its test set to a trusted learner who sends back differentially private predictions over the test points. This setting is prevalent in modern online systems like search engines, ad engines etc. In the second model, the learner sends back a differentially private version of the optimal parameter vector \w^* but requires access to a small subset of unlabeled test set beforehand. This also is a practical setting that involves two parties interacting through trusted third party. Our third model is similar to the traditional model, where learner is oblivious to the test set and needs to send a differentially private version of \w^*, but the kernels are restricted to efficiently computable functions over low-dimensional vector spaces. For each of the models, we derive differentially private learning algorithms with provable “utlity” or error bounds. Moreover, we show that our methods can also be applied to the traditional setting of \cite Rubinstein09, CMS11. Here, our sample complexity bounds have only O(d^1/3) dependence on the dimensionality d while existing methods require O(d^1/2) samples to achieve same generalization error.} }
Endnote
%0 Conference Paper %T Differentially Private Learning with Kernels %A Prateek Jain %A Abhradeep Thakurta %B Proceedings of the 30th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2013 %E Sanjoy Dasgupta %E David McAllester %F pmlr-v28-jain13 %I PMLR %P 118--126 %U https://proceedings.mlr.press/v28/jain13.html %V 28 %N 3 %X In this paper, we consider the problem of differentially private learning where access to the training features is through a kernel function only. Existing work on this problem is restricted to translation invariant kernels only, where (approximate) training features are available explicitly. In fact, for general class of kernel functions and in general setting of releasing different private predictor (\w^*), the problem is impossible to solve \citeCMS11. In this work, we relax the problem setting into three different easier but practical settings. In our first problem setting, we consider an interactive model where the user sends its test set to a trusted learner who sends back differentially private predictions over the test points. This setting is prevalent in modern online systems like search engines, ad engines etc. In the second model, the learner sends back a differentially private version of the optimal parameter vector \w^* but requires access to a small subset of unlabeled test set beforehand. This also is a practical setting that involves two parties interacting through trusted third party. Our third model is similar to the traditional model, where learner is oblivious to the test set and needs to send a differentially private version of \w^*, but the kernels are restricted to efficiently computable functions over low-dimensional vector spaces. For each of the models, we derive differentially private learning algorithms with provable “utlity” or error bounds. Moreover, we show that our methods can also be applied to the traditional setting of \cite Rubinstein09, CMS11. Here, our sample complexity bounds have only O(d^1/3) dependence on the dimensionality d while existing methods require O(d^1/2) samples to achieve same generalization error.
RIS
TY - CPAPER TI - Differentially Private Learning with Kernels AU - Prateek Jain AU - Abhradeep Thakurta BT - Proceedings of the 30th International Conference on Machine Learning DA - 2013/05/26 ED - Sanjoy Dasgupta ED - David McAllester ID - pmlr-v28-jain13 PB - PMLR DP - Proceedings of Machine Learning Research VL - 28 IS - 3 SP - 118 EP - 126 L1 - http://proceedings.mlr.press/v28/jain13.pdf UR - https://proceedings.mlr.press/v28/jain13.html AB - In this paper, we consider the problem of differentially private learning where access to the training features is through a kernel function only. Existing work on this problem is restricted to translation invariant kernels only, where (approximate) training features are available explicitly. In fact, for general class of kernel functions and in general setting of releasing different private predictor (\w^*), the problem is impossible to solve \citeCMS11. In this work, we relax the problem setting into three different easier but practical settings. In our first problem setting, we consider an interactive model where the user sends its test set to a trusted learner who sends back differentially private predictions over the test points. This setting is prevalent in modern online systems like search engines, ad engines etc. In the second model, the learner sends back a differentially private version of the optimal parameter vector \w^* but requires access to a small subset of unlabeled test set beforehand. This also is a practical setting that involves two parties interacting through trusted third party. Our third model is similar to the traditional model, where learner is oblivious to the test set and needs to send a differentially private version of \w^*, but the kernels are restricted to efficiently computable functions over low-dimensional vector spaces. For each of the models, we derive differentially private learning algorithms with provable “utlity” or error bounds. Moreover, we show that our methods can also be applied to the traditional setting of \cite Rubinstein09, CMS11. Here, our sample complexity bounds have only O(d^1/3) dependence on the dimensionality d while existing methods require O(d^1/2) samples to achieve same generalization error. ER -
APA
Jain, P. & Thakurta, A.. (2013). Differentially Private Learning with Kernels. Proceedings of the 30th International Conference on Machine Learning, in Proceedings of Machine Learning Research 28(3):118-126 Available from https://proceedings.mlr.press/v28/jain13.html.

Related Material