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 701–800 of 1,005
Privacy-Adaptive BERT for Natural Language UnderstandingPreprint
Qu, C., Kong, W., Liu, Y., Zhang, M., Bendersky, M., & Najork, M. (2021) · arXiv (Cornell University) · Cited by 8
The Power of Sampling: Dimension-free Risk Bounds in Private ERMPreprint
Lee, Y. T., Liu, D., & Zhou, L. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2105.13637 · Cited by 8
“The proof is based on the well-known ’secrecy of the sample’ lemma from Kasiviswanathan et al. [2011].”
BackgroundZhu, Y., Zhao, X., Guo, C., & Wang, Y.-X. (2023) · arXiv (Cornell University) · doi:10.48550/arxiv.2306.07381 · Cited by 8
“The predominant setting for private ML is to produce the model learned from sensitive data using DP primitives, a.k.a. private training [Chaudhuri et al., 2011, Kasiviswanathan et al., 2011, Abadi et al., 2016].”
MethodMadl, T., Xu, W., Choudhury, O., & Howard, M. (2023) · arXiv (Cornell University) · doi:10.48550/arxiv.2307.01875 · Cited by 8
“2011) or generating new samples based on the original data distribution (Zhang et al. 2017b; Blum, Ligett, and Roth 2013; Kasiviswanathan et al. 2011; Hardt, Ligett, and McSherry 2012).”
BackgroundMethodShifted Interpolation for Differential PrivacyPreprint
Bok, J., Su, W., & Altschuler, J. M. (2024) · arXiv (Cornell University) · doi:10.48550/arxiv.2403.00278 · Cited by 8
Decision Making in Changing Environments: Robustness, Query-Based Learning, and Differential PrivacyPreprint
Chen, F., & Rakhlin, A. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2501.14928 · Cited by 8
Towards Privacy-preserving Photorealistic Self-avatars in Mixed RealityPreprint
Wilson, E., Bindschaedler, V., Jörg, S., Sheikholeslam, S., Butler, K. R. B., & Jain, E. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2507.22153 · Cited by 8
“Formulations such as differential privacy (DP) are preferable in developing a robust privacy solution [56], [57].”
Statistical Inference in the Differential Privacy ModelPreprint
Zhang, H. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2108.05000 · Cited by 8
Locally Differentially Private Trajectory Publication Based on Regional Popularity Awareness
Zhang, D., Ni, W., Fu, N., Hou, L., & Zhang, R. (2025) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2025.3577967 · Cited by 7
“Local di ff erential privacy (LDP) [3] is a distributed variant of di ff erential privacy [2].”
Continuous Publication of Weighted Graphs with Local Differential Privacy
Xu, W., Qiao, P., Liu, S., Zheng, Z., Cao, Y., & Li, Z. (2025) · Proceedings of the VLDB Endowment · doi:10.14778/3749646.3749688 · Cited by 7
“Local differential privacy (LDP) [7, 20] is a strong privacy-preserving technique that can be used to collect sensitive data from users in a decentralized network without a complete central database.”
The Gaussian Mixing Mechanism: Renyi Differential Privacy via Gaussian Sketches
Lev, O., Srinivasan, V., Shenfeld, M., Ligett, K., Sekhari, A., & Wilson, A. (2025) · neural information processing systems · doi:10.52202/085713-1690 · Cited by 7
Optimizing Privacy-Utility Trade-off in Decentralized Learning with Generalized Correlated Noise
Rodio, A., Chen, Z., & Larsson, E. G. (2025) · IEEE Information Theory Workshop (ITW) · doi:10.1109/itw62417.2025.11240322 · Cited by 7
“A classical LDP mechanism is presented in [13].”
Preserving Privacy in the Age of Wireless Evolution: Differential Privacy in 5G, Beyond 5G, and 6G
Sanon, S. P., Lipps, C., & Schotten, H. D. (2023) · International Conference on Future Communications and Networks (FCN) · doi:10.1109/fcn60432.2023.10543856 · Cited by 7
“DP can be classified into two distinct categories: Local Differential Privacy (LDP) [20] and Global Differential Privacy (GDP) [21].”
BackgroundRamsey Theorems for Trees and a General ‘Private Learning Implies Online Learning’ Theorem
Fioravanti, S., Hanneke, S., Moran, S., Schefler, H., & Tsubari, I. (2024) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs61266.2024.00119 · Cited by 7
“: Recently, Ramsey theory has been employed to prove impossibility results in the differentially private PAC learning (or DP learning) model [41], merging the requirements of differential privacy [23] with the ones of classical PAC learning [55].”
Aydin, S., & Yıldırım, S. (2024) · ACM Transactions on Knowledge Discovery from Data · doi:10.1145/3706584 · Cited by 7
“Hence LDP can be said to provide a stricter form of privacy and is used in cases where the aggregator may not be trustable (Kasiviswanathan et al., 2011).”
Rokvic, L., Danassis, P., Karimireddy, S. P., & Faltings, B. V. (2024) · IEEE International Conference on Big Data (BigData) · doi:10.1109/bigdata62323.2024.10825097 · Cited by 7
“A variation of DP, instrumental in our context, given the decentralized nature of federated learning, is Local Differential Privacy (LDP) [21], [34].”
SoK: What Makes Private Learning Unfair?
Yao, K., & Juarez, M. (2025) · IEEE Conference on Secure and Trustworthy Machine Learning (SaTML) · doi:10.1109/satml64287.2025.00052 · Cited by 7
“There are various existing data privacy frameworks, but most PPML algorithms fall within DP, a rigorous mathematical framework that controls the risk of revealing whether an individual’s data is included in the training dataset [1], [29].”
Privacy tradeoffs in predictive analytics
Ioannidis, S., Andrea Montanari, A., Weinsberg, U., Bhagat, S., Fawaz, N., & Taft, N. (2014) · ACM SIGMETRICS Performance Evaluation Review · doi:10.1145/2637364.2592011 · Cited by 7
Local differential privacy for unbalanced multivariate nominal attributes
Feng, X., & Zhang, C. (2020) · Human-centric Computing and Information Sciences · doi:10.1186/s13673-020-00233-x · Cited by 7
“As users, they prefer to ensure data security on the user side, enabling themselves to process and protect their confidential information separately (i.e., local differential privacy [9, 10]).”
BackgroundAlgorithms with More Granular Differential Privacy Guarantees
Ghazi, B., Kumar, R., Manurangsi, P., & Steinke, T. (2022) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.itcs.2023.54 · Cited by 7
Schrödinger Mechanisms: Optimal Differential Privacy Mechanisms for Small Sensitivity
Alghamdi, W., Asoodeh, S., Calmon, F. P., Gomez, J. F., Kosut, O., & Sankar, L. (2023) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit54713.2023.10206616 · Cited by 7
“In particular, we subsample both mechanisms, following standard practice in the DP machine learning community for amplifying privacy [8], [36], [37].”
MethodDifferentially Private Guarantees for Analytics and Machine Learning on Graphs: A Survey of Results
Mueller, T. T., Usynin, D., Paetzold, J. C., Braren, R., Rueckert, D., & Kaissis, G. A. (2024) · Journal of Privacy and Confidentiality · doi:10.29012/jpc.820 · Cited by 7
Decentralized Privacy Preservation for Critical Connections in Graphs
Li, C., Ni, W., Ding, M., Qu, Y., Chen, J., Smith, D. B., Zhang, W., & Rakotoarivelo, T. (2024) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2024.3406641 · Cited by 7
“Answering questions related to graphs under LDP requires to collect information from individuals [40], which may ruin the property (lower the data utility) of the raw graph [37].”
BackgroundPractical Two-party Computational Differential Privacy with Active Security
Meisingseth, F., Rechberger, C., & Schmid, F. (2024) · Proceedings on Privacy Enhancing Technologies · doi:10.56553/popets-2025-0019 · Cited by 7
Exactly Minimax-Optimal Locally Differentially Private Sampling
Park, H.-Y., Asoodeh, S., & Lee, S.-H. (2024) · neural information processing systems · doi:10.52202/079017-0329 · Cited by 7
“Among these, local differential privacy (LDP) [5] stands out as a standard model and has been deployed in industry, e.g., by Google [6, 7], Apple [8], Microsoft [9].”
Locally Differentially Private In-Context Learning
Zheng, C., Sun, K., Zhao, W., Zhou, H., Jiang, L., Song, S., & Zhou, C. (2024) · Language Resources and Evaluation Conference (LREC) · doi:10.63317/4s5kvtse3mzz · Cited by 7
Private Everlasting Prediction
Naor, M., Kobbi Nissim, B., Stemmer, U., & Yan, C. (2023) · neural information processing systems · doi:10.52202/075280-2390 · Cited by 7
Bounded privacy-utility monotonicity indicating bounded tradeoff of differential privacy mechanisms
Liu, H., Wu, Z., Peng, C., Tian, F., & Lu, L. (2020) · Theoretical Computer Science · doi:10.1016/j.tcs.2020.02.004 · Cited by 7
Chaturvedi, A., Jones, M., & Nguyễn, H. L. (2022) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v36i6.20565 · Cited by 7
Differential Privacy-Preserving User Linkage across Online Social Networks
Yao, X., Zhang, R., & Zhang, Y. (2021) · International Workshop on Quality of Service · doi:10.1109/iwqos52092.2021.9521333 · Cited by 7
“Recently, Local Differential Privacy (LDP) [13] has been widely recognized as a strong and mathematically rigorous privacy-preserving framework and has found success in many statistic problems [14]–[23].”
BackgroundBarua, E., & Dutta, M. (2024) · International Journal of Computers and Applications · doi:10.1080/1206212x.2024.2307086 · Cited by 7
“By Kasiviswanathan et al., it was formalized in the context of learning [41].”
BackgroundTraining Generative Models From Privatized Data via Entropic Optimal Transport
Reshetova, D., Chen, W., & Özgür, A. (2024) · IEEE Journal on Selected Areas in Information Theory · doi:10.1109/jsait.2024.3387463 · Cited by 7
“The understanding of learning problems under LDP constraints is relatively limited, and even less so in the non-interactive setting when the data is accessed only once, which can be exponentially harder to train as shown in Kasiviswanathan et al. [2011], Bhowmick et al. [2018]. The exploration of differentially privat…”
BackgroundInfluentialPROVGEN: A Privacy-Preserving Approach for Outcome Validation in Genomic Research
Jiang, Y., Ji, T., & Ayday, E. (2026) · Proceedings on Privacy Enhancing Technologies · doi:10.56553/popets-2026-0064 · Cited by 7
Large Margin Multiclass Gaussian Classification with Differential Privacy
Pathak, M. A., & Raj, B. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-19896-0_9 · Cited by 7
“[5] present a framework for converting a general agnostic PAC learning algorithm to an algorithm that satisfies privacy constraints.”
BackgroundMethodLearning, cryptography, and the average case
Servedio, R. A., Malkin, T., & Wan, A. (2010) · Cited by 7
Differentially Private Recommender System with Autoencoders
Liu, X., Li, Q., Ni, Z., & Hou, J. (2019) · IEEE International Conference on Internet of Things (iThings) and IEEE Green Computing and Communications (GreenCom) and IEEE Cyber, Physical and Social Computing (CPSCom) and IEEE Smart Data (SmartData) · doi:10.1109/ithings/greencom/cpscom/smartdata.2019.00094 · Cited by 7
“According to privacy amplification theorem [39], [40], since sampling has introduced randomness, the privacy of the original privacy Algorithm 2 Privacy preserving recommendation algorithm based on autoencoder 1: Input: user rating vector u1,u2, .”
BackgroundThe Privacy Funnel from the viewpoint of Local Differential PrivacyPreprint
Lopuhaä-Zwakenberg, M. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2002.01501 · Cited by 7
“The first one is an adaptation of Local Differential Privacy (LDP), the de facto standard in information privacy [11]:”
BackgroundOptimal Rates for Learning Hidden Tree StructuresPreprint
Nikolakakis, K. E., Kalogerias, D. S., & Sarwate, A. D. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1909.09596 · Cited by 7
“One recent application domain is the analysis of data protected by local differential privacy [9, 10, 11, 12, 13, 14].”
BackgroundAdaptive Differentially Private Empirical Risk MinimizationPreprint
Wu, X., Wang, L., Cristali, I., Gu, Q., & Willett, R. M. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2110.07435 · Cited by 7
LDP-FPMiner: FP-Tree Based Frequent Itemset Mining with Local Differential PrivacyPreprint
Chen, Z., & Wang, J. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2209.01333 · Cited by 7
“Generally, there are two types of differential privacy - centralized differential privacy (CDP)[8] and local differential privacy (LDP)[20], and the focus of this work is the local setting.”
BackgroundUser Customizable and Robust Geo-Indistinguishability for Location PrivacyPreprint
Pappachan, P., Chenxi, Q., Squicciarini, A., & Manjunath, V. S. H. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2206.08396 · Cited by 7
“Local Differential Privacy (LDP) has recently emerged as an approach to avoid using a centralized server and perturb users’ data locally before it leaves their device [15].”
BackgroundGao, C., Lowy, A. M., Zhou, X., & Wright, S. J. (2024) · arXiv (Cornell University) · doi:10.48550/arxiv.2407.09690 · Cited by 7
“Moreover, we do not require smoothness of the loss function to attain the optimal rate: see Theorem 3.1.”
BackgroundInfluentialA Unified Theoretical Analysis of Private and Robust Offline Alignment: from RLHF to DPOPreprint
Zhou, X., Wu, Y., & Orabona, F. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2505.15694 · Cited by 7
“Corruption-then-LDP (CTL) : An adversary first corrupts the labels in D to ¯ y i .”
InfluentialOttun, A.-R. O., & Flores, H. (2025) · doi:10.36227/techrxiv.176118749.93102582/v1 · Cited by 6
Shuffled Differentially Private Federated Learning for Time Series Data Analytics
Huang, C., Jiang, C., & Chen, Z. (2023) · IEEE Conference on Industrial Electronics and Applications (ICIEA) · doi:10.1109/iciea58696.2023.10241529 · Cited by 6
“We also introduce shuffle mechanisms that satisfy LDP while enhancing utility, resulting in privacy amplification [9] [10].”
MethodGeneral inferential limits under differential and Pufferfish privacy
Bailie, J., & Gong, R. (2024) · International Journal of Approximate Reasoning · doi:10.1016/j.ijar.2024.109242 · Cited by 6
Local Differential Privacy for correlated location data release in ITS
Chong, K. M., & Malip, A. (2024) · Computer Networks · doi:10.1016/j.comnet.2024.110830 · Cited by 6
DP-FedCMRS: Privacy-Preserving Federated Learning Algorithm to Solve Heterogeneous Data
Zhang, Y., Long, S., Liu, G., & Zhang, J. (2025) · IEEE Access · doi:10.1109/access.2025.3546473 · Cited by 6
“LDP was implicitly introduced by Evfimievski et al. [26] and Dwork et al [27], and was first formalized by Kasiviswanathan et al. [28].”
PAUSE: Low-Latency and Privacy-Aware Active User Selection for Federated Learning
Peleg, O., Lang, N., Ben-Ami, D., Rini, S., Shlezinger, N., & Cohen, K. (2025) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2025.3627252 · Cited by 6
“In FL, privacy is commonly quantified in terms of LDP [54], [55], as this metric assumes an untrusted server by the users.”
A Sensitivity-Driven Framework for Privacy-Preserving Big Data Publishing: The CAG+RAG Approach
Rao, K. R., Nandan, D., & Satyanarayana, S. (2025) · Advances in engineering research/Advances in Engineering Research · doi:10.2991/978-94-6463-978-0_17 · Cited by 6
Zeng, Y., Long, S., Liu, H., & Ding, H. (2022) · Security and Communication Networks · doi:10.1155/2022/9127412 · Cited by 6
“In this context, Local Differential Privacy (LDP) [2] has been proposed as a variant of DP.”
BackgroundDistributed Linear Bandits With Differential Privacy
Li, F., Zhou, X., & Ji, B. (2024) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2024.3362978 · Cited by 6
“…instead of only considering ,wewillalsoincorporateotherpopularDP models,includingthestrongerlocalmodel(whereeachclient directlyprotectsherdata)[16]andtherecentlyproposedshuffle model(whereatrustedshufflerbetweenclientsandserver isadoptedtoamplifyprivacy)[17],inaunifiedalgorithmic…”
BackgroundDifferential Private Identification Protection for Face Images
Wen, Y., Liu, B., Song, L., Cao, J., & Xie, R. (2024) · Springer eBooks · doi:10.1007/978-3-031-58222-6_5 · Cited by 6
Optimal Locally Private Data Stream Analytics
Wang, S., Peng, Y., Chen, K., & Yang, W. (2024) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infocom52122.2024.10621194 · Cited by 6
“Definition 1 (Local ϵ -DP [9]): Let D K denote the output domain, a randomized mechanism K satisfies local ϵ - differential privacy iff for any data pair x , x ′ ∈ { 0 , 1 } d × T , and any outputs z ∈ D K , Exponential Mechanism.”
BackgroundMethodProtecting Infinite Data Streams from Wearable Devices with Local Differential Privacy Techniques
Zhao, F., & Fan, S. (2024) · Information · doi:10.3390/info15100630 · Cited by 6
Privacy protection against user profiling through optimal data generalization
Gil, C., Parra‐Arnau, J., & Forné, J. (2024) · Computers & Security · doi:10.1016/j.cose.2024.104178 · Cited by 6
PriFairFed: A Local Differentially Private Federated Learning Algorithm for Client-Level Fairness
Hu, C., Wu, N., Shi, S., Liu, X., Luo, B., Wang, K. Y., Jiang, J., & Cheng, D. (2024) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2024.3516813 · Cited by 6
“To protect private local data, Local Differential Privacy (LDP), first formalized in [3], perturbs data or gradients locally with rigorously designed noise before sending them to the central server.”
Predictable and Consistent Information Extraction
Kassaie, B., & Tompa, F. W. (2019) · ACM Symposium on Document Engineering (DocEng) · doi:10.1145/3342558.3345391 · Cited by 6
A study of event frequency profiling with differential privacy
Zhang, H., Hao, Y., Latif, S., Bassily, R., & Rountev, A. (2020) · doi:10.1145/3377555.3377887 · Cited by 6
“There exists a large body of work on differential privacy in the context of distribution estimation [14], clustering [33], heavy hitters [5, 9], learning [25], and convex optimization [39].”
BackgroundEnhancing Utility In The Watchdog Privacy Mechanism
Zarrabian, M. A., Ding, N., Sadeghi, P., & Rakotoarivelo, T. (2022) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp43922.2022.9747673 · Cited by 6
Tight Bounds for Differentially Private Anonymized Histograms
Manurangsi, P. (2022) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611977066.14 · Cited by 6
dK-Personalization: Publishing Network Statistics with Personalized Differential Privacy
Iftikhar, M., Wang, Q., & Li, Y. (2022) · Lecture notes in computer science · doi:10.1007/978-3-031-05933-9_16 · Cited by 6
Robust Optimization for Local Differential Privacy
Goseling, J., & Lopuhaä-Zwakenberg, M. (2022) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit50566.2022.9834796 · Cited by 6
Calibration with Privacy in Peer Review
Ding, W., Kamath, G., Wang, W., & Shah, N. B. (2022) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit50566.2022.9834716 · Cited by 6
Disclosure Risk From Homogeneity Attack in Differentially Privately Sanitized Frequency Distribution
Liu, F., & Zhao, X. (2022) · IEEE Transactions on Dependable and Secure Computing · doi:10.1109/tdsc.2022.3220592 · Cited by 6
“principles [8], [9], [10], [11], [12], making it attractive and”
BackgroundTowards Measuring Fairness for Local Differential Privacy
Salas, J., Torra, V., & Megías, D. (2023) · Lecture notes in computer science · doi:10.1007/978-3-031-25734-6_2 · Cited by 6
MPC for Tech Giants (GMPC): Enabling Gulliver and the Lilliputians to Cooperate Amicably
Alon, B., Naor, M., Omri, E., & Stemmer, U. (2024) · Lecture notes in computer science · doi:10.1007/978-3-031-68397-8_3 · Cited by 6
Zhao, P., Zhang, K., Zhang, H., & Chen, H. (2024) · Expert Systems with Applications · doi:10.1016/j.eswa.2024.125279 · Cited by 6
Collecting Spatial Data Under Local Differential Privacy
Ye, Y., Zhang, M., & Feng, D. (2021) · International Conference on Mobility, Sensing and Networking (MSN) · doi:10.1109/msn53354.2021.00032 · Cited by 6
Exponential Separations in Local Privacy
Joseph, M., Mao, J., & Roth, A. (2022) · ACM Transactions on Algorithms · doi:10.1145/3459095 · Cited by 6
“(1) It has been known since Kasiviswanathan et al. [21] that the query complexity of locally private protocols is polynomially related to the query complexity of algorithms in the statistical query model from learning theory [22], for which there are a number of lower bounds.”
BackgroundMethodInfluentialpMSE Mechanism: Differentially Private Synthetic Data with Maximal Distributional SimilarityPreprint
Snoke, J., & Slavković, A. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1805.09392 · Cited by 6
“It has been explored in numerous contexts such as machine learning algorithms (e.g., Blum et al. (2005); Kasiviswanathan et al. (2011); Kifer et al. (2012)), categorical data (e.g., Barak et al. (2007); Li et al. (2010)), dimension reduction (e.g., Chaudhuri et al. (2012); Kapralov and Talwar…”
BackgroundTask-aware Privacy Preservation for Multi-dimensional DataPreprint
Cheng, J., Tang, A., & Chinchali, S. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2110.02329 · Cited by 6
“-LDP (Kasiviswanathan et al., 2011).”
InfluentialLocal Differential Privacy-Preserving Spectral Clustering for General GraphsPreprint
Mukherjee, S., & Suppakitpaisarn, V. (2023) · arXiv (Cornell University) · doi:10.48550/arxiv.2309.06867 · Cited by 6
“In this work, we are interested in a variant of differential privacy called local differential privacy introduced by Kasiviswanathan et al. (2011).”
Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many MessagesPreprint
Asi, H., Feldman, V., Nelson, J., Nguyễn, H. L., Talwar, K., & Zhou, S. (2024) · arXiv (Cornell University) · doi:10.48550/arxiv.2404.10201 · Cited by 6
“In particular, local differential privacy (LDP) [KLN + 11] demands that the distribution of the transcript of the communication protocol cannot be greatly affected by a change in a single distributed user’s input.”
BackgroundSchuchardt, J., Dalirrooyfard, M., Guzelkabaagac, J., Schneider, A., Nevmyvaka, Y., & Günnemann, S. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2502.02410 · Cited by 6
Privacy-Preserving Conformal Prediction Under Local Differential PrivacyPreprint
Penso, C., Mahpud, B., Goldberger, J., & Sheffet, O. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2505.15721 · Cited by 6
“In contrast, LDP (Duchi et al., 2013; Kairouz et al., 2016; Kasiviswanathan et al., 2011) treats the aggregator as untrusted : individual users randomize their own data locally before sending it to the aggregator, thus ensuring strong privacy.”
Data Compression with Relative Entropy Coding
Flamich, G. (2024) · arXiv (Cornell University) · doi:10.17863/cam.118972 · Cited by 6
Concept-Aware Privacy Mechanisms for Defending Embedding Inversion Attacks
Tsai, Y.-C., Hsiao, H., Chen, K.-Y., & Lin, S.-D. (2026) · International Conference on Learning Representations · doi:10.48550/arxiv.2602.07090 · Cited by 6
“To instantiate a mechanism satisfying metric LDP under ℓ 2 distance, we introduce the generalized Laplace mechanism, which is widely used for embedding sanitization against adversarial attacks.”
InfluentialDifferentially Private Language Generation and Identification in the LimitPreprint
Mehrotra, A., Velegkas, G., Yu, X., & Zhou, F. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2604.08504 · Cited by 6
The communication cost of security and privacy in federated frequency estimationPreprint
Chen, W., Özgür, A., Cormode, G., & Bharadwaj, A. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2211.10041 · Cited by 6
“We also distinguish our setup from the local DP setting (Kasiviswanathan et al., 2011; Evfimievski et al., 2004; Warner, 1965), where the data is perturbed on the userside before it is collected by the server.”
MethodWang, S., Zheng, Y., Jia, X., & Hu, H. (2025) · Proceedings of the VLDB Endowment · doi:10.14778/3749646.3749722 · Cited by 5
SoK: Data Minimization in Machine Learning
Staab, R., Jovanović, N., Mai, K. T., Ganesh, P., Vechev, M., Fioretto, F., & Jagielski, M. (2026) · IEEE Conference on Secure and Trustworthy Machine Learning (SaTML) · doi:10.1109/satml68715.2026.00009 · Cited by 6
“It is possible to provide differential privacy guarantees earlier in the data collection process, in both local differential privacy [47] and distributed differential privacy [9], [48].”
Private Learning of Littlestone Classes, Revisited
Lyu, X. (2026) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3798129.3800924 · Cited by 5
Quantum Advantage in Locally Differentially Private Hypothesis Testing
Nam, S.-H., Park, H.-Y., Lee, S.-H., & Bae, J. (2026) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2026.3709807 · Cited by 5
“This identification recovers the original definition for an (cid:15) -LDP mechanism [7], [8], [9].”
Calibrating Privacy Budgets for Locally Private Graph Neural Networks
Du, W., Ma, X., Dong, W., Zhang, D., Zhang, C., & Sun, Q. (2021) · International Conference on Networking and Network Applications (NaNA) · doi:10.1109/nana53684.2021.00012 · Cited by 5
A Federated Data-driven Multiobjective Evolutionary Algorithm via Continual Learnable Clustering
Kinoshita, T., Masuyama, N., & Nojima, Y. (2024) · IEEE Congress on Evolutionary Computation (CEC) · doi:10.1109/cec60901.2024.10611787 · Cited by 5
“3) In addition to the case without noise, we also compare the search performance of MOEAs in the case with noise by local differential privacy [9] in the computational experiments.”
MethodEvaluating the Impact of Local Differential Privacy on Utility Loss via Influence Functions
Carey, A. N., Van, M.-H., & Wu, X. (2024) · International Joint Conference on Neural Networks (IJCNN) · doi:10.1109/ijcnn60899.2024.10651257 · Cited by 5
“Let ϵ represent the privacy parameter in LDP and let P [ · ] denote probability.”
BackgroundWhat to Consider When Considering Differential Privacy for Policy
Nanayakkara, P., & Hullman, J. R. (2024) · Policy Insights from the Behavioral and Brain Sciences · doi:10.1177/23727322241278687 · Cited by 5
“…or the user level) (Dwork et al., 2019); which variation of DP to use; and the deployment model (such as the central model, where raw data are collected and noise added by the curator, or the local model, where data are noised prior to being sent to the curator [Kasiviswanathan et al., 2011]).”
Ye, Q., Yu, L., Huang, K., Xiao, X., Liu, W., & Hu, H. (2025) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp61157.2025.00215 · Cited by 5
“To address these privacy challenges, Local Differential Privacy (LDP) [9], [20] has emerged as the predominant privacy model in many large-scale distributed systems, used by tech giants such as Apple [26], Google [15] and Microsoft [6], to protect end users’ data.”
PoisonCatcher: Revealing and Identifying LDP Poisoning Attacks in IIoT
Shuai, L., Tan, S., Zhang, N., Zhang, J., Zhang, M., Dong, G., & Yang, X. (2025) · IEEE Internet of Things Journal · doi:10.1109/jiot.2025.3587314 · Cited by 5
“Local differential privacy (LDP) [2], a robust privacy protection model, is widely employed in IIoT due to its lightweight, independence, and scalability [3].”
An Extension of the Adversarial Threat Model in Quantitative Information Flow
Zarrabian, M. A., & Sadeghi, P. (2025) · IEEE Computer Security Foundations Workshop (CSFW) · doi:10.1109/csf64896.2025.00036 · Cited by 5
“Notable examples include differential privacy (DP) [6], [7] and local differential privacy (LDP) [8], [9].”
Arcolezi, H. H., & Gambs, S. (2026) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde65706.2026.00029 · Cited by 5
“This limitation has led to the rise of Local Differential Privacy (LDP) [2], a model that removes the need for a trusted aggregator by requiring users to perturb their data locally before sharing it with the server.”
Credit Attribution and Stable Compression
Livni, R., Moran, S., Kobbi Nissim, B., & Pabbaraju, C. (2024) · neural information processing systems · doi:10.52202/079017-0087 · Cited by 5
Breaking the Communication-Privacy-Accuracy Tradeoff with $f$-Differential Privacy
Jin, R., Su, Z., Zhong, C., Zhang, Z., Quek, T. Q. S., & Dai, H. (2023) · neural information processing systems · doi:10.52202/075280-3242 · Cited by 5
“central server to perturb the collected data [18], distributed differential privacy that relies on secure aggregation during data collection [3], and local differential privacy (LDP) that avoids the need for the trusted server by perturbing the local data on the user side [19].”
BackgroundAccuracy Gains from Privacy Amplification Through Sampling for Differential Privacy
Hu, J., Drechsler, J., & Kim, H. J. (2022) · Journal of Survey Statistics and Methodology · doi:10.1093/jssam/smac012 · Cited by 5
Relying on the Metrics of Evaluated Agents
Wang, S., Jordan, M. I., Ligett, K., & McAfee, R. P. (2025) · International World Wide Web Conference (WWW) · doi:10.1145/3696410.3714864 · Cited by 5
“Definition 1 (Local Randomizer [Kasiviswanathan et al., 2011]) .”
On Public Key Encryption from Noisy Codewords
Ben‐Sasson, E., Bentov, I., Damgård, I., Ishai, Y., & Ron‐Zewi, N. (2016) · Lecture notes in computer science · doi:10.1007/978-3-662-49387-8_16 · Cited by 5
An Alphabet of Leakage Measures
Gilani, A., Kurri, G. R., Kosut, O., & Sankar, L. (2022) · IEEE Information Theory Workshop (ITW) · doi:10.1109/itw54588.2022.9965918 · Cited by 5
“We note that this subsumes an operational meaning of LDP given by Issa et al. [5] via maximal realizable leakage, a leakage measure definition concerned with worst-case analysis, akin to LDP. Interestingly, maximal α, β-leakage is defined in terms of average-case analysis (in the spirit of MaxL and MaxαL), and yet, it…”
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.