Nearly-Optimal Private Selection via Gaussian Mechanism

Steinke [Ste25] recently asked the following intriguing open question: Can we solve the differentially private selection problem with nearly-optimal error by only (adaptively) invoking Gaussian mechanism on low-sensitivity queries? In this short note, we resolve this question positively. In particular, for a candidate set Y, we achieve error guarantee of O ̃ (log |Y|), which is within a factor of (log log |Y|)^O(1) of the exponential mechanism [MT07]. This improves on Steinke’s mechanism which achieves an error of O(log^{3/2} |Y|).