Differentially Private Quasi-Concave Optimization: Bypassing the Lower Bound and Application to Geometric Problems
Abstract
We study the sample complexity of differentially private optimization of quasi-concave functions. For a fixed input domain \(\mathcal{X}\), Cohen et al. [STOC 2023] proved that any generic private optimizer for low sensitive quasi-concave functions must have sample complexity \(\Omega(2^{\log^* |\mathcal{X}|})\).
Fields of Study & Subjects
Cryptography and Data Security
Stochastic Gradient Optimization Techniques
Complexity and Algorithms in Graphs
Publication details
- Journal / source
- Society for Industrial and Applied Mathematics eBooks
- Pages
- 5824–5842
- Publication date
- 1 January 2026
- Language
- EN