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 401–500 of 1,005
Differentially Private Streaming to Untrusted Edge Servers in Intelligent Transportation System
Ghane, S., Jolfaei, A., Kulik, L., & Ramamohanarao, K. (2019) · IEEE International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom) · doi:10.1109/trustcom/bigdatase.2019.00113 · Cited by 22
“To address the problem of untrusted server, a number of works [7], [8], [9] investigated local differential privacy [10] mechanisms, which randomize the attributed values before leaving the user’s device.”
BackgroundInfluentialDifferentially Private Federated Learning with Shuffling and Client Self-Sampling
Girgis, A. M., Data, D., & Diggavi, S. N. (2021) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit45174.2021.9517906 · Cited by 22
A Survey on Statistical, Information, and Estimation—Theoretic Views on Privacy
Hsu, H., Gil, N. M., Bertrán, M., Sapiro, G., & Calmon, F. P. (2021) · IEEE BITS the Information Theory Magazine · doi:10.1109/mbits.2021.3108124 · Cited by 22
Model-based Differentially Private Data SynthesisPreprint
Liu, F. (2016) · arXiv (Cornell University) · Cited by 22
Differentially Private Learning of Undirected Graphical Models using Collective Graphical ModelsPreprint
Bernstein, G., McKenna, R., Sun, T., Sheldon, D. R., Hay, M., & Miklau, G. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1706.04646 · Cited by 22
“, 2016), and parameter estimation (Smith, 2011); and theoretical analysis of what can be learned privately (e.g., Blum et al., 2005; Kasiviswanathan et al., 2011).”
BackgroundInformation Laundering for Model PrivacyPreprint
Wang, X., Xiang, Y., Gao, J. Y., & Ding, J. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2009.06112 · Cited by 22
“Data privacy concerns the protection of (usually personal) data information from different perspectives, including lossless cryptography [9], [10], randomized data collection [11], [12], statistical database query [13], [14].”
BackgroundQuantum Differential Privacy in the Local Model
Angrisani, A., & Kashefi, E. (2025) · IEEE Transactions on Information Theory · doi:10.1109/tit.2025.3552671 · Cited by 21
“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.”
InfluentialChen, E., Cao, Y., & Ge, Y. (2024) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v38i10.29005 · Cited by 21
Ren, X., Fan, J., Xu, N., Wang, S., Dong, C., & Wen, Z. A. (2024) · Information Sciences · doi:10.1016/j.ins.2024.120720 · Cited by 21
“[38]: An algorithm ( ⋅ ) adheres to 𝜀 -local differential privacy ( 𝜀 -LDP), with 𝜀 ≥ 0 , if for any two inputs 𝑥 1 , 𝑥 2 and any output 𝑜 , the following inequality holds: This condition specifies the degree of privacy safeguarding, where lower 𝜀 values signify enhanced privacy.”
MethodLocal Differential Privacy for Sampling
Husain, H., Balle, B., Cranko, Z., & Nock, R. (2020) · International Conference on Artificial Intelligence and Statistics · Cited by 21
Improved Information Theoretic Generalization Bounds for Distributed and Federated Learning
Barnes, L. P., Dytso, A., & Poor, H. V. (2022) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit50566.2022.9834700 · Cited by 21
LDPart: Effective Location-Record Data Publication via Local Differential Privacy
Zhao, X., Li, Y., Yuan, Y., Bi, X., & Wang, G. (2019) · IEEE Access · doi:10.1109/access.2019.2899099 · Cited by 21
“In addition, some efforts are also devoted to explore a variety of perturbation mechanisms for achieving theoretical optimal utility [8], [35], [39], [40].”
BackgroundFaster Algorithms for Privately Releasing MarginalsPreprint
Thaler, J., Ullman, J., & Vadhan, S. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1205.1758 · Cited by 21
“Connections between differentially private data analysis and the statistical queries model have been studied extensively [2, 16, 11].”
BackgroundDifferentially Private Assouad, Fano, and Le CamPreprint
Acharya, J., Sun, Z., & Zhang, H. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2004.06830 · Cited by 21
The Privacy Power of Correlated Noise in Decentralized LearningPreprint
Allouah, Y., Koloskova, A., Firdoussi, A. E., Jaggi, M., & Guerraoui, R. (2024) · arXiv (Cornell University) · doi:10.48550/arxiv.2405.01031 · Cited by 21
“Several threat models have been considered in decentralized learning, the strongest corresponding to the classical notion of local differential privacy (LDP) (Kasiviswanathan et al., 2011).”
BackgroundTree-based Models for Vertical Federated Learning: A Survey
Qian, B., Xie, Y., Li, Y., Ding, B., & Zhou, J. (2025) · ACM Computing Surveys · doi:10.1145/3728314 · Cited by 20
QuanCrypt-FL: Quantized Homomorphic Encryption with Pruning for Secure Federated Learning
Mia, M. J., & Amini, M. H. (2025) · IEEE Transactions on Artificial Intelligence · doi:10.1109/tai.2025.3612906 · Cited by 20
Interaction is Necessary for Distributed Learning with Privacy or Communication Constraints
Dagan, Y., & Feldman, V. (2020) · Journal of Privacy and Confidentiality · doi:10.1145/3357713.3384315 · Cited by 20
“The converse of this connection is also known: SQ algorithms can be simulated by ǫ - compositional LDP protocols (and this simulation preserves the number of rounds of interaction) [KLNRS11].”
BackgroundMethodInfluentialPPDU: dynamic graph publication with local differential privacy
Hou, L., Ni, W., Zhang, S., Fu, N., & Zhang, D. (2023) · Knowledge and Information Systems · doi:10.1007/s10115-023-01838-1 · Cited by 20
Schäler, C., Hütter, T., & Schäler, M. (2023) · Proceedings of the VLDB Endowment · doi:10.14778/3594512.3594515 · Cited by 20
“In the local model [23], each individual stream (i.”
BackgroundGuiding Text-to-Text Privatization by Syntax
Arnold, S., Yesilbas, D., & Weinzierl, S. (2023) · Workshop on Trustworthy Natural Language Processing (TrustNLP) · doi:10.18653/v1/2023.trustnlp-1.14 · Cited by 20
Li, Q., Gundersen, J. S., Lopuhaä-Zwakenberg, M., & Heusdens, R. R. (2023) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2023.3343599 · Cited by 20
“Specifically, this approach falls under local differential privacy (LDP) [45], in which there is no centralized server available and Authorized licensed use limited to the terms of the applicable license agreement with IEEE.”
BackgroundBuying Data from Privacy-Aware Individuals: The Effect of Negative Payments
Wang, W., Ying, L., & Zhang, J. (2016) · Lecture notes in computer science · doi:10.1007/978-3-662-54110-4_7 · Cited by 20
Privacy-Preserving Analytics on Decentralized Social Graphs: The Case of Eigendecomposition
Wang, S., Zheng, Y., Jia, X., & Yi, X. (2022) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2022.3185079 · Cited by 20
“that assumes a trusted data collector which can collect and see raw data, the recently emerging LDP model [37] considers the data collector to be untrusted, in which each user only reports perturbed data with calibrated noises added.”
BackgroundIterative Constructions and Private Data ReleasePreprint
Gupta, A., Roth, A., & Ullman, J. (1987) · arXiv (Cornell University) · doi:10.1184/r1/6606647 · Cited by 20
Synthetic Data Generators: Sequential and PrivatePreprint
Bousquet, O., Livni, R., & Moran, S. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1902.03468 · Cited by 20
“– We show that a class is DP–Foolable if and only if it is Privately (proper) PAC learnable [30].”
BackgroundLowy, A. M., Li, Z., Liu, J., Koike–Akino, T., Parsons, K., & Wang, Y. (2024) · arXiv (Cornell University) · doi:10.48550/arxiv.2402.09540 · Cited by 20
“A consequence of the equivalence between (2) and (3) is that if n “ 1 , then ε -PMP and ε -DP are equivalent—and satisfy ε - local differential privacy (Kasiviswanathan et al. 2011): Corollary 4.”
BackgroundXu, C., Mei, X., Liu, D., Zhao, K., & Ding, A. S. (2022) · Complex & Intelligent Systems · doi:10.1007/s40747-022-00917-0 · Cited by 19
“Local differential privacy (LDP) is proposed as a distributed variant of differential privacy, which locally perturbs the data of each user on the client-side [31–33].”
BackgroundMAGO: Maliciously Secure Subgraph Counting on Decentralized Social Graphs
Wang, S., Zheng, Y., Jia, X., Wang, Q., & Wang, C. (2023) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2023.3271888 · Cited by 19
“Little work has been done when graphs are presented in a decentralized manner, where the state-of-the-art methods are [9], [10], which fully rely on local differential privacy (LDP) [15] to protect the privacy of local views from a data collector counting subgraphs over a decentralized social graph.”
BackgroundTowards Differential Privacy in Sequential Recommendation: A Noisy Graph Neural Network Approach
Hu, W., & Fang, H. (2024) · ACM Transactions on Knowledge Discovery from Data · doi:10.1145/3643821 · Cited by 19
“They utilize edge-level differential privacy to protect graph topology data and local differential privacy [58] to protect user attributes.”
BackgroundExtremal Mechanisms for Pointwise Maximal Leakage
Grosse, L., Saeidian, S., & Oechtering, T. J. (2024) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2024.3449556 · Cited by 19
“With implementations in systems by Google [3] and Apple [4], among others, differential privacy (DP) [5] and its local variant, local differential privacy (LDP) [6], [7] are today often used in practical implementations.”
PrivFED: Protecting User Privacy in Federated Learning Systems Through Differential Privacy
Thumula, K., Holla, H., Gutti, C., Sasikumar, A. A., & Gogineni, H. (2025) · International Conference on Electronics, Materials Engineering & Nano-Technology (IEMENTech) · doi:10.1109/iementech65115.2025.10959665 · Cited by 19
“While implicitly introduced in [18] and formalized in [19], LDP only recently gained widespread adoption in applications like private data collection [7], [9], [10] and federated learning model training.”
On the Round Complexity of the Shuffle Model
Beimel, A., Haitner, I., Kobbi Nissim, B., & Stemmer, U. (2020) · Lecture notes in computer science · doi:10.1007/978-3-030-64378-2_24 · Cited by 19
Utility Fairness for the Differentially Private Federated-Learning-Based Wireless IoT Networks
Alvi, S. A., Hong, Y., & Durrani, S. (2022) · IEEE Internet of Things Journal · doi:10.1109/jiot.2022.3165596 · Cited by 19
“Moreover, if the training data are sampled from the data set with probability q, then from the privacy amplification theorem proposed in [35], Algorithm 1 will be (O(q ),O(qδ))-DP.”
MethodGeo-Graph-Indistinguishability: Location Privacy on Road Networks with Differential Privacy
Takagi, S., Cao, Y., Asano, Y., & Yoshikawa, M. (2023) · IEICE Transactions on Information and Systems · doi:10.1587/transinf.2022dap0011 · Cited by 19
Privacy-Aware Distributed Hypothesis Testing
Sreekumar, S., Cohen, A., & Gündüz, D. (2020) · Entropy · doi:10.3390/e22060665 · Cited by 19
Privacy Preserving Stream Analytics: The Marriage of Randomized Response and Approximate ComputingPreprint
Quoc, D. L., Beck, M., Bhatotia, P., Chen, R., Fetzer, C. W., & Strufe, T. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1701.05403 · Cited by 19
“l back to differential privacy using the result from [45], Proposition 3, which states that any ε-zeroknowledgeprivatealgorithmis also2ε-differentiallyprivate. Using the results from sampling secrecy [62], which achieve a privacy boost by applying pre-sampling before using a differentiallyprivate algorithm, we derive…”
MethodEstimating Smooth GLM in Non-interactive Local Differential Privacy Model with Public Unlabeled DataPreprint
Wang, D., Hu, L., Zhang, H., Gaboardi, M., & Xu, J. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1910.00482 · Cited by 19
“[22] Shiva Prasad Kasiviswanathan, Homin K Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith.”
BackgroundMethodPAC learning with stable and private predictionsPreprint
Dagan, Y., & Feldman, V. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1911.10541 · Cited by 19
“Privacy amplification by subsampling: The following lemma is an adaptation of the standard privacy amplification-by-sampling technique (Kasiviswanathan et al., 2011) to private prediction.”
BackgroundMethodInfluentialShuffle Private Stochastic Convex OptimizationPreprint
Cheu, A., Joseph, M., Mao, J., & Peng, B. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2106.09805 · Cited by 19
“A similar utility gap between central and local privacy also appears in many other problems (Kasiviswanathan et al., 2011; Chan et al., 2012; Duchi et al., 2018; Duchi and Rogers, 2019; Joseph et al., 2019).”
BackgroundPrivate learning implies quantum stabilityPreprint
Arunachalam, S., Quek, Y., & Smolin, J. A. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2102.07171 · Cited by 19
“Classically, for the Boolean setting, it is well-known that the so-called Standard Optimal Algorithm is an online learner for any concept class, that makes at most Littlestone dimension-many mistakes [22].”
BackgroundMethodInfluentialStatistical Indistinguishability of Learning AlgorithmsPreprint
Kalavasis, A., Karbasi, A., Moran, S., & Velegkas, G. (2023) · International Conference on Machine Learning · doi:10.48550/arxiv.2305.14311 · Cited by 22
“The last step of the algorithm is to feed this list into the Generic Private Learner (cf. Lemma D.2) with privacy parameters (ε/2, 0) and accuracy parameters (α′/2, β′/3).”
MethodInfluentialAlmost Tight Bounds for Differentially Private Densest Subgraph
Dinitz, M., Kale, S., Lattanzi, S., & Vassilvitskii, S. (2025) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611978322.94 · Cited by 18
“This model was originally introduced by [47] in the context of learning, and has since become an important model of privacy (including in practice; see, for example, the discussion in [18]).”
Differentially private high dimensional sparse covariance matrix estimation
Wang, D., & Xu, J. (2021) · Theoretical Computer Science · doi:10.1016/j.tcs.2021.03.001 · Cited by 18
Differentially Private Linear Bandits with Partial Distributed Feedback
Li, F., Zhou, X., & Ji, B. (2022) · International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt) · doi:10.23919/wiopt56218.2022.9930524 · Cited by 18
“…the privacy, we will also incorporate other popular DP models, including the stronger local model (where each client directly protects her data) [31] and the recently proposed shuffle model (where a trusted shuffler between clients and server is adopted to amplify privacy) [32], in a unified…”
MethodIndividual fairness for local private graph neural network
Wang, X., Gu, T., Bao, X., Chang, L., & Li, L. (2023) · Knowledge-Based Systems · doi:10.1016/j.knosys.2023.110490 · Cited by 18
Unifying Privacy Measures via Maximal (α, β)-Leakage (MαbeL)
Gilani, A., Kurri, G. R., Kosut, O., & Sankar, L. (2024) · IEEE Transactions on Information Theory · doi:10.1109/tit.2024.3384922 · Cited by 18
“In an effort to quantify this leakage precisely, a variety of privacy measures have been proposed in computer science [2], [3], [4], [5], [6], [7], [8] and in information theory [9], [10], [11], [12], [13], [14], [15], [16], [17], [18], [19], [20].”
BackgroundZhang, T., & Zhu, Q. (2016) · ACM Workshop on Artificial Intelligence and Security (AISec) · doi:10.1145/2996758.2996762 · Cited by 18
“For example, Kasiviswanathan et al. have derived a general method for probably approximately correct (PAC, [19]) in [11].”
MethodDifferentially Private Release and Learning of Threshold FunctionsPreprint
Bun, M., Kobbi Nissim, B., Stemmer, U., & Vadhan, S. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1504.07553 · Cited by 18
Data Sanitisation Protocols for the Privacy Funnel with Differential Privacy GuaranteesPreprint
Lopuhaä-Zwakenberg, M., Tong, H., & Škorić, B. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2008.13151 · Cited by 18
“In this paper, we adapt two Differential Privacy-like privacy metrics to the Privacy Funnel situation, namely Local Differential Privacy (LDP) [15] and Local Information Privacy (LIP) [13][24].”
BackgroundMethodInfluentialPrivate Learning of Halfspaces: Simplifying the Construction and Reducing the Sample ComplexityPreprint
Kaplan, H. Y., Mansour, Y., Stemmer, U., & Tsfadia, E. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2004.07839 · Cited by 18
“Formally, Definition 2.9 (Private PAC Learning [Kasiviswanathan et al., 2011]) .”
BackgroundMethodInfluentialThe Role of Interactivity in Structured EstimationPreprint
Acharya, J., Canonne, C. L., Sun, Z., & Tyagi, H. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2203.06870 · Cited by 18
“[33], who designed a problem for which there show a separation between interactive and noninteractive schemes.”
BackgroundLocally differentially private high-dimensional data synthesis
Chen, X., Wang, C., Yang, Q., Hu, T., & Jiang, C. (2022) · Science China Information Sciences · doi:10.1007/s11432-022-3583-x · Cited by 17
Tchaye-Kondi, J., Zhai, Y., Shen, J., & Zhu, L. (2023) · IEEE Transactions on Network and Service Management · doi:10.1109/tnsm.2023.3266257 · Cited by 17
“The concept was introduced in [21], and it is formalized as follows: Definition 2 ( ε − LDP ): Let ε > = 0 and A be a randomized algorithm that takes its input in X with X representing the user local data.”
BackgroundUnbiased Locally Private Estimator for Polynomials of Laplacian Variables
Hillebrand, Q., Suppakitpaisarn, V., & Shibuya, T. (2023) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/3580305.3599537 · Cited by 17
“( 1 ) ( 2 ) ( 𝑗 ) ( 𝑗 ) The mechanism ( R , A ) is ( 1 ) ( 2 ) , any user 𝑖 , 𝑆 ⊂ S , and 𝑥 access to the output of the randomized algorithm R , cannot obtain 𝑖 Definition 3 (Edge Local Differential Privacy [21]) .”
A Federated Learning Framework Based on Differentially Private Continuous Data Release
Cai, J., Liu, X., Ye, Q., Liu, Y., & Wang, Y. (2024) · IEEE Transactions on Dependable and Secure Computing · doi:10.1109/tdsc.2024.3364060 · Cited by 17
“2, FL-DPCR is an FL framework with local DP (LDP) [38].”
MethodMeisenbacher, S., Chevli, M., & Matthes, F. (2024) · ACM International Workshop on Security and Privacy Analytics (IWSPA) · doi:10.1145/3643651.3659896 · Cited by 17
Secure Aggregation Is Not Private Against Membership Inference Attacks
Ngo, K., Östman, J., Durisi, G., & Amat, A. G. I. (2024) · Lecture notes in computer science · doi:10.1007/978-3-031-70365-2_11 · Cited by 17
Privacy Passport: Privacy-Preserving Cross-Domain Data Sharing
Chen, X., Wang, C., Yang, Q., Hu, T., & Jiang, C. (2024) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2024.3515797 · Cited by 17
Privacy-Preserving Mechanisms for Multi-Label Image Recognition
Xu, H., Cai, Z., & Li, W. (2022) · ACM Transactions on Knowledge Discovery from Data · doi:10.1145/3491231 · Cited by 17
Privacy-Preserving Data Mining on Blockchain-Based WSNs
Hrovatin, N., Tošić, A., Mrissa, M., & Kavšek, B. (2022) · Applied Sciences · doi:10.3390/app12115646 · Cited by 17
Mitigating Statistical Bias within Differentially Private Synthetic Data
Ghalebikesabi, S., Wilde, H., Jewson, J., Arnaud Doucet, B., Vollmer, S. J., & Holmes, C. C. (2021) · Warwick Research Archive Portal (University of Warwick) · doi:10.48550/arxiv.2108.10934 · Cited by 17
“Lastly, the differential privacy with respect to the dataset follows from the amplification theorem [Kasiviswanathan et al., 2011], the fact that sampling one particular private observation within a lot of size L is q = L N D + N G and the reasoning behind the moment accountant of Abadi et al.…”
BackgroundControlling Privacy Loss in Sampling Schemes: An Analysis of Stratified and Cluster Sampling
Bun, M., Drechsler, J., Gaboardi, M., McMillan, A., & Sarathy, J. (2020) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.forc.2022.1 · Cited by 17
“Prior results on privacy amplification by subsampling [23, 33, 11, 31, 6] all focus on constant sampling rates where the sampling rate (the fraction of the data set sampled) is fixed in advance.”
BackgroundBarnes, L. P., Dytso, A., & Poor, H. V. (2022) · Entropy · doi:10.3390/e24091178 · Cited by 17
“There has been considerable interest in understanding the impact of both communication constraints [7], [8] and privacy constraints [9], [10], [11], [12] on the performance of machine learning systems, and in designing protocols that efficiently train systems under these constraints.”
BackgroundCommunity detection in decentralized social networks with local differential privacy
Fu, N., Ni, W., Hou, L., Zhang, D., & Zhang, R. (2024) · Information Sciences · doi:10.1016/j.ins.2024.120164 · Cited by 17
Statistical Active Learning Algorithms for Noise Tolerance and Differential Privacy
Balcan, M.-F., & Feldman, V. (2014) · Algorithmica · doi:10.1007/s00453-014-9954-9 · Cited by 17
The Value of Privacy: Strategic Data Subjects, Incentive Mechanisms, and Fundamental Limits
Wang, W., Ying, L., & Zhang, J. (2018) · ACM Transactions on Economics and Computation · doi:10.1145/3232863 · Cited by 17
“The local model of differential privacy, which is a generalization of randomized response [31] and is formalized in Reference [19], has been studied in the literature [1, 5–9, 16, 18, 27, 29, 30].”
BackgroundHDDA: DataSifter: statistical obfuscation of electronic health records and other sensitive datasets
Marino, S., Zhou, N., Zhao, Y., Wang, L., Wu, Q., & Dinov, I. D. (2018) · Journal of Statistical Computation and Simulation · doi:10.1080/00949655.2018.1545228 · Cited by 17
“Model-free Probably Approximately Correct (PAC) learning provides another solution for low-dimensional synthetic data sharing [12].”
BackgroundTrust but Verify: Cryptographic Data Privacy for Mobility Management
Tsao, M., Yang, K., Zoepf, S. M., & Pavone, M. (2022) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2022.3141027 · Cited by 17
Usable Differential Privacy: A Case Study with PSIPreprint
Murtagh, J., Taylor, K., Kellaris, G., & Vadhan, S. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1809.04103 · Cited by 17
“Lemma 1 (Secrecy of the sample [11, 20]) Let M be an ( (cid:15), δ ) -differentially private algorithm for datasets of size n .”
BackgroundShuffled Model of Federated Learning: Privacy, Communication and Accuracy Trade-offs
Girgis, A. M., Data, D., Diggavi, S., Kairouz, P., & Suresh, A. T. (2020) · arXiv · doi:10.48550/arxiv.2008.07180 · Cited by 16
PrivLM-Bench: A Multi-level Privacy Evaluation Benchmark for Language Models
Li, H., Guo, D., Li, D., Fan, W., Hu, Q., Liu, X., Chan, C., Yao, D., Yao, Y., & Song, Y. (2024) · Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) · doi:10.18653/v1/2024.acl-long.4 · Cited by 16
“…PPLMs’ privacy and it is rather hard to make a fair comparison among PPLMs. Firstly, Different DP formulations such as central DP, lo-cal DP (Kasiviswanathan et al., 2011), and d χ privacy (Chatzikokolakis et al., 2013) assign distinct heuristic meanings to DP parameters to implement PPLMs.”
Differentially Private Heatmaps
Ghazi, B., He, J., Kohlhoff, K., Kumar, R., Manurangsi, P., Navalpakkam, V., & Valliappan, N. (2023) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v37i6.25933 · Cited by 16
Locally Differentially Private Frequency Estimation Based on Convolution Framework
Fang, H., Chen, L., Liu, Y., & Gao, Y. (2023) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp46215.2023.10179389 · Cited by 16
“Recently, local differential privacy (LDP) [3] has been proposed, which is a more rigorous differential privacy technique in the local setting for protecting personal privacy.”
BackgroundTotal Variation Meets Differential Privacy
Ghazi, E., & Issa, I. (2024) · IEEE Journal on Selected Areas in Information Theory · doi:10.1109/jsait.2024.3384083 · Cited by 16
“Proposition 1: The proof (deferred to Appendix C) is based on the privacy amplification by subsampling result for (ε , δ )-DP appearing in [23], [24], [25], [26] and stated in [27, Th. 29].”
MethodCan LLMs get help from other LLMs without revealing private information?
Hartmann, F., Tran, D.-H., Kairouz, P., Cărbune, V., & y Arcas, B. A. (2024) · Workshop on Privacy in Natural Language Processing (PrivateNLP) · doi:10.18653/v1/2024.privatenlp-1.12 · Cited by 16
An Attack-Agnostic Defense Framework Against Manipulation Attacks Under Local Differential Privacy
Zhao, P., Zhang, Z., Dong, J., Wu, J., Liu, Z., Wang, S., & Gao, Y. (2025) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp61157.2025.00255 · Cited by 16
“(LDP [26], [27]) A local randomizer Q i satisfies (cid”
Synthetic Tabular Data: Methods, Attacks and Defenses
Cormode, G., Maddock, S., Ullah, E., & Gade, S. (2025) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/3711896.3736562 · Cited by 16
“…of the definition, which affect the exact nature of the privacy guarantee and the mathematical properties that support the privacy analysis – including local differential privacy (LDP) [37], pure/approximate privacy [18], Rényi privacy (RDP) [52], and zero-concentrated differential privacy (zCDP) [9].”
Private Rank Aggregation in Central and Local Models
Alabi, D., Ghazi, B., Kumar, R., & Manurangsi, P. (2022) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v36i6.20544 · Cited by 16
Joint Privacy Enhancement and Quantization in Federated Learning
Lang, N., & Shlezinger, N. (2022) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit50566.2022.9834551 · Cited by 16
Secure outsourced NB: Accurate and efficient privacy-preserving Naive Bayes classification
Zhao, X., & Xia, Z. (2022) · Computers & Security · doi:10.1016/j.cose.2022.103011 · Cited by 16
Efficient Noise Generation Protocols for Differentially Private Multiparty Computation
Eriguchi, R., Ichikawa, A., Kunihiro, N., & Nuida, K. (2022) · IEEE Transactions on Dependable and Secure Computing · doi:10.1109/tdsc.2022.3227568 · Cited by 16
“There are many differentially private mechanisms in the local model [10], [11], [12], [13], in which every party locally randomizes his private input and sends it to a designated party, who then computes a function on the noisy data.”
BackgroundPrivacy Enhancement Via Dummy Points in the Shuffle Model
Li, X., Liu, W., Feng, H., Huang, K., Hu, Y., Liu, J., Ren, K., & Qin, Z. (2023) · IEEE Transactions on Dependable and Secure Computing · doi:10.1109/tdsc.2023.3263162 · Cited by 16
“In constrast, the local model [27] allows each user to locally perturb his data using a randomization algorithm M before sending it to the untrusted analyst so that the analyst cannot see the raw data.”
MethodDPAUC: Differentially Private AUC Computation in Federated Learning
Sun, J., Yang, X., Yao, Y., Xie, J., Wu, D., & Wang, C. (2023) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v37i12.26770 · Cited by 16
Differential Aggregation against General Colluding Attackers
Du, R., Ye, Q., Fu, Y., Hu, H., Li, J., Fang, C., & Shi, J. (2023) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde55515.2023.00169 · Cited by 16
“Local differential privacy (LDP) [10], [18], [32], a variant of DP [20], [21], [43], is proposed to protect the data privacy of users in an untrusted environment.”
Differentially Private Heavy Hitter Detection using Federated Analytics
Chadha, K. N., Chen, J., Duchi, J. C., Feldman, V., Hashemi, H., Javidbakht, O., McMillan, A., & Talwar, K. (2024) · IEEE Conference on Secure and Trustworthy Machine Learning (SaTML) · doi:10.1109/satml59370.2024.00032 · Cited by 16
Private k-Means Clustering with Stability Assumptions.
Shechner, M., Sheffet, O., & Stemmer, U. (2020) · International Conference on Artificial Intelligence and Statistics · Cited by 16
Differentially Private Bayesian Neural Networks on Accuracy, Privacy and Reliability
Zhang, Q., Bu, Z., Chen, K., & Long, Q. (2023) · Lecture notes in computer science · doi:10.1007/978-3-031-26412-2_37 · Cited by 16
Distributed Large Independent Sets in One Round on Bounded-Independence Graphs
Halldórsson, M. M., & Konrad, C. (2015) · Lecture notes in computer science · doi:10.1007/978-3-662-48653-5_37 · Cited by 16
Model-Agnostic Private Learning via StabilityPreprint
Bassily, R., Thakkar, O. D., & Thakurta, A. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1803.05101 · Cited by 16
Noninteractive Locally Private Learning of Linear Models via Polynomial ApproximationsPreprint
Wang, D., Smith, A., & Xu, J. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1812.06825 · Cited by 16
“ERM in the interactive local model of differential privacy has been studied for quite some time (Kasiviswanathan et al., 2011; Beimel et al., 2008; Duchi et al., 2017, 2013; Zheng et al., 2017; Smith et al., 2017).”
InfluentialSelf-citationInformation-theoretic metrics for Local Differential Privacy protocolsPreprint
Lopuhaä-Zwakenberg, M., Škorić, B., & Li, N. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1910.07826 · Cited by 16
“One approach to protect privacy is offered by Local Differential Privacy (LDP) protocols [33].”
BackgroundInfluentialOracle Efficient Private Non-Convex OptimizationPreprint
Neel, S., Roth, A., Vietri, G., & Wu, S. Y.-P. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1909.01783 · Cited by 16
“…implementation (and the implementation of related mechanisms, like “Report-Noisy-Max” [DR14]) requires the ability to enumerate the parameter range W , making it infeasible in most learning settings, despite its use in proving general information theoretic bounds in private PAC learning [KLN + 11].”
BackgroundContraction of $E_γ$-Divergence and Its Applications to PrivacyPreprint
Asoodeh, S., Diaz, M., & Calmon, F. P. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2012.11035 · Cited by 16
“…of statistical efficiency under pure LDP constraints was initiated by Duchi et al. [20] in the minimax setting and has since gained considerable attention, e.g., [21–25 , 40– 48 Online learning [49, 50] is a framework where a sequence of predictions are made given the knowledge of past actions.”
BackgroundLessons from Generalization Error Analysis of Federated Learning: You May Communicate Less Often!Preprint
Sefidgaran, M., Chor, R., Zaidi, A., & Wan, Y. (2023) · arXiv (Cornell University) · doi:10.48550/arxiv.2306.05862 · Cited by 16
“…collect all the data at one point prior to applying a suitable machine learning algo-rithm to it (Kone ˇ cn ` y et al., 2016; McMahan et al., 2017; Aguerri & Zaidi, 2019; Zaidi et al., 2020; Verbraeken et al., 2020; Moldoveanu & Zaidi, 2021; Kasiviswanathan et al., 2011; Sefidgaran et al., 2023).”
MethodOptimal Differentially Private Model Training with Public DataPreprint
Lowy, A. M., Li, Z., Huang, T., & Razaviyayn, M. (2023) · arXiv (Cornell University) · doi:10.48550/arxiv.2306.15056 · Cited by 16
Tighter Privacy Auditing of DP-SGD in the Hidden State Threat ModelPreprint
Cebere, T., Bellet, A., & Papernot, N. (2024) · arXiv (Cornell University) · doi:10.48550/arxiv.2405.14457 · Cited by 16
“Privacy amplification techniques [24, 18, 17, 11, 2] can further decrease the overall privacy loss by exploiting the non-disclosure of certain intermediate computations.”
BackgroundOn the Privacy of Noisy Stochastic Gradient Descent for Convex Optimization
Altschuler, J. M., Bok, J., & Talwar, K. (2024) · SIAM Journal on Computing · doi:10.1137/23m1556538 · Cited by 15
Explaining ∊ in Local Differential Privacy Through the Lens of Quantitative Information Flow
Fernandes, N., McIver, A. K., & Sadeghi, P. (2024) · IEEE Computer Security Foundations Workshop (CSFW) · doi:10.1109/csf61375.2024.00012 · Cited by 15
“Alternatively, in the local model for differential privacy [12], [13], each individual first applies noise to their data before sending it to an untrusted data curator, who releases some aggregate information about the (noisy) data.”
BackgroundPrivacy-Preserving Graph Embedding based on Local Differential Privacy
Li, Z., Li, R.-H., Liao, M., Jin, F., & Wang, G. (2024) · ACM International Conference on Information and Knowledge Management (CIKM) · doi:10.1145/3627673.3679759 · Cited by 15
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.