The DOI matches its Crossref record; 3 of the 3 references it cites were found in a registry or an index.
Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds
Abstract
Convex empirical risk minimization is a basic tool in machine learning and statistics. We provide new algorithms and matching lower bounds for differentially private convex empirical risk minimization assuming only that each data point's contribution to the loss function is Lipschitz and that the domain of optimization is bounded. We provide a separate set of algorithms and matching lower bounds for the setting in which the loss functions are known to also be strongly convex. Our algorithms run in polynomial time, and in some cases even match the optimal nonprivate running time (as measured by oracle complexity). We give separate algorithms (and lower bounds) for (ε, 0)and (ε, δ)-differential privacy; perhaps surprisingly, the techniques used for designing optimal algorithms in the two cases are completely different. Our lower bounds apply even to very simple, smooth function families, such as linear and quadratic functions. This implies that algorithms from previous work can be used to obtain optimal error rates, under the additional assumption that the contributions of each data point to the loss function is smooth. We show that simple approaches to smoothing arbitrary loss functions (in order to apply previous techniques) do not yield optimal error rates. In particular, optimal algorithms were not previously known for problems such as training support vector machines and the high-dimensional median.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Boyd, S., & Vandenberghe, L. (2004) · doi:10.1017/cbo9780511804441 · Cited by 56,601
Calibrating Noise to Sensitivity in Private Data Analysis
Dwork, C., McSherry, F., Nissim, K., & Smith, A. (2006) · Lecture Notes in Computer Science · doi:10.1007/11681878_14 · Cited by 7,272
Self-citationOur Data, Ourselves: Privacy Via Distributed Noise Generation
Dwork, C., Kenthapadi, K., McSherry, F., Mironov, I., & Naor, M. (2006) · Lecture Notes in Computer Science · doi:10.1007/11761679_29 · Cited by 1,835
Cited by
Deep Learning with Differential Privacy
Abadi, M., Chu, A., Goodfellow, I., McMahan, H. B., Mironov, I., Talwar, K., & Zhang, L. (2016) · Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/2976749.2978318 · Cited by 6,578
Membership Inference Attacks Against Machine Learning Models
Shokri, R., Stronati, M., Song, C., & Shmatikov, V. (2017) · 2017 IEEE Symposium on Security and Privacy (SP) · doi:10.1109/sp.2017.41 · Cited by 4,754
Privacy-preserving deep learning
Shokri, R., & Shmatikov, V. (2015) · Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/2810103.2813687 · Cited by 2,356
A survey on federated learning
Zhang, C., Xie, Y., Bai, H., Yu, B., Li, W., & Gao, Y. (2021) · Knowledge-Based Systems · doi:10.1016/j.knosys.2021.106775 · Cited by 1,899
SCAFFOLD: Stochastic Controlled Averaging for Federated Learning
Karimireddy, S. P., Kale, S., Mohri, M., Reddi, S. J., Stich, S. U., & Suresh, A. T. (2019) · arXiv · doi:10.48550/arxiv.1910.06378 · Cited by 1,734
Nasr, M., Shokri, R., & Houmansadr, A. (2019) · 2019 IEEE Symposium on Security and Privacy (SP) · doi:10.1109/sp.2019.00065 · Cited by 1,760
Privacy Risk in Machine Learning: Analyzing the Connection to Overfitting
Yeom, S., Giacomelli, I., Fredrikson, M., & Jha, S. (2018) · 2018 IEEE 31st Computer Security Foundations Symposium (CSF) · doi:10.1109/csf.2018.00027 · Cited by 1,001
Learning Differentially Private Recurrent Language Models
McMahan, H. B., Ramage, D., Talwar, K., & Zhang, L. (2017) · arXiv · doi:10.48550/arxiv.1710.06963 · Cited by 849
Machine Learning with Membership Privacy using Adversarial Regularization
Nasr, M., Shokri, R., & Houmansadr, A. (2018) · Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/3243734.3243855 · Cited by 458
Dong, J., Roth, A., & Su, W. J. (2019) · arXiv · doi:10.48550/arxiv.1905.02383 · Cited by 389
Privacy preservation in federated learning: An insightful survey from the GDPR perspective
Truong, N., Sun, K., Wang, S., Guitton, F., & Guo, Y. (2021) · Computers & Security · doi:10.1016/j.cose.2021.102402 · Cited by 399
Scalable Private Learning with PATE
Papernot, N., Song, S., Mironov, I., Raghunathan, A., Talwar, K., & Erlingsson, Ú. (2018) · arXiv · doi:10.48550/arxiv.1802.08908 · Cited by 373
Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity
Erlingsson, Ú., Feldman, V., Mironov, I., Raghunathan, A., Talwar, K., & Thakurta, A. (2019) · Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms · doi:10.1137/1.9781611975482.151 · Cited by 264
Self-citationTrustworthy ai: A computational perspective
Liu, H., Wang, Y., Fan, W., Liu, X., Li, Y., Jain, S., Liu, Y., Jain, A., & Tang, J. (2023) · ACM Transactions on Intelligent Systems and Technology · doi:10.1145/3546872 · Cited by 261
Distributed Privacy-Preserving Collaborative Intrusion Detection Systems for VANETs
Zhang, T., & Zhu, Q. (2018) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2018.2801622 · Cited by 168
The distributed discrete gaussian mechanism for federated learning with secure aggregation
Kairouz, P., Liu, Z., & Steinke, T. (2021) · arXiv · doi:10.48550/arxiv.2102.06387 · Cited by 117
Generative Models for Effective ML on Private, Decentralized Datasets
Augenstein, S., McMahan, H. B., Ramage, D., Ramaswamy, S., Kairouz, P., Chen, M., Mathews, R., & Arcas, B. A. Y. (2019) · arXiv · doi:10.48550/arxiv.1911.06679 · Cited by 103
Differentially Private Fine-tuning of Language Models
Yu, D., Naik, S., Backurs, A., Gopi, S., Inan, H. A., Kamath, G., Kulkarni, J., Lee, Y. T., Manoel, A., Wutschitz, L., et al. (2021) · arXiv · doi:10.48550/arxiv.2110.06500 · Cited by 101
Analyzing Information Leakage of Updates to Natural Language Models
Zanella-Béguelin, S., Wutschitz, L., Tople, S., Rühle, V., Paverd, A., Ohrimenko, O., Köpf, B., & Brockschmidt, M. (2020) · Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/3372297.3417880 · Cited by 86
Survey: Leakage and Privacy at Inference Time
Jegorova, M., Kaul, C., Mayor, C., O'Neil, A. Q., Weir, A., Murray-Smith, R., & Tsaftaris, S. A. (2022) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2022.3229593 · Cited by 77
Property Inference from Poisoning
Mahloujifar, S., Ghosh, E., & Chase, M. (2022) · 2022 IEEE Symposium on Security and Privacy (SP) · doi:10.1109/sp46214.2022.9833623 · Cited by 67
Learning Anonymized Representations with Adversarial Neural Networks
Feutry, C., Piantanida, P., Bengio, Y., & Duhamel, P. (2018) · arXiv · doi:10.48550/arxiv.1802.09386 · Cited by 52
Practical and private (deep) learning without sampling or shuffling
Kairouz, P., McMahan, B., Song, S., Thakkar, O., Thakurta, A., & Xu, Z. (2021) · arXiv · doi:10.48550/arxiv.2103.00039 · Cited by 52
Self-citationHo, T.-T., Tran, K.-D., & Huang, Y. (2022) · Sensors · doi:10.3390/s22103728 · Cited by 44
On the Power of Multiple Anonymous Messages
Ghazi, B., Golowich, N., Kumar, R., Pagh, R., & Velingker, A. (2019) · arXiv · doi:10.48550/arxiv.1908.11358 · Cited by 26
Machine Unlearning via Algorithmic Stability
Ullah, E., Mai, T., Rao, A., Rossi, R., & Arora, R. (2021) · arXiv · doi:10.48550/arxiv.2102.13179 · Cited by 26
Shuffled Model of Federated Learning: Privacy, Communication and Accuracy Trade-offs
Girgis, A. M., Data, D., Diggavi, S., Kairouz, P., & Suresh, A. T. (2020) · arXiv · doi:10.48550/arxiv.2008.07180 · Cited by 16
Trustworthy AI Inference Systems: An Industry Research View
Cammarota, R., Schunter, M., Rajan, A., Boemer, F., Kiss, Á., Treiber, A., Weinert, C., Schneider, T., Stapf, E., Sadeghi, A.-R., et al. (2020) · arXiv · doi:10.48550/arxiv.2008.04449 · Cited by 9
Angelopoulos, A. N., Bates, S., Zrnic, T., & Jordan, M. I. (2022) · Harvard Data Science Review · doi:10.1162/99608f92.16c71dad · Cited by 8
Graves, L., Nagisetty, V., & Ganesh, V. (2021) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v35i13.17371 · Cited by 5
Privacy-Preserving Recommendation with Debiased Obfuscaiton
Lin, C., Liu, B., Zhang, X., Wang, Z., Hu, C., & Luo, L. (2022) · 2022 IEEE International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom) · doi:10.1109/trustcom56396.2022.00086 · Cited by 4
Metadata
- Authors
- Bassily, R., Smith, A., & Thakurta, A.
- Venue
- 2014 IEEE 55th Annual Symposium on Foundations of Computer Science
- Publisher
- IEEE
- Published
- 2014-10
- Pages
- 464-473
- ISSN
- 0272-5428 (ISSN-L)
- OpenAlex
- W1992926795
- Cited by
- 621
- References
- 3
- FWCI
- 10.08
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.
