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 901–1,000 of 1,005
Quantum Advantage in Private Multiple Hypothesis Testing
Nam, S.-H., Park, H., Bae, J., & Lee, S.-H. (2025) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit63088.2025.11195216 · Cited by 3
“For a classical privacy mechanism, Definition 1 is reduced to the original definition of the local differential privacy (LDP) [6]–[8] given as follows.”
Demo: Exploring Utility and Attackability Trade-offs in Local Differential Privacy
Zhang, H., Mishra, A. K., & Arcolezi, H. H. (2025) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/3719027.3760706 · Cited by 3
Takagi, S., & Hasegawa, S. (2026) · Proceedings on Privacy Enhancing Technologies · doi:10.56553/popets-2026-0025 · Cited by 3
Bhuekar, A. (2026) · Scientific Reports · doi:10.1038/s41598-026-38537-0 · Cited by 3
Feature-Rich, Data-Private: A Sparse Learning Framework for the High-Dimensional Newsvendor
Chang, J., Yang, L., Zhang, Y., & Zhou, W. (2026) · Operations Research · doi:10.1287/opre.2025.2370 · Cited by 3
Fisher Information as a Utility Metric for Frequency Estimation under Local Differential Privacy
Lopuhaä-Zwakenberg, M., korić, B., & Li, N.-H. (2022) · WPES@CCS · doi:10.1145/3559613.3563194 · Cited by 3
“The de facto standard privacy metric is ε-Local Differential Privacy (ε-LDP) [13]; here ε ∈ [0,∞] is a privacy parameter that determines the maximum amount of information leakage.”
BackgroundThe Sample Complexity of Distribution-Free Parity Learning in the Robust Shuffle Model
Kobbi Nissim, B., & Yan, C. (2022) · Journal of Privacy and Confidentiality · doi:10.29012/jpc.805 · Cited by 3
Block-HRG: Block-based differentially private IoT networks release
Hou, L., Ni, W., Zhang, S., Fu, N., & Zhang, D. (2022) · Ad Hoc Networks · doi:10.1016/j.adhoc.2022.103059 · Cited by 3
PFED-AGG: A Personalized Private Federated Learning Aggregation Algorithm
Zhu, Y., Yan, Y., & Han, Q. (2023) · International Joint Conference on Neural Networks (IJCNN) · doi:10.1109/ijcnn54540.2023.10191978 · Cited by 3
“Definition 3.1 (Local Differential Privacy [31]): A randomized algorithm A satisfies ε -local differential privacy, if for any pair of values y , y ′ ∈ L, and for any O ⊆ Range(A), where the probability space is over the coin flips of A.”
BackgroundInfluentialDifferentially Private Sparse Covariance Matrix Estimation under Lower-Bounded Moment Assumption
Li, H., & Wang, J. (2023) · Mathematics · doi:10.3390/math11173670 · Cited by 3
Tan, Q., Che, X., Wu, S., Qian, Y., & Tao, Y.-H. (2023) · Electronic Research Archive · doi:10.3934/era.2023356 · Cited by 3
“( ε - DP [29]).”
Federated Experiment Design under Distributed Differential Privacy
Chen, W., Cormode, G., Bharadwaj, A., Romov, P., & Özgür, A. (2023) · Warwick Research Archive Portal (University of Warwick) · doi:10.48550/arxiv.2311.04375 · Cited by 3
“We distinguish our Distributed DP model from Local DP (Kasiviswanathan et al., 2011; Evfimievski et al., 2004; Warner, 1965), where data is perturbed on the client-side before the server collects it in the clear.”
BackgroundMethodDifferentially Private Federated Frank-Wolfe
Francis, R., & Chepuri, S. P. (2024) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp48485.2024.10447559 · Cited by 3
Hybrid aggregation for federated learning under blockchain framework
Li, X., Wu, G., Yao, L., & Geng, S. (2024) · Computer Communications · doi:10.1016/j.comcom.2024.06.009 · Cited by 3
Wu, M. H. (2024) · IEEE International Conference on Civil Aviation Safety and Information Technology (ICCASIT) · doi:10.1109/iccasit62299.2024.10827947 · Cited by 3
Shuffle Model of Differential Privacy: Numerical Composition for Federated Learning
Wang, S., Zeng, S., Li, J., Huang, S., & Chen, Y. (2025) · Applied Sciences · doi:10.3390/app15031595 · Cited by 3
Multi-Dimensional Data Collection Under Personalized Local Differential Privacy
Song, K., Sun, M., Zhou, K., Tang, P., Wang, N., & Guo, S. (2024) · IEEE International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom) · doi:10.1109/trustcom63139.2024.00199 · Cited by 3
“Definition 3.1: ( ε -Local Differential Privacy [13]).”
InfluentialPrivate and Effective Range Counting Query Over Evolving Data in Internet of Things
Zhao, P., & Hu, D. (2025) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2025.3590918 · Cited by 3
“Local Differential Privacy (LDP) [36] is proposed as a method to achieve data privacy in a local setting.”
Actual Knowledge Gain as Privacy Loss in Local Privacy Accounting
Pan, M. (2025) · IEEE Computer Security Foundations Workshop (CSFW) · doi:10.1109/csf64896.2025.00014 · Cited by 3
“To protect the true value of an object from being inferred by an adversary, [5] has proposed LDP to ensure a query to yield similar output distributions for all inputs.”
Counting Subgraphs under Shuffle Differential Privacy
Fang, J., & Yi, K. (2025) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/3719027.3765047 · Cited by 3
Necessity of Block Designs for Optimal Locally Private Distribution Estimation
Gentle, A. (2025) · IEEE Information Theory Workshop (ITW) · doi:10.1109/itw62417.2025.11240420 · Cited by 3
“Definition 1 (Local differential privacy [3]) .”
Private Estimation When Data and Privacy Demands Are Correlated
Chaudhuri, S., & Courtade, T. A. (2024) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.forc.2025.3 · Cited by 3
“The two most common models for DP are the central-DP model [22] and the local-DP model [32]; we focus on the central-DP model.”
Exact zCDP Characterizations for Fundamental Differentially Private Mechanisms
Harrison, C., & Manurangsi, P. (2025) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.forc.2026.3 · Cited by 3
Personalized Differential Privacy Preserving Data Aggregation for Smart Homes
Zhang, X., Huang, L., Wang, S., Zhu, Z.-Y., & Xu, H. (2017) · doi:10.2991/icwcsn-16.2017.45 · Cited by 3
“Definition 1 (Local Differential Privacy [16]): A randomized algorithm satisfies ϵ-local differential privacy, if for all pairs of values m and m' D, and for all M ⊆Range( ), P[ (m) M] ≤ exp(ϵ) P[ (m') M], where ϵ denotes privacy budget, and D is the domain of privacy data.”
BackgroundInfluentialHeal the Privacy: Functional Encryption and Privacy-Preserving Analytics
Bakas, A., & Michalas, A. (2022) · IEEE Mediterranean Electrotechnical Conference (MELECON) · doi:10.1109/melecon53508.2022.9843016 · Cited by 3
A Probabilistic Design for Practical Homomorphic Majority Voting with Intrinsic Differential Privacy
Sébert, A. G., Zuber, M., Stan, O., Sirdey, R., & Gouy‐Pailler, C. (2023) · Workshop on Encrypted Computing & Applied Homomorphic Cryptography (WAHC) · doi:10.1145/3605759.3625258 · Cited by 3
Privacy-Preserving Data Collection and Analysis for Smart Cities
Sei, Y. (2024) · Springer eBooks · doi:10.1007/978-981-97-0779-9_5 · Cited by 3
On Doeblin Curves and Their Properties
Lu, W., Makur, A., & Singh, J. (2024) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit57864.2024.10619264 · Cited by 3
Xiong, X., Liu, S., Liu, X., Niu, X., & You, W. (2024) · IEEE International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom) · doi:10.1109/trustcom63139.2024.00188 · Cited by 3
“The current state-of-the-art paradigm for privacy-preserving data collection is local differential privacy[4], which is a distributed variant of differential privacy without depending on a trusted server and has become the most popular privacy protection technique.”
On Heuristic Models, Assumptions, and Parameters
Judson, S., & Feigenbaum, J. (2025) · ACM Journal on Responsible Computing · doi:10.1145/3735562 · Cited by 3
Prink: $$k_s$$-Anonymization for Streaming Data in Apache Flink
Groneberg, P., von Voigt, S. N., Janke, T., Loechel, L., Wolf, K., Grünewald, E., & Pallas, F. (2025) · Lecture notes in computer science · doi:10.1007/978-3-032-00624-0_2 · Cited by 3
Differentially Private Sampling from Distributions
Raskhodnikova, S., Sivakumar, S., Smith, A., & Swanberg, M. (2025) · SIAM Journal on Computing · doi:10.1137/22m1538703 · Cited by 3
Self-citationCompressive Sensing Approaches for Sparse Distribution Estimation Under Local Privacy
Xiong, Z., Sun, J., Mao, X., Wang, J., Shan, Y., & Huang, Z. (2022) · International World Wide Web Conference (WWW) · doi:10.1145/3485447.3512220 · Cited by 3
“LDP distribution estimation.”
BackgroundInfluentialA Geographical and Social Society Attributes Based Privacy Preserving Recommendation Method for POIs
Wang, M., Lei, H., & Li, S. (2022) · Security and Communication Networks · doi:10.1155/2022/4262814 · Cited by 3
“In the proposed method, each user firstly perturbs local data to satisfy LDP and then uploads the noisy data to the recommendation system.”
BackgroundInfluentialA High-Utility Differentially Private Mechanism for Space Information Networks
Zhuo, M., Huang, W. C., Liu, L., Zhou, S., & Tian, Z. (2022) · Remote Sensing · doi:10.3390/rs14225844 · Cited by 3
Li, Q., Lopuhaä-Zwakenberg, M., Heusdens, R. R., & Christensen, M. G. (2022) · European Signal Processing Conference (EUSIPCO) · doi:10.23919/eusipco55093.2022.9909706 · Cited by 3
Mean estimation of multidimensional numerical data with local differential privacy
Ma, Y., Xu, H., Zhang, Y., & Wang, H. (2022) · International Conference on Cloud Computing, Big Data Application and Software Engineering (CBASE) · doi:10.1109/cbase57816.2022.00041 · Cited by 3
Total Variation with Differential Privacy: Tighter Composition and Asymptotic Bounds
Ghazi, E., & Issa, I. (2023) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit54713.2023.10206716 · Cited by 3
“The proof is based on the privacy amplification by subsampling result for ( ε , δ )-DP appearing in [12]–[14] and stated in [15, Theorem 29], hence its tightness derives from the tightness of the ( ε, δ ) -DP result.”
MethodPricing Personalized Preferences for Privacy Protection in Constant Function Market Makers
Goyal, M., & Ramseyer, G. (2023) · doi:10.1145/3605768.3623540 · Cited by 3
Differentially private online Bayesian estimation with adaptive truncation
Yıldırım, S. (2024) · TURKISH JOURNAL OF ELECTRICAL ENGINEERING & COMPUTER SCIENCES · doi:10.55730/1300-0632.4054 · Cited by 3
“2 Remark 1 We remark that Algorithm 1 also satisfies ϵ -local differential privacy [3], since ϵ -DP is satisfied for every user’s piece of data.”
InfluentialThe Symmetric alpha-Stable Privacy Mechanism
Zawacki, C. C., & Abed, E. H. (2024) · Conference on Information Sciences and Systems · doi:10.1109/ciss59072.2024.10480198 · Cited by 3
“is said to be locally differentially private if, when applied to a client’s local dataset D , satisfies for any pair of datapoints v 1 , v 2 ∈ D the following [14]: for all X ∈ R ( M ) .”
BackgroundTowards achieving geo‐indistinguishability for 3D GPS location: A 3D Laplace mechanism approach
Yan, Y., Yan, P., Mahmood, A., Xu, F., & Sheng, Q. Z. (2024) · Concurrency and Computation Practice and Experience · doi:10.1002/cpe.8111 · Cited by 3
Privacy-Utility Tradeoff Based on α-lift
Zarrabian, M. A., & Sadeghi, P. (2024) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton63246.2024.10735268 · Cited by 3
Differentially private query learning: From data publishing to model publishing
Zhu, T., Xiong, P., Li, G., Zhou, W., & Yu, P. S. (2017) · IEEE International Conference on Big Data (BigData) · doi:10.1109/bigdata.2017.8258037 · Cited by 3
Differential Privacy and Its Application
Zhu, T. (2014) · Cited by 3
A Utility-Optimized Framework for Personalized Private Histogram Estimation (Extended Abstract)
Nie, Y., Yang, W., Huang, L., Xie, X., Zhao, Z., & Wang, S. (2019) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2019.00270 · Cited by 3
“In privacy aspect, it can be proved that RCF preserves the original effect of privacy protection, satisfying personalized LDP.”
BackgroundMethodInfluentialDifferentially-private software frequency profiling under linear constraints
Zhang, H., Hao, Y., Latif, S., Bassily, R., & Rountev, A. (2020) · Proceedings of the ACM on Programming Languages · doi:10.1145/3428271 · Cited by 3
"To Tell You the Truth" by Interval-Private Data
Ding, J., & Bangjun, D. (2020) · IEEE International Conference on Big Data (BigData) · doi:10.1109/bigdata50022.2020.9378253 · Cited by 3
“A popular framework to evaluate such privacy is the local differential privacy [4], [5], [12], [13], where the main idea is to restrict the conditional distributions of the privatized data on any two different raw data to be ‘close’.”
BackgroundWeStat: a Privacy-Preserving Mobile Data Usage Statistics System
Canard, S., Desmoulins, N., Hallay, S., Hamdi, A., & Hello, D. L. (2021) · doi:10.1145/3445970.3451151 · Cited by 3
“But this is still feasible, using so called local differential privacy , which may need to add substantially more noise than necessary [11].”
BackgroundDecoupling Statistical Trends from Data Volume on LDP-Based Spatio-Temporal Data Collection
Sasada, T., Taenaka, Y., & Kadobayashi, Y. (2022) · IEEE Future Networks World Forum (FNWF) · doi:10.1109/fnwf55208.2022.00053 · Cited by 3
“By contrast, Local Differential Privacy (LDP) [6] needs no conditions for keeping data anonymized and trusts only the device belonging to a person from whom the location information is collected.”
BackgroundFrom Bounded to Unbounded: Privacy Amplification via Shuffling with Dummies
Takagi, S., Kato, F., Cao, Y., & Yoshikawa, M. (2023) · IEEE Computer Security Foundations Workshop (CSFW) · doi:10.1109/csf57540.2023.00034 · Cited by 3
“Given this, Kasiviswanathan [14] first formalized local differential privacy (LDP) to eliminate the assumption.”
BackgroundPrivacy and the Complexity of Simple Queries
Ullman, J. (2013) · Digital Access to Scholarship at Harvard (DASH) (Harvard University) · Cited by 3
Liu, F. (2016) · arXiv (Cornell University) · Cited by 3
Information and Estimation Theoretic Approaches to Data Privacy
Asoodeh, S. (2017) · QSpace (Queen's University Library) · Cited by 3
Wang, D., Gaboardi, M., & Xu, J. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1802.04085 · Cited by 3
“(Kasiviswanathan et al., 2011; Smith et al., 2017) An algorithm Q is (cid:15) -locally differentially private (LDP) if for all pairs x, x (cid:48) ∈ D , and for all events E in the output space of Q , we have A multi-player protocol is (cid:15) -LDP if for all possible inputs and runs of the…”
BackgroundMethodPrivacy-preserving Recommender Systems Facilitated By The Machine Learning Approach
Wang, J. (2018) · Open Repository and Bibliography (University of Luxembourg) · Cited by 3
Characterizing the Sample Complexity of Private LearnersPreprint
Beimel, A., Kobbi Nissim, B., & Stemmer, U. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1402.2224 · Cited by 3
“The VC-dimension of a concept class is bounded by this quantity (and significantly lower for some interesting concept classes), and hence the results of [16] left open the possibility that the sample complexity of private learning may be significantly higher than that of non-private learning.”
BackgroundResultInfluentialNelson, B., & Reuben, J. (2019) · arXiv (Cornell University) · Cited by 3
A Computational Separation between Private Learning and Online LearningPreprint
Bun, M. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2007.05665 · Cited by 3
On the Round Complexity of the Shuffle ModelPreprint
Beimel, A., Haitner, I., Kobbi Nissim, B., & Stemmer, U. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2009.13510 · Cited by 3
“cular, the execution of Ri may depend on the identity i of player Pi. 4. Local model protocols. An (ε,δ)-differentially private protocol Π with zero shuffle complexity satisfies local differential privacy [26, 27]. 5. Shuffle model with an analyzer. In prior work on the shuffle model one party, A, is an analyzer. The analyzer…”
MethodRandori: Local Differential Privacy for AllPreprint
Nelson, B. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2101.11502 · Cited by 3
Shuffle Gaussian Mechanism for Differential PrivacyPreprint
Liew, S. P., & Takahashi, T. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2206.09569 · Cited by 3
“Within this setup, each user sends a locally differentially private (LDP) [33] report to a trusted shuffler, where the collected reports are anonymized/shuffled, before being forwarded to the untrusted analyzer/server.”
BackgroundPrivacy-preserving data analytics
Zhao, Y. (2022) · DR-NTU (Nanyang Technological University) · doi:10.32657/10356/160032 · Cited by 3
Online Local Differential Private Quantile Inference via Self-normalizationPreprint
Liu, Y., Hu, Q., Ding, L., Jiang, B., & Kong, L. (2023) · arXiv (Cornell University) · doi:10.48550/arxiv.2306.10260 · Cited by 3
“The concept of LDP was first introduced formally by (Kasiviswanathan et al., 2011), but its early form can be traced back to (Evfimievski et al., 2003) and (Warner, 1965), in the name of ”amplification” and ”randomized response survey,” respectively.”
BackgroundImproving the Variance of Differentially Private Randomized Experiments through ClusteringPreprint
Javanmard, A., Mirrokni, V., & Pouget-Abadie, J. (2023) · arXiv (Cornell University) · doi:10.48550/arxiv.2308.00957 · Cited by 3
“In other words, the U NIFORM - PRIOR -DP mechanism provides a local DP guarantee, defined by (Kasiviswanathan et al., 2011), which is stronger than a DP guarantee.”
Private Truly-Everlasting Robust-PredictionPreprint
Stemmer, U. (2024) · arXiv (Cornell University) · doi:10.48550/arxiv.2401.04311 · Cited by 3
“The line of work on private learning , introduced by Ka-siviswanathan et al. (2011), aims to understand the computational and statistical aspects of PAC learning while providing strong privacy protections for the training data.”
BackgroundScholler, R. (2024) · theses.fr (ABES) · doi:10.70675/8c6a1a6dz39b2z4274z82e6zd5df3a23a9bb · Cited by 3
Bridging Privacy and Robustness for Trustworthy Machine LearningPreprint
Zhang, X., & Chen, W. (2024) · arXiv (Cornell University) · doi:10.48550/arxiv.2403.16591 · Cited by 3
“In groundbreaking research, Kasiviswanathan et al. (2011) scrutinized the concept classes amenable to learning under differential privacy.”
Chen, W., Isik, B., Kairouz, P., No, A., Oh, S., & Xu, Z. (2024) · arXiv (Cornell University) · doi:10.48550/arxiv.2405.02341 · Cited by 3
“…work, we consider FL (or more specifically, DME) under a central -DP setting where the server is trusted, which is different from the local DP model (Ka-siviswanathan et al., 2011) 2 and the distributed DP model with secure aggregation (Bonawitz et al., 2016; Bell et al., 2020; Kairouz et al.,…”
MethodLocally Private Sampling with Public DataPreprint
Zamanlooy, B., Díaz, M., & Asoodeh, S. (2024) · arXiv (Cornell University) · doi:10.48550/arxiv.2411.08791 · Cited by 3
“To relax this assumption, local differential privacy (LDP) was introduced by Kasiviswanathan et al. (2011), allowing users to randomize their data on their own devices before sharing it with an untrusted curator.”
Private Rate-Constrained Optimization with Applications to Fair Learning
Yaghini, M., Cebere, T., Menart, M., Bellet, A., & Papernot, N. (2025) · International Conference on Learning Representations · doi:10.48550/arxiv.2505.22703 · Cited by 3
“This allows us to leverage privacy amplification by subsampling [37, 5] for both the Laplace mechanism used in histogram computation (Section 4.1) and the Gaussian mechanism used for the per-sample gradient (Section 4.2).”
InfluentialDifferentially Private aggregate hints in mev-sharePreprint
Passerat‐Palmbach, J., & Wadhwa, S. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2508.14284 · Cited by 3
“The formalization of this intuition is provided by privacy amplification by subsampling [5, 16].”
High-Probability Bounds For Heterogeneous Local Differential PrivacyPreprint
Aliakbarpour, M., Fallah, A., Roy, S., & Stevens, R. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2510.11895 · Cited by 3
“Local Differential Privacy (LDP) offers a compelling solution, enabling the analysis of population-level statistics without exposing any individual’s raw data—even to the aggregator [Dwork et al., 2006, Kasiviswanathan et al., 2011].”
Heavy-Tailed Privacy: The Symmetric alpha-Stable Privacy MechanismPreprint
Zawacki, C. C., & Abed, E. H. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2504.18411 · Cited by 3
“The mechanism M locf is said to be locally differentially privacy if, for any pair of data points v 1 , v 2 ∈ D , it satisfies the following Kasiviswanathan et al. (2011): for all X ∈ R ( M locf ) .”
Practitioners' Perspectives on a Differential Privacy Deployment RegistryPreprint
Nanayakkara, P., Ghazi, E., & Vadhan, S. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2509.13509 · Cited by 3
“On the other hand, in the local model [2, 26], the curator is not permitted to access the underlying data.”
Personalized Federated Training of Diffusion Models with Privacy GuaranteesPreprint
Patel, K. K., Zhang, W., & Wang, L. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2504.00952 · Cited by 3
“To formalize privacy in the federated multi-distribution setting, we use two notions: central differential privacy (central DP) [27] and local differential privacy (local DP) [50].”
Generation of synthetic mobility data with differential privacy guarantees
Rubio Jornet, V. (2023) · UPCommons institutional repository (Universitat Politècnica de Catalunya) · Cited by 3
The disparate impact of noise on quantum learning algorithms
Angrisani, A. (2023) · theses.fr (ABES) · doi:10.70675/69f942ebz4417z4eceza746z1c9d436d09bb · Cited by 3
Nearly Linear Private Learning of Littlestone ClassesPreprint
Moran, S., & Yan, C. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2610.23160 · Cited by 3
“Private PAC learning combines privacy with the usual prediction guarantee [15].”
Zhao, X., Zhou, R., & Liu, F. (2024) · IEEE Transactions on Privacy · doi:10.1109/tp.2024.3502320 · Cited by 2
“This result is used implicitly in designing a private proba-bilistically approximately correct learner [12] in [13].”
Analysis, Design, and Implementation of a User-Friendly Differential Privacy Application
Tjhin, R., Akbar, M. S., Canonne, C. L., & Bashir, R. (2025) · Sensors · doi:10.3390/s25051358 · Cited by 2
“This concept, known as local differential privacy [30], is based on the notion of differential privacy.”
Differentially Private and Communication-efficient Decentralized Learning Using Deep Quantizers
Francis, R., & Chepuri, S. P. (2025) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp49660.2025.10888588 · Cited by 2
“In decentralized learning, the focus is mainly on ensuring privacy for individual clients, i.e., maintaining local differential privacy (LDP) [10]–[12] while ensuring convergence for the global model.”
Pan, M. (2025) · IEEE Computer Security Foundations Workshop (CSFW) · doi:10.1109/csf64896.2025.00024 · Cited by 2
“To address these concerns, Local Differential Privacy (LDP) [3] has been proposed, which requires enough perturbation on individual data on the client side before sending them to the server for statistical analysis, theoretically preventing eavesdropping or data breaches.”
Multi-Class Item Mining Under Local Differential Privacy
Mao, Y., Ye, Q., Du, R., Wang, Q., Huang, K., & Hu, H. (2025) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde65448.2025.00265 · Cited by 2
“The formal definition of LDP is as follows: Definition 2 (Local Differential Privacy [4], [5]) .”
InfluentialVFBoost-MO: Scable vertical federated gradient boosting decision tree for multi-class problem
Yu, B., Shen, H., Yang, Y., Xu, Q., & He, W. (2025) · Journal of Systems Architecture · doi:10.1016/j.sysarc.2025.103545 · Cited by 2
Privacy for Free: Leveraging Local Differential Privacy Perturbed Data from Multiple Services
Du, R., Ye, Q., Fu, Y., & Hu, H. (2025) · Proceedings of the VLDB Endowment · doi:10.14778/3725688.3725703 · Cited by 2
LabelDP Leaks Privacy — A Tightened Correlation-Aware Privacy Model for Labeled Training Data
Xue, Q., Ye, Q., Hu, H., Lou, J., Li, J., Fang, C., & Shi, J. (2025) · IEEE Transactions on Dependable and Secure Computing · doi:10.1109/tdsc.2025.3607786 · Cited by 2
“To prevent the infringement on individual privacy, businesses have been adopting LDP [1].”
InfluentialBai, Y., Xiao, L., Zhao, H., & Shi, X. (2025) · Information Sciences · doi:10.1016/j.ins.2025.122695 · Cited by 2
Frequency Estimation of Correlated Multi-attribute Data under Local Differential Privacy
Seeam, S. R., Ye, Z., & Hu, Y. (2026) · Proceedings on Privacy Enhancing Technologies · doi:10.56553/popets-2026-0034 · Cited by 2
Differentially Private Bilevel Optimization: Efficient Algorithms with Near-Optimal Rates
Lowy, A. M., & Liu, D. (2025) · neural information processing systems · doi:10.52202/085713-0916 · Cited by 2
Managing Correlations in Data and Privacy Demand
Chaudhuri, S., & Courtade, T. A. (2025) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/3719027.3765048 · Cited by 2
VPrivKV: Verifiable Local Differential Privacy for Key-Value Data
Zhou, Z., Xu, L., & Zhu, L. (2025) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2025.3639964 · Cited by 2
“To address this issue, Local Di ff erential Privacy (LDP) [1] has been proposed as a rigorous framework, allowing the user to locally perturb his data with randomized mechanisms before transmission, thereby ensuring strong individual-level privacy.”
Locally Optimal Private Sampling: Beyond the Global Minimax
Ghoukasian, H., Lee, B., & Asoodeh, S. (2025) · neural information processing systems · doi:10.52202/085713-5285 · Cited by 2
Xu, S., Hua, Z., & Zheng, Y. (2026) · IEEE Transactions on Dependable and Secure Computing · doi:10.1109/tdsc.2026.3663543 · Cited by 2
“On the other hand, local differential privacy (LDP) [8] has been explored as a more appropriate framework for FL [9], [10], [28].”
Sequential Change Detection with Local Differential Privacy
Zhang, L., Liu, X., Zhang, R., & Xie, L. (2026) · Entropy · doi:10.3390/e28040402 · Cited by 2
“Instead, each participant may transmit only a randomized or sanitized version of their observation, typically under the framework of local differential privacy (LDP) [18].”
InfluentialYoon, S.-M., Park, H.-Y., Nam, S.-H., & Lee, S.-H. (2026) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2026.3696567 · Cited by 2
“Comparison between two binary randomized response models, where ˆ X denotes a guess about X based on Y . little about the true record, thereby removing the need for a trusted curator [1], [2].”
Sparse Estimation Under Local Differential Privacy at All Privacy Levels
Zhao, P., Ye, Q., Wang, S., Feng, J., Yue, S., Chen, Z., & Cao, X. (2026) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp63933.2026.00234 · Cited by 2
“As the de facto standard for privacy protection, local differential privacy (LDP) [13], [14] has been applied in sparse data estimation in some recent studies [15], [16], [17], [18], [19].”
Privacy-Preserving Traffic Flow Release with Consistency Constraints
Zhu, X., Zheng, L., Zhang, C., Cheng, P., Meng, R., Chen, L., Lin, X., & Yin, J. P. (2024) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde60146.2024.00138 · Cited by 2
“Definition II.4 (Local Differential Privacy [9]) .”
Johora, F. T., Jony, M. H., Habiba, S. U., & Khatun, A. (2019) · International Conference on Sustainable Technologies for Industry 5.0 (STI) · doi:10.1109/sti47673.2019.9068100 · Cited by 2
“Generally, the local algorithm [5] automatically adds random information to each person’s information.”
Background
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.