Nearly-Optimal Private Selection via Gaussian Mechanism

2025/11/10 by Leeman, Ethan, Manurangsi, Pasin
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Auction Theory and Applications #Cryptography and Data Security #Cryptography and Security (cs.CR) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2511.06871

openalex publication_date 2025/11/10 · openalex created_date 2025/11/12 · openalex updated_date 2026/07/28

Abstract

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 Y, we achieve error guarantee of O(log |Y|), which is within a factor of (log log |Y|)^O(1) of the exponential mechanism (McSherry and Talwar, 2007). This improves on Steinke's mechanism which achieves an error of O(log^3/2 |Y|).

Citations

• Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds
• Concentrated Differential Privacy
• Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
• Differentially Private Combinatorial Optimization

Related

• Private Selection from Private Candidates
• Exponential Randomized Response: Boosting Utility in Differentially Private Selection
• Tight Lower Bounds for Differentially Private Selection
• Differentially Private Selection using Smooth Sensitivity
• Permute-and-Flip: A new mechanism for differentially private selection