Styjun

I'm implementing L-2 sensitivity for a data set and a function f. From this link on Differential Privacy, the L-2 sensitivity is defined as follows:

I'm looking to incorporate this to make my gradient calculation in training an ML model differentially private.

In my context, D is a vector like this: X = np.random.randn(100, 10)

D' is defined to be the subset of D that has only a one row missing from D, for example X_ = np.delete(X, 0, 0)

f is the gradient vector (even though the definition says f is a real valued function). In my case f(x) evaluates to be f(D)like:

grad_fx = (1/X.shape[0])*(((1/(1+np.exp(-(y * (X @ b.T))))) - 1) * (y * X)).sum(axis=0)

where:

y = np.random.randn(100, 1)
b = np.random.randn(1, 10)

If my understanding of the definition is correct, I have to evaulate the 2-norm of f(D) - f(D') for all possible D' arrays and get the minimum.

Here's my implementation (I tried to accelerate with numba.jit and hence the usage of limited numpy functionality):

def l2_sensitivity(X, y, b):

 norms = [] 
 for i in range(X.shape[0]):
 # making the neigboring dataset X'
 X_ = np.delete(X, i, 0)
 y_ = np.delete(X, i, 0)
 # calculate l2-norm of f(X)-f(X')
 grad_fx =(1/X.shape[0])*(((1/(1+np.exp(-(y * (X @ b.T))))) - 1) * (y * X)).sum(axis=0)
 grad_fx_ =(1/X_.shape[0])*(((1/(1+np.exp(-(y_ * (X_ @ b.T))))) - 1) * (y_ * X_)).sum(axis=0)
 grad_diff = grad_fx - grad_fx_
 norm = np.sqrt((grad_diff**2).sum())
 #norm = np.linalg.norm(compute_gradient(b, X, y) - compute_gradient(b,X_,y_))
 norms.append(norm)
 norms = np.array(norms)

 return norms.min() 

Question:

The function call l2_sensitivity(X, y, b) takes a lot of time to run. How can I speed this up - -perhaps using numba or JAX?

I just started studying this, but I don't think you need to do the full gradient calculation every time because the summations over D and D' differ by only the kth observation (row). I posted the derivation in this forum b/c I don't have rep for images, here: https://security.stackexchange.com/a/206453/203228
Here is an example implementation

norms = []
B = np.random.rand(num_features) #choice of B is arbitrary
Y = labels #vector of classification labels of height n
X = observations #data matrix of shape nXnum_features
for i in range(0,len(X)):
 A = Y[i]*(np.dot(B.T,X[i])) 
 S = sigmoid(A) - 1 
 C = Y[i]*X[i] 
 norms.append(np.linalg.norm(S*C,ord=2))
sensitivity = max(norms) - min(norms)