The DOI matches its Crossref record; 27 of the 52 references it cites were found in a registry or an index, and 25 are not checked yet.
What Can We Learn Privately?
Abstract
Learning problems form an important category of computational tasks that generalizes many of the computations researchers apply to large real-life data sets. We ask, What concept classes can be learned privately, namely, by an algorithm whose output does not depend too heavily on any one input or specific training example? More precisely, we investigate learning algorithms that satisfy differential privacy, a notion that provides strong confidentiality guarantees in contexts where aggregate information is released about a database containing sensitive information about individuals. Our goal is a broad understanding of the resources required for private learning in terms of samples, computation time, and interaction. We demonstrate that, ignoring computational constraints, it is possible to privately agnostically learn any concept class using a sample size approximately logarithmic in the cardinality of the concept class. Therefore, almost anything learnable is learnable privately: specifically, if a concept class is learnable by a (nonprivate) algorithm with polynomial sample complexity and output size, then it can be learned privately using a polynomial number of samples. We also present a computationally efficient private probabilistically approximately correct learner for the class of parity functions. This result dispels the similarity between learning with noise and private learning (both must be robust to small changes in inputs), since parity is thought to be very hard to learn given random classification noise. Local (or randomized response) algorithms are a practical class of private algorithms that have received extensive investigation. We provide a precise characterization of local private learning algorithms. We show that a concept class is learnable by a local algorithm if and only if it is learnable in the statistical query (SQ) model. Therefore, for local private learning algorithms, the similarity to learning with noise is stronger: local learning is equivalent to SQ learning, and SQ algorithms include most known noise-tolerant learning algorithms. Finally, we present a separation between the power of interactive and noninteractive local learning algorithms. Because of the equivalence to SQ learning, this result also separates adaptive and nonadaptive SQ learning.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The check wasn’t confident either way, so it gives no verdict — never disputed.
In the citing paper
“Comparing these two results, we see that minibatch SGD attains the optimal 'statistical' term ( σ / √ TKM ), whilst SGD on a single device (ignoring the updates of the other devices) achieves the optimal 'optimization' term ( H / ( TK ) 2 ).”
From Advances and Open Problems in Federated Learning (2021) · cites this paper as [294]
Experimental — accuracy not yet measured
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
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-citationDwork, C. (2006) · Lecture Notes in Computer Science · doi:10.1007/11787006_1 · Cited by 5,291 · cited 2×
“A recent line of work, initiated by Dinur and Nissim [15] and called private data analysis, seeks to place data privacy on firmer theoretical foundations and has been successful at formulating a strong, yet attainable privacy definition.”
Probability Inequalities for Sums of Bounded Random Variables
Hoeffding, W. (1963) · Journal of the American Statistical Association · doi:10.1080/01621459.1963.10500830 · Cited by 4,852
A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
Chernoff, H. (1952) · The Annals of Mathematical Statistics · doi:10.1214/aoms/1177729330 · Cited by 3,550
Valiant, L. G. (1984) · Communications of the ACM · doi:10.1145/1968.1972 · Cited by 3,279 · cited 1×
“We examine two basic notions from learning: Valiant's probabilistically approximately correct (PAC) learning [39] model and Kearns' statistical query (SQ) model [29].”
Randomized Response: A Survey Technique for Eliminating Evasive Answer Bias
Warner, S. L. (1965) · Journal of the American Statistical Association · doi:10.1080/01621459.1965.10480775 · Cited by 3,255 · cited 1×
“The difficulty of constructing private learners lies in finding a good hypothesis in what is typically an exponentially large space.”
Privacy-preserving data mining
Agrawal, R., & Srikant, R. (2000) · ACM SIGMOD Record · doi:10.1145/335191.335438 · Cited by 2,961
On lattices, learning with errors, random linear codes, and cryptography
Regev, O. (2009) · Journal of the ACM · doi:10.1145/1568318.1568324 · Cited by 2,315 · cited 1×
“More compellingly , learning parity with noise is thought to be computationally hard, and has been used as the basis of several cryptographic primitives (e.g., [11] [25] [4] [38]).”
Our 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 1×
“A recent line of work, initiated by Dinur and Nissim [15] and called private data analysis, seeks to place data privacy on firmer theoretical foundations and has been successful at formulating a strong, yet attainable privacy definition.”
An Introduction to Computational Learning Theory
Kearns, M. J., & Vazirani, U. (1994) · doi:10.7551/mitpress/3897.001.0001 · Cited by 1,697 · cited 5×
“However, our result can be extended to the compression version, which captures the general relationship between compression and learning (we borrow the “cardinality version” terminology from [42]).”
Influential
Research works printed but not linked: 9
- S. Ben-David, D. Pál, and H.U. Simon, Stability of k -means clustering , in COLT '07:Proceedings of the 20th Annual Conference on Learning Theory, N. H. Bshouty and C. Gentile, eds., Springer, Berlin, 2007, pp. 20–34. · doi:10.1007/978-3-540-72927-3_4
- Bousquet O., 2002, J. Mach. Learn. Res., 2, 499
- Bshouty N. H., 2002, J. Mach. Learn. Res., 2, 359
- Elisseeff A., 2005, J. Mach. Learn. Res., 6, 55
- S. P. Kasiviswanathan and A. Smith, A Note on Differential Privacy: Defining Resistance to Arbitrary Side Information , Preprint arXiv:0803.39461 [cs.CR], 2008.
- -1S. Kutin and P. Niyogi, Almost-everywhere algorithmic stability and generalization error , in Proceedings of UAI, Association for Uncertainty in Artificial Intelligence, 2002, pp. 275–282.
- T. Moran and M. Naor, Polling with physical envelopes: A rigorous analysis of a human-centric protocol , in Advances in Cryptology, Lecture Notes in Comput. Sci. 4004, Springer, Berlin, 2006, pp. 88–108. · doi:10.1007/11761679_7
- V. Rastogi, S. Hong, and D. Suciu, The boundary between privacy and utility in data publishing , in Proceedings of VLDB '07, VLDB Endowment, Vienna, Austria, 2007, pp. 531–542.
- 10.2307/1403910 · doi:10.2307/1403910
Cited by
Advances and Open Problems in Federated Learning
Kairouz, P., & McMahan, H. B. (2021) · Foundations and Trends in Machine Learning · doi:10.1561/2200000083 · Cited by 7,772
“2, achieving LDP while maintaining utility can be difficult [229, 388].”
BackgroundMethodDeep 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
Communication-Efficient Learning of Deep Networks from Decentralized Data
McMahan, H. B., Moore, E., Ramage, D., Hampson, S., & Arcas, B. A. Y. (2016) · arXiv · doi:10.48550/arxiv.1602.05629 · Cited by 14,215
“A stronger guarantee can be achieved by enforcing local differential privacy (Kasiviswanathan et al., 2008; Duchi et al., 2014), where rather than adding noise to the final model, we noise the individual updates, which precludes the central server from making any definitive inference about a client.”
BackgroundThe Algorithmic Foundations of Differential Privacy
Dwork, C., & Roth, A. (2013) · doi:10.1561/9781601988195 · Cited by 3,856
Deep Models Under the GAN: Information Leakage from Collaborative Deep Learning
Hitaj, B., Ateniese, G., & Perez-Cruz, F. (2017) · Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/3133956.3134012 · Cited by 1,377
“Differential privacy plays an important role in deep learning as shown in [1, 38, 75, 77].”
BackgroundFederated Learning of Deep Networks using Model AveragingPreprint
McMahan, H. B., Moore, E., Ramage, D., & y Arcas, B. A. (2016) · arXiv (Cornell University) · Cited by 1,288
(2011) · PubMed · Cited by 990
Local Privacy and Statistical Minimax Rates
Duchi, J. C., Jordan, M. I., & Wainwright, M. J. (2013) · 2013 IEEE 54th Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2013.53 · Cited by 954
“In recent years, the notion of differential privacy has been put forth as one formal definition of privacy (e.g., [11, 10, 12, 16, 18]).”
BackgroundA Field Guide to Federated OptimizationPreprint
Wang, J., Charles, Z., Xu, Z., Joshi, G., McMahan, H. B., y Arcas, B. A., Al-Shedivat, M., Andrew, G., Avestimehr, S., Daly, K., et al. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2107.06917 · Cited by 543
Privacy Amplification by Subsampling: Tight Analyses via Couplings and DivergencesPreprint
Balle, B., Barthe, G., & Gaboardi, M. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1807.01647 · Cited by 537
“Privacy amplification with Poisson sampling was used in [Chaudhuri and Mishra, 2006, Beimel et al., 2010, Kasiviswanathan et al., 2011, Beimel et al., 2014], which considered loose bounds.”
MethodA learning theory approach to non-interactive database privacy
Blum, A., Ligett, K., & Roth, A. (2008) · Proceedings of the fortieth annual ACM symposium on Theory of computing · doi:10.1145/1374376.1374464 · Cited by 505
SoK: Security and Privacy in Machine Learning
Papernot, N., McDaniel, P., Sinha, A., & Wellman, M. P. (2018) · 2018 IEEE European Symposium on Security and Privacy (EuroS&P) · doi:10.1109/eurosp.2018.00035 · Cited by 502
“An instance of training data randomization is formalized by local privacy [89].”
MethodLDP-Fed: federated learning with local differential privacy
Truex, S., Liu, L., Chow, K.-H., Gursoy, M. E., & Wei, W. (2020) · Proceedings of the Third ACM International Workshop on Edge Systems, Analytics and Networking · doi:10.1145/3378679.3394533 · Cited by 435
“The privacy amplification theorem [4, 14] additionally states that if random samples are selected rather than all available data, then each round satisfying ε-DP incurs only a cost of (qε) against the privacy budget where q = L/N is the sampling ratio.”
BackgroundRényi Differential Privacy of the Sampled Gaussian MechanismPreprint
Mironov, I., Talwar, K., & Zhang, L. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1908.10530 · Cited by 416
Differentially Private Spatial Decompositions
Cormode, G., Procopiuc, C., Srivastava, D., Shen, E., & Yu, T. (2012) · 2012 IEEE 28th International Conference on Data Engineering · doi:10.1109/icde.2012.16 · Cited by 411
A Statistical Framework for Differential Privacy
Wasserman, L., & Zhou, S. (2010) · Journal of the American Statistical Association · doi:10.1198/jasa.2009.tm08651 · Cited by 397
Calibrating Noise to Sensitivity in Private Data Analysis
Dwork, C., McSherry, F., Nissim, K., & Smith, A. (2017) · Journal of Privacy and Confidentiality · doi:10.29012/jpc.v7i3.405 · Cited by 390
Self-citationDong, J., Roth, A., & Su, W. J. (2019) · arXiv · doi:10.48550/arxiv.1905.02383 · Cited by 389
Minimax Optimal Procedures for Locally Private Estimation
Duchi, J. C., Jordan, M. I., & Wainwright, M. J. (2018) · Journal of the American Statistical Association · doi:10.1080/01621459.2017.1389735 · Cited by 386
“There are results that are more favorable for differential privacy, for example, Smith (2011) showed that the nonlocal form of differential privacy (Dwork et al. 2006) can be satisfied while yielding asymptotically optimal parametric rates of convergence for some point estimators.”
BackgroundInfluentialCollecting and Analyzing Multidimensional Data with Local Differential Privacy
Wang, N., Xiao, X., Yang, Y., Zhao, J., Hui, S. C., Shin, H., Shin, J., & Yu, G. (2019) · 2019 IEEE 35th International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2019.00063 · Cited by 381
Dong, J., Roth, A., & Su, W. J. (2022) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/rssb.12454 · Cited by 374
Personalized Federated Learning With Differential Privacy
Hu, R., Guo, Y., Li, H., Pei, Q., & Gong, Y. (2020) · IEEE Internet of Things Journal · doi:10.1109/jiot.2020.2991416 · Cited by 350
“Recently, some advanced composition theorems [6], [9], [12]–[14] have been proposed to achieve tighter analysis of the privacy loss for multiple iterations.”
BackgroundKasiviswanathan, S. P., Lee, H. K., Nissim, K., Raskhodnikova, S., & Smith, A. (2008) · 2008 49th Annual IEEE Symposium on Foundations of Computer Science · doi:10.1109/focs.2008.27 · Cited by 334
Self-citationHeavy Hitter Estimation over Set-Valued Data with Local Differential Privacy
Qin, Z., Yang, Y., Yu, T., Khalil, I., Xiao, X., & Ren, K. (2016) · Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/2976749.2978409 · Cited by 324
“Local differential privacy (LDP) [22, 14] is a data collection (cid:2) noisy version of her data to a data collector.”
BackgroundDai, E., Zhao, T., Zhu, H., Xu, J., Guo, Z., Liu, H., Tang, J., & Wang, S. (2024) · Machine Intelligence Research · doi:10.1007/s11633-024-1510-8 · Cited by 323
“For example, the locally private GNN [152] adopts local differential privacy [92] to protect the privacy of node features by perturbing the user’s features locally.”
BackgroundLocal, Private, Efficient Protocols for Succinct Histograms
Bassily, R., & Smith, A. (2015) · Proceedings of the forty-seventh annual ACM symposium on Theory of Computing · doi:10.1145/2746539.2746632 · Cited by 315
“Most relevant here are the results of [15, 3] on learning and statistical estimation in the local model.”
BackgroundSelf-citationTrading Private Range Counting over Big IoT Data
Cai, Z., & He, Z. (2019) · 2019 IEEE 39th International Conference on Distributed Computing Systems (ICDCS) · doi:10.1109/icdcs.2019.00023 · Cited by 313
“4 generalized from [11] shows the relationship of ′, p and .”
BackgroundA Survey on Differential Privacy for Unstructured Data Content
Zhao, Y., & Chen, J. (2022) · ACM Computing Surveys · doi:10.1145/3490237 · Cited by 313
“3) [20, 53], aiming at applying the formalized privacy model to individual data in the user’s setting rather than the aggregated setting in the curator’s setting.”
BackgroundSubsampled Rényi Differential Privacy and Analytical Moments Accountant
Wang, Y.-X., Balle, B., & Kasiviswanathan, S. P. (2020) · Journal of Privacy and Confidentiality · doi:10.29012/jpc.723 · Cited by 305
Self-citationThe cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy
Cai, T., Wang, Y., & Zhang, L. (2021) · The Annals of Statistics · doi:10.1214/21-aos2058 · Cited by 281
Algorithms that remember: model inversion attacks and data protection law
Veale, M., Binns, R., & Edwards, L. (2018) · Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rsta.2018.0083 · Cited by 278
“Theoretically , such learning algorithms are just as powerful as non-differentially private ones [46].”
BackgroundFanti, G., Pihur, V., & Erlingsson, Ú. (2016) · Proceedings on Privacy Enhancing Technologies · doi:10.1515/popets-2016-0015 · Cited by 275
“When there is no party trusted to construct a database of the sensitive data, the more refined notion of local differential privacy is often considered [16, 7, 14].”
BackgroundPractical Locally Private Heavy HittersPreprint
Bassily, R., Kobbi Nissim, B., Stemmer, U., & Thakurta, A. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1707.04982 · Cited by 275
“Furthermore, some tasks which are possible in the curator model are impossible in the local model [9, 14, 7].”
Privacy- and Utility-Preserving Textual Analysis via Calibrated Multivariate Perturbations
Feyisetan, O., Balle, B., Drake, T. M., & Diethe, T. (2020) · ACM International Conference on Web Search and Data Mining (WSDM) · doi:10.1145/3336191.3371856 · Cited by 273
“Together, these requirements push us towards solutions where each data record is processed independently, similar to the setting in Local DP (LDP) [31].”
BackgroundMethodInfluentialA learning theory approach to noninteractive database privacy
Blum, A., Ligett, K., & Roth, A. (2013) · Journal of the ACM · doi:10.1145/2450142.2450148 · Cited by 242
Generating Synthetic Decentralized Social Graphs with Local Differential Privacy
Qin, Z., Yu, T., Yang, Y., Khalil, I., Xiao, X., & Ren, K. (2017) · Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/3133956.3134086 · Cited by 236
“Here we show that LDPGen satisfies ϵ -edge local differential privacy Let ( δ , . . . , δ k ) be u ’s degree vector for a given partition ξ .”
BackgroundMethodInfluentialDuchi, J. C., Jordan, M. I., & Wainwright, M. J. (2014) · Journal of the ACM · doi:10.1145/2666468 · Cited by 231
Local differential privacy and its applications: A comprehensive survey
Yang, M., Guo, T., Zhu, T., Tjuawinata, I., Zhao, J., & Lam, K.-Y. (2024) · Computer Standards & Interfaces · doi:10.1016/j.csi.2023.103827 · Cited by 229
Subsampled Rényi Differential Privacy and Analytical Moments Accountant
Wang, Y.-X., Balle, B., & Kasiviswanathan, S. (2018) · arXiv · doi:10.48550/arxiv.1808.00087 · Cited by 224
“The first privacy amplification lemma appeared in (Kasiviswanathan et al., 2011; Beimel et al., 2013), with many subsequent improvements in different settings.”
BackgroundSelf-citationDifferentially Private Release and Learning of Threshold Functions
Bun, M., Kobbi Nissim, B., Stemmer, U., & Vadhan, S. (2015) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2015.45 · Cited by 223
A survey on the complexity of learning quantum states
Anshu, A., & Arunachalam, S. (2023) · Nature Reviews Physics · doi:10.1038/s42254-023-00662-4 · Cited by 212
“Although, a priori, it seems that PAC learning, online learning and DP learning have little to do with one another, classically, there has been a series of works establishing tight connections between these models 81 .”
Deep Models Under the GAN: Information Leakage from Collaborative Deep Learning
Hitaj, B., Ateniese, G., & Pérez‐Cruz, F. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1702.07464 · Cited by 205
“Differential privacy plays an important role in deep learning as shown in [1, 38, 75, 77].”
BackgroundDynamic Differential Privacy for ADMM-Based Distributed Classification Learning
Zhang, T., & Zhu, Q. (2017) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2016.2607691 · Cited by 202
“have derived a general method for probabilistically approximately correct (PAC, [10]) in [11].”
MethodComposable and versatile privacy via truncated CDP
Bun, M., Dwork, C., Rothblum, G. N., & Steinke, T. (2018) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3188745.3188946 · Cited by 201
Statistical Algorithms and a Lower Bound for Detecting Planted Cliques
Feldman, V., Grigorescu, E., Reyzin, L., Vempala, S., & Xiao, Y. (2017) · Journal of the ACM · doi:10.1145/3046674 · Cited by 195
Fingerprinting codes and the price of approximate differential privacy
Bun, M., Ullman, J., & Vadhan, S. (2014) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2591796.2591877 · Cited by 193
Towards the Science of Security and Privacy in Machine Learning
Papernot, N., McDaniel, P. D., Sinha, A., & Wellman, M. P. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1611.03814 · Cited by 192
“An instance of training data randomization is formalized by local privacy [96].”
MethodFast-adapting and privacy-preserving federated recommender system
Wang, Q., Yin, H., Chen, T., Yu, J., Zhou, A., & Zhang, X. (2021) · The VLDB Journal · doi:10.1007/s00778-021-00700-6 · Cited by 192
Finite Sample Differentially Private Confidence Intervals
Karwa, V., & Vadhan, S. (2017) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.itcs.2018.44 · Cited by 187
Locally Private Graph Neural Networks
Sajadmanesh, S., & Gática-Pérez, D. (2021) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/3460120.3484565 · Cited by 186
“To prevent the aggregator from inferring the original private value from the perturbed one, the mechanismM must satisfy the following definition [19]: Definition 2.”
MethodPrivacy in Large Language Models: Attacks, Defenses and Future DirectionsPreprint
Li, H., Chen, Y., Luo, J., Wang, J., Peng, H., Kang, Y., Zhang, X., Hu, Q., Chan, C., Xu, Z., et al. (2023) · arXiv (Cornell University) · doi:10.48550/arxiv.2310.10383 · Cited by 185
“Feyisetan et al. [76] applied 𝑑𝜒 privacy [5, 32], a variant of local differential privacy (LDP) [122], on the word embedding space to perform text perturbation on Bi-LSTM.”
BackgroundThe Staircase Mechanism in Differential Privacy
Geng, Q., Kairouz, P., Oh, S., & Viswanath, P. (2015) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2015.2425831 · Cited by 184
The Optimal Noise-Adding Mechanism in Differential Privacy
Geng, Q., & Viswanath, P. (2016) · IEEE Transactions on Information Theory · doi:10.1109/tit.2015.2504967 · Cited by 169
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
“[22], for instance, have driven a general method for probabilistically approximately correct learning.”
BackgroundMethodHow to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy
Ponomareva, N., Hazimeh, H., Kurakin, A., Xu, Z., Denison, C., McMahan, H. B., Vassilvitskii, S., Chien, S., & Thakurta, A. G. (2023) · Journal of Artificial Intelligence Research · doi:10.1613/jair.1.14649 · Cited by 166
“privacy amplification by sampling (Kasiviswanathan et al., 2011), which allowed them to run the algorithm for more steps without a significant cost to privacy.”
BackgroundMethodInfluentialDP-Forward: Fine-tuning and Inference on Language Models with Differential Privacy in Forward Pass
Du, M., Yue, X., Chow, S. S. M., Wang, T., Huang, C., & Sun, H. (2023) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/3576915.3616592 · Cited by 165
“In contrast, local DP (LDP) [38] removes the trusted curator, allowing individuals to locally perturb their data using M before being sent to an untrusted aggregator for analytics.”
BackgroundIs Interaction Necessary for Distributed Private Learning?
Smith, A., Thakurta, A., & Upadhyay, J. (2017) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp.2017.35 · Cited by 161
“[26] initiated the study of private local learning.”
BackgroundInfluentialSelf-citationManipulation Attacks in Local Differential Privacy
Cheu, A., Smith, A., & Ullman, J. (2021) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp40001.2021.00001 · Cited by 161
Self-citationRobust Anomaly Detection and Backdoor Attack Detection Via Differential PrivacyPreprint
Du, M., Jia, R., & Song, D. X. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1911.07116 · Cited by 159
“A known fact is that differential privacy implies stability ([3]).”
BackgroundPrivate selection from private candidates
Liu, J., & Talwar, K. (2019) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3313276.3316377 · Cited by 157
“tially Private Selection problem, often known as dierentially private maximization, is a very general algorithmic problem that arises in many applications. Some examples include private PAC learning [21], private frequent itemset mining [4], private PCA [8,20] and private multiple hypothesis testing [15,34]. The Spars…”
BackgroundStevens, R. L., USDOE, Taylor, V., Nichols, J., Maccabe, A. B. ‘., Yelick, K., & Brown, D. L. (2020) · OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) · doi:10.2172/1604756 · Cited by 157
A Comprehensive Survey on Local Differential Privacy toward Data Statistics and Analysis
Wang, T., Zhang, X., Feng, J., & Yang, X. (2020) · Sensors · doi:10.3390/s20247030 · Cited by 154
“Based on the definition of DP, local differential privacy (LDP) [25] is proposed as a distributed variant of DP, which achieves privacy guarantees for each user locally and is independent of any assumptions on the third-party servers.”
BackgroundMethodLocal Privacy and Minimax Bounds: Sharp Rates for Probability EstimationPreprint
Duchi, J. C., Jordan, M. I., & Wainwright, M. J. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1305.6000 · Cited by 153
“Differential privacy has strong semantic privacy guarantees make it a good candidate for declaring a statistical procedure or data collection mechanism private, and has been the focus of a growing body of recent work [14, 17, 20, 28, 25, 7, 21, 9, 6, 11].”
BackgroundWhen is memorization of irrelevant training data necessary for high-accuracy learning?
Brown, G., Bun, M., Feldman, V., Smith, A., & Talwar, K. (2021) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3406325.3451131 · Cited by 152
“, [8, 25]), including a number of striking separations from nonprivate algorithms [11, 5, 2].”
BackgroundSelf-citationLocal Privacy, Data Processing Inequalities, and Statistical Minimax RatesPreprint
Duchi, J. C., Jordan, M. I., & Wainwright, M. J. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1302.3203 · Cited by 150
“rk in developing differentially private mechanisms, both in local and non-local settings, and a number of authors have attempted to characterize optimal mechanisms. For example, Kasiviswanathan et al. [37], working within a local differential privacy setting, study Probably-Approximately-Correct (PAC) learning problems…”
BackgroundA Comprehensive Survey on Local Differential Privacy
Xiong, X., Liu, S., Li, D., Cai, Z., & Niu, X. (2020) · Security and Communication Networks · doi:10.1155/2020/8829523 · Cited by 147
“Identical to the CDP, the LDP has two frameworks of privacy preservation, interactive and noninteractive framework [5, 30, 31].”
BackgroundMethodLearnability of Quantum Neural Networks
Du, Y., Hsieh, M.-H., Liu, T., You, S., & Tao, D. (2021) · PRX Quantum · doi:10.1103/prxquantum.2.040337 · Cited by 147
LF-GDPR: A Framework for Estimating Graph Metrics With Local Differential Privacy
Ye, Q., Hu, H., Au, M. H., Meng, X., & Xiao, X. (2020) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2020.3047124 · Cited by 146
“Local differential privacy [10], [13] is proposed to assume each individual is responsible for her own tuple in the database.”
BackgroundPrivate PAC learning implies finite Littlestone dimension
Alon, N., Livni, R., Malliaris, M., & Moran, S. (2019) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3313276.3316312 · Cited by 145
The optimal mechanism in differential privacy
Geng, Q., & Viswanath, P. (2014) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2014.6875258 · Cited by 143
Distributed Learning, Communication Complexity and PrivacyPreprint
Balcan, M.-F., Blum, A. L., Fine, S., & Mansour, Y. (2012) · arXiv (Cornell University) · doi:10.1184/r1/6475568 · Cited by 142
Analyzing Subgraph Statistics from Extended Local Views with Decentralized Differential Privacy
Sun, H., Xiao, X., Khalil, I. M., Yang, Y., Qin, Z., Wang, H., & Yu, T. (2019) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/3319535.3354253 · Cited by 140
“The LDP notion [23] assumes there is no trusted centralized data curator.”
Background"I need a better description": An Investigation Into User Expectations For Differential Privacy
Cummings, R., Kaptchuk, G., & Redmiles, E. M. (2021) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/3460120.3485252 · Cited by 140
Differentially Private Releasing via Deep Generative Model (Technical Report)Preprint
Zhang, X., Ji, S., & Wang, T. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1801.01594 · Cited by 137
“According to the privacy amplification theorems [4, 20], this sampling procedure achieves (O( qϵ , qδ )) -DP per iteration with respect to the whole dataset where q = m n is the sampling ratio per batch, σ = 2log 1 .”
MethodBounds on the sample complexity for private learning and private data release
Beimel, A., Brenner, H., Kasiviswanathan, S. P., & Kobbi Nissim, B. (2013) · Machine Learning · doi:10.1007/s10994-013-5404-1 · Cited by 129
“Research partly supported by the Israel Science Foundation (grant No. 860/06).”
BackgroundMethodResultInfluentialSelf-citationLeveraging Hierarchical Representations for Preserving Privacy and Utility in Text
Feyisetan, O., Diethe, T., & Drake, T. (2019) · Proceedings · doi:10.1109/icdm.2019.00031 · Cited by 128
Trustworthy Distributed AI Systems: Robustness, Privacy, and Governance
Wei, W., & Liu, L. (2024) · ACM Computing Surveys · doi:10.1145/3645102 · Cited by 128
“Therefore, they introduce a gradient ascent-based anti-backdoor mechanism into the standard training to help isolate low-loss backdoor examples in early training and unlearn the backdoor correlation.”
Statistical algorithms and a lower bound for detecting planted cliques
Feldman, V., Grigorescu, E., Reyzin, L., Vempala, S., & Xiao, Y. (2013) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2488608.2488692 · Cited by 127
Answering range queries under local differential privacy
Cormode, G., Kulkarni, T., & Srivastava, D. (2019) · Proceedings of the VLDB Endowment · doi:10.14778/3339490.3339496 · Cited by 127
Differential Privacy for Functions and Functional DataPreprint
HallRob, RinaldoAlessandro, & WassermanLarry (2010) · arXiv (Cornell University) · doi:10.1184/r1/6586565 · Cited by 126
Natural Language Understanding with Privacy-Preserving BERT
Qu, C., Kong, W., Yang, L., Zhang, M., Bendersky, M., & Najork, M. (2021) · ACM International Conference on Information and Knowledge Management (CIKM) · doi:10.1145/3459637.3482281 · Cited by 124
Bounds on the Sample Complexity for Private Learning and Private Data Release
Beimel, A., Kasiviswanathan, S. P., & Kobbi Nissim, B. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-11799-2_26 · Cited by 119
Self-citationLDP-IDS: Local Differential Privacy for Infinite Data Streams
Ren, X., Shi, L., Yu, W., Yang, S., Zhao, C., & Xu, Z. (2022) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/3514221.3526190 · Cited by 118
“Recently, local differential privacy (LDP) [14, 15, 29] has demonstrated a great potential in accomplishing analytic tasks [9, 22, 33, 34, 36, 37, 39, 42, 45, 47, 48, 51, 52], without relying on a trusted aggregator.”
BackgroundA survey on federated learning: a perspective from multi-party computation
Liu, F., Zheng, Z., Shi, Y., Tong, Y., & Zhang, Y. (2023) · Frontiers of Computer Science · doi:10.1007/s11704-023-3282-7 · Cited by 118
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
“The privacy guarantees ε we report rely on privacy amplification via sampling (Kasiviswanathan et al., 2011; Bassily et al., 2014; Abadi et al., 2016), which is necessary to obtain reasonable privacy-accuracy tradeoffs”
BackgroundMethodInfluentialIdentityDP: Differential private identification protection for face images
Wen, Y., Liu, B., Ding, M., Xie, R., & Song, L. (2022) · Neurocomputing · doi:10.1016/j.neucom.2022.06.039 · Cited by 116
Privacy-Preserving Dynamic Personalized Pricing with Demand Learning
Chen, X., Simchi‐Levi, D., & Wang, Y. (2021) · Management Science · doi:10.1287/mnsc.2021.4129 · Cited by 116
A Survey on Differentially Private Machine Learning [Review Article]
Gong, M., Xie, Y., Pan, K., Feng, K., & Qin, A. K. (2020) · IEEE Computational Intelligence Magazine · doi:10.1109/mci.2020.2976185 · Cited by 115
Privately releasing conjunctions and the statistical query barrier
Gupta, A., Hardt, M., Roth, A., & Ullman, J. (2011) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1993636.1993742 · Cited by 115
Bonawitz, K., Kairouz, P., McMahan, H. B., & Ramage, D. (2021) · Queue · doi:10.1145/3494834.3500240 · Cited by 114
Continuous Release of Data Streams under both Centralized and Local Differential Privacy
Wang, T., Chen, J. Q., Zhang, Z., Su, D., Cheng, Y., Li, Z., Li, N., & Jha, S. (2021) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/3460120.3484750 · Cited by 111
Plis, S., Sarwate, A. D., Wood, D., Dieringer, C., Landis, D., Reed, C., Panta, S. R., Turner, J. A., Shoemaker, J. M., Carter, K. W., et al. (2016) · Frontiers in Neuroscience · doi:10.3389/fnins.2016.00365 · Cited by 111
“…by Dwork et al. (2006), differentially private algorithms have been designed for a number of applications, including statistical parameter estimation (Kasiviswanathan et al., 2008; Smith, 2008, 2011; Chaudhuri and Hsu, 2011, 2012), regression and classification (Chaudhuri et al., 2011; Kifer et al.,…”
Mutual Information Optimally Local Private Discrete Distribution EstimationPreprint
Wang, S., Huang, L., Wang, P., Nie, Y., Xu, H., Yang, W., Li, X., & Qiao, C. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1607.08025 · Cited by 110
“…privacy guarantee, and achieves plenty of theoretical results or mechanisms characterizing the definition, both in centralized database setting (e.g. in [21][4][13]) and in the local setting [18] (e.g. in [6][14][16]), where each data provider sanitizes their secret data locally and independently.”
BackgroundDeep Learning with Label Differential PrivacyPreprint
Ghazi, B., Golowich, N., Kumar, R., Manurangsi, P., & Zhang, C. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2102.06062 · Cited by 110
Lower Bounds for Locally Private Estimation via Communication ComplexityPreprint
Duchi, J. C., & Rogers, R. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1902.00582 · Cited by 109
Locally Differentially Private Document Generation Using Zero Shot Prompting
Utpala, S., Hooker, S., & Chen, P. (2023) · Findings of the Association for Computational Linguistics: EMNLP (Findings of EMNLP) · doi:10.18653/v1/2023.findings-emnlp.566 · Cited by 107
An Equivalence Between Private Classification and Online Prediction
Bun, M., Livni, R., & Moran, S. (2020) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs46700.2020.00044 · Cited by 106
Privacy-preserving PredictionPreprint
Dwork, C., & Feldman, V. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1803.10266 · Cited by 106
“For comparison, Kasiviswanathan et al. [KLNRS11] showed that the sample complexity of differentially privately PAC learning a class C over domain X is O (log( C ) / ( ǫα )).”
BackgroundHeavy Hitters and the Structure of Local Privacy
Bun, M., Nelson, J., & Stemmer, U. (2018) · ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS) · doi:10.1145/3196959.3196981 · Cited by 105
“[22], where it was used to show an equivalence between the local model (under pure-privacy) and SQ learning.”
MethodShuffled Model of Federated Learning: Privacy, Accuracy and Communication Trade-Offs
Girgis, A. M., Data, D., Diggavi, S. N., Kairouz, P., & Suresh, A. T. (2021) · IEEE Journal on Selected Areas in Information Theory · doi:10.1109/jsait.2021.3056102 · Cited by 102
“When we are not concerned about the communication budget, we succinctly denote the corresponding ((cid:4) 0 , ∞ ) -CLDP, by its correspondence to the classical LDP as 0 -LDP [9].”
BackgroundInfluential
Metadata
- Authors
- Kasiviswanathan, S. P., Lee, H. K., Nissim, K., Raskhodnikova, S., & Smith, A.
- Venue
- SIAM Journal on Computing
- Published
- 2011-01
- Volume
- 40
- Issue
- 3
- Pages
- 793-826
- ISSN
- 0097-5397 (ISSN-L)
- 1095-7111
- OpenAlex
- W2245160765
- Cited by
- 898
- References
- 20
- Citations by year
- 2026: 55 · 2025: 93 · 2024: 130 · 2023: 102 · 2022: 102 · 2021: 107 · 2020: 107 · 2019: 63 · 2018: 27 · 2017: 24 · 2016: 33 · 2015: 20 · 2014: 18 · 2013: 11 · 2012: 2
- FWCI
- 9.70
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- SIAM Journal on Computing (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Privacy-Preserving Technologies in Data
- Physical Sciences › Computer Science › Computer Networks and Communications › Cryptography and Data Security
- Physical Sciences › Computer Science › Artificial Intelligence › Machine Learning and Algorithms
- Keywords
- private learning, differential privacy, agnostic learning, sample complexity, parity function, statistical query model
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.