2

From this link on Differential Privacy, the L-2 sensitivity is defined as follows:

enter image description here

Question:

Here's my understanding of the above equation:

  • Make a set of D' data sets such that D' is same as D except it has an absence of a one row. For each D', calculate the given L-2 norm and return the maximum L-2 norm.

In pseudo-code.

REQUIRE: D
INITIALIZE empty list: norms
FOR each row in D:
    1. Define D` such that D` is the same as D except it doesn't have "row" in it
    2. Calculate norm = ||f(D) - f(D')||_2 
    3. Store the norm in norms 
RETURN max value in norms
  1. Is my understanding correct?

Background:

For a machine learning task, I'm trying to perform differentially private gradient descent optimization on a data set D by adding noise to the gradient.

In order to add Gaussian noise to the gradient, I need to calculate the L-2 sensitivity first. In my case, f is a vector-valued function (gradient), but I think there's no issue with the definition here.

Related SO question on implementation

  • @ Rory Alsop I'm not sure the reason to mark this as off topic, my best guess is that you've seen this as a programming question - whereas this is not, this is asking about a specific definition in differential privacy. I hope specific questions on differential privacy are not off topic here; see: what is differential privacy? and Real-world applications of Differential Privacy? are allowed although open ended. – akilat90 Mar 31 at 7:33
  • The question you asked is not about privacy, though. It is either a pure programming question (how to implement the function in code) or a programming efficiency question (computationally feasible). The questions you linked are not open-ended even though they are conceptual. – schroeder Mar 31 at 9:21
  • 1
    @schroeder I want to ask "What is the definition of L-2 sensitivity?" I want to know what is written in that equation in plain English. I haven't intended this to be either a pure programming question or a computational feasibility question. I've written a pseudo-code because that conveys my understanding in an easy to understand way. I have added a plain English description to the top and removed the computational feasibility mentions, if that makes any difference. – akilat90 Mar 31 at 10:01

Browse other questions tagged or ask your own question.