Mean estimation in the add-remove model of differential privacy Article Swipe
Alex Kulesza
,
Ananda Theertha Suresh
,
Yuyan Wang
·
YOU?
·
· 2023
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2312.06658
YOU?
·
· 2023
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2312.06658
Differential privacy is often studied under two different models of neighboring datasets: the add-remove model and the swap model. While the swap model is frequently used in the academic literature to simplify analysis, many practical applications rely on the more conservative add-remove model, where obtaining tight results can be difficult. Here, we study the problem of one-dimensional mean estimation under the add-remove model. We propose a new algorithm and show that it is min-max optimal, achieving the best possible constant in the leading term of the mean squared error for all $ε$, and that this constant is the same as the optimal algorithm under the swap model. These results show that the add-remove and swap models give nearly identical errors for mean estimation, even though the add-remove model cannot treat the size of the dataset as public information. We also demonstrate empirically that our proposed algorithm yields at least a factor of two improvement in mean squared error over algorithms frequently used in practice. One of our main technical contributions is a new hour-glass mechanism, which might be of independent interest in other scenarios.
Related Topics
Concepts
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- http://arxiv.org/abs/2312.06658
- https://arxiv.org/pdf/2312.06658
- OA Status
- green
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4389708230
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4389708230Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.48550/arxiv.2312.06658Digital Object Identifier
- Title
-
Mean estimation in the add-remove model of differential privacyWork title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2023Year of publication
- Publication date
-
2023-12-11Full publication date if available
- Authors
-
Alex Kulesza, Ananda Theertha Suresh, Yuyan WangList of authors in order
- Landing page
-
https://arxiv.org/abs/2312.06658Publisher landing page
- PDF URL
-
https://arxiv.org/pdf/2312.06658Direct link to full text PDF
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://arxiv.org/pdf/2312.06658Direct OA link when available
- Concepts
-
Differential privacy, Estimation, Computer science, Differential (mechanical device), Internet privacy, Data mining, Economics, Engineering, Management, Aerospace engineeringTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
0Total citation count in OpenAlex
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W4389708230 |
|---|---|
| doi | https://doi.org/10.48550/arxiv.2312.06658 |
| ids.doi | https://doi.org/10.48550/arxiv.2312.06658 |
| ids.openalex | https://openalex.org/W4389708230 |
| fwci | |
| type | preprint |
| title | Mean estimation in the add-remove model of differential privacy |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T10764 |
| topics[0].field.id | https://openalex.org/fields/17 |
| topics[0].field.display_name | Computer Science |
| topics[0].score | 0.9904999732971191 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/1702 |
| topics[0].subfield.display_name | Artificial Intelligence |
| topics[0].display_name | Privacy-Preserving Technologies in Data |
| topics[1].id | https://openalex.org/T11045 |
| topics[1].field.id | https://openalex.org/fields/33 |
| topics[1].field.display_name | Social Sciences |
| topics[1].score | 0.9793000221252441 |
| topics[1].domain.id | https://openalex.org/domains/2 |
| topics[1].domain.display_name | Social Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/3312 |
| topics[1].subfield.display_name | Sociology and Political Science |
| topics[1].display_name | Privacy, Security, and Data Protection |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C23130292 |
| concepts[0].level | 2 |
| concepts[0].score | 0.7247540354728699 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q5275358 |
| concepts[0].display_name | Differential privacy |
| concepts[1].id | https://openalex.org/C96250715 |
| concepts[1].level | 2 |
| concepts[1].score | 0.6378416419029236 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q965330 |
| concepts[1].display_name | Estimation |
| concepts[2].id | https://openalex.org/C41008148 |
| concepts[2].level | 0 |
| concepts[2].score | 0.475620299577713 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[2].display_name | Computer science |
| concepts[3].id | https://openalex.org/C93226319 |
| concepts[3].level | 2 |
| concepts[3].score | 0.45693105459213257 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q193137 |
| concepts[3].display_name | Differential (mechanical device) |
| concepts[4].id | https://openalex.org/C108827166 |
| concepts[4].level | 1 |
| concepts[4].score | 0.323902428150177 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q175975 |
| concepts[4].display_name | Internet privacy |
| concepts[5].id | https://openalex.org/C124101348 |
| concepts[5].level | 1 |
| concepts[5].score | 0.26141157746315 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q172491 |
| concepts[5].display_name | Data mining |
| concepts[6].id | https://openalex.org/C162324750 |
| concepts[6].level | 0 |
| concepts[6].score | 0.1569560468196869 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q8134 |
| concepts[6].display_name | Economics |
| concepts[7].id | https://openalex.org/C127413603 |
| concepts[7].level | 0 |
| concepts[7].score | 0.1268901526927948 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q11023 |
| concepts[7].display_name | Engineering |
| concepts[8].id | https://openalex.org/C187736073 |
| concepts[8].level | 1 |
| concepts[8].score | 0.0 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q2920921 |
| concepts[8].display_name | Management |
| concepts[9].id | https://openalex.org/C146978453 |
| concepts[9].level | 1 |
| concepts[9].score | 0.0 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q3798668 |
| concepts[9].display_name | Aerospace engineering |
| keywords[0].id | https://openalex.org/keywords/differential-privacy |
| keywords[0].score | 0.7247540354728699 |
| keywords[0].display_name | Differential privacy |
| keywords[1].id | https://openalex.org/keywords/estimation |
| keywords[1].score | 0.6378416419029236 |
| keywords[1].display_name | Estimation |
| keywords[2].id | https://openalex.org/keywords/computer-science |
| keywords[2].score | 0.475620299577713 |
| keywords[2].display_name | Computer science |
| keywords[3].id | https://openalex.org/keywords/differential |
| keywords[3].score | 0.45693105459213257 |
| keywords[3].display_name | Differential (mechanical device) |
| keywords[4].id | https://openalex.org/keywords/internet-privacy |
| keywords[4].score | 0.323902428150177 |
| keywords[4].display_name | Internet privacy |
| keywords[5].id | https://openalex.org/keywords/data-mining |
| keywords[5].score | 0.26141157746315 |
| keywords[5].display_name | Data mining |
| keywords[6].id | https://openalex.org/keywords/economics |
| keywords[6].score | 0.1569560468196869 |
| keywords[6].display_name | Economics |
| keywords[7].id | https://openalex.org/keywords/engineering |
| keywords[7].score | 0.1268901526927948 |
| keywords[7].display_name | Engineering |
| language | en |
| locations[0].id | pmh:oai:arXiv.org:2312.06658 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S4306400194 |
| locations[0].source.issn | |
| locations[0].source.type | repository |
| locations[0].source.is_oa | True |
| locations[0].source.issn_l | |
| locations[0].source.is_core | False |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | arXiv (Cornell University) |
| locations[0].source.host_organization | https://openalex.org/I205783295 |
| locations[0].source.host_organization_name | Cornell University |
| locations[0].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[0].license | |
| locations[0].pdf_url | https://arxiv.org/pdf/2312.06658 |
| locations[0].version | submittedVersion |
| locations[0].raw_type | text |
| locations[0].license_id | |
| locations[0].is_accepted | False |
| locations[0].is_published | False |
| locations[0].raw_source_name | |
| locations[0].landing_page_url | http://arxiv.org/abs/2312.06658 |
| locations[1].id | doi:10.48550/arxiv.2312.06658 |
| locations[1].is_oa | True |
| locations[1].source.id | https://openalex.org/S4306400194 |
| locations[1].source.issn | |
| locations[1].source.type | repository |
| locations[1].source.is_oa | True |
| locations[1].source.issn_l | |
| locations[1].source.is_core | False |
| locations[1].source.is_in_doaj | False |
| locations[1].source.display_name | arXiv (Cornell University) |
| locations[1].source.host_organization | https://openalex.org/I205783295 |
| locations[1].source.host_organization_name | Cornell University |
| locations[1].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[1].license | |
| locations[1].pdf_url | |
| locations[1].version | |
| locations[1].raw_type | article |
| locations[1].license_id | |
| locations[1].is_accepted | False |
| locations[1].is_published | |
| locations[1].raw_source_name | |
| locations[1].landing_page_url | https://doi.org/10.48550/arxiv.2312.06658 |
| indexed_in | arxiv, datacite |
| authorships[0].author.id | https://openalex.org/A5032936063 |
| authorships[0].author.orcid | |
| authorships[0].author.display_name | Alex Kulesza |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Kulesza, Alex |
| authorships[0].is_corresponding | False |
| authorships[1].author.id | https://openalex.org/A5103890688 |
| authorships[1].author.orcid | |
| authorships[1].author.display_name | Ananda Theertha Suresh |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Suresh, Ananda Theertha |
| authorships[1].is_corresponding | False |
| authorships[2].author.id | https://openalex.org/A5100677212 |
| authorships[2].author.orcid | https://orcid.org/0000-0001-5585-3789 |
| authorships[2].author.display_name | Yuyan Wang |
| authorships[2].author_position | last |
| authorships[2].raw_author_name | Wang, Yuyan |
| authorships[2].is_corresponding | False |
| has_content.pdf | False |
| has_content.grobid_xml | False |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://arxiv.org/pdf/2312.06658 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | Mean estimation in the add-remove model of differential privacy |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T06:51:31.235846 |
| primary_topic.id | https://openalex.org/T10764 |
| primary_topic.field.id | https://openalex.org/fields/17 |
| primary_topic.field.display_name | Computer Science |
| primary_topic.score | 0.9904999732971191 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/1702 |
| primary_topic.subfield.display_name | Artificial Intelligence |
| primary_topic.display_name | Privacy-Preserving Technologies in Data |
| related_works | https://openalex.org/W4391375266, https://openalex.org/W2748952813, https://openalex.org/W3038283795, https://openalex.org/W2604501336, https://openalex.org/W2734500670, https://openalex.org/W2558166297, https://openalex.org/W2315671126, https://openalex.org/W798507144, https://openalex.org/W2964481303, https://openalex.org/W1751413323 |
| cited_by_count | 0 |
| locations_count | 2 |
| best_oa_location.id | pmh:oai:arXiv.org:2312.06658 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S4306400194 |
| best_oa_location.source.issn | |
| best_oa_location.source.type | repository |
| best_oa_location.source.is_oa | True |
| best_oa_location.source.issn_l | |
| best_oa_location.source.is_core | False |
| best_oa_location.source.is_in_doaj | False |
| best_oa_location.source.display_name | arXiv (Cornell University) |
| best_oa_location.source.host_organization | https://openalex.org/I205783295 |
| best_oa_location.source.host_organization_name | Cornell University |
| best_oa_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| best_oa_location.license | |
| best_oa_location.pdf_url | https://arxiv.org/pdf/2312.06658 |
| best_oa_location.version | submittedVersion |
| best_oa_location.raw_type | text |
| best_oa_location.license_id | |
| best_oa_location.is_accepted | False |
| best_oa_location.is_published | False |
| best_oa_location.raw_source_name | |
| best_oa_location.landing_page_url | http://arxiv.org/abs/2312.06658 |
| primary_location.id | pmh:oai:arXiv.org:2312.06658 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S4306400194 |
| primary_location.source.issn | |
| primary_location.source.type | repository |
| primary_location.source.is_oa | True |
| primary_location.source.issn_l | |
| primary_location.source.is_core | False |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | arXiv (Cornell University) |
| primary_location.source.host_organization | https://openalex.org/I205783295 |
| primary_location.source.host_organization_name | Cornell University |
| primary_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| primary_location.license | |
| primary_location.pdf_url | https://arxiv.org/pdf/2312.06658 |
| primary_location.version | submittedVersion |
| primary_location.raw_type | text |
| primary_location.license_id | |
| primary_location.is_accepted | False |
| primary_location.is_published | False |
| primary_location.raw_source_name | |
| primary_location.landing_page_url | http://arxiv.org/abs/2312.06658 |
| publication_date | 2023-12-11 |
| publication_year | 2023 |
| referenced_works_count | 0 |
| abstract_inverted_index.a | 65, 149, 171 |
| abstract_inverted_index.We | 63, 138 |
| abstract_inverted_index.as | 99, 135 |
| abstract_inverted_index.at | 147 |
| abstract_inverted_index.be | 48, 177 |
| abstract_inverted_index.in | 26, 80, 154, 162, 181 |
| abstract_inverted_index.is | 2, 23, 72, 96, 170 |
| abstract_inverted_index.it | 71 |
| abstract_inverted_index.of | 9, 55, 84, 132, 151, 165, 178 |
| abstract_inverted_index.on | 37 |
| abstract_inverted_index.to | 30 |
| abstract_inverted_index.we | 51 |
| abstract_inverted_index.One | 164 |
| abstract_inverted_index.all | 90 |
| abstract_inverted_index.and | 15, 68, 92, 113 |
| abstract_inverted_index.can | 47 |
| abstract_inverted_index.for | 89, 120 |
| abstract_inverted_index.new | 66, 172 |
| abstract_inverted_index.our | 143, 166 |
| abstract_inverted_index.the | 12, 16, 20, 27, 38, 53, 60, 76, 81, 85, 97, 100, 104, 111, 125, 130, 133 |
| abstract_inverted_index.two | 6, 152 |
| abstract_inverted_index.also | 139 |
| abstract_inverted_index.best | 77 |
| abstract_inverted_index.even | 123 |
| abstract_inverted_index.give | 116 |
| abstract_inverted_index.main | 167 |
| abstract_inverted_index.many | 33 |
| abstract_inverted_index.mean | 57, 86, 121, 155 |
| abstract_inverted_index.more | 39 |
| abstract_inverted_index.over | 158 |
| abstract_inverted_index.rely | 36 |
| abstract_inverted_index.same | 98 |
| abstract_inverted_index.show | 69, 109 |
| abstract_inverted_index.size | 131 |
| abstract_inverted_index.swap | 17, 21, 105, 114 |
| abstract_inverted_index.term | 83 |
| abstract_inverted_index.that | 70, 93, 110, 142 |
| abstract_inverted_index.this | 94 |
| abstract_inverted_index.used | 25, 161 |
| abstract_inverted_index.$ε$, | 91 |
| abstract_inverted_index.Here, | 50 |
| abstract_inverted_index.These | 107 |
| abstract_inverted_index.While | 19 |
| abstract_inverted_index.error | 88, 157 |
| abstract_inverted_index.least | 148 |
| abstract_inverted_index.might | 176 |
| abstract_inverted_index.model | 14, 22, 127 |
| abstract_inverted_index.often | 3 |
| abstract_inverted_index.other | 182 |
| abstract_inverted_index.study | 52 |
| abstract_inverted_index.tight | 45 |
| abstract_inverted_index.treat | 129 |
| abstract_inverted_index.under | 5, 59, 103 |
| abstract_inverted_index.where | 43 |
| abstract_inverted_index.which | 175 |
| abstract_inverted_index.cannot | 128 |
| abstract_inverted_index.errors | 119 |
| abstract_inverted_index.factor | 150 |
| abstract_inverted_index.model, | 42 |
| abstract_inverted_index.model. | 18, 62, 106 |
| abstract_inverted_index.models | 8, 115 |
| abstract_inverted_index.nearly | 117 |
| abstract_inverted_index.public | 136 |
| abstract_inverted_index.though | 124 |
| abstract_inverted_index.yields | 146 |
| abstract_inverted_index.dataset | 134 |
| abstract_inverted_index.leading | 82 |
| abstract_inverted_index.min-max | 73 |
| abstract_inverted_index.optimal | 101 |
| abstract_inverted_index.privacy | 1 |
| abstract_inverted_index.problem | 54 |
| abstract_inverted_index.propose | 64 |
| abstract_inverted_index.results | 46, 108 |
| abstract_inverted_index.squared | 87, 156 |
| abstract_inverted_index.studied | 4 |
| abstract_inverted_index.academic | 28 |
| abstract_inverted_index.constant | 79, 95 |
| abstract_inverted_index.interest | 180 |
| abstract_inverted_index.optimal, | 74 |
| abstract_inverted_index.possible | 78 |
| abstract_inverted_index.proposed | 144 |
| abstract_inverted_index.simplify | 31 |
| abstract_inverted_index.achieving | 75 |
| abstract_inverted_index.algorithm | 67, 102, 145 |
| abstract_inverted_index.analysis, | 32 |
| abstract_inverted_index.datasets: | 11 |
| abstract_inverted_index.different | 7 |
| abstract_inverted_index.identical | 118 |
| abstract_inverted_index.obtaining | 44 |
| abstract_inverted_index.practical | 34 |
| abstract_inverted_index.practice. | 163 |
| abstract_inverted_index.technical | 168 |
| abstract_inverted_index.add-remove | 13, 41, 61, 112, 126 |
| abstract_inverted_index.algorithms | 159 |
| abstract_inverted_index.difficult. | 49 |
| abstract_inverted_index.estimation | 58 |
| abstract_inverted_index.frequently | 24, 160 |
| abstract_inverted_index.hour-glass | 173 |
| abstract_inverted_index.literature | 29 |
| abstract_inverted_index.mechanism, | 174 |
| abstract_inverted_index.scenarios. | 183 |
| abstract_inverted_index.demonstrate | 140 |
| abstract_inverted_index.empirically | 141 |
| abstract_inverted_index.estimation, | 122 |
| abstract_inverted_index.improvement | 153 |
| abstract_inverted_index.independent | 179 |
| abstract_inverted_index.neighboring | 10 |
| abstract_inverted_index.Differential | 0 |
| abstract_inverted_index.applications | 35 |
| abstract_inverted_index.conservative | 40 |
| abstract_inverted_index.information. | 137 |
| abstract_inverted_index.contributions | 169 |
| abstract_inverted_index.one-dimensional | 56 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 3 |
| sustainable_development_goals[0].id | https://metadata.un.org/sdg/16 |
| sustainable_development_goals[0].score | 0.550000011920929 |
| sustainable_development_goals[0].display_name | Peace, Justice and strong institutions |
| citation_normalized_percentile |