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 801–900 of 1,005
Compare the Impacts of Data Correlation on Privacy Leakage in a Combined Privacy Preserving Approach
Hemkumar, D. (2023) · International Conference on Applied Intelligence and Sustainable Computing (ICAISC) · doi:10.1109/icaisc58445.2023.10199728 · Cited by 5
Differential Privacy and Neural Networks: A Preliminary Analysis
Manco, G., & Pirrò, G. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-71970-2_4 · Cited by 5
Tsou, Y.-T., Zhen, H., Kuo, S., Chang, C., Fukushima, A., & Rong, B.-D. (2020) · Computer Communications · doi:10.1016/j.comcom.2020.01.001 · Cited by 5
POSTER: Data Collection via Local Differential Privacy with Secret Parameters
Takagi, S., Cao, Y., & Yoshikawa, M. (2020) · ACM Asia Conference on Computer and Communications Security (ASIA CCS) · doi:10.1145/3320269.3405441 · Cited by 5
“(ε-local differential privacy [6]) A mechanism M : X → Z satisfies ε-LDP iff ∀d, d ′ ∈ X, z ∈ Z, Pr(M (d) = z) ≤ e Pr(M (d ′) = z)”
Locally differentially private distributed algorithms for set intersection and union
Xue, Q., Zhu, Y., Wang, J., Li, X., & Zhang, J. (2021) · Science China Information Sciences · doi:10.1007/s11432-018-9899-8 · Cited by 5
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 Operating Systems Review · doi:10.1145/3352020.3352032 · Cited by 5
“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].”
Budget allocation on differentially private decision trees and random forests
Borhan, N. M. (2018) · OPUS - Open Publications of UTS Scholars (University of Technology Sydney) · Cited by 5
Assisted Learning for Organizations with Limited Imbalanced DataPreprint
Chen, C., Zhou, J., Ding, J., & Zhou, Y. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2109.09307 · Cited by 5
“Using the strong composition formula [Kasiviswanathan et al., 2011], the privacy after T SGD steps and batch fraction q satisfies ( (cid:15) (cid:48) , δ (cid:48) ) -DP, with (cid:15) (cid:48) = 2 q(cid:15) T log(1 /δ ) , δ (cid:48) = qTδ .”
BackgroundMethodNonparametric extensions of randomized response for private confidence setsPreprint
Waudby-Smith, I., Wu, Z. S., & Ramdas, A. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2202.08728 · Cited by 5
“Background I: Local Differential Privacy There are two main models of privacy within the DP framework: central and local DP (LDP) (Dwork et al., 2006; Kasiviswanathan et al., 2011; Dwork & Roth, 2014).”
BackgroundPointwise Maximal LeakagePreprint
Saeidian, S., Cervia, G., Oechtering, T. J., & Skoglund, M. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2205.04935 · Cited by 5
“More specifically, we discuss max-information [43], [44], local differential privacy [5], [6], local information privacy [16], [18], local differential identifiability [9], [21], mutual information, f -information [13], and total variation privacy [14].”
BackgroundInfluentialPrivacy Amplification via Shuffled Check-InsPreprint
Liew, S. P., Hasegawa, S., & Takahashi, T. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2206.03151 · Cited by 5
“When D consists of only a single element, the mechanism, also known as a local randomizer, is said to be satisfying local DP: Definition 2 (Local Differential Privacy (LDP) [29]) .”
BackgroundA Framework for Understanding Model Extraction Attack and DefensePreprint
Xian, X., Hong, M., & Ding, J. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2206.11480 · Cited by 5
Gromov-Wasserstein Discrepancy with Local Differential Privacy for Distributed Structural GraphsPreprint
Jin, H., & Chen, X. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2202.00808 · Cited by 5
“More specifically, such kind of algorithm helps to protect the statistics of graph, such as subgraph counts, number of edges and degree distribution [Kasiviswanathan et al., 2011].”
BackgroundThe Saddle-Point Accountant for Differential PrivacyPreprint
Alghamdi, W., Asoodeh, S., Calmon, F. P., Gomez, J. F., Kosut, O., Sankar, L., & Wei, F. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2208.09595 · Cited by 5
Discrete Distribution Estimation under User-level Local Differential PrivacyPreprint
Acharya, J., Liu, Y., & Sun, Z. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2211.03757 · Cited by 5
“In the distributed setting, the more stringent version, local differential privacy (LDP) [25, 20] requires users to privatize their data before sending it to the data collector (see Definition 1.”
Gradients Look Alike: Sensitivity is Often Overestimated in DP-SGDPreprint
Thudi, A., Jia, H., Meehan, C., Shumailov, I., & Papernot, N. (2023) · arXiv (Cornell University) · doi:10.48550/arxiv.2307.00310 · Cited by 5
“To then analyze the sampled Gaussian mechanism one would incorporate the privacy gain from not sampling x ∗ sometimes [4][24] to get the privacy guarantees of M as ( ε ′ , δ ′ ) -DP where ε ′ = ln ( P x ∗ ( 1 ) e C δ , σ C U + P x ∗ ( 0 )) and δ ′ = P x ∗ ( 1 ) δ .”
Balancing Privacy, Robustness, and Efficiency in Machine LearningPreprint
Allouah, Y., Guerraoui, R., & Stephan, J. (2023) · arXiv (Cornell University) · doi:10.48550/arxiv.2312.14712 · Cited by 5
“We consider that algorithm A must satisfy local differential privacy (LDP) [50], the strongest DP requirement whereby all user communications are DP and no entity is trusted for privacy.”
BadGD: A unified data-centric framework to identify gradient descent vulnerabilitiesPreprint
Wang, C., & Cheng, G. (2024) · arXiv (Cornell University) · doi:10.48550/arxiv.2405.15979 · Cited by 5
Makhlouf, K. (2024) · theses.fr (ABES) · doi:10.70675/30eb5919zcfb1z4231z81e0z61ac4b58ec29 · Cited by 5
Private, Augmentation-Robust and Task-Agnostic Data Valuation Approach for Data MarketplacePreprint
Jahani-Nezhad, T., Moradi, P., Maddah-Ali, M. A., & Caire, G. (2024) · arXiv (Cornell University) · doi:10.48550/arxiv.2411.00745 · Cited by 5
“A mechanism M : X → R with data domain X and range R satisfies ( ϵ, δ ) -Local Differential Privacy (Dwork et al., 2006; Kasiviswanathan et al., 2011), if for every pair of adjacent inputs x 1 , x 2 ∈ X and for any possible output O ⊆ R , the following inequality holds where ϵ ≥ 0 , 0 ≤ δ ≤ 1 , and…”
BackgroundA Decade of Metric Differential Privacy: Advancements and ApplicationsPreprint
Xie, X., Yu, C., Huang, Y., Cao, Y., & Qiu, C. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2502.08970 · Cited by 5
“Thus, small input changes lead to only bounded changes in the law of M ( x ) . mDP vs. local DP. mDP defined in Definition II.1 is closely related to the definition of local DP [15], where a random mechanism M is applied independently to each element of a database.”
Theory of Privacy and Testing in a Quantum World
Nuradha, T. (2025) · eCommons (Cornell University) · doi:10.7298/0jdp-1r42 · Cited by 5
Sébert, A. G. (2023) · theses.fr (ABES) · doi:10.70675/10bb5f06zd04az4edbzadfcz7fabd892f109 · Cited by 5
On the Price of Privacy for Language Identification and GenerationPreprint
Li, X., Han, A., Jiang, J., & Gao, J. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2604.07238 · Cited by 5
“There is a rich literature on differentially private PAC learning [Kasiviswanathan et al., 2011; Bun et al., 2015; Bun, 2020] and private statistical estimation [Chaudhuri and Hsu, 2012; Aden-Ali et al., 2021; Bie et al., 2022].”
Estimating Group Means Under Local Differential Privacy
Raab, R., Bohr, A., Klede, K., Gmeiner, B., & Eskofier, B. M. (2025) · Proceedings on Privacy Enhancing Technologies · doi:10.56553/popets-2025-0129 · Cited by 4
“It was first introduced by Dwork et al. [16] for DP and Kasiviswanathan et al. [35] for LDP and is based on additive noise drawn from the Laplace distribution.”
Truss Decomposition Under Edge Local Differential Privacy
Zhang, Y., Ni, W., Wang, K., He, Y., & Li, C. (2025) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde65448.2025.00201 · Cited by 4
Uniformity Testing Under User-Level Local Privacy
Canonne, C. L., Gentle, A., & Singhal, V. (2025) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.itcs.2026.33 · Cited by 4
Versatile differentially private learning for general loss functions
Lu, Q., Chen, S. X., & Qiu, Y. (2026) · The Annals of Statistics · doi:10.1214/25-aos2583 · Cited by 4
SoK: Practical Aspects of Releasing Differentially Private Graphs
D'Silva, N., Nepal, S., & Kanhere, S. S. (2026) · ACM Asia Conference on Computer and Communications Security (ASIA CCS) · doi:10.1145/3779208.3805972 · Cited by 4
“A key variant, local-DP [59], has at-tracted attention but remains less explored due to utility and efficiency challenges.”
Yu, M., Li, J., & Zhou, Y. (2025) · Journal of Econometrics · doi:10.1016/j.jeconom.2025.106125 · Cited by 4
Kobbi Nissim, B., Tsfadia, E., & Yan, C. (2026) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611978971.206 · Cited by 4
SPPM: sparse privacy preserving mappings
Salamatian, S., Fawaz, N., Kveton, B., & Taft, N. (2014) · Uncertainty in Artificial Intelligence · Cited by 4
On the fine asymptotics of information theoretic privacy
Kalantari, K., Kosut, O., & Sankar, L. (2016) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2016.7852277 · Cited by 4
Frequent Itemset Mining of User’s Multi-attribute Under Local Differential Privacy
Liu, H., Cui, L., Ma, X., & Wu, C. (2020) · Computers, materials & continua/Computers, materials & continua (Print) · doi:10.32604/cmc.2020.010987 · Cited by 4
Ma, X., Liu, H., & Guan, S. (2021) · IEEE International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom) · doi:10.1109/trustcom53373.2021.00072 · Cited by 4
“In order to solve the shortcomings of this mechanism, local differential privacy [2] is proposed, which advances the steps of the disturbance.”
BackgroundLocal Differential Privacy for Person-to-Person Interactions
Sei, Y., & Ohsuga, A. (2022) · IEEE Open Journal of the Computer Society · doi:10.1109/ojcs.2022.3228999 · Cited by 4
“Several large organizations such as Apple, Google, and Microsoft have been collecting users’ information while protecting their privacy [3], [4], [5], [6] using the (cid:2) -local differential privacy (LDP) technique [7].”
BackgroundOptimal Multidimensional Differentially Private Mechanisms in the Large-Composition Regime
Alghamdi, W., Asoodeh, S., Calmon, F. P., Gomez, J. F., Kosut, O., & Sankar, L. (2023) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit54713.2023.10206658 · Cited by 4
“9) , whereas its vector p ∈ (0 , ∞ ) N +1 is computed numerically with the aid of Theorem 4. guarantees [11], [14], [15].”
MethodRandomized Response Has No Disparate Impact on Model Accuracy
Carey, A. N., Bhaila, K., & Wu, X. (2023) · IEEE International Conference on Big Data (BigData) · doi:10.1109/bigdata59044.2023.10386574 · Cited by 4
“More formally, ϵ -LDP is defined as follows: Definition 1 ( ϵ -LDP [27]): A randomized mechanism M satisfies ϵ -local differential privacy if and only if for any pair of input values r, r ′ in the domain of M , and for any possible output o in the range of M : Definition 1 states that the…”
BackgroundDifferential Privacy Preservation for Continuous Release of Real-Time Location Data
Mao, L., & Xu, Z. (2024) · Entropy · doi:10.3390/e26020138 · Cited by 4
“To solve this problem, local differential privacy (LDP) [9] has been proposed.”
BackgroundYan, Y., Yan, P., Mahmood, A., Zhang, Y., & Sheng, Q. Z. (2024) · Journal of King Saud University - Computer and Information Sciences · doi:10.1016/j.jksuci.2024.102085 · Cited by 4
“The relative error of spatial range counting query within 𝑞 𝐾𝐿 ( 𝑃 || 𝑄 ) Kullback–Leibler divergence of two probability distributions 𝑃 ( 𝑥 ) and 𝑄 ( 𝑥 ) Definition 1 ( 𝜀 -Local Differential Privacy, Kasiviswanathan et al., 2011; Duchi et al., 2013 ) .”
CHESSFL: Clustering Hierarchical Embeddings for Semi-Supervised Federated Learning
Farcas, A.-J., Lee, M., Payani, A., Latapie, H. M., Kompella, R. R., & Mărculescu, R. (2024) · IEEE/ACM International Conference on Internet-of-Things Design and Implementation (IoTDI) · doi:10.1109/iotdi61053.2024.00015 · Cited by 4
“On top of the resulting benefits of decentralization through hierarchy, when compared to local differential privacy [5], hierarchical differential privacy [6] highlights an opportunity for privacy strengthening due to differential privacy noise being injected multiple times throughout the hierarchy,…”
BackgroundKurri, G. R., Managoli, M. A., & Prabhakaran, V. M. (2024) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit57864.2024.10619300 · Cited by 4
“In fact, such distributions completely characterize the set of all distributions for which L h ( G ) -pw ( X → y ) = ∞ . where the expression in RHS corresponds to the leakage measure in terms of local differential privacy for P Y | X [20].”
BackgroundNam, S.-H., Park, H.-Y., & Lee, S.-H. (2024) · IEEE Transactions on Information Theory · doi:10.1109/tit.2024.3448475 · Cited by 4
“I N STATISTICAL inference problems, local differential privacy (LDP) is one of the most representative privacy requirements for preserving privacy during the data collection process [2], [3], [4].”
BackgroundMeasuring Local and Shuffled Privacy of Gradient Randomized Response
Matsumoto, M., Takahashi, T., Liew, S. P., & Oguchi, M. (2024) · Journal of Information Processing · doi:10.2197/ipsjjip.32.990 · Cited by 4
Federated Learning-Based Tokenizer for Domain-Specific Language Models in Finance
Damoun, F., Seba, H., & State, R. (2025) · Lecture notes in computer science · doi:10.1007/978-3-031-78538-2_1 · Cited by 4
PAUSE: Privacy-Aware Active User Selection for Federated Learning
Peleg, O., Lang, N., Rini, S., Shlezinger, N., & Cohen, K. (2025) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp49660.2025.10890399 · Cited by 4
“In FL, privacy is commonly quantified in terms of LDP [40], [41], as this metric assumes an untrusted server by the users.”
On Computing Pairwise Statistics with Local Differential Privacy
Ghazi, B., Kamath, P., Kumar, R. R., Manurangsi, P., & Sealfon, A. (2023) · neural information processing systems · doi:10.52202/075280-1181 · Cited by 4
Local Differential Privacy Meets Computational Social Choice - Resilience under Voter Deletion
Tao, L., Chen, L., Xu, L., & Shi, W. (2022) · International Joint Conference on Artificial Intelligence · doi:10.24963/ijcai.2022/547 · Cited by 4
Zhang, X., Wang, Y., Yang, Q., Shen, Y., & Wen, H. (2023) · Multimedia Tools and Applications · doi:10.1007/s11042-023-15743-w · Cited by 4
“The new sensing modality is attracting significant efforts to adapt it to a number of important vision tasks, such as object classification [17, 33], human activity recognition [4, 5, 36, 40], robotic vision [8, 14, 16], video reconstruction [25, 29, 30, 34, 38, 39], and etc.”
MistNet: A superior edge-cloud privacy-preserving training framework with one-shot communication
Guo, W., Cui, J., Li, X., Qu, L., Li, H., Hu, A., & Cai, T. (2023) · Internet of Things · doi:10.1016/j.iot.2023.100975 · Cited by 4
Human-Centered Services Computing for Smart Cities: IEICE Monograph
Murakami, Y., & Kimura, K. (2024) · Springer eBooks · doi:10.1007/978-981-97-0779-9 · Cited by 4
Differentially Private Distributed Data Analysis
Takabi, H., Koppikar, S. D., & Zargar, S. T. (2016) · IEEE International Conference on Collaboration and Internet Computing (CIC) · doi:10.1109/cic.2016.038 · Cited by 4
“[20] showed that any probability approximately correct (PAC)-learning algorithm could be converted to a differentially private PAClearning algorithm, although not necessarily one that runs in polynomial time.”
BackgroundOn the Optimality of the Exponential Mechanism
Aldà, F., & Simon, H. U. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-60080-2_5 · Cited by 4
“If we ignore the efficiency issues that this algorithm inherently has, it has proved extremely successful in a number of applications, from privately generating synthetic databases that can accurately answer a large class of queries [4], to private PAC-learning [16].”
BackgroundOn Fair Cost Sharing Games in Machine Learning
Redko, I., & Laclau, C. (2019) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v33i01.33014790 · Cited by 4
Differentially Private Learning of Geometric Concepts
Kaplan, H. Y., Mansour, Y., Matias, Y., & Stemmer, U. (2022) · SIAM Journal on Computing · doi:10.1137/21m1406428 · Cited by 4
Price of Privacy in the Keynesian Beauty Contest
Elzayn, H., & Schutzman, Z. (2019) · ACM Conference on Economics and Computation (EC) · doi:10.1145/3328526.3329607 · Cited by 4
“[14] and recent work has shown that this notion is a powerful framework for addressing privacy concerns (c.”
BackgroundParameter-Free Locally Differentially Private Stochastic Subgradient Descent
Jun, K.-S., & Orabona, F. (2019) · OpenBU (Boston University) · doi:10.48550/arxiv.1911.09564 · Cited by 4
“Hence, we can construct sanitized subgradients simply returning a noisy version G(w) ∈ ∂`(w,x) + ξ where the noise ξ guarantees the -Local Differential Privacy ( -LDP), which prevents the private information from being identified.”
MethodInfluentialInformation Thresholds for Non-Parametric Structure Learning on Tree Graphical Models
Nikolakakis, K. E., Kalogerias, D. S., & Sarwate, A. D. (2019) · Cited by 4
Privacy Preserving Detection of Path Bias Attacks in Tor
Watson, L., Mediratta, A., Elahi, T., & Sarkar, R. (2020) · Proceedings on Privacy Enhancing Technologies · doi:10.2478/popets-2020-0065 · Cited by 4
“The subroutine of sampling has been shown to increase the level of privacy obtained by an differentially private algorithm [2, 4, 5, 8, 10, 18].”
BackgroundDifferentially Private Social Graph Publishing for Community Detection
Ma, X., Yang, J., & Guan, S. (2020) · Lecture notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering · doi:10.1007/978-3-030-63095-9_11 · Cited by 4
Differentially private approximate aggregation based on feature selection
He, Z., Sai, A. M. V. V., Huang, Y., Seo, D., Zhang, H., & Han, Q. (2021) · Journal of Combinatorial Optimization · doi:10.1007/s10878-020-00666-1 · Cited by 4
Privacy Operators for Semantic Graph Databases as Graph Rewriting
Boiret, A., Eichler, C., & Nguyen, B. (2022) · Communications in computer and information science · doi:10.1007/978-3-031-15743-1_34 · Cited by 4
Adversarial Manifold Estimation
Aamari, E., & Knop, A. (2022) · Foundations of Computational Mathematics · doi:10.1007/s10208-022-09588-2 · Cited by 4
Nam, S.-H., Park, H.-Y., & Lee, S.-H. (2024) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit57864.2024.10619385 · Cited by 4
“In statistical inference problems, local differential privacy (LDP) is one of the most representative privacy requirements for preserving privacy during the data collection process [1]– [3].”
BackgroundPrivate Distribution Testing with Heterogeneous Constraints: Your Epsilon Might Not Be Mine
Canonne, C. L., & Sun, Y. (2023) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.3929/ethz-b-000659609 · Cited by 4
On the Power of Learning from $k$-Wise Queries
Feldman, V., & Ghazi, B. (2017) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.itcs.2017.41 · Cited by 4
Reconciling Privacy and Utility in Continuous-Time Diffusion Networks
Michael Backes, A., Gomez-Rodriguez, M., Manoharan, P., & Surma, B. (2017) · IEEE Computer Security Foundations Workshop (CSFW) · doi:10.1109/csf.2017.29 · Cited by 4
“For instance, Differential Privacy [5] protects entries in statistical databases from revealing sensitive information by perturbing the sensitive columns in the database, while at the same time ensuring limited utility by carefully calibrating the applied noise [14].”
BackgroundLeveraging Privacy In Data Analysis
Rogers, R. (2017) · ScholarlyCommons (University of Pennsylvania) · Cited by 4
Mathematical foundations of differential privacy
Holohan, N. (2017) · Trinity's Access to Research Output (TARA) (Trinity College Dublin) · Cited by 4
Locally Differentially-Private Randomized Response for Discrete Distribution LearningPreprint
Pastore, A., & Gastpar, M. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1811.12257 · Cited by 4
“…the original purpose of DP was to provide strong privacy guarantees against a resourceful attacker who can access queries to a central database, Kasiviswanathan et al. (2011) and Wainwright et al. (2012) considered a decentralized privatization model referred to as local privacy , in which…”
BackgroundUniversally Optimal Privacy Mechanisms for Minimax AgentsPreprint
Gupte, M., & Sundararajan, M. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1001.2767 · Cited by 4
“VC dimension. Kasiviswanathan et al. [ 11 ] give further results for privately learning hypotheses from a given class.”
BackgroundOptimal Lower Bounds for Universal and Differentially Private Steiner Tree and TSPPreprint
Bhalgat, A., Chakrabarty, D., & Khanna, S. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1011.3770 · Cited by 4
“de from the work of Gupta et al.[12] on various combinatorial optimization problems, algorithms with privacy constraints have been developed for other problems such as computational learning problems [17], geometric clustering problems [9], recommendation systems [22], to name a few. Organization. In Section 2, we est…”
MethodThe Privacy-Utility Tradeoff of Robust Local Differential PrivacyPreprint
Lopuhaä-Zwakenberg, M., & Goseling, J. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2101.09139 · Cited by 4
“In this paper we consider measures based on Local Differential Privacy (LDP) [9], [23].”
MethodOn the Sample Complexity of Privately Learning Axis-Aligned RectanglesPreprint
Sadigurschi, M., & Stemmer, U. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2107.11526 · Cited by 4
“Works in this vein include [Kasiviswanathan et al., 2011, Beimel et al., 2014, 2019b, 2016, 2020, Bun et al., 2015, Feldman and Xiao, 2015, Bun et al., 2019, Beimel et al., 2019a, Kaplan et al., 2019, 2020a, Alon et al., 2020, Kaplan et al., 2020b, Bun et al., 2020, Alon et al., 2019], and much…”
MethodOptimal SQ Lower Bounds for Learning Halfspaces with Massart NoisePreprint
Nasser, R., & Tiegel, S. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2201.09818 · Cited by 4
“( / Note, that it has also found applications outside of PAC learning, see e.g., [KLN + 11, FGV21] for examples.”
BackgroundA Generative Framework for Personalized Learning and Estimation: Theory, Algorithms, and PrivacyPreprint
Ozkara, K., Girgis, A. M., Data, D., & Diggavi, S. N. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2207.01771 · Cited by 4
“Definition 1 (Local Differential Privacy - LDP [32]) .”
BackgroundThe Poisson binomial mechanism for secure and private federated learningPreprint
Chen, W., Özgür, A., & Kairouz, P. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2207.09916 · Cited by 4
“Given its strong privacy guarantees, local DP naturally suffers from poor privacy-utility trade-offs Kasiviswanathan et al. (2011); Duchi et al. (2013); Kairouz et al. (2016).”
BackgroundMethodPrivacy-Preserving Federated Heavy Hitter Analytics for Non-IID DataPreprint
Shao, J., Han, S., He, C., & Luo, B. (2023) · arXiv (Cornell University) · doi:10.48550/arxiv.2307.02277 · Cited by 4
“Other algorithms employ LDP (Kasiviswanathan et al., 2011) to protect individual privacy without a trusted server by perturbing individual’s local data before sending, such as PEM (Wang et al., 2019), RAPPOR (Erlingsson et al., 2014), PrivTrie (Wang et al., 2018), TreeHist and Bit-stogram (Bassily…”
MethodHuang, T.-W., & Ascarza, E. (2023) · SSRN Electronic Journal · doi:10.2139/ssrn.4575240 · Cited by 4
Federated Learning with Reduced Information Leakage and Computation
Yin, T., Tan, X., Zhang, X., Khalili, M. M., & Liu, M. (2023) · Transactions on machine learning research · doi:10.48550/arxiv.2310.06341 · Cited by 4
“…approaches were proposed in the DP literature to improve the privacy-accuracy trade-off (e.g., privacy amplification by sampling [21, 22, 23, 24, 25, 26, 27], leveraging non-private public data [28, 29], shuffling [30], using weaker privacy notion [31], using tighter privacy composition…”
Private Synthetic Data Meets Ensemble LearningPreprint
Sun, H., Azizan, N., Srivastava, A., & Wang, H. (2023) · arXiv (Cornell University) · doi:10.48550/arxiv.2310.09729 · Cited by 4
“It suggests that the privacy guarantees of a DP mechanism can be enhanced by applying the mechanism to a random subsample of the original dataset [39, 40].”
K-stars LDP: A Novel Framework for (p, q)-clique Enumeration under Local Differential PrivacyPreprint
Sun, H., Wu, Z., Li, R.-H., Wang, G., & Li, Z. (2024) · arXiv (Cornell University) · doi:10.48550/arxiv.2403.01788 · Cited by 4
“The existing privacy protection algorithms for subgraph counting are usually under edge LDP [18], [5], [19].”
BackgroundMethodOptimality of Matrix Mechanism on $\ell_p^p$-metricPreprint
Liu, J., Upadhyay, J., & Zou, Z. (2024) · arXiv (Cornell University) · doi:10.48550/arxiv.2406.02140 · Cited by 4
The Complexities of Differential Privacy for Survey DataPreprint
Drechsler, J., & Bailie, J. (2024) · arXiv (Cornell University) · doi:10.48550/arxiv.2408.07006 · Cited by 4
“This idea has been formalized in several papers in the context of DP (Balle et al., 2018; Bun et al., 2015; Kasiviswanathan et al., 2011; Wang et al., 2016, 2019).”
Privacy-Preserving Race/Ethnicity Estimation for Algorithmic Bias Measurement in the U.SPreprint
Badrinarayanan, S., Osoba, O., Cheng, M., Rogers, R., Jain, S., Tandra, R., & Pillai, N. S. (2024) · arXiv (Cornell University) · doi:10.48550/arxiv.2409.04652 · Cited by 4
“Using secure two-party computation tools such as commutative encryption and homomorphic encryption for performing joins and computing on associated features have been widely studied ([10, 11, 12] to name a few) and local DP has also been comprehensively studied ([13, 14, 15] to name a few).”
BackgroundInvestigating Privacy Attacks in the Gray-Box Setting to Enhance Collaborative Learning SchemesPreprint
Mazzone, F., Badawi, A. A., Polyakov, Y., Everts, M. H., Hahn, F. F. W., & Peter, A. (2024) · arXiv (Cornell University) · doi:10.48550/arxiv.2409.17283 · Cited by 4
“Applying noise to each computed gradients could be done as well, and the overall effect over batches can be analyzed using the privacy amplification theorem [37], [6].”
MethodEnhancing Feature-Specific Data Protection via Bayesian Coordinate Differential PrivacyPreprint
Aliakbarpour, M., Chaudhuri, S., Courtade, T. A., Fallah, A., & Jordan, M. I. (2024) · arXiv (Cornell University) · doi:10.48550/arxiv.2410.18404 · Cited by 4
“A variant of DP, local differential privacy (LDP), suitable for distributed settings where users do not trust any central authority has been extensively studied [Warner, 1965, Evfimievski et al., 2003, Beimel et al., 2008, Kasiviswanathan et al., 2011, Chan et al., 2012].”
BackgroundOn Theoretical Limits of Learning with Label Differential PrivacyPreprint
Zhao, P., Ma, C., Shen, L., Wang, S., & Fan, R. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2502.14309 · Cited by 4
“Under the local model, [54] finds the relation between local DP and statistical query.”
Leveraging Randomness in Model and Data Partitioning for Privacy AmplificationPreprint
Dong, A., Chen, W., & Özgür, A. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2503.03043 · Cited by 4
“…in federated learning (Kairouz et al., 2021)) is randomly selected to participate in each training iteration (independently across iterations) (Kasiviswanathan et al., 2011; Li et al., 2012; Bassily et al., 2014; Wang et al., 2015; Balle et al., 2018; Wang et al., 2019; Zhu & Wang, 2019;…”
Zhou, X., Wu, Y., Weng, W., & Orabona, F. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2505.21395 · Cited by 4
“For preference label privacy under the local model of Differential Privacy (DP) (Kasiviswanathan et al., 2011; Chaudhuri & Hsu, 2011), Square χ PO achieves the optimal privacy cost, even with general function approximations.”
Private List Learnability vs. Online List LearnabilityPreprint
Hanneke, S., Moran, S., Schefler, H., & Tsubari, I. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2506.12856 · Cited by 4
“The study of the PAC learning model under differential privacy was initiated by [KLN + 11], who showed that every finite concept class C is privately learnable with a sample complexity of O (log |C| ).”
Data Poisoning Attacks to Locally Differentially Private Range Query ProtocolsPreprint
Liao, T.-W., Lin, C.-H., Tsai, Y.-L., Murakami, T., Yu, C.-M., Sakuma, J., Huang, C., & Kikuchi, H. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2503.03454 · Cited by 4
“In the local differential privacy (LDP) model [11,23], we consider a scenario with n local users and a remote, untrusted data collector.”
An $\tilde{O}$ptimal Differentially Private Learner for Concept Classes with VC Dimension 1Preprint
Yan, C. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2505.06581 · Cited by 4
“Kasiviswanathan et al. [17] give a upper bound O (log |C| ), which works for pure differential privacy ( δ = 0).”
InfluentialImproved Bounds for Private and Robust AlignmentPreprint
Weng, W., He, Y., & Zhou, X. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2512.23816 · Cited by 4
Local Node Differential PrivacyPreprint
Raskhodnikova, S., Smith, A., Wagaman, C., & Zavyalov, A. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2602.15802 · Cited by 4
Self-citationOptimal e-variables under constraintsPreprint
Saha, A., & Ramdas, A. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2604.21680 · Cited by 4
“Local differential privacy (Dwork et al., 2006; Kasiviswanathan et al., 2011; Duchi et al., 2013) is defined through a conditional probability distribution Q ( ·| x ), which represents the mechanism that randomizes an input x ∈ X to an output y ∈ Y .”
Simplifying Differential Privacy for Non-Experts: The ENCRYPT Project Approach
Erotokritou, S., Giannoulakis, I., Kafetzakis, E., & Kaltakis, K. (2024) · IEEE International Conference on Cyber Security and Resilience (CSR) · doi:10.1109/csr61664.2024.10679407 · Cited by 3
“DP can be implemented using one of two main approaches - local differential privacy (LDP) and global differential privacy (GDP) [12].”
BackgroundDual Utilization of Perturbation for Stream Data Publication Under Local Differential Privacy
Du, R., Ye, Q., Xiao, Y., Yu, L., Fu, Y., & Hu, H. (2025) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde65448.2025.00263 · Cited by 3
“Local Differential Privacy (LDP) [3], [9], [19], a cryptographic technique extensively deployed in various real-world contexts [5], [14], [27], [34], provides formal privacy guarantees by bounding the information leakage of individual users through a privacy parameter (cid:2) .”
Toward Personalized Privacy-Preserving Content Caching With Edge Cooperation
Gao, Y. M., Tao, J., Wang, H., Sun, W., & Song, C. (2025) · IEEE Transactions on Services Computing · doi:10.1109/tsc.2025.3617116 · Cited by 3
“Definition 3 (Local Differential Privacy [49]): An algorithm R : X → Y satisfies (cid:2) -LDP, where (cid:2) > 0 , if and only if for any pair of input items x, x (cid:13) ∈ X , and for any output y ∈ Y , the following inequality holds: Lemma 1 (Sequential Composition [26]): For a given sequence of…”
Fine-Grained Manipulation Attacks to Local Differential Privacy Protocols for Data Streams
Li, X., Ren, X., Yang, S., Shi, L., Yu, C.-M., & Han, Q. (2026) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2026.3652139 · Cited by 3
“L OCAL Differential Privacy (LDP) [1], [2], [3] enables massive data collection and analytics while ensuring end-users’ privacy without relying on a trusted aggregator.”
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.