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 201–300 of 1,005
D 2 P: distance-based differential privacy in recommenders
Guerraoui, R., Kermarrec, A.-M., Patra, R., & Taziki, M. (2015) · Proceedings of the VLDB Endowment · doi:10.14778/2757807.2757811 · Cited by 55
“Most of the research focused on theoretical aspects and provided feasibility and infeasibility results [15].”
BackgroundInteractive Inference Under Information Constraints
Acharya, J., Canonne, C. L., Liu, Y., Sun, Z., & Tyagi, H. (2021) · IEEE Transactions on Information Theory · doi:10.1109/isit45174.2021.9518069 · Cited by 55
Locally Differentially Private (Contextual) Bandits LearningPreprint
Zheng, K., Cai, T., Huang, W., Li, Z., & Wang, L. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2006.00701 · Cited by 55
“Compared with Differential Privacy, most of time Local Differential Privacy (LDP) [26, 11] is a much stronger and user-friendly standard of privacy and is more appealing in real applications [10], as LDP requires protecting each user’s data before collection.”
BackgroundParameter-Free Online Convex Optimization with Sub-Exponential Noise
Jun, K.-S., & Orabona, F. (2019) · OpenBU (Boston University) · doi:10.48550/arxiv.1902.01500 · Cited by 54
“In the stricter definition of local differential privacy (Wasserman and Zhou, 2010; Kasiviswanathan et al., 2011; Duchi et al., 2014; Song et al., 2015) instead an untrusted algorithm is allowed to access a perturbed version of a sensitive dataset only through a sanitization interface.”
MethodAnswering Range Queries Under Local Differential Privacy
Kulkarni, T. (2019) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/3299869.3300102 · Cited by 53
Privacy accounting and quality control in the sage differentially private ML platform
Lécuyer, M., Spahn, R., Vodrahalli, K., Geambasu, R., & Hsu, D. (2019) · ACM SIGOPS Symposium on Operating Systems Principles (SOSP) · doi:10.1145/3341301.3359639 · Cited by 53
“First, we can increase the dataset’s size: at least in theory, it has been proven that one can compensate for the loss in accuracy due to any (ε,δ )-DP guarantee by increasing the training set size [29].”
PRIPEL: Privacy-Preserving Event Log Publishing Including Contextual Information
Fahrenkrog-Petersen, S. A., van der Aa, H., & Weidlich, M. (2020) · Lecture notes in computer science · doi:10.1007/978-3-030-58666-9_7 · Cited by 54
Connecting Robust Shuffle Privacy and Pan-Privacy
Balcer, V., Cheu, A., Joseph, M., & Mao, J. (2021) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611976465.142 · Cited by 53
DDRM: A Continual Frequency Estimation Mechanism with Local Differential Privacy
Xue, Q., Ye, Q., Hu, H., Zhu, Y., & Wang, J. (2022) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2022.3177721 · Cited by 53
“Local differential privacy (LDP) [2] is proposed for the local setting where data contributors (users) may upload their sensitive information to an untrusted data collector.”
BackgroundPrivately Estimating a Gaussian: Efficient, Robust, and Optimal
Alabi, D., Kothari, P. K., Tankala, P., Venkat, P., & Zhang, F. (2023) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3564246.3585194 · Cited by 53
Bounding Training Data Reconstruction in Private (Deep) LearningPreprint
Guo, C., Karrer, B., Chaudhuri, K., & van der Maaten, L. J. P. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2201.12383 · Cited by 53
“Privacy amplification by subsampling (Kasiviswanathan et al., 2011) is a powerful technique for reducing privacy leakage by randomizing the batches in private SGD: we draw each Bt uniformly from the set of all B-subsets of Dtrain, where B is the batch size.”
MethodExploring Strategies for Privacy-Preserving Machine Learning in Distributed EnvironmentsPreprint
Dodda, S., Kumar, A., Kamuni, N., & Ayyalasomayajula, M. M. T. (2024) · doi:10.36227/techrxiv.171340711.17793838/v1 · Cited by 53
Practical and private (deep) learning without sampling or shuffling
Kairouz, P., McMahan, B., Song, S., Thakkar, O., Thakurta, A., & Xu, Z. (2021) · arXiv · doi:10.48550/arxiv.2103.00039 · Cited by 52
“This improvement is significant because it distinguishes centrally private OCO from locally private (Warner, 1965; Evfimievski et al., 2003; Kasiviswanathan et al., 2008) OCO4.”
BackgroundMethodSoK: Differentially Private Publication of Trajectory Data
Miranda-Pascual, À., Guerra-Balboa, P., Parra‐Arnau, J., Forné, J., & Strufe, T. (2023) · Proceedings on Privacy Enhancing Technologies · doi:10.56553/popets-2023-0065 · Cited by 52
Trajectory Data Collection with Local Differential Privacy
Zhang, Y., Ye, Q., Chen, R., Hu, H., & Han, Q. (2023) · Proceedings of the VLDB Endowment · doi:10.14778/3603581.3603597 · Cited by 52
“To avoid these problems, LDP [26] was proposed.”
BackgroundMethodOn the Protection of Private Information in Machine Learning Systems: Two Recent Approches
Abadi, M., Erlingsson, U., Goodfellow, I., McMahan, H. B., Mironov, I., Papernot, N., Talwar, K., & Zhang, L. (2017) · 2017 IEEE 30th Computer Security Foundations Symposium (CSF) · doi:10.1109/csf.2017.10 · Cited by 39
“, [11], [12], [13], [14], [15], [16], [17], [18]), and undoubtedly neither noisy SGD nor PATE constitutes the last word on the subject; surveying this research is beyond the scope of this note.”
BackgroundDifferentially Private Empirical Risk Minimization with Input Perturbation
Fukuchi, K., Tran, Q. K., & Sakuma, J. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-67786-6_6 · Cited by 52
“Definition 2 (( (cid:15), δ )-differential local privacy (Wainwright et al., 2012; Evfimievski et al., 2003; Kasiviswanathan et al., 2011)) .”
Federating recommendations using differentially private prototypes
Ribero, M., Henderson, J., Williamson, S. A., & Vikalo, H. (2022) · Pattern Recognition · doi:10.1016/j.patcog.2022.108746 · Cited by 52
Memory, Communication, and Statistical QueriesPreprint
Steinhardt, J., Valiant, G. J., & Wager, S. (2015) · Electronic colloquium on computational complexity · Cited by 52
Privacy Amplification by Mixing and Diffusion MechanismsPreprint
Balle, B., Barthe, G., Gaboardi, M., & Geumlek, J. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1905.12264 · Cited by 52
“Generally speaking, these are referred to as privacy amplification rules, with prominent examples being amplification by subsampling [9, 18, 20, 6, 5, 8, 2, 27], shuffling [16, 10, 3] and iteration [17].”
BackgroundDifferentially Private Federated Bayesian Optimization with Distributed ExplorationPreprint
Dai, Z., Low, B. K. H., & Jaillet, P. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2110.14153 · Cited by 52
“In particular, privacy preservation using DP has been an important topic for FL [27, 41, 62, 65], including both central DP (with trusted central server) [47] and local [32, 64, 70] or distributed DP [4, 6, 18, 58] (without trusted central server).”
BackgroundFederated Learning for Heterogeneous Data Integration and Privacy Protection
Gong, C., Zhang, X., Lin, Y., Su, P.-C., Lü, H., & Zhang, J. (2025) · International Conference on Computer Supported Cooperative Work in Design (CSCWD) · doi:10.1109/cscwd64889.2025.11033572 · Cited by 51
Security in high-performance computing environments
Peisert, S. (2017) · Communications of the ACM · doi:10.1145/3096742 · Cited by 51
Inference Under Information Constraints III: Local Privacy Constraints
Acharya, J., Canonne, C. L., Freitag, C., Sun, Z., & Tyagi, H. (2021) · IEEE Journal on Selected Areas in Information Theory · doi:10.1109/jsait.2021.3053569 · Cited by 50
On Sampling, Anonymization, and Differential Privacy: Or, k-Anonymization Meets Differential PrivacyPreprint
Li, N., Qardaji, W. H., & Su, D. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1101.2604 · Cited by 50
“Smith’s blog(2) includes an “amplification” lemma for differential privacy, which was used implicitly in the design of a PAC lear ner for the parity class in [17].”
MethodA Systematic Survey for Differential Privacy Techniques in Federated Learning
Zhang, Y., Lu, Y., & Liu, F. (2023) · Journal of Information Security · doi:10.4236/jis.2023.142008 · Cited by 50
DPAR: Decoupled Graph Neural Networks with Node-Level Differential Privacy
Zhang, Q., Lee, H., Ma, J., Lou, J., Yang, C., & Xiong, L. (2024) · International World Wide Web Conference (WWW) · doi:10.1145/3589334.3645531 · Cited by 49
“This sampling step brings a privacy amplification effect in our privacy guarantee by a factor of 𝑞 ′ [5, 23].”
BackgroundMethodSelf-citationLocal Differential Privately Anonymizing Online Social Networks Under HRG-Based Model
Gao, T., Li, F., Chen, Y., & Zou, X. (2018) · IEEE Transactions on Computational Social Systems · doi:10.1109/tcss.2018.2877045 · Cited by 49
“A different definition of local differential privacy is also introduced in other studies [33], [34].”
BackgroundSingular Spectrum Analysis for Local Differential Privacy of Classifications in the Smart Grid
Ou, L., Qin, Z., Liao, S., Li, T., & Zhang, D. (2020) · IEEE Internet of Things Journal · doi:10.1109/jiot.2020.2977220 · Cited by 49
“LDP [38] is the extension of the standard DP metric [24], [25] in the local model and it is defined as follows.”
BackgroundStatistical Queries and Statistical Algorithms: Foundations and Applications
Reyzin, L. (2026) · Springer eBooks · doi:10.48550/arxiv.2004.00557 · Cited by 49
“Theorem 47 (Kasiviswanathan, Lee, Nissim, Raskhodnikova, and Smith [2011]) .”
MethodSecrecy by Design With Applications to Privacy and Compression
Shkel, Y. Y., Blum, R. S., & Poor, H. V. (2020) · IEEE Transactions on Information Theory · doi:10.1109/tit.2020.3041224 · Cited by 49
“The problem of partial secrecy in the setting of database privacy has been widely studied in the computer science literature; approaches such as differential privacy [2], [3], ( , δ)-differential privacy [19], and local differential privacy [20]–[22] can also be viewed through the lens of information leakage [23]–[27].”
BackgroundMinimax rates for memory-bounded sparse linear regression
Steinhardt, J., & Duchi, J. C. (2015) · Conference on Learning Theory · Cited by 49
DP-OPT: Make Large Language Model Your Privacy-Preserving Prompt Engineer
Hong, J., Wang, J. T., Zhang, C., Li, Z., Li, B., & Wang, Z. (2023) · International Conference on Learning Representations · doi:10.48550/arxiv.2312.03724 · Cited by 50
“These works introduce randomness at the word level and are able to achieve the privacy guarantee in terms of local differential privacy (LDP) (Kasiviswanathan et al., 2011) or a similar definition called metric differential privacy.”
BackgroundSecuring Distributed SGD Against Gradient Leakage Threats
Wei, W., Liu, L., Zhou, J., Chow, K.-H., & Wu, Y. (2023) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2023.3273490 · Cited by 48
“extends the LDP concept and techniques [42], [43] developed for protecting user identity when sharing web access log or click”
MethodChannel Simulation: Theory and Applications to Lossy Compression and Differential Privacy
Li, C. T. (2024) · Foundations and Trends® in Communications and Information Theory · doi:10.1561/0100000141 · Cited by 47
LDPGuard: Defenses Against Data Poisoning Attacks to Local Differential Privacy Protocols
Huang, K., Ouyang, G., Ye, Q., Hu, H., Zheng, B., Zhao, X., Zhang, R., & Zhou, X. (2024) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2024.3358909 · Cited by 46
Privately Releasing Conjunctions and the Statistical Query Barrier
Gupta, A., Hardt, M., Roth, A., & Ullman, J. (2013) · SIAM Journal on Computing · doi:10.1137/110857714 · Cited by 46
OpBoost: a vertical federated tree boosting framework based on order-preserving desensitization
Li, X., Hu, Y., Liu, W., Feng, H., Peng, L., Hong, Y., Ren, K., & Qin, Z. (2022) · Proceedings of the VLDB Endowment · doi:10.14778/3565816.3565823 · Cited by 46
“in local differential privacy [39], which allows each user to perturb his sensitive data using a randomization mechanismM such that the perturbed results from different data values will be “close".”
Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean Estimation
Georgiev, K., & Hopkins, S. B. (2022) · neural information processing systems · doi:10.52202/068431-0495 · Cited by 46
Differentially Private Bayesian Inference for Exponential FamiliesPreprint
Bernstein, G., & Sheldon, D. R. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1809.02188 · Cited by 46
SoK: Differential Privacy on Graph-Structured DataPreprint
Mueller, T. T., Usynin, D., Paetzold, J. C., Rueckert, D., & Kaissis, G. A. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2203.09205 · Cited by 47
“The advantage of local DP [77] in comparison to central DP is that no trusted third party is required.”
BackgroundA perspective on data sharing in digital food safety systems
Qian, C., Liu, Y., Barnett-Neefs, C., Salgia, S., Serbetci, O., Adalja, A., Acharya, J., Zhao, Q. Q., Ivanek, R., & Wiedmann, M. (2022) · Critical Reviews in Food Science and Nutrition · doi:10.1080/10408398.2022.2103086 · Cited by 45
“While central differential privacy requires a central trusted server, local differential privacy (LDP) addresses this problem when users do not want to trust a third party with their data (Kasiviswanathan et al. 2011) (See Figure 2 ).”
BackgroundPersonalization and targeting: how to experiment, learn & optimize
Lemmens, A., Roos, J. M. T., Gabel, S., Ascarza, E., Bruno, H. A., Gordon, B. R., Israeli, A., Feit, E. M., Mela, C. F., & Netzer, O. (2025) · International Journal of Research in Marketing · doi:10.1016/j.ijresmar.2025.07.004 · Cited by 45
A systematic literature review on wearable health data publishing under differential privacy
Saifuzzaman, M., Ananna, T. N., Chowdhury, M. J. M., Ferdous, M. S., & Chowdhury, F. (2022) · International Journal of Information Security · doi:10.1007/s10207-021-00576-1 · Cited by 45
Mean estimation over numeric data with personalized local differential privacy
Xue, Q., Zhu, Y., & Wang, J. (2021) · Frontiers of Computer Science · doi:10.1007/s11704-020-0103-0 · Cited by 45
Privacy-Preserving Probabilistic Voltage Forecasting in Local Energy Communities
Toubeau, J., Teng, F., Morstyn, T., Krannichfeldt, L. V., & Wang, Y. (2022) · IEEE Transactions on Smart Grid · doi:10.1109/tsg.2022.3187557 · Cited by 45
“Indeed, if the training M is ( , δ)-DP, then drawing a random subset of end-users (from all |C| clients) before applying M follows (O(γ ), γ δ)-DP, with γ < 1 (which depends on the sampling strategy) [42].”
"I need a better description": An Investigation Into User Expectations For Differential Privacy
Cummings, R., Kaptchuk, G., & Redmiles, E. M. (2023) · Journal of Privacy and Confidentiality · doi:10.29012/jpc.813 · Cited by 45
Chen, W., Song, D., Özgür, A., & Kairouz, P. (2023) · neural information processing systems · doi:10.52202/075280-3030 · Cited by 45
Locally Private Hypothesis SelectionPreprint
Gopi, S., Kamath, G., Kulkarni, J., Nikolov, A., Wu, Z. S., & Zhang, H. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2002.09465 · Cited by 45
“Definition 19 (Warner (1965); Evfimievski et al. (2003); Kasiviswanathan et al. (2011)) Suppose there are n individuals, where the ith individual has datapoint Xi.”
BackgroundInfluentialWu, B., Zhao, S., Sun, G., Zhang, X., Su, Z., Zeng, C., & Liu, Z. (2019) · 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr.2019.00220 · Cited by 44
“The proof can be done using the privacy amplification [18] and the theorem in the prior literature [2].”
MethodAdaptive conformal classification with noisy labels
Sesia, M., Wang, Y. X. R., & Tong, X. (2024) · Journal of the Royal Statistical Society Series B (Statistical Methodology) · doi:10.1093/jrsssb/qkae114 · Cited by 44
Local Differential Privacy Is Equivalent to Contraction of an $f$-Divergence
Asoodeh, S., Aliakbarpour, M., & Calmon, F. P. (2021) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit45174.2021.9517999 · Cited by 44
Bagdasaryan, E., Kairouz, P., Mellem, S., Gascón, A., Bonawitz, K., Estrin, D. L., & Gruteser, M. (2022) · Proceedings on Privacy Enhancing Technologies · doi:10.56553/popets-2022-0104 · Cited by 44
Differential privacy for the analyst via private equilibrium computation
Hsu, J., Roth, A., & Ullman, J. (2013) · Proceedings of the forty-fifth annual ACM symposium on Theory of Computing · doi:10.1145/2488608.2488651 · Cited by 27
On the Privacy-Robustness-Utility Trilemma in Distributed LearningPreprint
Allouah, Y., Guerraoui, R., Gupta, N., Pinot, R., & Stephan, J. (2023) · arXiv (Cornell University) · doi:10.48550/arxiv.2302.04787 · Cited by 43
“, the queries made to the workers by the server may share arbitrary dependence (Kasiviswanathan et al., 2011).”
BackgroundQuantum Pufferfish Privacy: A Flexible Privacy Framework for Quantum Systems
Nuradha, T., Goldfeld, Z., & Wilde, M. M. (2024) · IEEE Transactions on Information Theory · doi:10.1109/tit.2024.3404927 · Cited by 42
“This is analogous to a version of the randomized response technique used to achieve classical local DP [59], [60], [61].”
MethodSample Complexity Bounds for Differentially Private Learning.
Chaudhuri, K., & Hsu, D. (2011) · Conference on Learning Theory · Cited by 42
A Survey on Data MarketsPreprint
Zhang, J., Bi, Y., Cheng, M., Liu, J., Ren, K., Sun, Q., Wu, Y.-H., Cao, Y., Fernandez, R. C., Xu, H., et al. (2024) · arXiv (Cornell University) · doi:10.48550/arxiv.2411.07267 · Cited by 42
ProGAP: Progressive Graph Neural Networks with Differential Privacy Guarantees
Sajadmanesh, S., & Gática-Pérez, D. (2024) · ACM International Conference on Web Search and Data Mining (WSDM) · doi:10.1145/3616855.3635761 · Cited by 41
“However, both of these approaches use local differential privacy [25], which operates under a different problem setting from our method.”
BackgroundpMSE Mechanism: Differentially Private Synthetic Data with Maximal Distributional Similarity
Snoke, J., & Slavković, A. (2018) · Lecture notes in computer science · doi:10.1007/978-3-319-99771-1_10 · Cited by 41
“It has been explored in numerous contexts such as machine learning algorithms (e.g., Blum et al. (2005); Kasiviswanathan et al. (2011); Kifer et al. (2012)), categorical data (e.g., Barak et al. (2007); Li et al. (2010)), dimension reduction (e.g., Chaudhuri et al. (2012); Kapralov and Talwar…”
BackgroundLocally differentially private item-based collaborative filtering
Guo, T., Luo, J., Dong, K., & Yang, M. (2019) · Information Sciences · doi:10.1016/j.ins.2019.06.021 · Cited by 41
Concurrent Composition of Differential Privacy
Vadhan, S., & Wang, T. (2021) · Lecture notes in computer science · doi:10.1007/978-3-030-90453-1_20 · Cited by 41
Locally Differentially Private Sparse Vector Aggregation
Zhou, M., Wang, T., Chan, T.-H. H., Fanti, G. C., & Shi, E. (2022) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp46214.2022.9833635 · Cited by 41
Triangle Counting With Local Edge Differential Privacy
Eden, T., Liu, Q. C., Raskhodnikova, S., & Smith, A. (2025) · Random Structures and Algorithms · doi:10.1002/rsa.70002 · Cited by 40
“We adapt the definition of local differential privacy from (Joseph et al. 2019; Kasiviswanathan et al. 2011) + 𝛿 for all a and a ′ that differ in one bit and all sets of outputs 𝑌 ⊆ .”
InfluentialSelf-citationLam-Weil, J., Laurent, B., & Loubes, J. (2021) · Bernoulli · doi:10.3150/21-bej1358 · Cited by 40
“This notion has been extensively studied through the concept of local algorithms, especially in the context of privacy-preserving data mining [52, 4, 3, 51, 26, 5, 44, 36, 39].”
BackgroundBlockchain Enabled AI Marketplace: The Price You Pay for Trust
Sarpatwar, K., Ganapavarapu, V. S., Shanmugam, K., Rahman, A., & Vaculín, R. (2019) · IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops (CVPRW) · doi:10.1109/cvprw.2019.00345 · Cited by 40
“In the machine learning literature, there is a lot of existing work on privacy-preserving classifier training on a single private dataset [13, 7, 23, 22, 14, 5, 12, 29, 2, 20, 27].”
BackgroundCollect at Once, Use Effectively: Making Non-interactive Locally Private Learning PossiblePreprint
Zheng, K., Mou, W., & Wang, L. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1706.03316 · Cited by 40
“In the interactive world, LDP is promised with connection to Statistical Query (SQ) model (Kearns, 1998), from its very beginning (Kasiviswanathan et al., 2011).”
BackgroundContext-Aware Local Differential PrivacyPreprint
Acharya, J., Bonawitz, K., Kairouz, P., Ramage, D., & Sun, Z. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1911.00038 · Cited by 40
“version, local differential privacy (LDP) (Definition 1), provides context-free privacy guarantees even in the absence of a trusted data collector (Warner, 1965; Beimel et al., 2008; Kasiviswanathan et al., 2011).”
BackgroundA Differentially Private Text Perturbation Method Using a Regularized Mahalanobis MetricPreprint
Xu, Z., Aggarwal, A., Feyisetan, O., & Teissier, N. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2010.11947 · Cited by 40
“Metric differential privacy arises as a generalization of local differential privacy (Kasiviswanathan et al., 2011), which originated in protecting location privacy such that locations near the user’s location are assigned with higher probability while those far away are given negligible…”
BackgroundInfluentialButucea, C., Rohde, A., & Steinberger, L. (2023) · The Annals of Statistics · doi:10.1214/22-aos2254 · Cited by 39
“Klemelä (2006) studies estimation of quadratic functionals for `p bodies with 2 < p < ∞.”
BackgroundDistPreserv: Maintaining User Distribution for Privacy-Preserving Location-Based Services
Ren, Y., Li, X., Miao, Y., Deng, R. H., Weng, J., Ma, S., & Ma, J. (2022) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2022.3141398 · Cited by 39
“It is worth noting that some works [17], [34], [35] adopt local differential privacy [36], the variant of differential privacy for user-specified privacy intensity, to keep users’ whereabouts private while allowing the server to obtain their distribution information.”
BackgroundPAC Privacy: Automatic Privacy Measurement and Control of Data Processing
Xiao, H., & Devadas, S. (2023) · Lecture notes in computer science · doi:10.1007/978-3-031-38545-2_20 · Cited by 39
“The first application is similar to local DP [31], [44], where a user does not trust any other parties and plans to publish her perturbed sample.”
BackgroundPrivyNet: A Flexible Framework for Privacy-Preserving Deep Neural Network TrainingPreprint
Li, M., Lai, L., Suda, N., Chandra, V., & Pan, D. Z. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1709.06161 · Cited by 39
“Different measures of privacy and utility are proposed based on the rate-distortion theory in communication [1–3], statistical estimation [4], and learnability [5].”
BackgroundEncrypted Databases for Differential Privacy
Agarwal, A., Herlihy, M. P., Kamara, S., & Moataz, T. (2019) · Proceedings on Privacy Enhancing Technologies · doi:10.2478/popets-2019-0042 · Cited by 38
“Since its conception, differential privacy has been an active research area [6– 9, 29, 44, 50], we refer the readers to [24, 28] for a comprehensive survey.”
BackgroundPrivate Release of Text Embedding Vectors
Feyisetan, O., & Kasiviswanathan, S. P. (2021) · Workshop on Trustworthy Natural Language Processing (TrustNLP) · doi:10.18653/v1/2021.trustnlp-1.3 · Cited by 38
“Lipschitz privacy is closely related to LDP where the adjacency relation is defined through the Hamming metric, but also generalizes to include Euclidean, Manhattan, and Chebyshev metrics, among others (Chatzikokolakis et al., 2013; Andrés et al., 2013; Chatzikokolakis et al., 2015; Fernandes et al., 2019; Feyisetan et…”
MethodInfluentialSelf-citationFederated Inverse Reinforcement Learning for Smart ICUs With Differential Privacy
Gong, W., Cao, L. J., Zhu, Y., Zuo, F., He, X., & Zhou, H. (2023) · IEEE Internet of Things Journal · doi:10.1109/jiot.2023.3281347 · Cited by 38
“LDP ran-domizes the raw clinical data before releasing it to the hospital, but this may conflict with the trust that patients have in their healthcare providers [19], [20], [21], [22].”
BackgroundThe Large Margin Mechanism for Differentially Private MaximizationPreprint
Chaudhuri, K., Hsu, D., & Song, S. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1409.2177 · Cited by 38
“Our bound only relies on uniform convergence properties of H, and can be significantly tighter than the bounds from [25] when the number of hypotheses with error close to minh∈H err(h) is small.”
BackgroundMethodInfluentialScore Attack: A Lower Bound Technique for Optimal Differentially Private LearningPreprint
Cai, T. T., Wang, Y., & Zhang, L. (2023) · arXiv (Cornell University) · doi:10.48550/arxiv.2303.07152 · Cited by 38
A Survey of Differential Privacy Techniques for Federated Learning
Wang, X., Jiaqian, L., Xueshuang, D., Zhang, H., & Lianshan, S. (2024) · IEEE Access · doi:10.1109/access.2024.3523909 · Cited by 37
Private Weighted Histogram Aggregation in Crowdsourcing
Wang, S., Huang, L., Wang, P., Deng, H., Xu, H., & Yang, W. (2016) · Lecture notes in computer science · doi:10.1007/978-3-319-42836-9_23 · Cited by 37
On the Generalization Properties of Differential PrivacyPreprint
Kobbi Nissim, B., & Stemmer, U. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1504.05800 · Cited by 37
“Another application of Theorem 1.2 is in the context of private learning [6].”
BackgroundInfluentialDifferentially private cross-silo federated learningPreprint
Heikkilä, M., Koskela, A., Shimizu, K., Kaski, S., & Honkela, A. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2007.05553 · Cited by 37
“This is especially true for DP learning with limited dataset sizes due to privacy am-plification results: the uncertainty induced by using only a batch of the full data augments privacy, when the identities of the samples in a batch are kept secret [29, 7, 1, 6, 30].”
BackgroundFederated $f$-Differential PrivacyPreprint
Zheng, Q., Chen, S., Long, Q., & Su, W. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2102.11158 · Cited by 37
“One privacy notion that is related to the general concept of privacy in federated learning is local differential privacy [EGS03, KLN + 11].”
BackgroundOn a Utilitarian Approach to Privacy Preserving Text Generation
Xu, Z., Aggarwal, A., Feyisetan, O., & Teissier, N. (2021) · Workshop on Privacy in Natural Language Processing (PrivateNLP) · doi:10.18653/v1/2021.privatenlp-1.2 · Cited by 36
Differentially Private Matrix Factorization using Sketching Techniques
Balu, R., & Furon, T. (2016) · ACM Workshop on Information Hiding and Multimedia Security (IH&MMSec) · doi:10.1145/2909827.2930793 · Cited by 36
“[16] studied the theoretical properties of learning under differential privacy setup.”
BackgroundLocal Differential Privacy: Tools, Challenges, and Opportunities
Ye, Q., & Hu, H. (2020) · Communications in computer and information science · doi:10.1007/978-981-15-3281-8_2 · Cited by 36
Closure Properties for Private Classification and Online PredictionPreprint
Alon, N., Beimel, A., Moran, S., & Stemmer, U. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2003.04509 · Cited by 36
“Kasiviswanathan et al. (2011) showed that the exponential mechanism can be used as a generic private learner – when used with the score function q(S, h) = |{i : h(xi) 6= yi}| = m · errorS(h), the probability that the exponential mechanism outputs a hypothesis h such that errorS(h) >…”
BackgroundMethodInfluentialThe Trade-Offs of Private PredictionPreprint
van der Maaten, L. J. P., & Hannun, A. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2007.05089 · Cited by 36
Local Differential Privacy for Bayesian Optimization
Zhou, X., & Tan, J. R. (2021) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v35i12.17330 · Cited by 35
Distribution-invariant differential privacy
Bi, X., & Shen, X. (2022) · Journal of Econometrics · doi:10.1016/j.jeconom.2022.05.004 · Cited by 35
Differentially Private Model Selection with Penalized and Constrained Likelihood
Lei, J., Charest, A.-S., Slavković, A., Smith, A., & Fienberg, S. E. (2017) · Journal of the Royal Statistical Society Series A (Statistics in Society) · doi:10.1111/rssa.12324 · Cited by 35
Self-citationSPEED: secure, PrivatE, and efficient deep learning
Sébert, A. G., Pinot, R., Zuber, M., Gouy‐Pailler, C., & Sirdey, R. (2021) · Machine Learning · doi:10.1007/s10994-021-05970-3 · Cited by 34
PLDP: Personalized Local Differential Privacy for Multidimensional Data Aggregation
Shen, Z., Xia, Z., & Yu, P. (2021) · Security and Communication Networks · doi:10.1155/2021/6684179 · Cited by 34
“In recent years, local differential privacy (LDP) [1, 2] has been found practical value in collection and utilization of data owners’ data with the privacy preserved.”
BackgroundCollecting High-Dimensional and Correlation-Constrained Data with Local Differential Privacy
Du, R., Ye, Q., Fu, Y., & Hu, H. (2021) · IEEE International Conference on Sensing, Communication, and Networking (SECON) · doi:10.1109/secon52354.2021.9491591 · Cited by 34
Learning Privacy-Preserving Graph Convolutional Network with Partially Observed Sensitive Attributes
Hu, H., Cheng, L., Vap, J. P., & Borowczak, M. (2022) · International World Wide Web Conference (WWW) · doi:10.1145/3485447.3511975 · Cited by 34
“[31] proposed a node-level privacy-preserving GNN using local differential privacy [22].”
BackgroundInteractive Proofs For Differentially Private Counting
Biswas, A., & Cormode, G. (2023) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/3576915.3616681 · Cited by 34
“Therefore, researchers studied local privacy (LDP) [43] using randomised response [57] to prevent any other party from seeing data in plaintext.”
BackgroundOrder-Revealing Encryption and the Hardness of Private Learning
Bun, M., & Zhandry, M. (2015) · Lecture notes in computer science · doi:10.1007/978-3-662-49096-9_8 · Cited by 34
The Cost of Privacy in Generalized Linear Models: Algorithms and Minimax Lower BoundsPreprint
Cai, T., Wang, Y., & Zhang, L. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2011.03900 · Cited by 34
“The need for data privacy protection has in turn inspired the development of formal criteria and frameworks for data privacy, with differential privacy [20, 21] (and its variants [33, 23, 41, 16]) being the most widely studied in theory [24, 22, 26, 1], and adopted in practice [14, 2, 15, 28].”
BackgroundLocally Private Graph Neural NetworksPreprint
Sajadmanesh, S., & Gática-Pérez, D. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2006.05535 · Cited by 34
“To prevent the aggregator from inferring the original private value from the perturbed one, the mechanismM must satisfy the following definition [19]: Definition 2.”
MethodContraction of Private Quantum Channels and Private Quantum Hypothesis Testing
Nuradha, T., & Wilde, M. M. (2025) · IEEE Transactions on Information Theory · doi:10.1109/tit.2025.3527859 · Cited by 33
“Designing learning algorithms that also ensure privacy for input data is of importance, and it has been widely studied in the classical setting (for example, see [54]).”
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.