Improved Lower Bound for Differentially Private Facility Location
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916151875862528 |
|---|---|
| author | Manurangsi, Pasin |
| author_facet | Manurangsi, Pasin |
| contents | We consider the differentially private (DP) facility location problem in the so called super-set output setting proposed by Gupta et al. [SODA 2010]. The current best known expected approximation ratio for an $ε$-DP algorithm is $O\left(\frac{\log n}{\sqrtε}\right)$ due to Cohen-Addad et al. [AISTATS 2022] where $n$ denote the size of the metric space, meanwhile the best known lower bound is $Ω(1/\sqrtε)$ [NeurIPS 2019].
In this short note, we give a lower bound of $\tildeΩ\left(\min\left\{\log n, \sqrt{\frac{\log n}ε}\right\}\right)$ on the expected approximation ratio of any $ε$-DP algorithm, which is the first evidence that the approximation ratio has to grow with the size of the metric space. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_04874 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Improved Lower Bound for Differentially Private Facility Location Manurangsi, Pasin Data Structures and Algorithms Cryptography and Security We consider the differentially private (DP) facility location problem in the so called super-set output setting proposed by Gupta et al. [SODA 2010]. The current best known expected approximation ratio for an $ε$-DP algorithm is $O\left(\frac{\log n}{\sqrtε}\right)$ due to Cohen-Addad et al. [AISTATS 2022] where $n$ denote the size of the metric space, meanwhile the best known lower bound is $Ω(1/\sqrtε)$ [NeurIPS 2019]. In this short note, we give a lower bound of $\tildeΩ\left(\min\left\{\log n, \sqrt{\frac{\log n}ε}\right\}\right)$ on the expected approximation ratio of any $ε$-DP algorithm, which is the first evidence that the approximation ratio has to grow with the size of the metric space. |
| title | Improved Lower Bound for Differentially Private Facility Location |
| topic | Data Structures and Algorithms Cryptography and Security |
| url | https://arxiv.org/abs/2403.04874 |