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 501–600 of 1,005
Privacy tradeoffs in predictive analytics
Ioannidis, S., Andrea Montanari, A., Weinsberg, U., Bhagat, S., Fawaz, N., & Taft, N. (2014) · ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS) · doi:10.1145/2591971.2592011 · Cited by 15
“A solution proposed by many recent research efforts is to allow a user to distort her ratings before revealing them to the analyst [7, 12, 22, 43].”
Arcolezi, H. H., Cerna, S., Couchot, J.-F., Guyeux, C., & Makhoul, A. (2021) · IEEE Transactions on Industrial Informatics · doi:10.1109/tii.2021.3123588 · Cited by 15
Differentially Private Adversarial Auto-Encoder to Protect Gender in Voice Biometrics
Chouchane, O., Panariello, M., Zari, O., Kerenciler, I., Chihaoui, I., Todisco, M., & Önen, M. (2023) · ACM Workshop on Information Hiding and Multimedia Security (IH&MMSec) · doi:10.1145/3577163.3595102 · Cited by 15
“While global DP mechanisms consist of a trusted central party/data curator collecting the users’ data, aggregating them, and further protecting the aggregated information by adding some calibrated noise before releasing it to the public, local DP (LDP) solutions [13] protect the input data immediately to prevent the d…”
BackgroundXie, P., & Yuan, Y.-X. (2024) · Journal of the Operations Research Society of China · doi:10.1007/s40305-023-00532-x · Cited by 15
“For example, in private black-box optimization, different transformations can be regarded as different encryptions formed by adding different noises according to the theory of differential privacy [65–70].”
Wasserstein Differential Privacy
Yang, C., Qi, J., & Zhou, A. (2024) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v38i15.29565 · Cited by 15
Separating Computational and Statistical Differential Privacy in the Client-Server Model
Bun, M., Chen, Y.-H., & Vadhan, S. (2016) · Lecture notes in computer science · doi:10.1007/978-3-662-53641-4_23 · Cited by 15
Private Cross-Silo Federated Learning for Extracting Vaccine Adverse Event Mentions
Kanani, P. H., Marathe, V. J., Peterson, D., Harpaz, R., & Bright, S. (2021) · Communications in computer and information science · doi:10.1007/978-3-030-93733-1_37 · Cited by 15
Multiparty Reach and Frequency Histogram: Private, Secure, and Practical
Ghazi, B., Kreuter, B., Kumar, R., Manurangsi, P., Peng, J., Skvortsov, E., Wang, Y., & Wright, C. (2021) · Proceedings on Privacy Enhancing Technologies · doi:10.2478/popets-2022-0019 · Cited by 15
“A widely studied distributed model of privacy is local DP [48].”
BackgroundThe Price of Differential Privacy for Low-Rank FactorizationPreprint
Upadhyay, J. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1604.01429 · Cited by 15
(Locally) Differentially Private Combinatorial Semi-BanditsPreprint
Chen, X., Zheng, K., Zhou, Z., Yang, Y., Chen, W., & Wang, L. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2006.00706 · Cited by 15
“…to preserve ε - differential privacy, if for any two data sequences D, D ′ that differ in at most one entry, and for any subset U ⊂ Y T , it holds that Compared with DP, Local Differential Privacy (LDP) is a stronger notion of privacy than DP, see Kasiviswanathan et al. (2011); Duchi et al. (2013).”
BackgroundAn Accurate, Scalable and Verifiable Protocol for Federated Differentially Private AveragingPreprint
Sabater, C., Bellet, A., & Ramon, J. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2006.07218 · Cited by 16
“Local differential privacy (LDP) (Kasiviswanathan et al., 2008; Duchi et al., 2013; Kairouz et al., 2015; 2016b;a) requires users to locally randomize their input before they send it to an untrusted aggregator.”
BackgroundInfluentialLocally Differentially Private Reinforcement Learning for Linear Mixture Markov Decision ProcessesPreprint
Liao, C., He, J., & Gu, Q. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2110.10133 · Cited by 15
“In this subsection, we introduce the standard definition of differential privacy (Dwork et al., 2006) and local differential privacy (Kasiviswanathan et al., 2011; Duchi et al., 2013).”
InfluentialIoT Privacy-Preserving Data Mining With Dynamic Incentive Mechanism
Gao, Y., Chen, L., Han, J., Wu, G., & Susilo, W. (2023) · IEEE Internet of Things Journal · doi:10.1109/jiot.2023.3285894 · Cited by 14
“Privacy: In 2011, Kasiviswanathan et al. [28] proposed local DP (LDP) as an extension of DP in decentralized scenarios.”
BackgroundMulti-Message Shuffled Privacy in Federated Learning
Girgis, A. M., & Diggavi, S. N. (2024) · IEEE Journal on Selected Areas in Information Theory · doi:10.1109/jsait.2024.3366225 · Cited by 14
“Definition 1 (Local Differential Privacy - LDP [22]): For ε 0 ≥ 0, a randomized mechanism R : X → Y is said to be ε 0 -local differentially private (in short, ε 0 -LDP), if for every pair of inputs d , d (cid:9) ∈ X , we have Let D = { d 1 , . . . , d n } denote a dataset comprising n points from X .”
BackgroundDifferentially Private Ad Conversion Measurement
Delaney, J., Ghazi, B., Harrison, C., Ilvento, C., Kumar, R. D., Manurangsi, P., Pál, M., Prabhakar, K., & Raykova, M. (2024) · Proceedings on Privacy Enhancing Technologies · doi:10.56553/popets-2024-0044 · Cited by 14
On the impact of multi-dimensional local differential privacy on fairness
Makhlouf, K., Arcolezi, H. H., Zhioua, S., Brahim, G. B., & Palamidessi, C. (2024) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-024-01031-0 · Cited by 14
“On the impact of multi‑dimensional local differential privacy…”
Differentially Private Reinforcement Learning
Ma, P., Wang, Z., Zhang, L., Wang, R., Zou, X., & Yang, T. (2020) · Lecture notes in computer science · doi:10.1007/978-3-030-41579-2_39 · Cited by 14
The Value of Privacy: Strategic Data Subjects, Incentive Mechanisms and Fundamental Limits
Wang, W., Ying, L., & Zhang, J. (2016) · ACM SIGMETRICS Performance Evaluation Review · doi:10.1145/2964791.2901461 · Cited by 14
Differentially Private Aggregation via Imperfect Shuffling
Ghazi, B., Kumar, R., Manurangsi, P., Nelson, J., & Zhou, S. (2023) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.itc.2023.17 · Cited by 14
“To address this shortcoming, the local model of DP [32, 42] (LDP) demands that all messages sent from an individual user to the curator is private.”
BackgroundPerturb and optimize users’ location privacy using geo-indistinguishability and location semantics
Yan, Y., Xu, F., Mahmood, A., Dong, Z., & Sheng, Q. Z. (2022) · Scientific Reports · doi:10.1038/s41598-022-24893-0 · Cited by 14
“In order to avoid user privacy leakage caused by untrusted third-party data collection platforms, the local differential privacy model (LDP) 7,8 is pro-Table The distance between any two locations x 1 and x 2 x 0 User’s real location”
BackgroundFrequency Estimation Mechanisms Under ϵδ-Utility-Optimized Local Differential Privacy
Zhang, Y., Zhu, Y., Zhou, Y., & Yuan, J. (2023) · IEEE Transactions on Emerging Topics in Computing · doi:10.1109/tetc.2023.3238839 · Cited by 14
“Kasiviswanathan et al. [7], [8] propose LDP for data analysis with an untrusted data collector which is a local model of DP. Wang et al. [23] design a framework for pure LDP mechanisms, which works for most existing frequency estimation mechanisms.”
BackgroundMethodInfluentialThe Power of Synergy in Differential Privacy: Combining a Small Curator with Local Randomizers
Beimel, A., Korolova, A., Kobbi Nissim, B., Sheffet, O., & Stemmer, U. (2019) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.itc.2020.14 · Cited by 14
Point-of-Interest Recommendation with User’s Privacy Preserving in an IoT Environment
Zhang, G., Qi, L., Zhang, X., Xu, X., & Dou, W. (2021) · Mobile Networks and Applications · doi:10.1007/s11036-021-01784-8 · Cited by 14
Na, S. H., Hong, H. G., Kim, J., & Shin, S. (2022) · Annual Computer Security Applications Conference · doi:10.1145/3564625.3564657 · Cited by 14
Distributed Private Data Analysis: On Simultaneously Solving How and WhatPreprint
Beimel, A., Kobbi Nissim, B., & Omri, E. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1103.2626 · Cited by 14
Efficient, Noise-Tolerant, and Private Learning via BoostingPreprint
Bun, M., Carmosino, M., & Sorrell, J. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2002.01100 · Cited by 14
“Despite the basic nature of this problem, it was only in very recent work of Nguy˜̂en et al. [2019] that dimension-independent sample complexity bounds were given for privately learning largemargin halfspaces.”
InfluentialLocal Differential Privacy Is Equivalent to Contraction of $E_γ$-DivergencePreprint
Asoodeh, S., Aliakbarpour, M., & Calmon, F. P. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2102.01258 · Cited by 14
“Arguably, the most stringent flavor of DP is local differential privacy (LDP) [8, 9].”
BackgroundTight Accounting in the Shuffle Model of Differential PrivacyPreprint
Koskela, A., Heikkilä, M., & Honkela, A. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2106.00477 · Cited by 14
Distributed Differential Privacy in Multi-Armed BanditsPreprint
Chowdhury, S. R., & Zhou, X. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2206.05772 · Cited by 14
“This motivates to employ a local model (Kasiviswanathan et al., 2011) of trust, where DP is achieved without a trusted server as each user perturbs her data prior to sharing with the server.”
MethodTowards Instance-Optimal Private Query ReleasePreprint
Błasiok, J., Bun, M., Nikolov, A., & Steinke, T. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1811.03763 · Cited by 14
Privacy amplification by random allocationPreprint
Feldman, V., & Shenfeld, M. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2502.08202 · Cited by 14
“As first shown by Kasiviswanathan et al. [2011], if each element of the dataset is included in the subset with probability λ (independently of other elements) then the privacy of the resulting algorithm is better (roughly) by a factor λ .”
Privacy-Preserving Record Linkage for Cardinality Counting
Wu, N., Vatsalan, D., Kâafar, M. A., & Ramesh, S. K. (2023) · ACM Asia Conference on Computer and Communications Security (ASIA CCS) · doi:10.1145/3579856.3590338 · Cited by 13
“It ensures differential privacy guarantees for each individual’s inputs by processing (perturbing) the data locally on-device rather than requiring a trusted data curator/central server [32].”
BackgroundRethinking Disclosure Prevention with Pointwise Maximal Leakage
Saeidian, S., Cervia, G., Oechtering, T. J., & Skoglund, M. (2025) · Journal of Privacy and Confidentiality · doi:10.29012/jpc.893 · Cited by 13
“In Fernandes et al. (2022), the quantity exp C ( P Y | X ) is called lift capacity and is used to establish a connection between a privacy measure called max-case g -leakage and local differential privacy (Kasiviswanathan et al., 2011; Duchi et al., 2013).”
PGB: Benchmarking Differentially Private Synthetic Graph Generation Algorithms
Liu, S., Du, H., Cao, Y., Yan, B., Liu, J., & Yoshikawa, M. (2025) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde65448.2025.00105 · Cited by 13
“In LDP, [62], each user randomizes the data to ensure local DP directly.”
Federated Learning on Riemannian Manifolds with Differential Privacy
Huang, Z., Huang, W., Jawanpuria, P., & Mishra, B. (2026) · Machine Learning · doi:10.1007/s10994-026-07018-w · Cited by 13
Optimal differential privacy mechanisms under Hamming distortion for structured source classes
Kalantari, K., Sankar, L., & Sarwate, A. D. (2016) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2016.7541663 · Cited by 13
“…∗DP(P, D) satisfies LBDP(P, D) ≤ ∗DP(P, D) ≤ UBDP (P, D), (10) where UBDP (P, D) is min l∈{0,1,...k} UB(l) (P, D), D(k) ≤ D D(k+1), ∀k ∈ {0, 1, . . . ,M − 2}, 0 D(M−1) ≤ D ≤ 1, (11) and LBDP(P, D) is min l∈{0,1,...k} LB(l)(P, D) D(k) ≤ D D(k+1), ∀k ∈ {0, 1, . . . ,M − 2}, 0 D(M−1) ≤ D ≤ 1.”
MethodOn Learnability Under General Stochastic Processes
Dawid, A. P., & Tewari, A. (2022) · Harvard Data Science Review · doi:10.1162/99608f92.dec7d780 · Cited by 13
Covert Learning: How to Learn with an Untrusted Intermediary
Canetti, R., & Karchmer, A. (2021) · Lecture notes in computer science · doi:10.1007/978-3-030-90456-2_1 · Cited by 13
Efficient protocols for heavy hitter identification with local differential privacy
Zhao, D., Zhao, S., Chen, H., Liu, R., Li, C., & Liang, W. (2022) · Frontiers of Computer Science · doi:10.1007/s11704-021-0412-y · Cited by 13
Zhao, J., Yang, M., Zhang, R., Song, W., Zheng, J., Feng, J., & Matwin, S. (2022) · Electronics · doi:10.3390/electronics11234007 · Cited by 13
A Crypto-Assisted Approach for Publishing Graph Statistics with Node Local Differential Privacy
Liu, S., Cao, Y., Murakami, T., & Yoshikawa, M. (2022) · IEEE International Conference on Big Data (BigData) · doi:10.1109/bigdata55660.2022.10020435 · Cited by 13
“Local differential privacy (LDP) [15], [16] is a promising model that does not require a trusted server to collect user information.”
BackgroundDP-NMT: Scalable Differentially Private Machine Translation
Igamberdiev, T., Vu, D. N. L., Künnecke, F., Yu, Z., Holmer, J., & Habernal, I. (2024) · Conference of the European Chapter of the Association for Computational Linguistics · doi:10.18653/v1/2024.eacl-demo.11 · Cited by 13
Interval Privacy: A Framework for Privacy-Preserving Data Collection
Ding, J., & Bangjun, D. (2022) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2022.3169432 · Cited by 13
“For example, we will point out (in the Appendix) that interval privacy is neither a generalization nor a specialization of local differential privacy [14], [15], a popular framework that has been extensively studied.”
BackgroundPrivacy-preserving Q-Learning with Functional Noise in Continuous State SpacesPreprint
Wang, B., & Hegde, N. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1901.10634 · Cited by 13
“In fact, the algorithm considers neighboring inputs that at most one data point can be different, therefore benefits from a 1 /B factor via privacy amplification [KLN + 11, BKN10] where B is the batch size.”
BackgroundLocally Private Learning without Interaction Requires SeparationPreprint
Daniely, A., & Feldman, V. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1809.09165 · Cited by 13
On the Equivalence between Online and Private Learnability beyond Binary ClassificationPreprint
Jung, Y. H., Kim, B., & Tewari, A. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2006.01980 · Cited by 13
“Definition 3 (Private PAC learning [18]).”
BackgroundMethodInfluentialRevisiting Model-Agnostic Private Learning: Faster Rates and Active LearningPreprint
Liu, C., Zhu, Y., Chaudhuri, K., & Wang, Y. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2011.03186 · Cited by 13
“More broadly, the learnability and sample complexity of private learning were studied under various models in Kasiviswanathan et al. (2011); Beimel et al. (2013, 2016); Chaudhuri and Hsu (2011); Bun et al. (2015); Wang et al. (2016); Alon et al. (2019).”
BackgroundPrivacy-Preserving Dynamic Personalized Pricing with Demand LearningPreprint
Chen, X., Simchi‐Levi, D., & Wang, Y. (2020) · SSRN Electronic Journal · doi:10.2139/ssrn.3700474 · Cited by 13
Unsupervised Information Obfuscation for Split Inference of Neural NetworksPreprint
Samragh, M., Hosseini, H., Triastcyn, A., Azarian, K., Soriaga, J. B., & Koushanfar, F. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2104.11413 · Cited by 13
“Using DP, however, can lead to a large loss of accuracy (Kasiviswanathan et al., 2011; Ullman, 2018; Kairouz et al., 2019).”
BackgroundDifferential privacy in the shuffle model
Cheu, A. (2021) · Digital Repository Service (Northeastern University) · doi:10.17760/d20409473 · Cited by 13
Towards Trustworthy Federated Learning with Untrusted ParticipantsPreprint
Allouah, Y., Guerraoui, R., & Stephan, J. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2505.01874 · Cited by 13
“We recall that local DP (LDP) (Kasiviswanathan et al., 2011) protects against an untrusted server without assuming the existence of secrets, at the price of a poor privacy-utility trade-off (Duchi et al., 2013).”
A Comprehensive Guide to Differential Privacy: From Theory to User ExpectationsPreprint
Karmitsa, N., Airola, A., Pahikkala, T., & Pitkämäki, T. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2509.03294 · Cited by 13
An overview of proposals towards the privacy-preserving publication of trajectory data
Miranda-Pascual, À., Guerra-Balboa, P., Parra‐Arnau, J., Forné, J., & Strufe, T. (2024) · International Journal of Information Security · doi:10.1007/s10207-024-00894-0 · Cited by 12
“The corresponding local ε -differential privacy ( ε -LDP) [39, 71], assumes every individual holds a database containing their records and shares them only after local obfuscation.”
Implications of Privacy Regulations on Video Surveillance Systems
Kansal, K., Wong, Y., & Kankanhalli, M. (2025) · ACM Transactions on Multimedia Computing Communications and Applications · doi:10.1145/3706108 · Cited by 12
Privacy-Preserving Coded Schemes for Multi-Server Federated Learning With Straggling Links
Liang, K., Li, S., Ding, M., Tian, F., & Wu, Y. (2024) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2024.3524160 · Cited by 12
“Therefore, this comes at the cost of facing more challenging privacy-utility-communication trade-o ff s [13], [15], [16].”
PPFLQB: A Privacy-Preserving Federated Learning enhanced Quantum-secure Blockchain layered framework
Sezer, B. B., & Turkmen, H. (2025) · Internet of Things · doi:10.1016/j.iot.2025.101719 · Cited by 12
Local Differential Privacy for Data Streams
Fang, X., Zeng, Q., & Yang, G. (2020) · Communications in computer and information science · doi:10.1007/978-981-15-9129-7_11 · Cited by 12
Inferring ground truth from crowdsourced data under local attribute differential privacy
Wang, D., & Xu, J. (2021) · Theoretical Computer Science · doi:10.1016/j.tcs.2021.02.039 · Cited by 12
“…D, D (cid:48) and for all events S in the output space of A , the following holds Instead of the trusted curator, in Local Differential Privacy model [16], each data provider perturb his/her private data record locally via some differentially private mechanisms before sending it to the curator.”
BackgroundEarly Detection of Diabetes Mellitus Using Differentially Private SGD in Federated Learning
Dolo, B., Loukil, F., & Boukadi, K. (2022) · IEEE/ACS International Conference on Computer Systems and Applications (AICCSA) · doi:10.1109/aiccsa56895.2022.10017908 · Cited by 12
“• Local Differential Privacy (LDP) [19], [20] ensures privacy when individuals do not trust the data curator.”
BackgroundAsymmetric Local Information Privacy and the Watchdog Mechanism
Zarrabian, M. A., Ding, N., & Sadeghi, P. (2022) · IEEE Information Theory Workshop (ITW) · doi:10.1109/itw54588.2022.9965910 · Cited by 12
“We demonstrate that in ALIP, only max-lift affects the bounds on IT average measures including, MI, maximal leakage, α-leakage (Arimoto MI), and Sibson MI; and LDP is upper bounded by ε = εu + εl.”
BackgroundInfluentialOne Step to Efficient Synthetic Data
Awan, J., & Cai, Z. (2023) · Statistica Sinica · doi:10.5705/ss.202022.0274 · Cited by 12
“On the other hand, local differential privacy (Kasiviswanathan et al., 2011; Duchi et al., 2013) in general does not permit efficient estimators and would not fit in our framework.”
BackgroundVarun, M., Feng, S., Wang, H., Sural, S., & Hong, Y. (2024) · ACM Conference on Data and Application Security and Privacy (CODASPY) · doi:10.1145/3626232.3653279 · Cited by 12
Makhlouf, K., Stefanović, T., Arcolezi, H. H., & Palamidessi, C. (2024) · IEEE Computer Security Foundations Workshop (CSFW) · doi:10.1109/csf61375.2024.00039 · Cited by 12
Compressed Private Aggregation for Scalable and Robust Federated Learning Over Massive Networks
Lang, N., Shlezinger, N., D’Oliveira, R. G. L., & Rouayheb, S. E. (2025) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2025.3564390 · Cited by 12
“Privacy in settings involving queries between users and a server is commonly quantified in terms of differential privacy (DP) [52], [53] and LDP [54], [55].”
On the Computational Landscape of Replicable Learning
Kalavasis, A., Karbasi, A., Velegkas, G., & Zhou, F. (2024) · neural information processing systems · doi:10.52202/079017-3359 · Cited by 12
Unified Mechanism-Specific Amplification by Subsampling and Group Privacy Amplification
Schuchardt, J., Stoian, M., Kosmala, A., & Günnemann, S. (2024) · neural information processing systems · doi:10.52202/079017-2496 · Cited by 12
PPFedIT : Towards Privacy-preserving Federated Instruction Tuning with Few-shot Local Examples
Zhang, Z. G., Zhang, J., Huang, J., Wang, H., Yu, Y., Zhang, H., Zhou, X., Qu, L., & Xu, Z. (2026) · ACM Transactions on Intelligent Systems and Technology · doi:10.1145/3806196 · Cited by 12
Assessing the Privacy Cost in Centralized Event-Based Demand Response for Microgrids
Karapetyan, A., Azman, S. K., & Aung, Z. (2017) · IEEE International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom) · doi:10.1109/trustcom/bigdatase/icess.2017.276 · Cited by 12
ARA: Aggregated RAPPOR and Analysis for Centralized Differential Privacy
Paul, S., & Mishra, S. (2019) · SN Computer Science · doi:10.1007/s42979-019-0023-y · Cited by 12
PILLAR: How to make semi-private learning more effective
Pinto, F., Hu, Y., Yang, F., & Sanyal, A. (2024) · IEEE Conference on Secure and Trustworthy Machine Learning (SaTML) · doi:10.1109/satml59370.2024.00014 · Cited by 12
“Nonetheless, meeting these guarantees often compromises model utility, unless the volume of available private training data is significantly increased [5]–[9].”
BackgroundStatistical Query Algorithms for Stochastic Convex Optimization
Feldman, V., Guzmán, C., & Vempala, S. (2015) · Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands · doi:10.1137/1.9781611974782.82 · Cited by 12
Estimation from Indirect Supervision with Linear MomentsPreprint
Raghunathan, A., Frostig, R., Duchi, J. C., & Liang, P. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1608.03100 · Cited by 12
“We work with the stronger notion of local differential privacy (Evfimievski et al., 2004; Kasiviswanathan et al., 2011; Duchi et al., 2013).”
BackgroundInteractive Privacy via the Median MechanismPreprint
Roth, A., & Roughgarden, T. (2009) · arXiv (Cornell University) · doi:10.48550/arxiv.0911.1813 · Cited by 12
Differentially private anonymized histogramsPreprint
Suresh, A. T. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1910.03553 · Cited by 12
“The second model is local DP, where ✏-DP is guaranteed for each individual user’s data [35, 36, 37, 38, 39].”
BackgroundDifferentially Private Collaborative Intrusion Detection Systems For VANETsPreprint
Zhang, T., & Zhu, Q. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2005.00703 · Cited by 12
“In the field of differential privacy, there is a number of works on applying differential privacy to machine learning [29, 30, 31, 32, 33].”
BackgroundMethodBenchmarking Differentially Private Residual Networks for Medical ImageryPreprint
Singh, S., Sikka, H., Kotti, S., & Trask, A. (2020) · OSF Preprints (OSF Preprints) · doi:10.31219/osf.io/v2ms6 · Cited by 12
Fernandes, N. (2021) · theses.fr (ABES) · doi:10.70675/362ab197z0f03z4d40zb0d4z43c13b3de6c5 · Cited by 12
Private Non-Convex Federated Learning Without a Trusted ServerPreprint
Lowy, A. M., Ghafelebashi, A., & Razaviyayn, M. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2203.06735 · Cited by 12
“The main takeaway from our numerical experiments is that ISRL-DP FedProx-SPIDER outperforms the other ISRLDP baselines for most privacy levels.”
BackgroundInfluentialThe Complexities of Differential Privacy for Survey Data
Drechsler, J., & Bailie, J. (2024) · National Bureau of Economic Research · doi:10.3386/w32905 · Cited by 12
Mean Estimation of Numerical Data Under (ϵ,δ) -Utility-Optimized Local Differential Privacy
Zhang, Y., Zhu, Y., Wang, S., & Huang, X. (2024) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2024.3478823 · Cited by 11
Revisiting EM-based Estimation for Locally Differentially Private Protocols
Ye, Y., Wang, T., Zhang, M., & Feng, D. (2025) · Network and Distributed System Security Symposium · doi:10.14722/ndss.2025.230521 · Cited by 11
“Kasiviswanathan et al. [31] systematically investigate the framework of local differential privacy and connect it to the classical randomized response technique [49], which is now the foundation.”
A Distributed Privacy-Preserving Learning Dynamics in General Social Networks
Tao, Y., Chen, S., Li, F., Yu, D., Yu, J., & Sheng, H. (2023) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2023.3241442 · Cited by 11
“2) Local Differential Privacy: In this article, we leverage the notion of Local Differential Privacy (LDP) for the purpose of privacy preserving.”
InfluentialFrom Noisy Fixed-Point Iterations to Private ADMM for Centralized and Federated Learning
Cyffers, E., Bellet, A., & Basu, D. (2023) · HAL · doi:10.48550/arxiv.2302.12559 · Cited by 11
Personalized sampling graph collection with local differential privacy for link prediction
Jiang, L., Yan, Y., Tian, Z., Xiong, Z., & Han, Q. (2023) · World Wide Web · doi:10.1007/s11280-023-01136-4 · Cited by 11
“To relieve this assumption, LDP [13] was proposed, which assumes that each user is responsible for his record in the database.”
BackgroundLocally Private Streaming Data Release with Shuffling and Subsampling
Li, X., Cao, Y., & Yoshikawa, M. (2023) · IEEE International Conference on Data Engineering Workshops (ICDEW) · doi:10.1109/icdew58674.2023.00026 · Cited by 11
“Centralized differential privacy (CDP) [19] and Local differential privacy (LDP) [12] [14] are two wide-studied DP schemes.”
BackgroundQian, Q., Ye, Q., Hu, H., Huang, K., Chan, T. T.-L., & Li, J. (2023) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2023.3289007 · Cited by 11
“Local differential privacy (LDP) is a promising privacy-preserving method for distributed data collection and analysis [4], [10].”
BackgroundMethodMean Estimation Under Heterogeneous Privacy Demands
Chaudhuri, S., Miagkov, K., & Courtade, T. A. (2024) · IEEE Transactions on Information Theory · doi:10.1109/tit.2024.3511498 · Cited by 11
“In the Local-DP model, users do not trust the central server and send their data through a noisy channel to the server to preserve privacy [26], [27].”
Privacy-Preserving Data Fusion
Tian, L., Turjeman, D., & Levy, S. (2026) · Marketing Science · doi:10.1287/mksc.2023.0068 · Cited by 11
On the Privacy and Utility Properties of Triple Matrix-Masking
Ding, A. A., Miao, G., & Wu, S. S. (2020) · Journal of Privacy and Confidentiality · doi:10.29012/jpc.674 · Cited by 11
Research Challenges in Designing Differentially Private Text Generation Mechanisms
Feyisetan, O., Aggarwal, A., Xu, Z., & Teissier, N. (2021) · Proceedings of the ... International Florida Artificial Intelligence Research Society Conference · doi:10.32473/flairs.v34i1.128461 · Cited by 11
Realizable Learning is All You Need
Hopkins, M., Kane, D. M., Lovett, S., & Mahajan, G. (2024) · TheoretiCS · doi:10.46298/theoretics.24.2 · Cited by 11
“The only difference in the argument is to replace the generic ERM learner over the output of LEARNINGTOCOVER with the exponential mechanism [49].”
BackgroundGDP vs. LDP: A Survey from the Perspective of Information-Theoretic Channel
Liu, H., Peng, C., Tian, Y., Long, S., Tian, F., & Wu, Z. (2022) · Entropy · doi:10.3390/e24030430 · Cited by 11
“Therefore, Kasiviswanathan et al. [2] proposed that local differential privacy (LDP) allows an untrusted third party to perform statistical analysis while achieving user’s privacy by random perturbation of local data.”
BackgroundChen, X., Wang, C., Cui, J., Yang, Q., Hu, T., & Jiang, C. (2022) · IEEE Transactions on Big Data · doi:10.1109/tbdata.2022.3190033 · Cited by 11
“Local differential privacy [30], [31], which is a variant of differential privacy [13], [32], provides strong privacy guarantees.”
BackgroundDifferentially Private Neighborhood-Based Recommender Systems
Wang, J., & Tang, Q. (2017) · IFIP advances in information and communication technology · doi:10.1007/978-3-319-58469-0_31 · Cited by 11
“The privacy enhancing technique [3,14] indicates that given a method which is (cid:15) -differentially private over a deterministic training set, then it maintains γ(cid:15) -differential privacy with respect to a full database if we uniform-randomly sample training set from the database where γ is…”
MethodPrivacy-Preserving Publication of Deep Neural Networks
Sei, Y., Okumura, H., & Ohsuga, A. (2016) · IEEE International Conference on High Performance Computing and Communications; IEEE International Conference on Smart City; IEEE International Conference on Data Science and Systems (HPCC/SmartCity/DSS) · doi:10.1109/hpcc-smartcity-dss.2016.0202 · Cited by 11
“Proof: We know from [32] that if a randomized algorithm A runs d algorithms A1, .”
BackgroundSecure Medical Data Collection via Local Differential Privacy
Wang, Z., Ma, P., Wang, R., Zhang, J., Chi, Y., Ma, Y., & Yang, T. (2018) · IEEE International Conference on Computer and Communications (ICCC) · doi:10.1109/compcomm.2018.8780925 · Cited by 11
“To address the problem, Local Differential Privacy (LDP) is proposed to preserve privacy with strong guarantee [10], [11], which extends the Differential Privacy to local privacy context.”
BackgroundLearning With Differential Privacy
Sengupta, P., Paul, S., & Mishra, S. (2020) · Advances in information security, privacy, and ethics book series · doi:10.4018/978-1-7998-5728-0.ch019 · Cited by 11
Improving Frequency Estimation under Local Differential Privacy
Lopuhaä-Zwakenberg, M., Li, Z., Škorić, B., & Li, N. (2020) · Workshop on Privacy in the Electronic Society · doi:10.1145/3411497.3420215 · Cited by 11
“(ε-LDP [18]) Let Q be a privacy protocol for A, and let ε ∈ R≥0.”
BackgroundAn Incentive Mechanism for Trading Personal Data in Data Markets
Biswas, S., Jung, K., & Catuscia Palamidessi, A. (2021) · Lecture notes in computer science · doi:10.1007/978-3-030-85315-0_12 · Cited by 11
New Separations in the Complexity of Differential Privacy
Bun, M. (2016) · Digital Access to Scholarship at Harvard (DASH) (Harvard University) · Cited by 11
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.