Differentially Private Quasi-Concave Optimization: Bypassing the Lower Bound and Application to Geometric Problems
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913810079547392 |
|---|---|
| author | Nissim, Kobbi Tsfadia, Eliad Yan, Chao |
| author_facet | Nissim, Kobbi Tsfadia, Eliad Yan, Chao |
| contents | 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 $Ω(2^{\log^*|\mathcal{X}|})$. We show that the lower bound can be bypassed for a series of ``natural'' problems. We define a new class of \emph{approximated} quasi-concave functions, and present a generic differentially private optimizer for approximated quasi-concave functions with sample complexity $\tilde{O}(\log^*|\mathcal{X}|)$. As applications, we use our optimizer to privately select a center point of points in $d$ dimensions and \emph{probably approximately correct} (PAC) learn $d$-dimensional halfspaces. In previous works, Bun et al. (FOCS 2015) proved a lower bound of $Ω(\log^*|\mathcal{X}|)$ for both problems. Beimel et al. (COLT 2019) and Kaplan et al. (NeurIPS 2020) gave an upper bound of $\tilde{O}(d^{2.5}\cdot 2^{\log^*|\mathcal{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 $\tilde{O}(d^{5.5}\cdot\log^*|\mathcal{X}|)$ for both problems. To the best of our understanding, this is the first work to reduce the sample complexity dependency on $|\mathcal{X}|$ for these two problems from exponential in $\log^* |\mathcal{X}|$ to $\log^* |\mathcal{X}|$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_19001 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Differentially Private Quasi-Concave Optimization: Bypassing the Lower Bound and Application to Geometric Problems Nissim, Kobbi Tsfadia, Eliad Yan, Chao Cryptography and Security 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 $Ω(2^{\log^*|\mathcal{X}|})$. We show that the lower bound can be bypassed for a series of ``natural'' problems. We define a new class of \emph{approximated} quasi-concave functions, and present a generic differentially private optimizer for approximated quasi-concave functions with sample complexity $\tilde{O}(\log^*|\mathcal{X}|)$. As applications, we use our optimizer to privately select a center point of points in $d$ dimensions and \emph{probably approximately correct} (PAC) learn $d$-dimensional halfspaces. In previous works, Bun et al. (FOCS 2015) proved a lower bound of $Ω(\log^*|\mathcal{X}|)$ for both problems. Beimel et al. (COLT 2019) and Kaplan et al. (NeurIPS 2020) gave an upper bound of $\tilde{O}(d^{2.5}\cdot 2^{\log^*|\mathcal{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 $\tilde{O}(d^{5.5}\cdot\log^*|\mathcal{X}|)$ for both problems. To the best of our understanding, this is the first work to reduce the sample complexity dependency on $|\mathcal{X}|$ for these two problems from exponential in $\log^* |\mathcal{X}|$ to $\log^* |\mathcal{X}|$. |
| title | Differentially Private Quasi-Concave Optimization: Bypassing the Lower Bound and Application to Geometric Problems |
| topic | Cryptography and Security |
| url | https://arxiv.org/abs/2504.19001 |