I have been reading a paper on private learning [1]. In the proof of lemma 3.3. they claim that $$ 2\left(\frac{2e n_\text{pub}}{d}\right)^{2d}e^{-\alpha n_\text{pub}/4} $$ is upper bounded by $\beta$ via standard manipulation when $n_\text{pub}=O\left(\frac{d\log(1/\alpha)+\log(1/\beta)}{\alpha}\right)$, $\alpha, \beta \in (0, 1)$, and $d>0$ is an integer. This step is essential in proving that an algorithm achieves semi-private learning. However, I do not see why this value is upper bounded by $\beta$. Any help as to why this is the case would be greatly appreciated. I have tried setting $n_\text{pub}$ to different values that satisfy $n_\text{pub}=O\left(\frac{d\log(1/\alpha)+\log(1/\beta)}{\alpha}\right)$, but I still can't seem to make it work.

  1. Limits of Private Learning with Access to Public Data by N. Alon et al (2019, 25 Oct)
  • $\begingroup$ Alright @D.W. I have added a better citation of the paper now. $\endgroup$ Commented Oct 23, 2023 at 11:47


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.