What Can We Learn Privately?
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.
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
Items 101–200 of 1,005
Shuffled 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].”
BackgroundInfluentialA survey of privacy-preserving mechanisms for heterogeneous data types
Cunha, M., Mendes, R., & Vilela, J. P. (2021) · Computer Science Review · doi:10.1016/j.cosrev.2021.100403 · Cited by 102
Faster Algorithms for Privately Releasing Marginals
Thaler, J., Ullman, J., & Vadhan, S. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-31594-7_68 · Cited by 102
“Connections between differentially private data analysis and the statistical queries model have been studied extensively [2, 16, 11].”
BackgroundPrivate-kNN: Practical Differential Privacy for Computer Vision
Zhu, Y., Yu, X., Chandraker, M. K., & Wang, Y.-X. (2020) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr42600.2020.01187 · Cited by 100
“Differentially private machine learning [12, 6] is a burgeoning area of research that aims to train ML models with formal DP guarantees, which ensures no attacker (with arbitrary side information) may distinguish models trained with or without a specific training example, thus, addressing the aforementioned problems.”
BackgroundDifferentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error BoundsPreprint
Bassily, R., Smith, A., & Thakurta, A. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1405.7085 · Cited by 100
“[31]) to run the algorithm for many steps without a significant cost to privacy.”
BackgroundSelf-citationThe structure of optimal private tests for simple hypotheses
Canonne, C. L., Kamath, G., McMillan, A., Smith, A., & Ullman, J. (2019) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3313276.3316336 · Cited by 99
“There are also several rich lines of work attempting to give tight instance-specific characterizations of the sample complexities of various differentially private computations, most notably linear query release [11, 43, 48, 57, 58] and PAC and agnostic learning [10, 39, 46].”
BackgroundSelf-citationSoK: Privacy-Preserving Data Synthesis
Hu, Y., Wu, F., Li, Q., Long, Y., Garrido, G. M., Ge, C., Ding, B., Forsyth, D. A., Li, B., & Song, D. X. (2024) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp54263.2024.00002 · Cited by 99
“…[90, 93, 103, 104] is built upon a series of prior work that lay down the theoretical foundation of differentially private query processing [34, 141], with the goal of privately releasing a synthetic dataset that can accurately answer an assigned workload of linear queries instead of making it…”
BackgroundJoint Privacy Enhancement and Quantization in Federated Learning
Lang, N., Sofer, E., Shaked, T., & Shlezinger, N. (2023) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2023.3244092 · Cited by 97
“Considering a users-server setting, privacy is commonly quantified in terms of DP [45], [46] and LDP [47], [48].”
Privacy Preserving Prompt Engineering: A Survey
Edemacu, K., & Wu, X. (2025) · ACM Computing Surveys · doi:10.1145/3729219 · Cited by 98
“The optimization process in discrete prompts searches for prompts in the discrete text space.”
Privacy of Noisy Stochastic Gradient Descent: More Iterations Without More Privacy Loss
Altschuler, J. M., & Talwar, K. (2022) · neural information processing systems · doi:10.52202/068431-0274 · Cited by 95
Adversarial Learning of Privacy-Preserving and Task-Oriented Representations
Xiao, T., Tsai, Y., Sohn, K., Chandraker, M. K., & Yang, M. (2020) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v34i07.6930 · Cited by 95
Breaking the Communication-Privacy-Accuracy Trilemma
Chen, W., Kairouz, P., & Özgür, A. (2022) · IEEE Transactions on Information Theory · doi:10.1109/tit.2022.3218772 · Cited by 94
“In particular, local differential privacy (LDP) [3], [4], [5], [6] is a widely adopted privacy paradigm, which guarantees that the outcome from a privatization mechanism will not release too much individual information statistically.”
BackgroundSimultaneous Private Learning of Multiple Concepts
Bun, M., Kobbi Nissim, B., & Stemmer, U. (2016) · Conference on Innovations in Theoretical Computer Science · doi:10.1145/2840728.2840747 · Cited by 92
“Most related to our work is the work on private learning and its sample complexity [7, 22, 12, 15, 2, 4, 5, 18, 6, 10] and the early work on sanitization [8].”
BackgroundMethodPrivacy-utility tradeoff under statistical uncertainty
Makhdoumi, A., & Fawaz, N. (2013) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2013.6736724 · Cited by 91
Differential Privacy Dynamics of Langevin Diffusion and Noisy Gradient DescentPreprint
Chourasia, R., Ye, J., & Shokri, R. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2102.05855 · Cited by 91
Wang, Y.-X., Lei, J., & Fienberg, S. E. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1502.06309 · Cited by 74
Differentially Private Federated Learning on Heterogeneous DataPreprint
Noble, M., Bellet, A., & Dieuleveut, A. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2111.09278 · Cited by 91
“A key result in DP is that applying a private algorithm on a random subsample of the dataset amplifies privacy guarantees (Kasiviswanathan et al., 2011).”
BackgroundMethodInfluentialPrivacy-preserving Federated Learning and its application to natural language processing
Nagy, B., Hegedűs, I., Sándor, N., Egedi, B., Mehmood, H., Saravanan, K., Lóki, G., & Kiss, Á. (2023) · Knowledge-Based Systems · doi:10.1016/j.knosys.2023.110475 · Cited by 89
Heavy Hitters and the Structure of Local Privacy
Bun, M., Nelson, J., & Stemmer, U. (2019) · ACM Transactions on Algorithms · doi:10.1145/3344722 · Cited by 89
Distributed K-Means clustering guaranteeing local differential privacy
Xia, C., Hua, J., Tong, W., & Zhong, S. (2019) · Computers & Security · doi:10.1016/j.cose.2019.101699 · Cited by 88
The Role of Interactivity in Local Differential Privacy
Joseph, M., Mao, J., Neel, S., & Roth, A. (2019) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2019.00015 · Cited by 88
“[26], who also gave the first separation between noninteractive locally private protocols and interactive locally private protocols.”
BackgroundPrivate Data Trading Towards Range Counting Queries in Internet of Things
Cai, Z., Zheng, X., Wang, J., & He, Z. (2022) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2022.3164325 · Cited by 87
“Lemma 4.5 generalized from [30] shows the relationship of 0 with p 0 and (cid:2) .”
BackgroundInfluentialChapter 3 Composition of Differential Privacy & Privacy Amplification by Subsampling
Steinke, T. (2025) · Emerald Group Publishing Limited eBooks · doi:10.1561/978-1-63828-477-220251005 · Cited by 87
Wainwright, M. J., Jordan, M. I., & Duchi, J. C. (2012) · neural information processing systems · Cited by 86
BLENDER: Enabling Local Search with a Hybrid Differential Privacy Model
Avent, B., Korolova, A., Zeber, D., Hovden, T., & Livshits, B. (2019) · Journal of Privacy and Confidentiality · doi:10.29012/jpc.680 · Cited by 86
“Furthermore, it is known that for fixed desired differential privacy parameters, the elimination of the trusted data collector comes at the cost of diminished utility [26, 27].”
BackgroundLocal Differential Privacy for Evolving Data
Joseph, M., Roth, A., Ullman, J., & Waggoner, B. (2020) · Journal of Privacy and Confidentiality · doi:10.29012/jpc.718 · Cited by 64
Evading the Curse of Dimensionality in Unconstrained Private GLMs
Song, S., Steinke, T., Thakkar, O. D., & Thakurta, A. (2021) · International Conference on Artificial Intelligence and Statistics · Cited by 82
Fingerprinting Codes and the Price of Approximate Differential Privacy
Bun, M., Ullman, J., & Vadhan, S. (2018) · SIAM Journal on Computing · doi:10.1137/15m1033587 · Cited by 81
Privacy Amplification by Iteration
Feldman, V., Mironov, I., Talwar, K., & Thakurta, A. (2018) · 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) · doi:10.1109/focs.2018.00056 · Cited by 80
“, [3], [8]) require that either data be stored centrally (thus eliminating local differential privacy guarantees) or all-to-all communications.”
BackgroundMethodInfluentialDifferential Privacy on Finite Computers
Balcer, V., & Vadhan, S. (2019) · Journal of Privacy and Confidentiality · doi:10.29012/jpc.679 · Cited by 80
PSI (Ψ): a Private data Sharing InterfacePreprint
Gaboardi, M., Honaker, J., King, G., Murtagh, J., Kobbi Nissim, B., Ullman, J., & Vadhan, S. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1609.04340 · Cited by 80
“1 (Secrecy of the sample [37, 61]) LetM be an ( , δ)-differentially private algorithm for datasets of size n.”
BackgroundSecure Byzantine-Robust Machine LearningPreprint
He, L., Karimireddy, S. P., & Jaggi, M. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2006.04747 · Cited by 81
“On the other hand, local differential privacy (LDP) [12, 18] is stronger notions which is also concerned with the training process itself.”
BackgroundInferDPT: Privacy-Preserving Inference for Closed-Box Large Language Models
Tong, M., Chen, K., Zhang, J., Qi, Y., Zhang, W., Yu, N., Zhang, T., & Zhang, Z. (2025) · IEEE Transactions on Dependable and Secure Computing · doi:10.1109/tdsc.2025.3550389 · Cited by 78
“Definition 1 ( ε -Local Differential Privacy [24]): In ε -LDP, given a privacy parameter ε ≥ 0 , a randomized mechanism M is ε -LDP compliant if it satisfies the following condition for any two inputs x, x (cid:7) ∈ X and any possible output y ∈ Y : Typically, a smaller value of ε provides higher…”
Local Differential Privacy: a tutorialPreprint
Bebensee, B. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1907.11908 · Cited by 78
“Local Differential Privacy (LDP) was first formalized in [17] although an equivalent definition under the name “amplification” had already been introduced by [15].”
Joint Distribution Estimation and Naïve Bayes Classification Under Local Differential Privacy
Xue, Q., Zhu, Y., & Wang, J. (2019) · IEEE Transactions on Emerging Topics in Computing · doi:10.1109/tetc.2019.2959581 · Cited by 77
A Utility-Optimized Framework for Personalized Private Histogram Estimation
Nie, Y., Yang, W., Huang, L., Xie, X., Zhao, Z., & Wang, S. (2018) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2018.2841360 · Cited by 77
“Local differential privacy (LDP) [1] is a de facto concept to defend user privacy without any reliance on trusted thirdparties.”
BackgroundThe Fundamental Price of Secure Aggregation in Differentially Private Federated LearningPreprint
Chen, W., Choquette-Choo, C. A., Kairouz, P., & Suresh, A. T. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2203.03761 · Cited by 77
“Thus, local DP suffers from worse privacy-utility tarde-offs (Kasiviswanathan et al., 2011; Duchi et al., 2013; Kairouz et al., 2016).”
InfluentialStability Is Stable: Connections between Replicability, Privacy, and Adaptive Generalization
Bun, M., Gaboardi, M., Hopkins, M., Impagliazzo, R., Lei, R., Pitassi, T., Sivakumar, S., & Sorrell, J. (2023) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3564246.3585246 · Cited by 76
SecGNN: Privacy-Preserving Graph Neural Network Training and Inference as a Cloud Service
Wang, S., Zheng, Y., & Jia, X. (2023) · IEEE Transactions on Services Computing · doi:10.1109/tsc.2023.3241615 · Cited by 75
“Specifically, we observe that local differential privacy (LDP) [74] and dummy edges padding are promising techniques, of which the blueprint is as follows.”
BackgroundInfluentialClustering Algorithms for the Centralized and Local ModelsPreprint
Kobbi Nissim, B., & Stemmer, U. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1707.04766 · Cited by 75
Private Graph Data Release: A Survey
Li, Y., Purcell, M., Rakotoarivelo, T., Smith, D. B., Ranbaduge, T., & Ng, K. S. (2023) · ACM Computing Surveys · doi:10.1145/3569085 · Cited by 74
Privacy-Preserving In-Context Learning with Differentially Private Few-Shot Generation
Tang, X., Shin, R., Inan, H. A., Manoel, A., Mireshghallah, F., Lin, Z., Gopi, S., Kulkarni, J., & Sim, R. (2023) · International Conference on Learning Representations · doi:10.48550/arxiv.2309.11765 · Cited by 75
“Due to the sheer amount of experiments with 5 rounds each, we fix the dataset to DBPedia in our ablation studies.”
MethodFisher Information Under Local Differential Privacy
Barnes, L. P., Chen, W., & Özgür, A. (2020) · IEEE Journal on Selected Areas in Information Theory · doi:10.1109/jsait.2020.3039461 · Cited by 73
“INTRODUCTION IN THE model of local differential privacy [1], [2], [3], [4], sensitive data is released to an aggregator or centralized processor only after having been processed by a privatization mechanism.”
BackgroundLearning Fair Graph Neural Networks with Limited and Private Sensitive Attribute Information
Dai, E., & Wang, S. (2022) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2022.3197554 · Cited by 73
“Formally, the local differential privacy is defined as follows: Definition 3 ( (cid:2) -Local Differential Privacy [17]).”
BackgroundInfluentialYang, M., Zhu, T., Liu, B., Xiang, Y., & Zhou, W. (2018) · IEEE Access · doi:10.1109/access.2018.2817523 · Cited by 73
“Lemma 1 (Sums of Laplace Random Variables [15]): Let λ 1 , λ 2 , . . . , λ m be a set of independent random variables drawn from Laplace ( σ ).”
BackgroundMethodInfluentialEffects of Differential Privacy and Data Skewness on Membership Inference Vulnerability
Truex, S., Liu, L., Gürsoy, M. E., Wei, W., & Yu, L. (2019) · IEEE International Conference on Trust, Privacy and Security in Intelligent Systems and Applications (TPS-ISA) · doi:10.1109/tps-isa48467.2019.00019 · Cited by 73
“Lt is randomly sampled from D then additional properties of random sampling [20], [21] may be applied.”
BackgroundFederated Heavy Hitters Discovery with Differential PrivacyPreprint
Zhu, W., Kairouz, P., McMahan, H. B., Sun, H., & Li, W. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1902.08534 · Cited by 73
“, assumes that the users do not have any trust in the service provider (Kasiviswanathan et al., 2011).”
BackgroundMethodPosition: Considerations for Differentially Private Learning with Large-Scale Public PretrainingPreprint
Tramèr, F., Kamath, G., & Carlini, N. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2212.06470 · Cited by 73
Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
Beimel, A., Nissim, K., & Stemmer, U. (2013) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-40328-6_26 · Cited by 72
Privacy Profiles and Amplification by Subsampling
Balle, B., Barthe, G., & Gaboardi, M. (2020) · Journal of Privacy and Confidentiality · doi:10.29012/jpc.726 · Cited by 71
“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.”
BackgroundMethodInfluentialThe Dynamic Privacy-Preserving Mechanisms for Online Dynamic Social Networks
Zhu, T., Li, J., Hu, X., Xiong, P., & Zhou, W. (2020) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2020.3015835 · Cited by 71
Minimax Filter: Learning to Preserve Privacy from Inference Attacks
Hamm, J. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1610.03577 · Cited by 45
DISCO: Dynamic and Invariant Sensitive Channel Obfuscation for deep neural networks
Singh, A., Chopra, A., Garza, E., Zhang, E., Vepakomma, P., Sharma, V., & Raskar, R. (2021) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr46437.2021.01195 · Cited by 70
“These mechanisms are sometimes built under the framework of differential privacy [16] or its derivatives [64, 65].”
Answering multi-dimensional range queries under local differential privacy
Yang, J., Wang, T., Li, N., Cheng, X., & Su, S. (2020) · Proceedings of the VLDB Endowment · doi:10.14778/3430915.3430927 · Cited by 70
LDP-Fed: Federated Learning with Local Differential PrivacyPreprint
Truex, S., Liu, L., Chow, K.-H., Gürsoy, M. E., & Wei, W. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2006.03637 · Cited by 70
“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.”
BackgroundSei, Y., & Ohsuga, A. (2016) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2016.2632069 · Cited by 69
“[7] show that this definition can be applied to anonymized data collection.”
BackgroundEnhancing Privacy via Hierarchical Federated Learning
Wainakh, A., Guinea, A. S., Grube, T., & Mühlhäuser, M. (2020) · IEEE European Symposium on Security and Privacy Workshops (EuroS&PW) · doi:10.1109/eurospw51379.2020.00053 · Cited by 69
“That is, the trade-off between privacy and accuracy needs to be considered [12].”
BackgroundBun, M., Kamath, G., Steinke, T., & Wu, Z. S. (2021) · IEEE Transactions on Information Theory · doi:10.1109/tit.2021.3049802 · Cited by 69
“We describe an application of our results to the task of binary classification, as modeled by differentially private PAC learning [88].”
BackgroundMethodDifferentially private inference via noisy optimization
Avella-Medina, M., Bradshaw, C., & Loh, P. (2023) · The Annals of Statistics · doi:10.1214/23-aos2321 · Cited by 68
On the Rényi Differential Privacy of the Shuffle Model
Girgis, A. M., Data, D., Diggavi, S. N., Suresh, A. T., & Kairouz, P. (2021) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/3460120.3484794 · Cited by 68
Differentially Private k-Means with Constant Multiplicative ErrorPreprint
Kaplan, H. Y., & Stemmer, U. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1804.08001 · Cited by 68
Decepticons: Corrupted Transformers Breach Privacy in Federated Learning for Language ModelsPreprint
Fowl, L., Geiping, J., Reich, S., Wen, Y., Czaja, W., Goldblum, M., & Goldstein, T. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2201.12675 · Cited by 68
“Local DP does come at a cost in utility, observed in theoretical (Kairouz et al., 2021b; Kasiviswanathan et al., 2011; Ullman, 2021) as well as practical investigations (Jayaraman & Evans, 2019) when a model is pretrained from scratch (Li et al., 2022; Noble et al., 2022).”
BackgroundCGM: an enhanced mechanism for streaming data collection with local differential privacy
Bao, E., Yang, Y., Xiao, X., & Ding, B. (2021) · Proceedings of the VLDB Endowment · doi:10.14778/3476249.3476277 · Cited by 66
Locating a Small Cluster Privately
Nissim, K., Stemmer, U., & Vadhan, S. (2016) · ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS) · doi:10.1145/2902251.2902296 · Cited by 66
“We will use the following lemma to argue that the random subsampling step maintains privacy: Lemma 6.4 ([13, 4]) .”
MethodInfluentialUnified Lower Bounds for Interactive High-dimensional Estimation under Information Constraints
Acharya, J., Canonne, C. L., Sun, Z., & Tyagi, H. (2023) · neural information processing systems · doi:10.52202/075280-2226 · Cited by 65
Graph neural networks: a survey on the links between privacy and security
Guan, F., Zhu, T., Zhou, W., & Choo, K. R. (2024) · Artificial Intelligence Review · doi:10.1007/s10462-023-10656-4 · Cited by 66
The Value of Privacy: Strategic Data Subjects, Incentive Mechanisms and Fundamental Limits
Wang, W., Ying, L., & Zhang, J. (2016) · ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS) · doi:10.1145/2896377.2901461 · Cited by 65
“We quantify the privacy loss incurred when a strategy is in use by the level of (local) differential privacy [8, 7, 19, 9] of the strategy, defined as follows.”
BackgroundMethodHow Much Privacy Does Federated Learning with Secure Aggregation Guarantee?
Elkordy, A. R., Zhang, J., Ezzeldin, Y. H., Psounis, K., & Avestimehr, S. (2023) · Proceedings on Privacy Enhancing Technologies · doi:10.56553/popets-2023-0030 · Cited by 64
PLDP-FL: Federated Learning with Personalized Local Differential Privacy
Shen, X., Jiang, H., Chen, Y., Wang, B., & Gao, L. (2023) · Entropy · doi:10.3390/e25030485 · Cited by 64
“Definition 1 (( (cid:101) -LDP) [36]) .”
Locally Private k -Means Clustering
Stemmer, U. (2019) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611975994.33 · Cited by 64
Private and Online Learnability Are Equivalent
Alon, N., Bun, M., Livni, R., Malliaris, M., & Moran, S. (2022) · Journal of the ACM · doi:10.1145/3526074 · Cited by 63
“We study these questions in the private PAC model [57, 78], which captures binary classification tasks under DP.”
BackgroundMethodInfluentialMitigating privacy risks in Retrieval-Augmented Generation via locally private entity perturbation
He, L., Tang, P., Zhang, Y., Zhou, P., & Su, S. (2025) · Information Processing & Management · doi:10.1016/j.ipm.2025.104150 · Cited by 63
Differentially Private Ordinary Least Squares
Sheffet, O. (2019) · Journal of Privacy and Confidentiality · doi:10.29012/jpc.654 · Cited by 63
“…the first differentially private algorithms were machine learning algorithms, with a special emphasis on the ubiquitous problem of linear regression (Kasiviswanathan et al., 2008; Chaudhuri et al., 2011; Kifer et al., 2012; Bass-1 Computing Science Dept., University of Alberta, Edmonton AB, Canada.”
MethodDifferential Privacy for Data and Model Publishing of Medical Data
Sun, Z., Wang, Y., Shu, M., Liu, R., & Zhao, H. (2019) · IEEE Access · doi:10.1109/access.2019.2947295 · Cited by 56
“The research on differential privacy can generally be divided into two directions: one is data publishing under privacy protection [13], [18], [35]–[45]; the other is privacy protection for machine learning [29], [40], [46]–[54].”
BackgroundSecure Multi-party Computation of Differentially Private Heavy Hitters
Böhler, J., & Kerschbaum, F. (2021) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/3460120.3484557 · Cited by 63
“To create the LDP reports, a client first reduces the domain size to 𝑢 = ⌈exp(𝜖) + 1⌉ via optimal local hashing [77], then applies generalized randomized response on the value from the reduced domain (which returns the input with probability exp(𝜖)exp(𝜖)+𝑢−1 and any other domain value with equal probability).”
BackgroundMethodInfluentialPrivKVM*: Revisiting Key-Value Statistics Estimation With Local Differential Privacy
Ye, Q., Hu, H., Meng, X., Zheng, H., Huang, K., Fang, C., & Shi, J. (2021) · IEEE Transactions on Dependable and Secure Computing · doi:10.1109/tdsc.2021.3107512 · Cited by 63
“As for the local setting , i.e., scenarios without such a collector, local differential privacy (LDP) [3], [24], [25] was proposed as a new and promising framework for private data collection and analysis.”
BackgroundAHEAD: Adaptive Hierarchical Decomposition for Range Query under Local Differential Privacy
Du, L., Zhang, Z., Bai, S., Liu, C., Ji, S., Cheng, P., & Chen, J. (2021) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/3460120.3485668 · Cited by 62
Privately Solving Linear Programs
Hsu, J., Roth, A., Roughgarden, T., & Ullman, J. (2014) · Lecture notes in computer science · doi:10.1007/978-3-662-43948-7_51 · Cited by 62
“[19] show how to privately PAC learn any PAC learnable concept class (without privacy) with only a small increase in the sample complexity, but via an exponential time algorithm.”
BackgroundMethodA General Characterization of the Statistical Query ComplexityPreprint
Feldman, V. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1608.02198 · Cited by 62
“Further, access to an SQ oracle is known to be equivalent (up to polynomial factors) to local differential privacy model (Kasiviswanathan et al., 2011) that has received much recent attention in industry (Erlingsson et al.”
BackgroundCommunication Complexity in Locally Private Distribution Estimation and Heavy HittersPreprint
Acharya, J., & Sun, Z. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1905.11888 · Cited by 62
“A popular privacy definition is local differential privacy (LDP), which was perhaps first proposed in (Warner, 1965), and more recently in (Beimel et al., 2008; Kasiviswanathan et al., 2011), where users do not trust the data collector, and privatize their data before releasing.”
BackgroundSubject Membership Inference Attacks in Federated LearningPreprint
Suri, A., Kanani, P. H., Marathe, V. J., & Peterson, D. W. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2206.03317 · Cited by 62
Dual Query: Practical Private Query Release for High Dimensional Data
Gaboardi, M., Arias, E. J. G., Hsu, J., Roth, A., & Wu, Z. S. (2017) · Journal of Privacy and Confidentiality · doi:10.29012/jpc.v7i2.650 · Cited by 61
Local Differential Privacy for data collection and analysis
Wang, T., Zhao, J., Hu, Z. J., Yang, X., Ren, X., & Lam, K. (2020) · Neurocomputing · doi:10.1016/j.neucom.2020.09.073 · Cited by 61
DP-cryptography: marrying differential privacy and cryptography in emerging applications
Wagh, S., He, X., Machanavajjhala, A., & Mittal, P. (2021) · Communications of the ACM · doi:10.1145/3418290 · Cited by 61
“The randomness of these sampling processes can amplify the privacy parameter based on a well studied sub-sampling argument [21, 5].”
BackgroundFederated learning and privacy
Bonawitz, K., Kairouz, P., McMahan, H. B., & Ramage, D. (2022) · Communications of the ACM · doi:10.1145/3500240 · Cited by 61
“Under distributed DP, clients first compute minimal application-specific reports, perturb these slightly with random noise, and then execute a private aggregation protocol.”
BackgroundInfluentialDhulipala, L., Liu, Q. C., Raskhodnikova, S., Shi, J., Shun, J., & Yu, S. (2022) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs54457.2022.00077 · Cited by 60
Self-citationSample Complexity Bounds on Differentially Private Learning via Communication Complexity
Feldman, V., & Xiao, D. (2015) · SIAM Journal on Computing · doi:10.1137/140991844 · Cited by 60
A Differentially Private Text Perturbation Method Using Regularized Mahalanobis Metric
Xu, Z., Aggarwal, A., Feyisetan, O., & Teissier, N. (2020) · doi:10.18653/v1/2020.privatenlp-1.2 · Cited by 60
Adaptive Learning with Robust Generalization GuaranteesPreprint
Cummings, R., Ligett, K., Nissim, K., Roth, A., & Wu, Z. S. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1602.07726 · Cited by 60
Robust Privacy-Utility Tradeoffs Under Differential Privacy and Hamming Distortion
Kalantari, K., Sankar, L., & Sarwate, A. D. (2018) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2018.2831619 · Cited by 59
“[26], which was based on the randomized response mechanism of Warner [24] and Evfimievski et al.”
MethodTowards Differentially Private Truth Discovery for Crowd Sensing Systems
Li, Y., Xiao, H., Qin, Z., Miao, C., Su, L., Gao, J., Ren, K., & Ding, B. (2020) · IEEE International Conference on Distributed Computing Systems (ICDCS) · doi:10.1109/icdcs47774.2020.00037 · Cited by 59
“Among the related work of differential privacy, distributed differential privacy [35], [36] shares some similarity with our work, and it enables individual information sources to add noise separately.”
BackgroundLearning discrete distributions: user vs item-level privacyPreprint
Liu, Y., Suresh, A. T., Yu, F., Kumar, S., & Riley, M. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2007.13660 · Cited by 58
“Differential privacy is studied in two scenarios, local differential privacy [Kasiviswanathan et al., 2011, Duchi et al., 2013], and global differential privacy [Dwork et al., 2006].”
BackgroundLearning to Invert: Simple Adaptive Attacks for Gradient Inversion in Federated LearningPreprint
Wu, R., Chen, X., Guo, C., & Weinberger, K. Q. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2210.10880 · Cited by 58
“A Gaussian random vector N ( 0 , σ 2 I ) is added to the gradient, which one can show achieves ϵ -local differential privacy [Kasiviswanathan et al., 2011] with ϵ = O (1 /σ ) .”
BackgroundBetween Privacy and Utility: On Differential Privacy in Theory and Practice
Seeman, J., & Susser, D. (2022) · ACM Journal on Responsible Computing · doi:10.1145/3626494 · Cited by 58
“The conventional łcentral" model of DP assumes a trustworthy data aggregator, but othersÐsuch as local DP [25, 37] and distributed DP via shuling [11]Ðdo not.”
BackgroundSecure multi-party differential privacy
Kairouz, P., Oh, S., & Viswanath, P. (2015) · neural information processing systems · Cited by 57
Ko, S., Lee, K., Cho, H., Hwang, Y., & Jang, H. (2023) · Expert Systems with Applications · doi:10.1016/j.eswa.2023.119896 · Cited by 56
Ruan, W., Xu, M., Fang, W., Wang, L., Wang, L., & Han, W. (2023) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp46215.2023.10179422 · Cited by 56
“magnitude larger than that caused by central DP [37], which requires a trusted server to handle all data.”
BackgroundOptimal Differentially Private Algorithms for k-Means Clustering
Huang, Z., & Liu, J. (2018) · ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS) · doi:10.1145/3196959.3196977 · Cited by 56
“How can one learn useful (aggregate) information from users’ data while protecting the privacy of individual? This has been the overarching question in a line of work that study differentially private algorithms in various learning models, including PAC learning [18], SQ learning [3], and general learning [27].”
BackgroundArcolezi, H. H., Couchot, J.-F., Bouna, B. A., & Xiao, X. (2022) · Digital Communications and Networks · doi:10.1016/j.dcan.2022.07.003 · Cited by 55
Saeidian, S., Cervia, G., Oechtering, T. J., & Skoglund, M. (2023) · IEEE Transactions on Information Theory · doi:10.1109/tit.2023.3304378 · Cited by 55
“More specifically, we discuss max-information [43], [44], local differential privacy [5], [6], local information privacy [16], [18], local differential identifiability [9], [21], mutual information, f -information [13], and total variation privacy [14].”
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.