# Differentially Private Quasi-Concave Optimization: Bypassing the Lower Bound and Application to Geometric Problems

arXiv: https://arxiv.org/abs/2504.19001 · HTML: https://mlsanity.com/paper/2504.19001/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Apr 2025.

## Built on by (most cited first, 3 of 3)

- [An tildeOptimal Differentially Private Learner for Concept Classes with VC Dimension 1](https://mlsanity.com/paper/2505.06581/) (2025)
- [Private Prediction via Shrinkage](https://mlsanity.com/paper/2602.05219/) (2026)
- [Private Component-by-Component Learning](https://mlsanity.com/paper/2610.05102/) (2026)

## Abstract (arXiv)

We study the sample complexity of differentially private optimization of quasi-concave functions. For a fixed input domain X, Cohen et al. (STOC 2023) proved that any generic private optimizer for low sensitive quasi-concave functions must have sample complexity Omega(2log^*|X|). We show that the lower bound can be bypassed for a series of ``natural'' problems. We define a new class of approximated quasi-concave functions, and present a generic differentially private optimizer for approximated quasi-concave functions with sample complexity tildeO(log^*|X|). As applications, we use our optimizer to privately select a center point of points in d dimensions and probably approximately correct (PAC) learn d-dimensional halfspaces. In previous works, Bun et al. (FOCS 2015) proved a lower bound of Omega(log^*|X|) for both problems. Beimel et al. (COLT 2019) and Kaplan et al. (NeurIPS 2020) gave an upper bound of tildeO(d2.5· 2log^*|X|) for the two problems, respectively. We improve the dependency of the upper bounds on the cardinality of the domain by presenting a new upper bound of tildeO(d5.5·log^*|X|) for both problems. To the best of our understanding, this is the first work to reduce the sample complexity dependency on |X| for these two problems from exponential in log^* |X| to log^* |X|.