The DOI matches its Crossref record; 46 of the 46 references it cites were found in a registry or an index.
Learning in a Large Function Space: Privacy-Preserving Mechanisms for SVM Learning
Open accessAbstract
The ubiquitous need for analyzing privacy-sensitive information—including health records, personal communications, product ratings and social network data—is driving significant interest in privacy-preserving data analysis across several research communities. This paper explores the release of Support Vector Machine (SVM) classifiers while preserving the privacy of training data. The SVM is a popular machine learning method that maps data to a high-dimensional feature space before learning a linear decision boundary. We present efficient mechanisms for finite-dimensional feature mappings and for (potentially infinite-dimensional) mappings with translation-invariant kernels. In the latter case, our mechanism borrows a technique from large-scale learning to learn in a finite-dimensional feature space whose inner-product uniformly approximates the desired feature space inner-product (the desired kernel) with high probability. Differential privacy is established using algorithmic stability, a property used in learning theory to bound generalization error. Utility—when the private classifier is pointwise close to the non-private classifier with high probability—is proven using smoothness of regularized empirical risk minimization with respect to small perturbations to the feature mapping. Finally we conclude with lower bounds on the differential privacy of any mechanism approximating the SVM.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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
LIBSVM: A library for support vector machines
Chang, C.-C., & Lin, C.-J. (2011) · ACM Transactions on Intelligent Systems and Technology · doi:10.1145/1961189.1961199 · Cited by 40,918
Book Review: Pattern Recognition and Machine Learning
Nasrabadi, N. M. (2007) · Journal of Electronic Imaging · doi:10.1117/1.2819119 · Cited by 22,066
A Tutorial on Support Vector Machines for Pattern Recognition
Burges, C. J. C. (1998) · Data Mining and Knowledge Discovery · doi:10.1023/a:1009715923555 · Cited by 16,429
Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond
Schölkopf, B., & Smola, A. J. (2001) · The MIT Press eBooks · doi:10.7551/mitpress/4175.001.0001 · Cited by 11,703
Libsvm : A library for support vector machines
Ferrari, V. (2008) · Medical Entomology and Zoology · Cited by 10,123
Pattern Recognition and Machine Learning
(2006) · doi:10.1007/978-0-387-45528-0 · Cited by 9,824
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
An Introduction to Support Vector Machines
Cristianini, N., & Shawe-Taylor, J. S. (2000) · ePrints Soton (University of Southampton) · Cited by 4,115
Optimizing search engines using clickthrough data
Joachims, T. (2002) · Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/775047.775067 · Cited by 3,873
A Probabilistic Theory of Pattern Recognition
Devroye, L., Györfi, L., & Lugosi, G. (1996) · Stochastic Modelling and Applied Probability · doi:10.1007/978-1-4612-0711-5 · Cited by 3,274
Random Features for Large-Scale Kernel Machines
Rahimi, A., & Recht, B. (2007) · Cited by 2,783
Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond
(2005) · IEEE Transactions on Neural Networks · doi:10.1109/tnn.2005.848998 · Cited by 2,225
Convergence of Stochastic Processes.
Robinson, P. M., & Pollard, D. (1985) · Economica · doi:10.2307/2553898 · Cited by 2,184
Multiclass cancer diagnosis using tumor gene expression signatures
Ramaswamy, S., Tamayo, P., Rifkin, R., Mukherjee, S., Yeang, C.-H., Angelo, M., Ladd, C., Reich, M., Latulippe, E., Mesirov, J. P., et al. (2001) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.211566398 · Cited by 2,023
Weak Convergence and Empirical Processes: With Applications to Statistics
Wellner, J. A. (1996) · Medical Entomology and Zoology · Cited by 1,969
Convergence of Stochastic Processes
Pollard, D. (1984) · Springer Series in Statistics · doi:10.1007/978-1-4612-5254-2 · Cited by 1,841
(2006) · Spectral Interpretation of Decision Diagrams · doi:10.1007/0-387-21734-7_4 · Cited by 1,771
Towards Sharp Inapproximability For Any 2-CSP
Austrin, P. (2007) · 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07) · doi:10.1109/focs.2007.41 · Cited by 1,294
Some results on Tchebycheffian spline functions
Kimeldorf, G., & Wahba, G. (1971) · Journal of Mathematical Analysis and Applications · doi:10.1016/0022-247x(71)90184-3 · Cited by 1,254
Map-Reduce for Machine Learning on Multicore
Chu, C.-T., Kim, S. K., Lin, Y.-A., Yu, Y., Bradski, G., Ng, A. Y., & Olukotun, K. (2007) · Advances in Neural Information Processing Systems 19 · doi:10.7551/mitpress/7503.003.0040 · Cited by 1,229
(2011) · PubMed · Cited by 990
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
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
Training a Support Vector Machine in the Primal
Chapelle, O. (2007) · Neural Computation · doi:10.1162/neco.2007.19.5.1155 · Cited by 780
Efficient noise-tolerant learning from statistical queries
Kearns, M. (1998) · Journal of the ACM · doi:10.1145/293347.293351 · Cited by 665
Differentially private recommender systems: Building privacy into the Netflix Prize contenders
McSherry, F., & Mironov, I. (2009) · Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1557019.1557090 · Cited by 664
Privacy-preserving logistic regression
Chaudhuri, K., & Monteleoni, C. (2008) · Cited by 525
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
Bousquet, O., Elisseeff, A., & Ron, D. (2001) · MPG.PuRe (Max Planck Society) · Cited by 493
Internet traffic classification demystified: myths, caveats, and the best practices
Kim, H., Claffy, K., Fomenkov, M., Barman, D., Faloutsos, M., & Lee, K. (2008) · Proceedings of the 2008 ACM CoNEXT Conference on - CONEXT '08 · doi:10.1145/1544012.1544023 · Cited by 485
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
Mandl, P., & Huskova, M. (1986) · Biometrics · doi:10.2307/2530729 · Cited by 458
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
Optimizing search engines using clickthrough data
Joachims, T. (2002) · Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining - KDD '02 · doi:10.1145/775066.775067 · Cited by 401
On the complexity of differentially private data release: efficient algorithms and hardness results
Dwork, C., Naor, M., Reingold, O., Rothblum, G. N., & Vadhan, S. (2009) · Proceedings of the forty-first annual ACM symposium on Theory of computing · doi:10.1145/1536414.1536467 · Cited by 358
Kasiviswanathan, 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
On the geometry of differential privacy
Hardt, M., & Talwar, K. (2010) · Proceedings of the forty-second ACM symposium on Theory of computing · doi:10.1145/1806689.1806786 · Cited by 314
A learning theory approach to noninteractive database privacy
Blum, A., Ligett, K., & Roth, A. (2013) · Journal of the ACM · doi:10.1145/2450142.2450148 · Cited by 242
Distribution-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
Mechanism Design via Differential Privacy
McSherry, F., & Talwar, K. (2007) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2007.4389483 · Cited by 202
Algorithmic stability and sanity-check bounds for leave-one-out cross-validation
Kearns, M. J., & Ron, D. (1997) · Conference on Learning Theory · doi:10.1145/267460.267491 · Cited by 123
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
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 95
Training a Support Vector Machine in the Primal
Chapelle, O. (2007) · The MIT Press eBooks · doi:10.7551/mitpress/7496.003.0004 · Cited by 57
Practical Privacy: The SuLQ Framework
Blum, A. L., Dwork, C., McSherry, F., & Kobbi Nissim, B. (2005) · doi:10.1184/r1/6608516 · Cited by 56
Almost-everywhere algorithmic stability and generalization errorPreprint
Kutin, S., & Niyogi, P. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1301.0579 · Cited by 21
Cited by
Membership Inference Attacks Against Machine Learning Models
Shokri, R., Stronati, M., Song, C., & Shmatikov, V. (2017) · 2017 IEEE Symposium on Security and Privacy (SP) · doi:10.1109/sp.2017.41 · Cited by 4,754
Privacy-preserving deep learning
Shokri, R., & Shmatikov, V. (2015) · Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/2810103.2813687 · Cited by 2,356
Federated Learning for Healthcare Informatics
Xu, J., Glicksberg, B. S., Su, C., Walker, P., Bian, J., & Wang, F. (2021) · Journal of Healthcare Informatics Research · doi:10.1007/s41666-020-00082-4 · Cited by 1,542
Federated Learning for Healthcare Informatics
Xu, J., Glicksberg, B. S., Su, C., Walker, P., Bian, J., & Wang, F. (2019) · arXiv · doi:10.48550/arxiv.1911.06270 · Cited by 1,538
Wild patterns: Ten years after the rise of adversarial machine learning
Biggio, B., & Roli, F. (2018) · Pattern Recognition · doi:10.1016/j.patcog.2018.07.023 · Cited by 1,409
Metadata
- Authors
- Rubinstein, B. I. P., Bartlett, P. L., Huang, L., & Taft, N.
- Venue
- Journal of Privacy and Confidentiality
- Published
- 2012-07-20
- Volume
- 4
- Issue
- 1
- ISSN
- 2575-8527 (ISSN-L)
- OpenAlex
- W2096633407
- Cited by
- 262
- References
- 46
- FWCI
- 17.41
- Type
- journal article
- Language
- en
- Open access
- diamond
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.