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.
What Can We Learn Privately?
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]).”
InfluentialMechanism Design via Differential Privacy
McSherry, F., & Talwar, K. (2007) · 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07) · doi:10.1109/focs.2007.66 · Cited by 1,371 · 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.”
Probability Inequalities for Sums of Bounded Random Variables
Hoeffding, W. (1963) · Journal of the American Statistical Association · doi:10.2307/2282952 · Cited by 1,166
Blumer, A., Ehrenfeucht, A., Haussler, D., & Warmuth, M. K. (1987) · Information Processing Letters · doi:10.1016/0020-0190(87)90114-1 · Cited by 1,054 · cited 1×
“This latter version states that any algorithm which “compresses” the data set, in the sense that it finds a consistent hypothesis which has a short description relative to the number of samples seen so far, is a good learner (see [15] and [42, p.”
On the design and quantification of privacy preserving data mining algorithms
Agrawal, D., & Aggarwal, C. C. (2001) · Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems · doi:10.1145/375551.375602 · Cited by 1,006 · cited 2×
“The difficulty of constructing private learners lies in finding a good hypothesis in what is typically an exponentially large space.”
Revealing information while preserving privacy
Dinur, I., & Nissim, K. (2003) · Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems · doi:10.1145/773153.773173 · Cited by 980 · 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.”
Self-citationSmooth sensitivity and sampling in private data analysis
Nissim, K., Raskhodnikova, S., & Smith, A. (2007) · Proceedings of the thirty-ninth annual ACM symposium on Theory of computing · doi:10.1145/1250790.1250803 · Cited by 974 · 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.”
Self-citationDecision theoretic generalizations of the PAC model for neural net and other learning applications
Haussler, D. (1992) · Information and Computation · doi:10.1016/0890-5401(92)90010-d · Cited by 843
Limiting privacy breaches in privacy preserving data mining
Evfimievski, A., Gehrke, J., & Srikant, R. (2003) · Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems · doi:10.1145/773153.773174 · Cited by 815 · cited 2×
“The difficulty of constructing private learners lies in finding a good hypothesis in what is typically an exponentially large space.”
Practical privacy: the SuLQ framework
Blum, A., Dwork, C., McSherry, F., & Nissim, K. (2005) · Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems · doi:10.1145/1065167.1065184 · Cited by 797 · cited 5×
“the power of nonadaptive SQ learners is an important problem. For example, the SQ algorithm for learning conjunctions [42] is nonadaptive, but SQ formulations of the perceptron and k-means algorithms [11] seem to rely heavily on adaptivity. Understanding the “price” of privacy for learning problems. The SQ result of B…”
InfluentialSelf-citationEfficient noise-tolerant learning from statistical queries
Kearns, M. (1998) · Journal of the ACM · doi:10.1145/293347.293351 · Cited by 665 · cited 4×
“We examine two basic notions from learning: Valiant's probabilistically approximately correct (PAC) learning [39] model and Kearns' statistical query (SQ) model [29].”
InfluentialDifferential privacy and robust statistics
Dwork, C., & Lei, J. (2009) · Proceedings of the forty-first annual ACM symposium on Theory of computing · doi:10.1145/1536414.1536466 · Cited by 611
Noise-tolerant learning, the parity problem, and the statistical query model
Blum, A., Kalai, A., & Wasserman, H. (2003) · Journal of the ACM · doi:10.1145/792538.792543 · Cited by 598
Fast probabilistic algorithms for hamiltonian circuits and matchings
Angluin, D., & Valiant, L. G. (1979) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(79)90045-x · Cited by 570
A learning theory approach to non-interactive database privacy
Blum, A., Ligett, K., & Roth, A. (2008) · Proceedings of the fortieth annual ACM symposium on Theory of computing · doi:10.1145/1374376.1374464 · Cited by 505 · cited 4×
“as mining frequent itemsets [29], k-means clustering [11, 47], learning decision trees [11], and learning mixtures of Gaussians [47]. As mentioned above, a subsequent result of Blum, Ligett and Roth [14] on approximating classes of low-VC-dimension functions was inspired by our generic agnostic learner. We discuss the…”
InfluentialSecure Human Identification Protocols
Hopper, N. J., & Blum, M. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-45682-1_4 · Cited by 499 · 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]).”
Privacy, accuracy, and consistency too: a holistic solution to contingency table release
Barak, B., Chaudhuri, K., Dwork, C., Kale, S., McSherry, F., & Talwar, K. (2007) · Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems · doi:10.1145/1265530.1265569 · Cited by 468
Algorithmic Stability and Sanity-Check Bounds for Leave-One-Out Cross-Validation
Kearns, M., & Ron, D. (1999) · Neural Computation · doi:10.1162/089976699300016304 · Cited by 407
A Statistical Framework for Differential Privacy
Wasserman, L., & Zhou, S. (2010) · Journal of the American Statistical Association · doi:10.1198/jasa.2009.tm08651 · Cited by 397
Privacy-Preserving Datamining on Vertically Partitioned Databases
Dwork, C., & Nissim, K. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-28628-8_32 · Cited by 348 · cited 2×
“…exists an algorithm A that takes inputs , α, β, z, where n, the number of labeled examples in z, is polynomial in 1//, d, 1/α, log(1/β), and satisfies a. [Privacy] For all > 0, algorithm A(, ·, ·, ·) is differentially private (Definition 2.1); b. [Utility] A PAC learns C using H (Definition 2.3).”
InfluentialSelf-citationKasiviswanathan, S. P., Lee, H. K., Nissim, K., Raskhodnikova, S., & Smith, A. (2008) · 2008 49th Annual IEEE Symposium on Foundations of Computer Science · doi:10.1109/focs.2008.27 · Cited by 334
Self-citationMore on average case vs approximation complexity
Alekhnovich, M. (2004) · 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. · doi:10.1109/sfcs.2003.1238204 · Cited by 247
Weakly learning DNF and characterizing statistical query learning using Fourier analysis
Blum, A., Furst, M., Jackson, J., Kearns, M., Mansour, Y., & Rudich, S. (1994) · Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 · doi:10.1145/195058.195147 · Cited by 244 · cited 5×
“It is impossible to obtain an analogous separation for weak learning, since the characterization of SQ learnable classes in terms of “SQ dimension” by Blumet al.[ 10 ] implies that adaptive and nonadaptive SQ algorithms are equivalent for weak learning (this is not explicit in [10] but follows from the fact that the w…”
InfluentialDistribution-free performance bounds for potential function rules
Devroye, L., & Wagner, T. (1979) · IEEE Transactions on Information Theory · doi:10.1109/tit.1979.1056087 · Cited by 226
A Sober Look at Clustering Stability
Ben-David, S., von Luxburg, U., & Pál, D. (2006) · Lecture Notes in Computer Science · doi:10.1007/11776420_4 · Cited by 216
The price of privacy and the limits of LP decoding
Dwork, C., McSherry, F., & Talwar, K. (2007) · Proceedings of the thirty-ninth annual ACM symposium on Theory of computing · doi:10.1145/1250790.1250804 · Cited by 205 · 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.”
A Framework for High-Accuracy Privacy-Preserving Mining
Agrawal, S., & Haritsa, J. R. (2005) · 21st International Conference on Data Engineering (ICDE'05) · doi:10.1109/icde.2005.8 · Cited by 177 · cited 1×
“The difficulty of constructing private learners lies in finding a good hypothesis in what is typically an exponentially large space.”
Toward Efficient Agnostic Learning
Kearns, M. J., Schapire, R. E., & Sellie, L. M. (1994) · Machine Learning · doi:10.1007/bf00993468 · Cited by 172
Bounds on the Sample Complexity for Private Learning and Private Data Release
Beimel, A., Kasiviswanathan, S. P., & Kobbi Nissim, B. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-11799-2_26 · Cited by 119
Self-citationRandomized Response, Statistical Disclosure Control and Misclassificatio: a Review
van den Hout, A., & van der Heijden, P. G. M. (2002) · International Statistical Review · doi:10.1111/j.1751-5823.2002.tb00363.x · Cited by 109 · cited 1×
“This equivalence relates notions that were conceived in very different con- texts.”
New Efficient Attacks on Statistical Disclosure Control Mechanisms
Dwork, C., & Yekhanin, S. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-85174-5_26 · Cited by 100
Generalization bounds for averaged classifiers
Freund, Y., Mansour, Y., & Schapire, R. E. (2004) · The Annals of Statistics · doi:10.1214/009053604000000058 · Cited by 84 · cited 2×
“Finally, in a different vein, Freund, Mansour and Schapire [31] used a weighted averaging technique with the same weights as the sampler in our generic learner to reduce generalization error (see Section 3.”
Helmbold, D. P., Sloan, R. H., & Warmuth, M. K. (1992) · SIAM Journal on Computing · doi:10.1137/0221019 · Cited by 80 · cited 1×
“The standard (non-private) PAC learner for PARITY [33, 30] looks for the hidden vector r by solving a system of linear equations imposed by examples (xi, cr(xi)) that the algorithm”
Efficient, Differentially Private Point EstimatorsPreprint
Smith, A. (2008) · arXiv (Cornell University) · doi:10.48550/arxiv.0809.4794 · Cited by 79
Self-citationPrivacy via pseudorandom sketches
Mishra, N., & Sandler, M. (2006) · ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS) · doi:10.1145/1142351.1142373 · Cited by 75 · cited 1×
“This equivalence relates notions that were conceived in very different con- texts.”
Differential privacy with compression
Zhou, S., Ligett, K., & Wasserman, L. (2009) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2009.5205863 · Cited by 60 · cited 1×
“also been several results connecting differential privacy to more “statistical” notions of utility, such as consistency of point estimation and density estimation [50, 23, 54, 56].”
Statistical Methods in e‐Commerce Research
Jank, W., & Shmueli, G. (2008) · Wiley eBooks · doi:10.1002/9780470315262 · Cited by 48
Cryptographic Randomized Response Techniques
Ambainis, A., Jakobsson, M., & Lipmaa, H. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-24632-9_31 · Cited by 46 · cited 1×
“The difficulty of constructing private learners lies in finding a good hypothesis in what is typically an exponentially large space.”
On Learning Ring-Sum-Expansions
Fischer, P., & Simon, H. U. (1992) · SIAM Journal on Computing · doi:10.1137/0221014 · Cited by 42 · cited 1×
“The standard (non-private) PAC learner for PARITY [33, 30] looks for the hidden vector r by solving a system of linear equations imposed by examples (xi, cr(xi)) that the algorithm”
New lower bounds for statistical query learning
Yang, K. (2004) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2004.10.003 · Cited by 39
Toward Efficient Agnostic Learning
Kearns, M. J., Schapire, R. E., & Sellie, L. M. (1994) · Machine Learning · doi:10.1023/a:1022615600103 · Cited by 23 · cited 1×
“Agnostic learning [23, 31 ] is an extension of PAC learning that removes assumptions about the target concept.”
Differential Privacy with CompressionPreprint
Zhou, S., Ligett, K., & Wasserman, L. (2009) · arXiv (Cornell University) · doi:10.48550/arxiv.0901.1365 · Cited by 9 · cited 1×
“also been several results connecting differential privacy to more “statistical” notions of utility, such as consistency of point estimation and density estimation [50, 23, 54, 56].”
A statistical framework for differential privacyPreprint
Wasserman, L., & Zhou, S. (2008) · arXiv (Cornell University) · doi:10.48550/arxiv.0811.2501 · Cited by 6
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
Advances and Open Problems in Federated Learning
Kairouz, P., & McMahan, H. B. (2021) · Foundations and Trends in Machine Learning · doi:10.1561/2200000083 · Cited by 7,772
“2, achieving LDP while maintaining utility can be difficult [229, 388].”
BackgroundMethodDeep Learning with Differential Privacy
Abadi, M., Chu, A., Goodfellow, I., McMahan, H. B., Mironov, I., Talwar, K., & Zhang, L. (2016) · Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/2976749.2978318 · Cited by 6,578
Communication-Efficient Learning of Deep Networks from Decentralized Data
McMahan, H. B., Moore, E., Ramage, D., Hampson, S., & Arcas, B. A. Y. (2016) · arXiv · doi:10.48550/arxiv.1602.05629 · Cited by 14,215
“A stronger guarantee can be achieved by enforcing local differential privacy (Kasiviswanathan et al., 2008; Duchi et al., 2014), where rather than adding noise to the final model, we noise the individual updates, which precludes the central server from making any definitive inference about a client.”
BackgroundThe Algorithmic Foundations of Differential Privacy
Dwork, C., & Roth, A. (2013) · doi:10.1561/9781601988195 · Cited by 3,856
Deep Models Under the GAN: Information Leakage from Collaborative Deep Learning
Hitaj, B., Ateniese, G., & Perez-Cruz, F. (2017) · Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/3133956.3134012 · Cited by 1,377
“Differential privacy plays an important role in deep learning as shown in [1, 38, 75, 77].”
Background
Metadata
- Authors
- Kasiviswanathan, S. P., Lee, H. K., Nissim, K., Raskhodnikova, S., & Smith, A.
- Venue
- SIAM Journal on Computing
- Published
- 2011-01
- Volume
- 40
- Issue
- 3
- Pages
- 793-826
- ISSN
- 0097-5397 (ISSN-L)
- 1095-7111
- OpenAlex
- W2245160765
- Cited by
- 898
- References
- 20
- Citations by year
- 2026: 55 · 2025: 93 · 2024: 130 · 2023: 102 · 2022: 102 · 2021: 107 · 2020: 107 · 2019: 63 · 2018: 27 · 2017: 24 · 2016: 33 · 2015: 20 · 2014: 18 · 2013: 11 · 2012: 2
- FWCI
- 9.70
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- SIAM Journal on Computing (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Privacy-Preserving Technologies in Data
- Physical Sciences › Computer Science › Computer Networks and Communications › Cryptography and Data Security
- Physical Sciences › Computer Science › Artificial Intelligence › Machine Learning and Algorithms
- Keywords
- private learning, differential privacy, agnostic learning, sample complexity, parity function, statistical query model
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.