4 ms·

One very interesting thing about differential privacy is its connection to generalizability in machine learning. In particular, a model can only provide differe

One very interesting thing about differential privacy is its connection to generalizability in machine learning. In particular, a model can only provide differential privacy if that model is completely generalizable. Generalizability is the ability of a model to do well on data outside its training set. Non generalized models violate differential privacy because you can find out if someone is in the training set by simply measuring the error rate on that person. A low error rate provides evidence that that particular person was in the training set. This connection is interesting because it implies that differential privacy techniques applied to machine learning must in turn result in more generalizable models, which is very useful in general. This can also provide a simple "upper bound" on how differentialy private your model is. Simply compare the performance on the training and test set and see how much it differs.

maksimum 9y ago
> This can also provide a simple "upper bound" on how differentialy private your model is. This is a very interesting idea. Are you aware of any resources that go through the mechanics?
- frankmcsherry 9y ago
  I think what they are getting at is the following, which isn't a proof or anything (if you are looking for rules to follow, the much simpler "your model isn't differentially private" is probably even more accurate): Let X be a set of iid samples drawn from a distribution D, let M be a model trained with eps-DP on the set X, and let x' be a fresh sample from D. Let's think about the random variable M(x'), which represents your test loss or whatever. Differential privacy says that the density of this random variable is pointwise within a factor of exp(eps) of M'(x') where M' is the random model resulting from training on X \cup { x' }. But M'(x') is distributed per a random x', random X, and M' trained on both just like your training loss or whatever. You can push linearity of expectations through all of this to show that your expected loss on test and training should vary by at most a factor of exp(eps), but I'm not aware of a pointwise test for a specific model (and it may not make sense, as DP isn't a property of specific models, but rather distributions of them). Edit: you can read a bit more about a special case of this at https://windowsontheory.org/2014/02/04/differential-privacy-for-measure-concentration/ https://windowsontheory.org/2014/02/04/differential-privacy-...
  - maksimum 9y ago
    Thanks, using DP to bound deviations of arbitrary functions of a model is a neat idea. I wonder if it it makes sense going from generalization error to an estimate of something similar in spirit to (but not as strong as) differential privacy, as the top-level comment suggested? For example I want to empirically argue that a particular function of my GMM, let's say the log-likelihood of x_i, is "private." To do so I form C iid train/test splits. For each split I estimate the density of the likelihood for train and test samples, and estimate an upper bound on their ratio. As a result I get C samples of epsilon, and I can use some kind of simple bound (Chebyshev?) on the probability of epsilon being within an interval. The idea is that we already have some "privacy" [1] from the data-sampling distribution. So we don't necessarily need to add noise to our algorithm. And it would be interesting to measure this privacy (at least for a particular function of the model) empirically. [1] http://ieeexplore.ieee.org/abstract/document/6686180/ http://ieeexplore.ieee.org/abstract/document/6686180/
gidim 9y ago
> you can find out if someone is in the training set by simply measuring the error rate on that person. I don't think it's that easy to detect if a sample exists in the training set. Error rate are usually informative when measured across multiple predictions. With a single prediction you're most likely looking at the estimated probability / confidence (with Logistic Regression for example). In that case models might assign high probability to unseen inputs as well.
mehrdadn 9y ago
> This connection is interesting because it implies that differential privacy techniques applied to machine learning must in turn result in more generalizable models, which is very useful in general. I'm confused. Wouldn't a model that produces completely random results be differentially private but not generalizable? Or is giving more random results considered generalization?
- lmkg 9y ago
  Technically, the output quality of a completely random model stays the same when you try to generalize. It wasn't actually good to begin with, but it doesn't get worse.
  - mehrdadn 9y ago
    Ahh right, makes sense, thanks. :)
deleted 9y ago
[deleted]
jaster 9y ago
Fun coincidence (or maybe not?), I just stumbled upon the following paper on arvix titled "Differentially Private Generative Adversarial Network" https://arxiv.org/pdf/1802.06739v1.pdf https://arxiv.org/pdf/1802.06739v1.pdf Its Related Work section also references some works on "differentially private learning in neural network". While the paper does not discuss directly OP remark about how differential privacy could help generality in machine learning, it shows that at least some connections exist between the domains.

maksimum 9y ago

> This can also provide a simple "upper bound" on how differentialy private your model is. This is a very interesting idea. Are you aware of any resources that go through the mechanics?

frankmcsherry 9y ago
I think what they are getting at is the following, which isn't a proof or anything (if you are looking for rules to follow, the much simpler "your model isn't differentially private" is probably even more accurate): Let X be a set of iid samples drawn from a distribution D, let M be a model trained with eps-DP on the set X, and let x' be a fresh sample from D. Let's think about the random variable M(x'), which represents your test loss or whatever. Differential privacy says that the density of this random variable is pointwise within a factor of exp(eps) of M'(x') where M' is the random model resulting from training on X \cup { x' }. But M'(x') is distributed per a random x', random X, and M' trained on both just like your training loss or whatever. You can push linearity of expectations through all of this to show that your expected loss on test and training should vary by at most a factor of exp(eps), but I'm not aware of a pointwise test for a specific model (and it may not make sense, as DP isn't a property of specific models, but rather distributions of them). Edit: you can read a bit more about a special case of this at https://windowsontheory.org/2014/02/04/differential-privacy-for-measure-concentration/ https://windowsontheory.org/2014/02/04/differential-privacy-...
- maksimum 9y ago
  Thanks, using DP to bound deviations of arbitrary functions of a model is a neat idea. I wonder if it it makes sense going from generalization error to an estimate of something similar in spirit to (but not as strong as) differential privacy, as the top-level comment suggested? For example I want to empirically argue that a particular function of my GMM, let's say the log-likelihood of x_i, is "private." To do so I form C iid train/test splits. For each split I estimate the density of the likelihood for train and test samples, and estimate an upper bound on their ratio. As a result I get C samples of epsilon, and I can use some kind of simple bound (Chebyshev?) on the probability of epsilon being within an interval. The idea is that we already have some "privacy" [1] from the data-sampling distribution. So we don't necessarily need to add noise to our algorithm. And it would be interesting to measure this privacy (at least for a particular function of the model) empirically. [1] http://ieeexplore.ieee.org/abstract/document/6686180/ http://ieeexplore.ieee.org/abstract/document/6686180/

gidim 9y ago

> you can find out if someone is in the training set by simply measuring the error rate on that person. I don't think it's that easy to detect if a sample exists in the training set. Error rate are usually informative when measured across multiple predictions. With a single prediction you're most likely looking at the estimated probability / confidence (with Logistic Regression for example). In that case models might assign high probability to unseen inputs as well.

mehrdadn 9y ago

> This connection is interesting because it implies that differential privacy techniques applied to machine learning must in turn result in more generalizable models, which is very useful in general. I'm confused. Wouldn't a model that produces completely random results be differentially private but not generalizable? Or is giving more random results considered generalization?

lmkg 9y ago
Technically, the output quality of a completely random model stays the same when you try to generalize. It wasn't actually good to begin with, but it doesn't get worse.
- mehrdadn 9y ago
  Ahh right, makes sense, thanks. :)

deleted 9y ago

[deleted]

jaster 9y ago

Fun coincidence (or maybe not?), I just stumbled upon the following paper on arvix titled "Differentially Private Generative Adversarial Network" https://arxiv.org/pdf/1802.06739v1.pdf https://arxiv.org/pdf/1802.06739v1.pdf Its Related Work section also references some works on "differentially private learning in neural network". While the paper does not discuss directly OP remark about how differential privacy could help generality in machine learning, it shows that at least some connections exist between the domains.