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 601–700 of 1,005
On Mean Estimation for General Norms with Statistical QueriesPreprint
Li, J. Z., Nikolov, A., Razenshteyn, I., & Waingarten, E. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1902.02459 · Cited by 11
Oblivious Sampling Algorithms for Private Data AnalysisPreprint
Sasy, S., & Ohrimenko, O. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2009.13689 · Cited by 11
Dai, E., & Wang, S. (2020) · arXiv (Cornell University) · Cited by 11
SoK: Chasing Accuracy and Privacy, and Catching Both in Differentially Private Histogram PublicationPreprint
Nelson, B., & Reuben, J. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1910.14028 · Cited by 11
Bit-efficient Numerical Aggregation and Stronger Privacy for Trust in Federated AnalyticsPreprint
Cormode, G., & Markov, I. L. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2108.01521 · Cited by 11
“Local differential privacy extends differential privacy guarantees to each client locally regardless of third-party servers [17, 25], so that aggregators do not see original data.”
Making Old Things New: A Unified Algorithm for Differentially Private ClusteringPreprint
la Tour, M. D., Henzinger, M. R., & Saulpic, D. (2024) · arXiv (Cornell University) · doi:10.48550/arxiv.2406.11649 · Cited by 11
Private and Efficient Learning With Hyperdimensional Computing
Khaleghi, B., Yu, X., Kang, J., Wang, X., & Rosing, T. (2024) · IEEE transactions on circuits and systems for artificial intelligence. · doi:10.1109/tcasai.2024.3481193 · Cited by 10
“Specifically, if the training is divided into batches of L = qN randomly selected samples (for N being the dataset size), following the privacy amplification theorem, each iteration is ( qϵ, qδ ) -private with respect to the whole dataset [6], [45].”
Enhancing Metric Privacy With a Shuffler
Athanasiou, A., Konstantinos Chatzikokolakis, A., & Catuscia Palamidessi, A. (2025) · Proceedings on Privacy Enhancing Technologies · doi:10.56553/popets-2025-0081 · Cited by 10
Zhou, A. C., Qiu, R., Lambert, T., Allard, T., Ibrahim, S., & Abbadi, A. E. (2022) · Symposium on Cloud Computing · doi:10.1145/3542929.3563474 · Cited by 10
“Sampling additionally benefits utility through its well-known amplification effect for DP [1, 6, 9, 38, 44, 65, 66].”
BackgroundUser-Driven Synthetic Dataset Generation With Quantifiable Differential Privacy
Tai, B.-C., Tsou, Y.-T., Li, S.-C., Huang, Y., Tsai, P.-Y., & Tsai, Y.-C. (2023) · IEEE Transactions on Services Computing · doi:10.1109/tsc.2023.3287239 · Cited by 10
Differentially Private Auction Design for Federated Learning With non-IID Data
Ren, K., Liao, G., Ma, Q., & Chen, X. (2023) · IEEE Transactions on Services Computing · doi:10.1109/tsc.2023.3332102 · Cited by 10
Alvim, M. S., Fernandes, N., McIver, A. K., Morgan, C. C., & Nunes, G. H. (2023) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/3576915.3623081 · Cited by 10
“The notion has later been extended to other domains, including those formed by individual records themselves [10], or subject to metrics modelling general notions of indistinguishability [22, 23].”
BackgroundOptimal Unbiased Randomizers for Regression with Label Differential Privacy
Badanidiyuru, A., Ghazi, B., Kamath, P., Kumar, R. R., Leeman, E., Manurangsi, P., Varadarajan, A. V., & Zhang, C. (2023) · neural information processing systems · doi:10.52202/075280-2631 · Cited by 10
Privacy-Preserving Transactions with Verifiable Local Differential Privacy
Davidow, D. M., Manevich, Y., & Toch, E. (2023) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.aft.2023.1 · Cited by 10
“Local DP models can be based on a randomized response mechanism as was first proposed by Warner in 1965 [45] and formalized in the context of learning by Kasiviswanathan et al. [34].”
Differential Privacy: An Umbrella Review
Kilpala, M., Kärkkäinen, T., & Hämäläinen, T. (2022) · Artificial Intelligence and Cybersecurity · doi:10.1007/978-3-031-15030-2_8 · Cited by 10
Locally differentially private multi-dimensional data collection via haar transform
Zhang, D., Ni, W., Fu, N., Hou, L., & Zhang, R. (2023) · Computers & Security · doi:10.1016/j.cose.2023.103291 · Cited by 10
Analyzing the Shuffle Model Through the Lens of Quantitative Information Flow
Jurado, M., Gonze, R. G., Alvim, M. S., & Catuscia Palamidessi, A. (2023) · IEEE Computer Security Foundations Workshop (CSFW) · doi:10.1109/csf57540.2023.00033 · Cited by 10
“In any case, once we have a QIF model for LDP and shuffle, the same techniques can be applied to derive results about their information leakage properties of other variants of adversaries.”
BackgroundInfluentialA novel privacy-preserving graph convolutional network via secure matrix multiplication
Zhang, H., Zhang, F., Wang, H., Ma, C., & Zhu, P. (2023) · Information Sciences · doi:10.1016/j.ins.2023.119897 · Cited by 10
Mechanisms for Robust Local Differential Privacy
Lopuhaä-Zwakenberg, M., & Goseling, J. (2024) · Entropy · doi:10.3390/e26030233 · Cited by 10
Locally differentially private continuous location sharing with randomized response
Xiong, X., Liu, S., Li, D., Wang, J., & Niu, X. (2019) · International Journal of Distributed Sensor Networks · doi:10.1177/1550147719870379 · Cited by 10
Statistical query complexity of manifold estimation
Aamari, E., & Knop, A. (2021) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3406325.3451135 · Cited by 10
“Instead of sample complexity, this paper considers the notion of statistical query complexity, which was proved to be equivalent to the locally private learning complexity up to a polynomial factor [32], and that naturally enforces robustness to clutter noise (see [2, Remark 4]).”
BackgroundInfluentialAnonymizing Trajectory Data: Limitations and Opportunities
Guerra-Balboa, P., Miranda-Pascual, À., Strufe, T., Parra‐Arnau, J., & Forné, J. (2022) · Repository KITopen (Karlsruhe Institute of Technology) · doi:10.5445/ir/1000148633 · Cited by 10
Sensitive Disclosures under Differential Privacy Guarantees
Han, C., & Wang, K. (2015) · IEEE International Congress on Big Data (BigData Congress) · doi:10.1109/bigdatacongress.2015.25 · Cited by 10
“For example, differential privacy has been applied to releasing query and click histograms from search logs [40, 48], recommender systems [63], publishing commuting patterns [59], publishing results of machine learning [13, 15, 46], clustering [33, 67], decision trees [34], mining frequent patterns [11], and aggregati…”
MethodDifferentially Private Combinatorial OptimizationPreprint
Gupta, A., Ligett, K., McSherry, F., Roth, A., & Talwar, K. (2009) · arXiv (Cornell University) · doi:10.48550/arxiv.0903.4510 · Cited by 10
Optimal Differential Privacy Composition for Exponential Mechanisms and the Cost of AdaptivityPreprint
Dong, J., Durfee, D., & Rogers, R. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1909.13830 · Cited by 10
Data-Dependent Differentially Private Parameter Learning for Directed Graphical ModelsPreprint
Chowdhury, A. R., Rekatsinas, T., & Jha, S. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1905.12813 · Cited by 10
“The privacy guarantee of a DP algorithm can be amplified by a preceding sampling step (Kasiviswanathan et al., 2011; Li et al., 2012).”
BackgroundUser-Level Private Learning via Correlated SamplingPreprint
Ghazi, B., Kumar, R., & Manurangsi, P. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2110.11208 · Cited by 10
Masked LARk: Masked Learning, Aggregation and Reporting worKflowPreprint
Pfeiffer, J. J., Charles, D. X., Gilton, D., Jung, Y. H., Parsana, M., & Anderson, E. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2110.14794 · Cited by 10
“This scheme is referred to as local Differential Privacy [26], so that privacy can be handled browser-side for gradient calculation.”
BackgroundInfluentialHartmann, V. N., & West, R. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1906.11993 · Cited by 10
Private federated discovery of out-of-vocabulary words for GboardPreprint
Sun, Z., Kairouz, P., Sun, H., Gascón, A., & Suresh, A. T. (2024) · arXiv (Cornell University) · doi:10.48550/arxiv.2404.11607 · Cited by 10
“Definition 2 (Local differential privacy (LDP) [8]) .”
BackgroundEdge-Private Matching Kernels Through Local DecodingPreprint
Dinitz, M., Li, G. Z., Liu, Q. C., & Zhou, F. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2501.00926 · Cited by 10
Differentially Private Multi-party Computation: Optimality of Non-Interactive Randomized ResponsePreprint
Kairouz, P., Oh, S., & Viswanath, P. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1407.1546 · Cited by 10
“In particular, it has been shown in [27] that under the centralized setting there exists a class of concepts that is efficiently learnable by interactive algorithms whereas a non-interactive algorithm requires exponential number of samples.”
BackgroundMethodCryptoRec: Novel Collaborative Filtering Recommender Made Privacy-Preserving Easy
Wang, J., Jin, C., Tang, Q., Liu, Z., & Aung, K. M. M. (2022) · IEEE Transactions on Dependable and Secure Computing · doi:10.1109/tdsc.2021.3065752 · Cited by 9
Jiang, X., Zhou, X., & Großklags, J. (2024) · IEEE Access · doi:10.1109/access.2024.3481652 · Cited by 9
“Thus, the definition of local differential privacy (LDP) has been proposed [37], which provides strong local privacy guarantees for each user.”
BackgroundFederated Heavy Hitter Analytics with Local Differential Privacy
Zhang, Y., Ye, Q., & Hu, H. (2025) · Proceedings of the ACM on Management of Data · doi:10.1145/3709739 · Cited by 9
Practical and Accurate Local Edge Differentially Private Graph Algorithms
Mundra, P., Papamanthou, C., Shun, J., & Liu, Q. C. (2025) · Proceedings of the VLDB Endowment · doi:10.14778/3749646.3749687 · Cited by 9
The Limits of Differential Privacy in Online Learning
Li, B., Wang, W. W., & Ye, P. (2024) · neural information processing systems · doi:10.52202/079017-2086 · Cited by 9
Li, X., Wang, C., 苏步新, Long, Q., & Su, W. (2025) · neural information processing systems · doi:10.52202/085713-5618 · Cited by 9
Quadtree-Based Adaptive Spatial Decomposition for Range Queries Under Local Differential Privacy
Wang, H., Huang, Y., & Li, H. (2023) · IEEE Transactions on Emerging Topics in Computing · doi:10.1109/tetc.2023.3317393 · Cited by 9
“…( (cid:2) -DP) if and only if for > 0 and any datasets D and D (cid:2) that differ in one element, we have Definition 2 (Local Differential Privacy [17]): An algorithm A satisfies (cid:2) -local differential privacy ( (cid:2) -LDP) if and only if for > 0 and any input v 1 and v 2 , we have It…”
BackgroundMethodPustozerova, A., Baumbach, J., & Mayer, R. L. (2023) · IEEE International Conference on Big Data (BigData) · doi:10.1109/bigdata59044.2023.10386466 · Cited by 9
“• Local Differential Privacy [17] refers to the case when an aggregator cannot be trusted and each party wants to protect their data (local models) before sending it to the aggregator (e.g. performing input perturbation or training of differentially-private local models).”
Background$\mathrm{E}_{\gamma}$-Mixing Time
Zamanlooy, B., Asoodeh, S., Díaz, M., & Calmon, F. P. (2024) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit57864.2024.10619250 · Cited by 9
“We focus on the family of locally differentially private (LDP) mechanisms [27, 28].”
BackgroundTop-k Discovery Under Local Differential Privacy: An Adaptive Sampling Approach
Du, R., Ye, Q., Fu, Y., Hu, H., & Huang, K. (2024) · IEEE Transactions on Dependable and Secure Computing · doi:10.1109/tdsc.2024.3471923 · Cited by 9
“LDP [6], [7], [30], or local differential privacy, is a technique that aims to provide privacy guarantees for individual users in distributed systems.”
PUFFLE: Balancing Privacy, Utility, and Fairness in Federated Learning
Corbucci, L., Heikkilä, M., Noguero, D. S., Monreale, A., & Kourtellis, N. (2024) · Frontiers in artificial intelligence and applications · doi:10.3233/faia240671 · Cited by 9
SoK: Computational and Distributed Differential Privacy for MPC
Meisingseth, F., & Rechberger, C. (2024) · Proceedings on Privacy Enhancing Technologies · doi:10.56553/popets-2025-0023 · Cited by 9
“Here there are no servers so the clients send their processed datapoints directly to the analyst.”
Efficient Verifiable Differential Privacy with Input Authenticity in the Local and Shuffle Model
Bontekoe, T., Asghar, H. J., & Türkmen, F. (2025) · Proceedings on Privacy Enhancing Technologies · doi:10.56553/popets-2025-0076 · Cited by 9
Low-Cost Privacy-Preserving Decentralized Learning
Biswas, S., Frey, D., Gaudel, R., Kermarrec, A.-M., Lerévérend, D., Pires, R. P., Sharma, R., & Taïani, F. (2025) · Proceedings on Privacy Enhancing Technologies · doi:10.56553/popets-2025-0108 · Cited by 9
“The most well-studied variants are (LDP) [22] and .”
Models Matter: Setting Accurate Privacy Expectations for Local and Central Differential Privacy
Smart, M. A., Nanayakkara, P., Cummings, R., Kaptchuk, G., & Redmiles, E. M. (2025) · Proceedings on Privacy Enhancing Technologies · doi:10.56553/popets-2025-0150 · Cited by 9
“The two most widely deployed models are the central model [29] and the local model [52].”
MethodChen, X., Wang, C., Yang, Q., Hu, T., & Jiang, C. (2022) · ACM Transactions on Management Information Systems · doi:10.1145/3569944 · Cited by 9
“Local differential privacy (LDP) [20], an advanced privacy-preserving technology, provides strong privacy guarantees as only the data owner can be accessible to the original data.”
BackgroundA Neighbourhood-Aware Differential Privacy Mechanism for Static Word Embeddings
Bollegala, D., Otake, S., Machide, T., & Kawarabayashi, K. (2023) · doi:10.18653/v1/2023.findings-ijcnlp.7 · Cited by 9
Differentially Private Frequent Itemset Mining from Smart Devices in Local Setting
Zhang, X., Huang, L., Fang, P., Wang, S., Zhu, Z., & Xu, H. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-60033-8_38 · Cited by 9
Near Optimal Jointly Private Packing Algorithms via Dual Multiplicative Weight Update
Huang, Z., & Zhu, X. (2018) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611975031.24 · Cited by 9
“, [6, 15], game theory (e.”
Multiple Privacy Regimes Mechanism for Local Differential Privacy
Ye, Y., Zhang, M., Feng, D., Li, H., & Chi, J. (2019) · Lecture notes in computer science · doi:10.1007/978-3-030-18579-4_15 · Cited by 9
A Practical Method to Reduce Privacy Loss When Disclosing Statistics Based on Small Samples
Chetty, R., & Friedman, J. N. (2019) · Journal of Privacy and Confidentiality · doi:10.29012/jpc.716 · Cited by 9
Learning Privately with Labeled and Unlabeled Examples
Beimel, A., Kobbi Nissim, B., & Stemmer, U. (2020) · Algorithmica · doi:10.1007/s00453-020-00753-z · Cited by 9
“[21], who also gave a generic construction of private learners.”
BackgroundMethodInfluentialA compression perspective on secrecy measures
Shkel, Y. Y., & Poor, H. V. (2020) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit44484.2020.9173959 · Cited by 9
“Then We omit the proof due to space constraints.”
BackgroundInformation Leakage Games: Exploring Information as a Utility Function
Alvim, M. S., Konstantinos Chatzikokolakis, A., Kawamoto, Y., & Catuscia Palamidessi, A. (2022) · ACM Transactions on Privacy and Security · doi:10.1145/3517330 · Cited by 9
Tian, H., Zheng, X., Zhang, X., & Zeng, D. D. (2021) · Electronic Commerce Research and Applications · doi:10.1016/j.elerap.2021.101105 · Cited by 9
Local Differential Privacy for Belief Functions
Li, Q., Zhou, C., Qin, B., & Xu, Z. (2022) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v36i9.21241 · Cited by 9
ZenoPS: A Distributed Learning System Integrating Communication Efficiency and Security
Xie, C., Koyejo, S., & Gupta, I. (2022) · Algorithms · doi:10.3390/a15070233 · Cited by 9
Investigating Users’ Privacy Concerns of Internet of Things (IoT) Smart Devices
Joy, D., Kotevska, O., & Al‐Masri, E. (2022) · IEEE Eurasia Conference on IOT, Communication and Engineering (ECICE) · doi:10.1109/ecice55674.2022.10042926 · Cited by 9
“The epsilon ( ϵ ) parameter is chosen based on much privacy loss is required by the user [27, 28].”
BackgroundPrivacy Preservation for Participatory Sensing Applications
Sei, Y., & Ohsuga, A. (2016) · International Conference on Advanced Information Networking and Applications (AINA) · doi:10.1109/aina.2016.19 · Cited by 9
“The privacy-preserving model in which users disguise and send their own attributes to the data collection server and the server analyzes the collected disguised attributes is referred to as a local model [14].”
BackgroundRevealing Encryption for Partial Ordering
Haagh, H., Ji, Y., Li, C., Orlandi, C., & Song, Y. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-71045-7_1 · Cited by 9
Differentially Private Distributed Data Summarization under Covariate ShiftPreprint
Sarpatwar, K., Shanmugam, K., Ganapavarapu, V. S., Jagmohan, A., & Vaculín, R. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1910.12832 · Cited by 9
“…that seeks to optimize the trade-off between accuracy of a trained classifier and differential privacy guarantees with respect to the training set [Kasiviswanathan et al. (2011); Chaudhuri et al. (2011); Song et al. (2013); Kifer et al. (2012); Bassily et al. (2014); Shokri & Shmatikov (2015);…”
BackgroundPrivacy Amplification Via Bernoulli SamplingPreprint
Imola, J., & Chaudhuri, K. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2105.10594 · Cited by 9
“…Balle et al., 2019a), and in the second, the randomness in sampling the data gives us privacy amplification by subsampling (Chaudhuri & Mishra, 2006; Kasiviswanathan et al., 2008; Li et al., 2011; Beimel et al., 2014b;a; Bun et al., 2015; Balle et al., 2018; Wang et al., 2019; Zhu & Wang, 2019;…”
BackgroundRobust Estimation of Discrete Distributions under Local Differential PrivacyPreprint
Chhor, J., & Sentenac, F. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2202.06825 · Cited by 9
“…constraint only (i.e. without contamination), the problem of estimating discrete distributions has been solved in (Evfimievski et al. (2003), Kasiviswanathan et al. (2008),Ye and Barg (2017)) where the authors propose a polynomial-time and minimax optimal algorithm for estimation under `1…”
BackgroundAlgorithms for bounding contribution for histogram estimation under user-level privacyPreprint
Liu, Y., Suresh, A. T., Zhu, W., Kairouz, P., & Gruteser, M. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2206.03008 · Cited by 9
“Differential privacy (DP) is studied in the central and local settings (Dwork et al., 2006; Kasiviswanathan et al., 2011; Duchi et al., 2013).”
BackgroundInstance-Optimal Differentially Private EstimationPreprint
McMillan, A., Smith, A., & Ullman, J. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2210.15819 · Cited by 9
“There is also a large body of research on so-called local differential privacy (Kasiviswanathan et al., 2008), where we assume that differential privacy is applied to each sample before it is collected.”
BackgroundInfluentialSelf-citationPrivate Federated Learning with Autotuned CompressionPreprint
Ullah, E., Choquette-Choo, C. A., Kairouz, P., & Oh, S. (2023) · arXiv (Cornell University) · doi:10.48550/arxiv.2307.10999 · Cited by 9
“Finally, many works, such as (Feldman and Talwar, 2021; Chen et al., 2020; Asi et al., 2022; Duchi et al., 2018; Girgis et al., 2021), study mean estimation, with and without compression, under local DP (Warner, 1965; Kasiviswanathan et al., 2011).”
BackgroundPreempting Text Sanitization Utility in Resource-Constrained Privacy-Preserving LLM InteractionsPreprint
Carpentier, R., Zhao, B. Z. H., Asghar, H. J., & Kâafar, M. A. (2024) · arXiv (Cornell University) · doi:10.48550/arxiv.2411.11521 · Cited by 9
“DP is achieved by adding properly calibrated noise to the result of the computation itself or to the input data in the case of Local DP [19].”
Modern challenges in distribution testing
Kamath, G. (2018) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 9
Efficient privacy loss accounting for subsampling and random allocationPreprint
Feldman, V., & Shenfeld, M. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2602.17284 · Cited by 9
Ibragimov, A., Wilson, E., Butler, K. R. B., & Jain, E. (2026) · IEEE Transactions on Visualization and Computer Graphics · doi:10.1109/tvcg.2026.3679093 · Cited by 8
Privacy in Theory, Bugs in Practice: Grey-Box Auditing of Differential Privacy Libraries
Cebere, T., Erb, D., Desfontaines, D., Bellet, A., & Fitzsimons, J. (2026) · Proceedings on Privacy Enhancing Technologies · doi:10.56553/popets-2026-0091 · Cited by 8
A minimax distortion view of differentially private query release
Wang, W., Ying, L., & Zhang, J. (2015) · Asilomar Conference on Signals, Systems and Computers (ACSSC) · doi:10.1109/acssc.2015.7421298 · Cited by 8
“, [13]).”
Nam, S.-H., & Lee, S.-H. (2022) · IEEE Signal Processing Letters · doi:10.1109/lsp.2022.3205276 · Cited by 8
Local differentially private frequency estimation based on learned sketches
Zhang, M., Lin, S., & Yin, L. (2023) · Information Sciences · doi:10.1016/j.ins.2023.119667 · Cited by 8
Unveiling the Role of Message Passing in Dual-Privacy Preservation on GNNs
Zhao, T., Hu, H., & Cheng, L. (2023) · ACM International Conference on Information and Knowledge Management (CIKM) · doi:10.1145/3583780.3615104 · Cited by 8
“[32] introduced node privacy in GNNs through local differential privacy [21].”
BackgroundCookie Monster: Efficient On-Device Budgeting for Differentially-Private Ad-Measurement Systems
Tholoniat, P., Kostopoulou, K., McNeely, P., Sodhi, P. S., Varanasi, A., Case, B., Cidon, A., Geambasu, R., & Lécuyer, M. (2024) · ACM SIGOPS Symposium on Operating Systems Principles (SOSP) · doi:10.1145/3694715.3695965 · Cited by 8
“Others function in the local-DP model, where devices randomize their data locally [23], and therefore inherently do on-device budgeting but have higher utility costs.”
SoK: Descriptive Statistics Under Local Differential Privacy
Raab, R., Berrang, P., Gerhart, P., & Schröder, D. (2024) · Proceedings on Privacy Enhancing Technologies · doi:10.56553/popets-2025-0008 · Cited by 8
“The local variant of differential privacy, Local Differential Privacy (LDP) [52], eliminates the need for trust in the system.”
A Metric Differential Privacy Mechanism for Sentence Embeddings
Bollegala, D., Otake, S., Machide, T., & Kawarabayashi, K. (2024) · ACM Transactions on Privacy and Security · doi:10.1145/3708321 · Cited by 8
“Learning models from data with DP guarantees has been studied under private learning [24].”
PPFL: Privacy-Preserving Techniques in Federated Learning
Jahani, K., Moshiri, B., & Khalaj, B. H. (2024) · Journal of Artificial Intelligence Applications and Innovations · doi:10.61838/jaiai.1.3.6 · Cited by 8
Privacy without Noisy Gradients: Slicing Mechanism for Generative Model Training
Greenewald, K. H., Yu, Y.-C., Wang, H., & Yu, Y.-C. (2024) · neural information processing systems · doi:10.52202/079017-3994 · Cited by 8
On provable privacy vulnerabilities of graph representations
Wu, R., Fang, G., Zhang, M., Pan, Q., Liu, T., & Wang, W. (2024) · neural information processing systems · doi:10.52202/079017-2885 · Cited by 8
On Differentially Private U Statistics
Chaudhuri, K., Loh, P., Pandey, S., & Sarkar, P. (2024) · neural information processing systems · doi:10.52202/079017-0727 · Cited by 8
Differential Privacy for Binary Functions via Randomized Graph Colorings
D’Oliveira, R. G. L., Médard, M., & Sadeghi, P. (2021) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit45174.2021.9517935 · Cited by 8
Differentially-Private Sublinear-Time Clustering
Blocki, J., Grigorescu, E., & Mukherjee, T. (2021) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit45174.2021.9518014 · Cited by 8
Assessing Differentially Private Variational Autoencoders Under Membership Inference
Bernau, D., Robl, J., & Kerschbaum, F. (2022) · Lecture notes in computer science · doi:10.1007/978-3-031-10684-2_1 · Cited by 8
Differential privacy: Review of improving utility through cryptography‐based technologies
Huang, W. C., Zhuo, M., Zhu, T., Zhou, S., & Liao, Y. (2022) · Concurrency and Computation Practice and Experience · doi:10.1002/cpe.7565 · Cited by 8
Oblivious Statistic Collection With Local Differential Privacy in Mutual Distrust
Sasada, T., Taenaka, Y., & Kadobayashi, Y. (2023) · IEEE Access · doi:10.1109/access.2023.3251560 · Cited by 8
“To anonymize such sensitive information, Local Differential Privacy (LDP)-based privacy protection attracts great attention [5].”
BackgroundFu, Y., Ye, Q., Du, R., & Hu, H. (2023) · ACM Transactions on Sensor Networks · doi:10.1145/3623637 · Cited by 8
“Local diferential privacy (LDP) is proposed as a formidable privacy assurance for crowdsourced systems where sensitive data, especially those associated with personal information, are perturbed before collection to estimate statistical attributes like frequency or mean [6, 11, 22].”
Federated Submodular Maximization With Differential Privacy
Wang, Y., Zhou, T., Chen, C., & Wang, Y. (2023) · IEEE Internet of Things Journal · doi:10.1109/jiot.2023.3324801 · Cited by 8
“1) The privacy guarantee of a DP mechanism can be amplified by subsampling [65], [66], [67], [68].”
BackgroundCaPS: Collaborative and Private Synthetic Data Generation from Distributed Sources
Pentyala, S., Pereira, M. W., & Cock, M. D. (2024) · Ghent University Academic Bibliography (Ghent University) · doi:10.48550/arxiv.2402.08614 · Cited by 8
“Decentralized paradigms such as peer-to-peer solutions that remove the need of central entity, adapt approaches based on local differential privacy (LDP) (Kasiviswanathan et al., 2011) or distributed differential privacy (Kairouz et al., 2021a) which are known to result in utility loss (Pasquini et al., 2023).”
BackgroundOptimal Private Discrete Distribution Estimation With 1-bit Communication
Nam, S.-H., Tan, V. Y. F., & Lee, S.-H. (2024) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2024.3419721 · Cited by 8
“Among numerous well-established privacy metrics, local differential privacy (LDP) has emerged as one of the most popular privacy requirements [1], [3], [6].”
BackgroundDistributed Set Intersection and Union with Local Differential Privacy
Xue, Q., Zhu, Y., Wang, J., & Li, X. (2017) · IEEE International Conference on Parallel and Distributed Systems (ICPADS) · doi:10.1109/icpads.2017.00036 · Cited by 8
“[9] first proposed the definition of local differential privacy (LDP).”
BackgroundDifferentially Private Mobile Crowd Sensing Considering Sensing Errors
Sei, Y., & Ohsuga, A. (2020) · Sensors · doi:10.3390/s20102785 · Cited by 8
“If two elements are protected by (cid:101) -differential privacy, we should divide the privacy budget (cid:101) into two elements [34].”
InfluentialUniformity Testing in the Shuffle Model: Simpler, Better, Faster
Canonne, C. L., & Lyu, H. (2022) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611977066.13 · Cited by 8
Mean Estimation Under Heterogeneous Privacy: Some Privacy Can Be Free
Chaudhuri, S., & Courtade, T. A. (2023) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit54713.2023.10206746 · Cited by 8
BUDS: Balancing Utility and Differential Privacy by Shuffling
Sengupta, P., Paul, S., & Mishra, S. (2020) · International Conference on Computing, Communication and Networking Technologies (ICCCNT) · doi:10.1109/icccnt49239.2020.9225470 · Cited by 8
Approximate Data Analytics Systems
Quoc, D. L. (2017) · Qucosa (Saxon State and University Library Dresden) · Cited by 8
When Differential Privacy Meets Graph Neural Networks.Preprint
Sajadmanesh, S., & Gática-Pérez, D. (2020) · arXiv (Cornell University) · Cited by 8
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.