Problems regarding the proof of Lemma 3.1 and Theorem 3.1.

[SunYatong]

Dear authors,

I wanted to reach out and let you know that I found your works on negative sampling for recommender systems incredibly helpful for my own research on the same topic. However, I did encounter two issues while reading this paper, and I'd be grateful if you could provide some clarification on them.

Firstly, in the proof of Lemma 3.1, I had some trouble understanding the meaning of P'. It seems that P' is not a probability distribution over items, given that 1/p_i can be greater than 1. Yet, the set of items J is still sampled from P' as if it were a distribution. I'd be grateful if you could elaborate on the definition of P'.

Secondly, I noticed that the highlighted pop(i) should perhaps be replaced with pop(j)? Additionally, I was unable to deduce how pop(j) or pop(j) could be converted into |B|/|D|. I would appreciate any clarification you could provide on this point as well.

Thank you very much for your time, and I eagerly await your response.

Best regards, Yatong

[HERECJ]

Thank you for your attention.

1. [Lemma 1] I apologize for the un-normalization of the distribution error.
   Actually, the probability of P' w.r.t. item i p'(i) \approx \frac{1}{p(1)}. We implement it through the ''torch.multinomial'', which automatically normalizes the probability.

2. [Theorem 1] Thank you for pointing out that the 'pop(i)' should be 'pop(j)'. You are right. As for the \frac{|B|}{|D|}, with the P' distribution, the mini-batch items can be treated as uniformly sampled items from the whole item set.

   Thank you again for your attention. Hope this will help you.

[SunYatong]

Thank you so much for your response and detailed explanation.

I have no further problems with Lemma A.1.

But for the second question, after correcting pop(i) into pop(j), I still don't get why these two red rectangles are approximately equivalent: