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 301–400 of 1,005
Comparing Local and Central Differential Privacy Using Membership Inference Attacks
Bernau, D., Robl, J., Grassal, P. W., Schneider, S., & Kerschbaum, F. (2021) · Lecture notes in computer science · doi:10.1007/978-3-030-81242-3_2 · Cited by 33
On the average-case complexity of learning output distributions of quantum circuits
Nietner, A., Ioannou, M., Sweke, R., Kueng, R., Eisert, J., Hinsche, M., & Haferkamp, J. (2025) · Quantum · doi:10.22331/q-2025-10-13-1883 · Cited by 33
Truth Inference on Sparse Crowdsourcing Data with Local Differential Privacy
Sun, H., Dong, B., Wang, H., Yu, T., & Qin, Z. (2018) · IEEE International Conference on Big Data (BigData) · doi:10.1109/bigdata.2018.8622635 · Cited by 33
Private Center Points and Learning of HalfspacesPreprint
Beimel, A., Moran, S., Kobbi Nissim, B., & Stemmer, U. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1902.10731 · Cited by 33
“This motivated the line of works on private learning, initiated by Kasiviswanathan et al. (2011), which provides strong (mathematically proven) privacy protections for the training data.”
BackgroundInfluentialAssessing differentially private deep learning with Membership InferencePreprint
Bernau, D., Grassal, P.-W., Robl, J., & Kerschbaum, F. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1912.11328 · Cited by 33
“We adapt the definitions of Kasiviswanathan et al. [19] to achieve LDP by using local randomizers LR .”
BackgroundMethodDifferential privacy in metric spaces: Numerical, categorical and functional data under the one roof
Holohan, N., Leith, D. J., & Mason, O. (2015) · Information Sciences · doi:10.1016/j.ins.2015.01.021 · Cited by 32
“Algorithms for search problems and learning are considered in [12, 13].”
BackgroundDistributed Cardinality Estimation of Set Operations with Differential Privacy
Stanojević, R., Nabeel, M., & Yu, T. (2017) · IEEE Symposium on Privacy-Aware Computing (PAC) · doi:10.1109/pac.2017.43 · Cited by 32
“, local differential privacy (LDP) [40], [26], [17].”
Tsitsiklis, J. N., Xu, K., & Xu, Z. (2021) · Operations Research · doi:10.1287/opre.2020.2021 · Cited by 32
Feldman, V. (2016) · Springer eBooks · doi:10.1007/978-1-4939-2864-4_401 · Cited by 32
Pan-Private Uniformity TestingPreprint
Amin, K., Joseph, M., & Mao, J. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1911.01452 · Cited by 32
“One solution to this family of problems is local differential privacy [24, 32].”
BackgroundALGEN: Few-shot Inversion Attacks on Textual Embeddings via Cross-Model Alignment and Generation
Chen, Y., Xu, Q., & Bjerva, J. (2025) · Proceedings of the conference - Association for Computational Linguistics. Meeting · doi:10.18653/v1/2025.acl-long.1185 · Cited by 31
Differentially Private Learning with Small Public Data
Wang, J., & Zhou, Z. (2020) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v34i04.6088 · Cited by 31
“Local differential privacy (Kasiviswanathan et al. 2008) allows database participants to perturb their data by themselves.”
BackgroundPost-selection inference via algorithmic stability
Zrnic, T., & Jordan, M. I. (2023) · The Annals of Statistics · doi:10.1214/23-aos2303 · Cited by 31
“For example, it would be valuable to understand bootstrapping [41] from the perspective of stability, due to its conceptual relations to the “privacy amplification by subsampling” principle in differential privacy, which argues that privacy is amplified when run on a random subsample of the entire dataset [28, 6].”
BackgroundHide me Behind the Noise: Local Differential Privacy for Indoor Location Privacy
Navidan, H., Moghtadaiee, V., Nazaran, N., & Alishahi, M. (2022) · IEEE European Symposium on Security and Privacy Workshops (EuroS&PW) · doi:10.1109/eurospw55150.2022.00061 · Cited by 31
“To eliminate the need for a trusted party and the computation overhead, Local Differential Privacy (LDP) offers a strong privacy guarantee in which the individuals perturb their data locally (on their own device) before sending them to the third party (named aggregator) [9].”
Differential Privacy for Databases
Near, J. P., & He, X. G. (2021) · Foundations and Trends in Databases · doi:10.1561/1900000066 · Cited by 31
Heavy Hitter Identification Over Large-Domain Set-Valued Data With Local Differential Privacy
Zhu, Y., Cao, Y., Xue, Q., Wu, Q., & Zhang, Y. (2023) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2023.3324726 · Cited by 31
“Local differential privacy (LDP) [1] is a variant of differential privacy (DP) [16], [17] in the local setting, to avoid a trusted collector.”
BackgroundMeisenbacher, S., Nandakumar, N., Klymenko, A., & Matthes, F. (2024) · Language Resources and Evaluation Conference (LREC) · doi:10.63317/4opsiuys8u8p · Cited by 31
Personalized Privacy-Preserving Data Aggregation for Histogram Estimation
Wang, S., Huang, L., Tian, M., Yang, W., Xu, H., & Guo, H. (2014) · Globecom · doi:10.1109/glocom.2015.7417364 · Cited by 31
A Two-Phase Algorithm for Generating Synthetic Graph Under Local Differential Privacy
Zhang, Y., Wei, J., Zhang, Z., Hu, X., & Liu, W. (2018) · International Conference on Communication and Network Security (ICCNS) · doi:10.1145/3290480.3290503 · Cited by 31
“[2] proposed local differential privacy technology.”
Locally Private Gaussian EstimationPreprint
Joseph, M., Kulkarni, J., Mao, J., & Wu, Z. S. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1811.08382 · Cited by 31
“For many problems, a locally private solution requires far more samples than a globally private solution [7, 10, 19, 23].”
BackgroundDifferential Privacy has Bounded Impact on Fairness in ClassificationPreprint
Mangold, P., Perrot, M., Bellet, A., & Tommasi, M. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2210.16242 · Cited by 31
Selective privacy-preserving framework for large language models fine-tuning
Wang, T., Zhai, L., Yang, T., Luo, Z., & Liu, S. (2024) · Information Sciences · doi:10.1016/j.ins.2024.121000 · Cited by 31
How to Use Heuristics for Differential Privacy
Neel, S., Roth, A., & Wu, Z. S. (2019) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2019.00014 · Cited by 30
“Di ff erential privacy is compatible with a tremendous number of powerful data analysis tasks, including essentially any statistical learning problem [KLN + 11, CMS11, BST14] and the generation of synthetic data consistent with exponentially large families of statistics [BLR13, RR10, HR10, GRU12,…”
BackgroundMethodInfluentialPrivacy-Preserving Travel Time Prediction With Uncertainty Using GPS Trace Data
Liu, F., Wang, D., & Xu, Z. (2021) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2021.3074865 · Cited by 30
“Definition 2 ( -local differential privacy [53], [54]).”
BackgroundSignDS-FL: Local Differentially Private Federated Learning with Sign-based Dimension Selection
Jiang, X., Zhou, X., & Großklags, J. (2022) · ACM Transactions on Intelligent Systems and Technology · doi:10.1145/3517820 · Cited by 30
“Due to the privacy and efficiency issues in the above-mentioned solutions, a more practical approach is to use LDP [23] to privatize the original local updates before sending them to the server.”
BackgroundMethodInfluentialContraction of Locally Differentially Private Mechanisms
Asoodeh, S., & Zhang, H. (2024) · IEEE Journal on Selected Areas in Information Theory · doi:10.1109/jsait.2024.3397305 · Cited by 30
Locally Private Distributed Reinforcement LearningPreprint
Ono, H., & Takahashi, T. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2001.11718 · Cited by 30
“ifferential privacy [13] is a rigorous privacy definition, which quantitatively evaluates the degree of privacy protection when releasing statistical aggregates. While local differential privacy (LDP) [16, 12] gives a rigorous privacy guarantee when data providers send information to a data curator. Suppose the data pr…”
BackgroundUniversal Exact Compression of Differentially Private Mechanisms
Liu, Y., Chen, W., Özgür, A., & Li, C. T. (2024) · neural information processing systems · doi:10.52202/079017-2904 · Cited by 29
Memristor-Based Variation-Enabled Differentially Private Learning Systems for Edge Computing in IoT
Fu, J., Liao, Z., Liu, J., Smith, S. C., & Wang, J. (2020) · IEEE Internet of Things Journal · doi:10.1109/jiot.2020.3023623 · Cited by 29
“Next, based on the privacy ampli-fication theorem [44], for the process of random sampling with probability L/N , as in Fig.”
MethodPrivacy-Preserving High-dimensional Data Collection with Federated Generative Autoencoder
Jiang, X., Zhou, X., & Großklags, J. (2021) · Proceedings on Privacy Enhancing Technologies · doi:10.2478/popets-2022-0024 · Cited by 29
“Local differential privacy (LDP) [31], as a state-of-the-art data anonymization mechanism, has been recently deployed by major technology organizations such as Apple [14], Google [23], and Microsoft [15] for privacy-preserving data collection.”
BackgroundConsideration of FedProx in Privacy Protection
An, T., Ma, L., Wang, W., Yang, Y., Wang, J., & Chen, Y. (2023) · Electronics · doi:10.3390/electronics12204364 · Cited by 29
Fair Ranking with Noisy Protected Attributes
Mehrotra, A., & Vishnoi, N. K. (2022) · neural information processing systems · doi:10.52202/068431-2299 · Cited by 29
Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization
Feldman, V., Guzmán, C., & Vempala, S. (2021) · Mathematics of Operations Research · doi:10.1287/moor.2020.1111 · Cited by 29
Privately Learning Thresholds: Closing the Exponential GapPreprint
Kaplan, H. Y., Ligett, K., Mansour, Y., Naor, M., & Stemmer, U. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1911.10137 · Cited by 29
AirGapAgent: Protecting Privacy-Conscious Conversational Agents
Bagdasarian, E., Yi, R., Ghalebikesabi, S., Kairouz, P., Gruteser, M., Oh, S., Balle, B., & Ramage, D. (2024) · Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/3658644.3690350 · Cited by 28
“Other methods that protect data, like local differential privacy (DP) [23, 24, 33, 61], are not context-aware and therefore reduce the agent’s utility by always introducing noise on user data [17, 22, 32].”
Tracking the Insider Attacker: A Blockchain Traceability System for Insider Threats
Hu, T., Xin, B., Liu, X., Chen, T., Ding, K., & Zhang, X. (2020) · Sensors · doi:10.3390/s20185297 · Cited by 28
“Local differential privacy (LDP) [29] provides stronger privacy guarantees than central differential privacy because it does not rely on the assumption of a trusted data administrator.”
BackgroundOn Distributed Differential Privacy and Counting Distinct Elements
Chen, L., Ghazi, B., Kumar, R., & Manurangsi, P. (2020) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.itcs.2021.56 · Cited by 28
Group Privacy for Personalized Federated Learning
Galli, F., Biswas, S., Jung, K., Cucinotta, T., & Palamidessi, C. (2023) · International Conference on Information Systems Security and Privacy (ICISSP) · doi:10.5220/0011885000003405 · Cited by 28
“The local model for differential privacy [33] can be derived from (6) when G, G ′ are taken to be datasets of only one record.”
BackgroundFair NLP Models with Differentially Private Text Encoders
Maheshwari, G., Denis, P., Keller, M., & Bellet, A. (2022) · Findings of the Association for Computational Linguistics: EMNLP (Findings of EMNLP) · doi:10.18653/v1/2022.findings-emnlp.514 · Cited by 28
Rate-Distortion Theoretic Bounds on Generalization Error for Distributed Learning
Sefidgaran, M., Chor, R., & Zaidi, A. (2022) · neural information processing systems · doi:10.52202/068431-1431 · Cited by 28
Privacy Amplification of Iterative Algorithms via Contraction Coefficients
Asoodeh, S., Díaz, M., & Calmon, F. P. (2020) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit44484.2020.9174133 · Cited by 28
“Among these variants, Rényi DP (RDP) has proven to be effective in studying private deep learning algorithms [5] especially when paired with subsampling techniques [11].”
BackgroundPrivacy-Preserving Personalized Federated Learning
Hu, R., Guo, Y., Li, H., Pei, Q., & Gong, Y. (2020) · International Conference on Communications · doi:10.1109/icc40277.2020.9149207 · Cited by 28
“And this can be further tightened by combining with the privacy amplification theorem proposed in [10] which makes the composed mechanism to be ( O ( q(cid:4) ) , O ( qδ )) -differentially private if the training data at each iteration is a random sample from the dataset with sampling probability q .”
BackgroundCollective location statistics release with local differential privacy
Errounda, F. Z., & Liu, Y. (2021) · Future Generation Computer Systems · doi:10.1016/j.future.2021.05.020 · Cited by 28
Implications of Data Anonymization on the Statistical Evidence of Disparity
Xu, H., & Zhang, N. (2022) · Management Science · doi:10.1287/mnsc.2021.4028 · Cited by 28
Utility Analysis and Enhancement of LDP Mechanisms in High-Dimensional Space
Duan, J., Ye, Q., & Hu, H. (2022) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde53745.2022.00035 · Cited by 27
Privacy-Conscious Information Diffusion in Social Networks
Giakkoupis, G., Guerraoui, R., Jégou, A., Kermarrec, A.-M., & Mittal, N. (2015) · Lecture notes in computer science · doi:10.1007/978-3-662-48653-5_32 · Cited by 27
“The local privacy model was first introduced in the context of learning, where it was shown that private learning in the local model is equivalent to non-private learning in the statistical query model [17,15].”
BackgroundThe limits of pan privacy and shuffle privacy for learning and estimation
Cheu, A., & Ullman, J. (2021) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3406325.3450995 · Cited by 27
“However, for problems such as learning parities and selecting the most common attribute, where the local model is most severely limited [19, 28, 40, 47], there is no evidence that either the pan-private or shuffle model can overcome these limitations.”
BackgroundMethodInfluentialSecure Sublinear Time Differentially Private Median Computation
Böhler, J., & Kerschbaum, F. (2020) · Network and Distributed System Security Symposium · doi:10.14722/ndss.2020.24150 · Cited by 27
Privacy-Preserving Dynamic Personalized Pricing with Demand LearningPreprint
Chen, X., Simchi‐Levi, D., & Wang, Y. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2009.12920 · Cited by 27
“First, we could extend the current privacy setting to the local DP (Evfimievski et al. 2003, Kasiviswanathan et al. 2011), which is a stronger notion of DP.”
BackgroundPrivacy-Aware Compression for Federated Data AnalysisPreprint
Chaudhuri, K., Guo, C., & Rabbat, M. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2203.08134 · Cited by 27
“This is usually achieved by applying a local differentially private (LDP) algorithm (Duchi et al., 2013; Kasiviswanathan et al., 2011) on the raw inputs at the client device so that only sanitized data is transmitted to the server.”
BackgroundPrivacy-Enhancing Paradigms within Federated Multi-Agent SystemsPreprint
Shi, Z., Wan, G., Huang, W., Zhang, G., Shao, J., Ye, M., & Yang, C. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2503.08175 · Cited by 27
“However, this assumption does not always hold in practice (Dwork, 2006; Kasiviswanathan et al., 2011).”
Wdt-SCAN: Clustering decentralized social graphs with local differential privacy
Hou, L., Ni, W., Zhang, S., Fu, N., & Zhang, D. (2022) · Computers & Security · doi:10.1016/j.cose.2022.103036 · Cited by 26
K-Means Clustering with Local Distance Privacy
Yang, M., Huang, L., & Tang, C. (2023) · Big Data Mining and Analytics · doi:10.26599/bdma.2022.9020050 · Cited by 26
An Operational Approach to Information Leakage via Generalized Gain Functions
Kurri, G. R., Sankar, L., & Kosut, O. (2023) · IEEE Transactions on Information Theory · doi:10.1109/tit.2023.3341148 · Cited by 26
“A number of approaches to quantify such information leakage have been proposed in both computer science [1], [2], [3], [4], [5], [6], [7] and information theory [8], [9], [10], [11], [12], [13], [14], [15], [16].”
BackgroundA general framework for differentially private quantum measurements
Angrisani, A., Doosti, M., & Kashefi, E. (2026) · ACM Transactions on Quantum Computing · doi:10.1145/3842143 · Cited by 26
Privacy‐preserving mechanism for mixed data clustering with local differential privacy
Yuan, L., Zhang, S., Zhu, G., & Alinani, K. (2021) · Concurrency and Computation Practice and Experience · doi:10.1002/cpe.6503 · Cited by 26
Differentially-Private Clustering of Easy InstancesPreprint
Cohen, E., Kaplan, H. Y., Mansour, Y., Stemmer, U., & Tsfadia, E. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2112.14445 · Cited by 26
“Lemma 2.10 ((Beimel et al., 2010; Kasiviswanathan et al., 2011)) .”
InfluentialOptimal Compression of Locally Differentially Private MechanismsPreprint
Shah, A., Chen, W., Ballé, J., Kairouz, P., & Theis, L. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2111.00092 · Cited by 26
“Privacy is often achieved by enforcing ε -local differential privacy ( ε -LDP) (Warner, 1965; Evfimievski et al., 2003; Dwork et al., 2006; Kasiviswanathan et al., 2011), which guarantees that the outcome from a privatization mechanism will not release too much individual information statistically.”
BackgroundDifferential Privacy Amplification in Quantum and Quantum-inspired AlgorithmsPreprint
Angrisani, A., Doosti, M., & Kashefi, E. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2203.03604 · Cited by 26
“Following the notation used in [7], we say that a randomized algorithm over datasets is ( ε, δ )-local differentially private if it’s an ( ε, δ )- differentially private algorithm that takes in input a dataset of size n = 1.”
Xiong, A., Wu, C., Wang, T., Proctor, R. W., Blocki, J., Li, N., & Jha, S. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2202.10014 · Cited by 26
“In recent years, local differential privacy ( Local DP ) [23], [27], [35], [54] has become popular because of its deployment in companies such as Google [26], Apple [4], and Microsoft [22].”
BackgroundXu, S., Zheng, Y., & Hua, Z. (2024) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/3658644.3690200 · Cited by 25
Differentially Private Real-Time Release of Sequential Data
Zhang, X., Khalili, M. M., & Liu, M. (2022) · ACM Transactions on Privacy and Security · doi:10.1145/3544837 · Cited by 25
“2) is reduced to that of local differential privacy [Kasiviswanathan et al. 2011].”
BackgroundOn the Lift, Related Privacy Measures, and Applications to Privacy–Utility Trade-Offs
Zarrabian, M. A., Ding, N., & Sadeghi, P. (2023) · Entropy · doi:10.3390/e25040679 · Cited by 25
“Another instance-wise measure is local differential privacy [5,6,28],”
BackgroundDifferentially Private Stochastic Linear Bandits: (Almost) for Free
Hanna, O. A., Girgis, A. M., Fragouli, C., & Diggavi, S. N. (2024) · IEEE Journal on Selected Areas in Information Theory · doi:10.1109/jsait.2024.3389954 · Cited by 25
“Definition 2 (LDP [26]): if for any rewards r t and r t , and any subset of outputs O ⊂ Z , the algorithm M satisfies: Similar to the DP definition, we say that M is pure locally differentially private (ε 0 -LDP) when δ 0 = 0.”
Universal Neural-Cracking-Machines: Self-Configurable Password Models from Auxiliary Data
Pasquini, D., Ateniese, G., & Troncoso, C. (2024) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp54263.2024.00032 · Cited by 25
“, the number of users) due to privacy amplification by sub-sampling [30], [5].”
BackgroundModel-Protected Multi-Task Learning
Liang, J., Liu, Z., Zhou, J., Jiang, X., Zhang, C., & Wang, F. (2020) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2020.3015859 · Cited by 25
Characterizing Private Clipped Gradient Descent on Convex Generalized Linear Problems.
Song, S., Thakkar, O. D., & Thakurta, A. (2020) · Cited by 25
Real-time and private spatio-temporal data aggregation with local differential privacy
Xiong, X., Liu, S., Li, D., Cai, Z., & Niu, X. (2020) · Journal of Information Security and Applications · doi:10.1016/j.jisa.2020.102633 · Cited by 25
Privacy-Preserving Collaborative Data Collection and Analysis with Many Missing Values
Sei, Y., Andrew, J., Okumura, H., & Ohsuga, A. (2022) · IEEE Transactions on Dependable and Secure Computing · doi:10.1109/tdsc.2022.3174887 · Cited by 25
“As there are g attributes in our scenario, each R ij should satisfy (cid:1)=g -differential privacy [48].”
BackgroundMethodInfluentialDifferential Privacy: A Cryptographic Approach to Private Data Analysis
Dwork, C. (2014) · Cambridge University Press eBooks · doi:10.1017/cbo9781107590205.018 · Cited by 25
Empirical Risk Minimization in the Non-interactive Local Model of Differential PrivacyPreprint
Wang, D., Gaboardi, M., Smith, A., & Xu, J. (2020) · OpenBU (Boston University) · doi:10.48550/arxiv.2011.05934 · Cited by 25
“Problem setting (Smith et al., 2017; Kasiviswanathan et al., 2011) Given a convex, closed and bounded constraint set C ⊆ R p , a data universe D , and a loss function ℓ : C × D 7→ R , a dataset D = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , · · · , ( x n , y n ) ∈ D n with data records { x i } ni =1 ⊂ R p…”
BackgroundSelf-citationPrivate Federated Learning Without a Trusted Server: Optimal Algorithms for Convex LossesPreprint
Lowy, A. M., & Razaviyayn, M. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2106.09779 · Cited by 25
Quantum Local Differential Privacy and Quantum Statistical Query ModelPreprint
Angrisani, A., & Kashefi, E. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2203.03591 · Cited by 25
“Furthermore, Arunachalam et al. [11] asked whether the established equivalence between statistical queries and local di ff erential privacy [54] can be extended to quantum statistical queries and quantum local di ff erential privacy.”
InfluentialFederated Domain-Specific Knowledge Transfer on Large Language Models Using Synthetic DataPreprint
Li, H., Zhao, X., Guo, D., Gu, H., Zeng, Z., Han, Y., Song, Y., Fan, L., & Yang, Q. (2024) · arXiv (Cornell University) · doi:10.48550/arxiv.2405.14212 · Cited by 25
“DP-BART [26] considered text rewriting under LDP [29] to rewrite the input with DP guarantee.”
MethodDistributed Differential Privacy via Shuffling Versus Aggregation: A Curious Study
Wei, Y. X., Jia, J., Wu, Y., Hu, C., Dong, C., Liu, Z., Chen, X., Peng, Y., & Wang, S. (2024) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2024.3351474 · Cited by 24
“In [24] a so-called local model was defined to capture private computation with local differential privacy.”
BackgroundMethodInfluentialIntegrating Differential Privacy and Contextual Integrity
Benthall, S., & Cummings, R. (2024) · ACM Symposium on Computer Science and Law (CSLAW) · doi:10.1145/3614407.3643702 · Cited by 24
“The local model [Kasiviswanathan et al. 2011] assumes that the curator is untrusted, and users do not wish to send their raw data directly to the curator.”
MethodSample Complexity of Locally Differentially Private Quantum Hypothesis Testing
Cheng, H., Hirche, C., & Rouzé, C. (2024) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit57864.2024.10619433 · Cited by 24
“In the classical case such problems have received a fair amount of attention recently [11], [18], [9], [1] and the classical equivalent of our particular problem was investigated in [2].”
BackgroundA game-theoretic approach to quality control for collecting privacy-preserving data
Wang, W., Ying, L., & Zhang, J. (2015) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2015.7447042 · Cited by 24
“The local model of differential privacy, which is a generalization of randomized response [19] and is formalized in [15], has been studied in the literature [13], [14], [16], [25]–[29].”
BackgroundExponential Separations in Local Differential Privacy
Joseph, M., Mao, J., & Roth, A. (2019) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611975994.31 · Cited by 24
A Compression Perspective on Secrecy Measures
Shkel, Y. Y., & Poor, H. V. (2021) · IEEE Journal on Selected Areas in Information Theory · doi:10.1109/jsait.2021.3055692 · Cited by 24
Privacy Amplification by Decentralization
Cyffers, E., & Bellet, A. (2020) · arXiv · doi:10.48550/arxiv.2012.05326 · Cited by 23
“The strongest model is local differential privacy (LDP) (Kasiviswanathan et al., 2008; Duchi et al., 2013), where each participant (user) does not trust anyone and aims to protect against an adversary that can observe ev-a r X i v : 2012 .”
BackgroundPrivate True Data Mining: Differential Privacy Featuring Errors to Manage Internet-of-Things Data
Sei, Y., & Ohsuga, A. (2022) · IEEE Access · doi:10.1109/access.2022.3143813 · Cited by 23
“A randomized mechanism A satisfies (cid:15) -differential privacy if and only if for all Y ⊂ Range ( A ) , the following equation holds : Kasiviswanathan et al. [28] established that this definition could be applied to anonymized data collection.”
BackgroundLocal differentially private federated learning with homomorphic encryption
Zhao, J., Huang, C., Wang, W., Xie, R., Dong, R., & Matwin, S. (2023) · The Journal of Supercomputing · doi:10.1007/s11227-023-05378-x · Cited by 23
“Recently, shuffling 1 3 Local differentially private federated learning with… mechanisms have been introduced which satisfy LDP while enhancing utility, thereby achieving privacy amplification [17, 18].”
BackgroundStrong Data Processing Inequalities for Locally Differentially Private Mechanisms
Zamanlooy, B., & Asoodeh, S. (2023) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit54713.2023.10206578 · Cited by 23
“Since its formal introduction [1, 2], LDP has been extensively incorporated into statistical problems, e.g., locally private mean estimation problem [3–11], locally private distribution estimation problem [12–17], and locally private entropy estimation problem [18, 19], to name a few.”
BackgroundSecurely Sampling Discrete Gaussian Noise for Multi-Party Differential Privacy
Wei, C., Yu, R., Fan, Y., Chen, W., & Wang, T. (2023) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/3576915.3616641 · Cited by 23
Hierarchical Federated Learning with Privacy
Chandrasekaran, V., Banerjee, S., Perino, D., & Kourtellis, N. (2024) · IEEE International Conference on Big Data (BigData) · doi:10.1109/bigdata62323.2024.10826023 · Cited by 24
“Thus far, DP guarantees in FL have been investigated at two levels: at the CA [11] ( i.e., central DP or CDP), or at the client level ( i.e., local DP or LDP) [ 12], [13], [14].”
Sampling and partitioning for differential privacy
Ebadi, H., Antignac, T., & Sands, D. (2016) · Conference on Privacy, Security and Trust · doi:10.1109/pst.2016.7906954 · Cited by 23
Learning New Words from Keystroke Data with Local Differential Privacy
Kim, S., Shin, H., Baek, C., Kim, S.-H., & Shin, J. (2018) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2018.2885749 · Cited by 23
“There are several works on distribution estimation of categorical data under LDP [1], [4], [5], [15], [17], [18], [21], [22], TABLE 3 Parameter Settings for the CCE with RAPPOR Encoding and Hadamard Encoding”
MethodOn the Hardness of PAC-learning Stabilizer States with Noise
Gollakota, A., & Liang, D. (2022) · Quantum · doi:10.22331/q-2022-02-02-640 · Cited by 23
“In fact, in the classical setting, some of the main examples of realistic DP learners are SQ (even though technically the inclusion is known to be strict) [17, 31], and one might expect the same to hold in the quantum setting as well.”
BackgroundNetwork Shuffling: Privacy Amplification via Random Walks
Liew, S. P., Takahashi, T., Takagi, S., Kato, F., Cao, Y., & Yoshikawa, M. (2022) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/3514221.3526162 · Cited by 23
Learning Privately with Labeled and Unlabeled Examples
Beimel, A., Kobbi Nissim, B., & Stemmer, U. (2014) · ACM-SIAM Symposium on Discrete Algorithms (SODA) · doi:10.1137/1.9781611973730.32 · Cited by 23
Renyi Differential Privacy of the Subsampled Shuffle Model in Distributed LearningPreprint
Girgis, A. M., Data, D., & Diggavi, S. N. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2107.08763 · Cited by 23
“Though DP was originally proposed in a framework where data resides centrally [18], for distributed learning the more appropriate notion is of local differential privacy (LDP) [35, 17].”
BackgroundFair Sequential Selection Using Supervised Learning ModelsPreprint
Khalili, M. M., Zhang, X., & Abroshan, M. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2110.13986 · Cited by 23
“Diffrentially private Ãi can be generated using the randomized response algorithm [39], where Ãi is generated based on the following distribution,6”
MethodEfficient Defenses Against Output Poisoning Attacks on Local Differential Privacy
Song, S., Xu, L., & Zhu, L. (2023) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2023.3305873 · Cited by 22
“local differential privacy (LDP) [1], a promising technique for privacy-preserving data aggregation, has been proposed.”
BackgroundPersonalized Privacy-Preserving Framework for Cross-Silo Federated Learning
Tran, V.-T., Pham, H., & Wong, K. (2024) · IEEE Transactions on Emerging Topics in Computing · doi:10.1109/tetc.2024.3356068 · Cited by 22
“prior to sharing it with the server without requiring trust in a server [17].”
BackgroundPrivacy Amplification via Shuffling: Unified, Simplified, and Tightened
Wang, S., Peng, Y., Li, J., Wen, Z. A., Li, Z., Yu, S., Wang, D., & Yang, W. (2024) · Proceedings of the VLDB Endowment · doi:10.14778/3659437.3659444 · Cited by 22
“Definition 3.1 (Hockey-stick divergence). divergence (with parameter 𝑒 ) between two random variables 𝑃 and 𝑄”
BackgroundInfluentialRevealing the True Cost of Locally Differentially Private Protocols: An Auditing Perspective
Arcolezi, H. H., & Gambs, S. (2024) · Proceedings on Privacy Enhancing Technologies · doi:10.56553/popets-2024-0110 · Cited by 22
A Huber Loss Minimization Approach to Mean Estimation under User-level Differential Privacy
Zhao, P., Li, Q., Shen, L. M., Li, Q., Wu, J., & Liu, Z. (2024) · neural information processing systems · doi:10.52202/079017-4131 · Cited by 22
Exact Optimality of Communication-Privacy-Utility Tradeoffs in Distributed Mean Estimation
Isik, B., Chen, W., Özgür, A., Weissman, T., & No, A. (2023) · neural information processing systems · doi:10.52202/075280-1643 · Cited by 22
{Preserving Privacy of Continuous High-dimensional Data with Minimax Filters}
Hamm, J. (2015) · International Conference on Artificial Intelligence and Statistics · Cited by 22
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.