Nearly-Optimal Private Selection via Gaussian Mechanism

Steinke (2025) 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? We resolve this question positively. In particular, for a candidate set $\mathcal{Y}$, we achieve error guarantee of $\tilde{O}(\log \mathrm{\mid }\mathcal{Y}\mathrm{\mid })$, which is within a factor of $(\log \log \mathrm{\mid }\mathcal{Y}\mathrm{\mid }{)}^{O(1)}$ of the exponential mechanism (McSherry and Talwar, 2007). This improves on Steinke’s mechanism which achieves an error of $O({\log }^{3\mathrm{/}2}\mathrm{\mid }\mathcal{Y}\mathrm{\mid })$.