Great question! I'll give a short answer and then give a longer answer (using the notation in the paper) that'll help if you want to read the paper in more depth . The short answer: we're computing bounds for each of the moments, and each moment gives you a different bound. We pick the tightest bound, and that might not necessarily be the highest moment, but we try out bounds from up to the 32nd moment to give us a range of bounds. ---------------------------------------------------------------------------------------- Okay, a deeper dive. First the wider context in case you're unfamiliar with moments: there is the whole field of concentration inequalities that I'd encourage you to check out (start with Markov's inequality and Chebyshev's inequality) en.wikipedia.org/wiki/Concentration_inequality From this field, the maths in the DP-SGD paper refers to a specific technique called moment-generating functions to get our bounds. In the paper, the moment generating function is written as α_M(λ). It takes in a number λ and returns the λth moment of the mechanism M's privacy loss distribution. E.g. if I pass in the number 1 to the function it would return the 1st moment. Essentially the "body" of this function α_M(λ) is an expression for the λth moment of our privacy loss distribution. In the paper the authors say the value of α_M(λ) is computed through numerical integration, they also discuss an upper bound under some mixture of two Gaussians. α_M(λ) ≤ q^2 λ(λ + 1)/(1 − q)σ^2 +O(q^3/σ^3) . The details don't matter (they're messy and relegated to the appendix), the point is that it's a general expression involving λ. We take this expression for the λth moment of the privacy loss distribution, from which we can derive a bound on the tail of the distribution (the part where the privacy loss is > ε). In the paper we get this: δ

@@MukulRathi I appreciate your detailed explanation. It's very clear. Thanks a lot! Looking forward to your video about Renyi DP, CDP, zCDP and their relations!

​@@MukulRathi Very nice explanation. Just wondering if you missed λ in the third equation, which I thinks should be ε

Thank you very much!

Awesome, thank you!

Glad you found it useful!

Glad it was helpful!

My pleasure!

Thanks! Yes I will do, I’m currently editing a video on what life as been like as a new software engineer at Facebook :)

Thanks!

linked in the description!

big O() is asymptotic complexity: we're measuring how much the overall loss changes as a function of q, epsilon, T, and big O notation lets us disregard constants. en.wikipedia.org/wiki/Asymptotic_computational_complexity

@Mukul Rathi Very Thanks Mukul ! 🥰 But I still confusing about the detail of compute the each epsilon_i in each step of gradient update. How to use the "Tail Bound" formula of original paper (Theorem 2.) to compute the each epsilon_i in training process?

​@@810602jay the authors use numerical integration to compute α(λ). Then since δ is fixed, we can rearrange the Tail Bound formula to get the value of ε in terms of α(λ) and δ.

@@MukulRathi Very Thanks Again ! 🥰 I try to rearrange the Tail Bound formula. i.imgur.com/Xnfb67h.png But I find there are not involved the training step T in the Tail Bound & the asymptotic bound α(λ) formula. Does that mean I can obtain the total Privacy Loss ε only use q & λ & σ & δ parameters, and without T? I think I was missing some concept because the experiment result shows the privacy loss ε increasing with the epochs (related to training step T) Can you give me a brief example of how to use these two formulas (Tail Bound & the asymptotic bound α(λ)) to obtain the privacy loss ε by when training step=T? Thank you in advance! 🥰 🥰 🥰 You really help me to learn a lot of concepts.

@@810602jay Regarding rearranging the tail bound formula, when we minimise the tail bound with respect to lambda, we try values up to 32 and pick the lambda that gives the smallest value of the expression. This is not necessarily when lambda=32 so you can't substitute 32 into the expression. I re-read the paper and the proofs contained in the appendix of the paper are pretty thorough. I'll try to fill in the gaps as to where the bounds in the proof presented in the appendix come from. The proof for Theorem 1 should fall out by convincing yourself first that α(λ)

It's defined at 4:26, no?

@@MukulRathi Thanks for pointing out. I was confused about privacy loss when looking at 8:45. How is it computed isn't obvious. In 4:26 it talks about probability with D and D'. But in 8:45 we are learning just single theta.

@@viralgupta5630 Hey, so the process of learning theta leaks information about the data we are training on. However, if we add Gaussian noise and clip the gradients (controlled by C, sigma) then we can bound the privacy loss for each gradient descent step. We compute this using the moments accountant. As discussed in 10:24 onwards, the intuition behind the moments accountant technique is that we treat the privacy loss (defined as 4:26) as a random variable and then compute bounds on its distribution - the plot of the distribution at 10:50 gives you an intuition for what epsilon and delta refer to. I'd suggest looking at the paper (+ its appendix) to see the specific bounds and proofs. I deliberately gave a high-level overview in the video as this is an introductory video, however if you look at the replies to the other comments I've gone into the details in response to specific questions about the proofs. I think HengJay's question was similar to yours, so perhaps that response also answers your question.