3 ms·

I've wondered before about whether Taylor series can allow one to impose the non-linearities of a NN on homomorphically encrypted data, but I've never been quit

I've wondered before about whether Taylor series can allow one to impose the non-linearities of a NN on homomorphically encrypted data, but I've never been quite convinced. I work with deep learning, but I'm certainly no expert on homomorphic encryption, so hopefully someone here who knows more can tell me whether this is valid or not. The reason the Taylor series argument makes me uncomfortable is that pretty much any function can be written as a Taylor series. But my understanding is that homomorphic encryption only works for a very specific set of functions. In a little more detail, if you're computing tanh(x), the unencrypted number needs only the first few terms of the Taylor series. But I could imagine that to get the decrypted number back, you actually need many terms of the Taylor series, because if you're off by even a little bit, you could end up with a very different answer after decryption. To put it a little more formally, if we have that y = encrypt(x) tanh(x) \approx x - x^3 / 3 + 2 x^5 / 15, tanh(y) \approx y - y^3 / 3 + 2 y^5 / 15, and tanh(x) = decrypt(tanh(y)), but it doesn't necessarily follow to me that tanh(x) \approx decrypt(y - y^3 + 2 y^5 / 15) Is this worry unfounded? I suppose if you have a limited number of decimal places and you can guarantee that your Taylor approximation is valid to that precision then this wouldn't be a problem.

williamtrask 10y ago
So the good news is that individual neuron activations often stay within a relatively narrow range. I think empirical evaluation is really needed to be able to tell how robustly this approach works. I think that that is certainly the greatest source of noise during training (and the first thing to break if you choose unstable hyperparameters). Great comment.
Y_Y 10y ago
I had a similar objection reading the article. If you take a look at [0] they go into a bit more detail. Briefly, you can distribute your decrypt function over the additions and multiplications by homomorphism and then bound the error, then you can judiciously choose your weighting to compensate. [0] https://courses.csail.mit.edu/6.857/2015/files/yu-lai-payor.pdf https://courses.csail.mit.edu/6.857/2015/files/yu-lai-payor....
KirinDave 10y ago
On the plus side, very small changes in the input to tanh already have surprising results due to the outright wackiness of IEE754.
quotelisp 10y ago
Perhaps you are thinking about the conditional number of a matrix or more simple for f(x) a function with derivative f' the inverse g(x) has derivative g'(x)= 1/f'(g(x)), so using an encoding with a function with little variability means that recovering the original from the encoded value is not robust, any small error is amplied. The condition number of a matrix is a way to measure the difficulty of solving a linear problem. For a non linear problem one usually apply the above using a linear approximation near a point, so you have the jacobian matrix and the condition number of the jacobian matrix is a good measure of the difficulty of recovering a value encoded when there are errors, obviously one way to enhance the precision is to use redundancy or error recovery techniques.

williamtrask 10y ago

So the good news is that individual neuron activations often stay within a relatively narrow range. I think empirical evaluation is really needed to be able to tell how robustly this approach works. I think that that is certainly the greatest source of noise during training (and the first thing to break if you choose unstable hyperparameters). Great comment.

Y_Y 10y ago

I had a similar objection reading the article. If you take a look at [0] they go into a bit more detail. Briefly, you can distribute your decrypt function over the additions and multiplications by homomorphism and then bound the error, then you can judiciously choose your weighting to compensate. [0] https://courses.csail.mit.edu/6.857/2015/files/yu-lai-payor.pdf https://courses.csail.mit.edu/6.857/2015/files/yu-lai-payor....

KirinDave 10y ago

On the plus side, very small changes in the input to tanh already have surprising results due to the outright wackiness of IEE754.

quotelisp 10y ago

Perhaps you are thinking about the conditional number of a matrix or more simple for f(x) a function with derivative f' the inverse g(x) has derivative g'(x)= 1/f'(g(x)), so using an encoding with a function with little variability means that recovering the original from the encoded value is not robust, any small error is amplied. The condition number of a matrix is a way to measure the difficulty of solving a linear problem. For a non linear problem one usually apply the above using a linear approximation near a point, so you have the jacobian matrix and the condition number of the jacobian matrix is a good measure of the difficulty of recovering a value encoded when there are errors, obviously one way to enhance the precision is to use redundancy or error recovery techniques.