Before revision:  Thus the privacy penalty is \mathcal{O \Theta (m) times smaller compared to the standard mechanisms  .
After revision:  Thus the privacy penalty is \mathcal{O \Theta (m) times smaller compared to the standard mechanisms in certain settings of interest. We further show that the proposed mechanism is nearly-optimal under certain regimes .