Differentially Private Learning with Margin Guarantees Article Swipe
Raef Bassily
,
Mehryar Mohri
,
Ananda Theertha Suresh
·
YOU?
·
· 2022
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2204.10376
YOU?
·
· 2022
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2204.10376
We present a series of new differentially private (DP) algorithms with dimension-independent margin guarantees. For the family of linear hypotheses, we give a pure DP learning algorithm that benefits from relative deviation margin guarantees, as well as an efficient DP learning algorithm with margin guarantees. We also present a new efficient DP learning algorithm with margin guarantees for kernel-based hypotheses with shift-invariant kernels, such as Gaussian kernels, and point out how our results can be extended to other kernels using oblivious sketching techniques. We further give a pure DP learning algorithm for a family of feed-forward neural networks for which we prove margin guarantees that are independent of the input dimension. Additionally, we describe a general label DP learning algorithm, which benefits from relative deviation margin bounds and is applicable to a broad family of hypothesis sets, including that of neural networks. Finally, we show how our DP learning algorithms can be augmented in a general way to include model selection, to select the best confidence margin parameter.
Related Topics
Concepts
Margin (machine learning)
Dimension (graph theory)
Computer science
Kernel (algebra)
Gaussian
Artificial neural network
Artificial intelligence
Support vector machine
Algorithm
Invariant (physics)
Mathematics
Machine learning
Discrete mathematics
Combinatorics
Physics
Quantum mechanics
Mathematical physics
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- http://arxiv.org/abs/2204.10376
- https://arxiv.org/pdf/2204.10376
- OA Status
- green
- Cited By
- 2
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4224434685
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4224434685Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.48550/arxiv.2204.10376Digital Object Identifier
- Title
-
Differentially Private Learning with Margin GuaranteesWork title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2022Year of publication
- Publication date
-
2022-04-21Full publication date if available
- Authors
-
Raef Bassily, Mehryar Mohri, Ananda Theertha SureshList of authors in order
- Landing page
-
https://arxiv.org/abs/2204.10376Publisher landing page
- PDF URL
-
https://arxiv.org/pdf/2204.10376Direct 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/2204.10376Direct OA link when available
- Concepts
-
Margin (machine learning), Dimension (graph theory), Computer science, Kernel (algebra), Gaussian, Artificial neural network, Artificial intelligence, Support vector machine, Algorithm, Invariant (physics), Mathematics, Machine learning, Discrete mathematics, Combinatorics, Physics, Quantum mechanics, Mathematical physicsTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
2Total citation count in OpenAlex
- Citations by year (recent)
-
2023: 2Per-year citation counts (last 5 years)
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W4224434685 |
|---|---|
| doi | https://doi.org/10.48550/arxiv.2204.10376 |
| ids.doi | https://doi.org/10.48550/arxiv.2204.10376 |
| ids.openalex | https://openalex.org/W4224434685 |
| fwci | |
| type | preprint |
| title | Differentially Private Learning with Margin Guarantees |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T12072 |
| topics[0].field.id | https://openalex.org/fields/17 |
| topics[0].field.display_name | Computer Science |
| topics[0].score | 0.9896000027656555 |
| 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 | Machine Learning and Algorithms |
| topics[1].id | https://openalex.org/T11206 |
| topics[1].field.id | https://openalex.org/fields/31 |
| topics[1].field.display_name | Physics and Astronomy |
| topics[1].score | 0.9747999906539917 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/3109 |
| topics[1].subfield.display_name | Statistical and Nonlinear Physics |
| topics[1].display_name | Model Reduction and Neural Networks |
| topics[2].id | https://openalex.org/T10320 |
| topics[2].field.id | https://openalex.org/fields/17 |
| topics[2].field.display_name | Computer Science |
| topics[2].score | 0.9692000150680542 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/1702 |
| topics[2].subfield.display_name | Artificial Intelligence |
| topics[2].display_name | Neural Networks and Applications |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C774472 |
| concepts[0].level | 2 |
| concepts[0].score | 0.8962352275848389 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q6760393 |
| concepts[0].display_name | Margin (machine learning) |
| concepts[1].id | https://openalex.org/C33676613 |
| concepts[1].level | 2 |
| concepts[1].score | 0.6475209593772888 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q13415176 |
| concepts[1].display_name | Dimension (graph theory) |
| concepts[2].id | https://openalex.org/C41008148 |
| concepts[2].level | 0 |
| concepts[2].score | 0.5231310725212097 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[2].display_name | Computer science |
| concepts[3].id | https://openalex.org/C74193536 |
| concepts[3].level | 2 |
| concepts[3].score | 0.49166232347488403 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q574844 |
| concepts[3].display_name | Kernel (algebra) |
| concepts[4].id | https://openalex.org/C163716315 |
| concepts[4].level | 2 |
| concepts[4].score | 0.48821523785591125 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q901177 |
| concepts[4].display_name | Gaussian |
| concepts[5].id | https://openalex.org/C50644808 |
| concepts[5].level | 2 |
| concepts[5].score | 0.47611531615257263 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q192776 |
| concepts[5].display_name | Artificial neural network |
| concepts[6].id | https://openalex.org/C154945302 |
| concepts[6].level | 1 |
| concepts[6].score | 0.4649452269077301 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q11660 |
| concepts[6].display_name | Artificial intelligence |
| concepts[7].id | https://openalex.org/C12267149 |
| concepts[7].level | 2 |
| concepts[7].score | 0.43920913338661194 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q282453 |
| concepts[7].display_name | Support vector machine |
| concepts[8].id | https://openalex.org/C11413529 |
| concepts[8].level | 1 |
| concepts[8].score | 0.4323842525482178 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q8366 |
| concepts[8].display_name | Algorithm |
| concepts[9].id | https://openalex.org/C190470478 |
| concepts[9].level | 2 |
| concepts[9].score | 0.42990821599960327 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q2370229 |
| concepts[9].display_name | Invariant (physics) |
| concepts[10].id | https://openalex.org/C33923547 |
| concepts[10].level | 0 |
| concepts[10].score | 0.3844137489795685 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[10].display_name | Mathematics |
| concepts[11].id | https://openalex.org/C119857082 |
| concepts[11].level | 1 |
| concepts[11].score | 0.3707062602043152 |
| concepts[11].wikidata | https://www.wikidata.org/wiki/Q2539 |
| concepts[11].display_name | Machine learning |
| concepts[12].id | https://openalex.org/C118615104 |
| concepts[12].level | 1 |
| concepts[12].score | 0.1206853985786438 |
| concepts[12].wikidata | https://www.wikidata.org/wiki/Q121416 |
| concepts[12].display_name | Discrete mathematics |
| concepts[13].id | https://openalex.org/C114614502 |
| concepts[13].level | 1 |
| concepts[13].score | 0.10093915462493896 |
| concepts[13].wikidata | https://www.wikidata.org/wiki/Q76592 |
| concepts[13].display_name | Combinatorics |
| concepts[14].id | https://openalex.org/C121332964 |
| concepts[14].level | 0 |
| concepts[14].score | 0.0 |
| concepts[14].wikidata | https://www.wikidata.org/wiki/Q413 |
| concepts[14].display_name | Physics |
| concepts[15].id | https://openalex.org/C62520636 |
| concepts[15].level | 1 |
| concepts[15].score | 0.0 |
| concepts[15].wikidata | https://www.wikidata.org/wiki/Q944 |
| concepts[15].display_name | Quantum mechanics |
| concepts[16].id | https://openalex.org/C37914503 |
| concepts[16].level | 1 |
| concepts[16].score | 0.0 |
| concepts[16].wikidata | https://www.wikidata.org/wiki/Q156495 |
| concepts[16].display_name | Mathematical physics |
| keywords[0].id | https://openalex.org/keywords/margin |
| keywords[0].score | 0.8962352275848389 |
| keywords[0].display_name | Margin (machine learning) |
| keywords[1].id | https://openalex.org/keywords/dimension |
| keywords[1].score | 0.6475209593772888 |
| keywords[1].display_name | Dimension (graph theory) |
| keywords[2].id | https://openalex.org/keywords/computer-science |
| keywords[2].score | 0.5231310725212097 |
| keywords[2].display_name | Computer science |
| keywords[3].id | https://openalex.org/keywords/kernel |
| keywords[3].score | 0.49166232347488403 |
| keywords[3].display_name | Kernel (algebra) |
| keywords[4].id | https://openalex.org/keywords/gaussian |
| keywords[4].score | 0.48821523785591125 |
| keywords[4].display_name | Gaussian |
| keywords[5].id | https://openalex.org/keywords/artificial-neural-network |
| keywords[5].score | 0.47611531615257263 |
| keywords[5].display_name | Artificial neural network |
| keywords[6].id | https://openalex.org/keywords/artificial-intelligence |
| keywords[6].score | 0.4649452269077301 |
| keywords[6].display_name | Artificial intelligence |
| keywords[7].id | https://openalex.org/keywords/support-vector-machine |
| keywords[7].score | 0.43920913338661194 |
| keywords[7].display_name | Support vector machine |
| keywords[8].id | https://openalex.org/keywords/algorithm |
| keywords[8].score | 0.4323842525482178 |
| keywords[8].display_name | Algorithm |
| keywords[9].id | https://openalex.org/keywords/invariant |
| keywords[9].score | 0.42990821599960327 |
| keywords[9].display_name | Invariant (physics) |
| keywords[10].id | https://openalex.org/keywords/mathematics |
| keywords[10].score | 0.3844137489795685 |
| keywords[10].display_name | Mathematics |
| keywords[11].id | https://openalex.org/keywords/machine-learning |
| keywords[11].score | 0.3707062602043152 |
| keywords[11].display_name | Machine learning |
| keywords[12].id | https://openalex.org/keywords/discrete-mathematics |
| keywords[12].score | 0.1206853985786438 |
| keywords[12].display_name | Discrete mathematics |
| keywords[13].id | https://openalex.org/keywords/combinatorics |
| keywords[13].score | 0.10093915462493896 |
| keywords[13].display_name | Combinatorics |
| language | en |
| locations[0].id | pmh:oai:arXiv.org:2204.10376 |
| 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/2204.10376 |
| 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/2204.10376 |
| locations[1].id | doi:10.48550/arxiv.2204.10376 |
| 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 | cc-by |
| locations[1].pdf_url | |
| locations[1].version | |
| locations[1].raw_type | article |
| locations[1].license_id | https://openalex.org/licenses/cc-by |
| 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.2204.10376 |
| indexed_in | arxiv, datacite |
| authorships[0].author.id | https://openalex.org/A5009609755 |
| authorships[0].author.orcid | |
| authorships[0].author.display_name | Raef Bassily |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Bassily, Raef |
| authorships[0].is_corresponding | False |
| authorships[1].author.id | https://openalex.org/A5058849006 |
| authorships[1].author.orcid | https://orcid.org/0000-0002-3987-9847 |
| authorships[1].author.display_name | Mehryar Mohri |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Mohri, Mehryar |
| authorships[1].is_corresponding | False |
| authorships[2].author.id | https://openalex.org/A5103890688 |
| authorships[2].author.orcid | |
| authorships[2].author.display_name | Ananda Theertha Suresh |
| authorships[2].author_position | last |
| authorships[2].raw_author_name | Suresh, Ananda Theertha |
| 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/2204.10376 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | Differentially Private Learning with Margin Guarantees |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T06:51:31.235846 |
| primary_topic.id | https://openalex.org/T12072 |
| primary_topic.field.id | https://openalex.org/fields/17 |
| primary_topic.field.display_name | Computer Science |
| primary_topic.score | 0.9896000027656555 |
| 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 | Machine Learning and Algorithms |
| related_works | https://openalex.org/W3125011624, https://openalex.org/W1508631387, https://openalex.org/W2370917603, https://openalex.org/W2017776670, https://openalex.org/W2952760143, https://openalex.org/W2347897961, https://openalex.org/W2979236518, https://openalex.org/W2358318464, https://openalex.org/W2340870721, https://openalex.org/W2379140333 |
| cited_by_count | 2 |
| counts_by_year[0].year | 2023 |
| counts_by_year[0].cited_by_count | 2 |
| locations_count | 2 |
| best_oa_location.id | pmh:oai:arXiv.org:2204.10376 |
| 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/2204.10376 |
| 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/2204.10376 |
| primary_location.id | pmh:oai:arXiv.org:2204.10376 |
| 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/2204.10376 |
| 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/2204.10376 |
| publication_date | 2022-04-21 |
| publication_year | 2022 |
| referenced_works_count | 0 |
| abstract_inverted_index.a | 2, 22, 48, 86, 92, 114, 131, 154 |
| abstract_inverted_index.DP | 24, 39, 51, 88, 117, 147 |
| abstract_inverted_index.We | 0, 45, 83 |
| abstract_inverted_index.an | 37 |
| abstract_inverted_index.as | 34, 36, 64 |
| abstract_inverted_index.be | 74, 151 |
| abstract_inverted_index.in | 153 |
| abstract_inverted_index.is | 128 |
| abstract_inverted_index.of | 4, 17, 94, 107, 134, 139 |
| abstract_inverted_index.to | 76, 130, 157, 161 |
| abstract_inverted_index.we | 20, 100, 112, 143 |
| abstract_inverted_index.For | 14 |
| abstract_inverted_index.and | 67, 127 |
| abstract_inverted_index.are | 105 |
| abstract_inverted_index.can | 73, 150 |
| abstract_inverted_index.for | 57, 91, 98 |
| abstract_inverted_index.how | 70, 145 |
| abstract_inverted_index.new | 5, 49 |
| abstract_inverted_index.our | 71, 146 |
| abstract_inverted_index.out | 69 |
| abstract_inverted_index.the | 15, 108, 163 |
| abstract_inverted_index.way | 156 |
| abstract_inverted_index.(DP) | 8 |
| abstract_inverted_index.also | 46 |
| abstract_inverted_index.best | 164 |
| abstract_inverted_index.from | 29, 122 |
| abstract_inverted_index.give | 21, 85 |
| abstract_inverted_index.pure | 23, 87 |
| abstract_inverted_index.show | 144 |
| abstract_inverted_index.such | 63 |
| abstract_inverted_index.that | 27, 104, 138 |
| abstract_inverted_index.well | 35 |
| abstract_inverted_index.with | 10, 42, 54, 60 |
| abstract_inverted_index.broad | 132 |
| abstract_inverted_index.input | 109 |
| abstract_inverted_index.label | 116 |
| abstract_inverted_index.model | 159 |
| abstract_inverted_index.other | 77 |
| abstract_inverted_index.point | 68 |
| abstract_inverted_index.prove | 101 |
| abstract_inverted_index.sets, | 136 |
| abstract_inverted_index.using | 79 |
| abstract_inverted_index.which | 99, 120 |
| abstract_inverted_index.bounds | 126 |
| abstract_inverted_index.family | 16, 93, 133 |
| abstract_inverted_index.linear | 18 |
| abstract_inverted_index.margin | 12, 32, 43, 55, 102, 125, 166 |
| abstract_inverted_index.neural | 96, 140 |
| abstract_inverted_index.select | 162 |
| abstract_inverted_index.series | 3 |
| abstract_inverted_index.further | 84 |
| abstract_inverted_index.general | 115, 155 |
| abstract_inverted_index.include | 158 |
| abstract_inverted_index.kernels | 78 |
| abstract_inverted_index.present | 1, 47 |
| abstract_inverted_index.private | 7 |
| abstract_inverted_index.results | 72 |
| abstract_inverted_index.Finally, | 142 |
| abstract_inverted_index.Gaussian | 65 |
| abstract_inverted_index.benefits | 28, 121 |
| abstract_inverted_index.describe | 113 |
| abstract_inverted_index.extended | 75 |
| abstract_inverted_index.kernels, | 62, 66 |
| abstract_inverted_index.learning | 25, 40, 52, 89, 118, 148 |
| abstract_inverted_index.networks | 97 |
| abstract_inverted_index.relative | 30, 123 |
| abstract_inverted_index.algorithm | 26, 41, 53, 90 |
| abstract_inverted_index.augmented | 152 |
| abstract_inverted_index.deviation | 31, 124 |
| abstract_inverted_index.efficient | 38, 50 |
| abstract_inverted_index.including | 137 |
| abstract_inverted_index.networks. | 141 |
| abstract_inverted_index.oblivious | 80 |
| abstract_inverted_index.sketching | 81 |
| abstract_inverted_index.algorithm, | 119 |
| abstract_inverted_index.algorithms | 9, 149 |
| abstract_inverted_index.applicable | 129 |
| abstract_inverted_index.confidence | 165 |
| abstract_inverted_index.dimension. | 110 |
| abstract_inverted_index.guarantees | 56, 103 |
| abstract_inverted_index.hypotheses | 59 |
| abstract_inverted_index.hypothesis | 135 |
| abstract_inverted_index.parameter. | 167 |
| abstract_inverted_index.selection, | 160 |
| abstract_inverted_index.guarantees, | 33 |
| abstract_inverted_index.guarantees. | 13, 44 |
| abstract_inverted_index.hypotheses, | 19 |
| abstract_inverted_index.independent | 106 |
| abstract_inverted_index.techniques. | 82 |
| abstract_inverted_index.feed-forward | 95 |
| abstract_inverted_index.kernel-based | 58 |
| abstract_inverted_index.Additionally, | 111 |
| abstract_inverted_index.differentially | 6 |
| abstract_inverted_index.shift-invariant | 61 |
| abstract_inverted_index.dimension-independent | 11 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 3 |
| citation_normalized_percentile |