Learning in a Large Function Space: Privacy-Preserving Mechanisms for SVM Learning

Benjamin I. P. Rubinstein; Peter L. Bartlett; Ling Huang; Nina Taft

Source-linked AI summary

Learning in a Large Function Space: Privacy-Preserving Mechanisms for SVM Learning

Benjamin I. P. Rubinstein, Peter L. Bartlett, Ling Huang, Nina Taft

arXiv:0911.5708v1Nov 30, 2009cs.LGcs.CRcs.DB

TL;DR

Private SVM learning must balance utility against differential privacy, including when feature spaces are potentially infinite-dimensional. The paper introduces stability-based mechanisms using finite features or random RKHS approximations, establishes privacy and high-probability similarity to non-private SVMs, and derives privacy lower bounds. These results show both how private SVM responses can be constructed and where simultaneous utility and privacy become impossible.

Problem
The paper asks how to achieve useful differential privacy for SVM learning, including with potentially infinite-dimensional feature mappings.
Method
The paper combines algorithmic stability with finite-feature and random-RKHS mechanisms whose approximated kernels support finite classifier representations.
Results
The mechanisms provide differential privacy and high-probability pointwise similarity to non-private SVM classifiers, while lower bounds establish privacy–utility impossibility results.
Takeaways & Limitations
Random-feature learning extends privacy-preserving SVM responses to large function spaces, while optimal-privacy lower bounds identify limits on simultaneous accuracy and privacy.
Takeaways & Limitations
The paper identifies deriving lower bounds for moderate to large ϵ and extending the mechanisms to other kernel methods as open problems.

Abstract

from arXiv · show

Several recent studies in privacy-preserving learning have considered the trade-off between utility or risk and the level of differential privacy guaranteed by mechanisms for statistical query processing. In this paper we study this trade-off in private Support Vector Machine (SVM) learning. We present two efficient mechanisms, one for the case of finite-dimensional feature mappings and one for potentially infinite-dimensional feature mappings with translation-invariant kernels. For the case of translation-invariant kernels, the proposed mechanism minimizes regularized empirical risk in a random Reproducing Kernel Hilbert Space whose kernel uniformly approximates the desired kernel with high probability. This technique, borrowed from large-scale learning, allows the mechanism to respond with a finite encoding of the classifier, even when the function class is of infinite VC dimension. Differential privacy is established using a proof technique from algorithmic stability. Utility--the mechanism's response function is pointwise epsilon-close to non-private SVM with probability 1-delta--is proven by appealing to the smoothness of regularized empirical risk minimization with respect to small perturbations to the feature mapping. We conclude with a lower bound on the optimal differential privacy of the SVM. This negative result states that for any delta, no mechanism can be simultaneously (epsilon,delta)-useful and beta-differentially private for small epsilon and small beta.

1. Introduction

The paper studies the privacy–utility trade-off in private SVM learning, introducing mechanisms for finite and potentially infinite-dimensional feature spaces. It also develops stability-based privacy analysis and proves a negative result for overly accurate private SVM mechanisms.

The paper addresses private SVM learning, extending privacy–utility analysis beyond simpler statistics and learning algorithms.
Two mechanisms target finite-dimensional feature mappings and translation-invariant kernels with potentially infinite-dimensional feature mappings.
Random-feature regularized ERM enables finite classifier encodings while approximating the target kernel and non-private SVM responses.
The paper bounds the optimal differential privacy of SVM learning from above using private mechanisms and from below using impossibility results.
Any mechanism that is too accurate with respect to the SVM cannot guarantee strong privacy, extending the paper’s privacy–utility impossibility perspective.
Algorithmic stability supplies the proof technique for establishing differential privacy.

2. Background & Definitions

The paper formalizes databases, mechanisms, differential privacy, and usefulness, then frames SVM learning as regularized empirical risk minimization in a kernel-induced feature space.

A database consists of n > 1 labeled examples, and neighboring databases differ in one entry.
A mechanism releases aggregate information while maintaining privacy, with M(D) denoting its response to database D.
Usefulness requires a private mechanism’s released function to remain close to the corresponding non-private mechanism under a specified function norm.
For SVMs, the relevant utility notion uses sup-norm closeness, which is stronger than merely guaranteeing closeness of hinge-loss risk.
SVM learning minimizes regularized empirical risk in an RKHS, with finite or potentially infinite-dimensional feature mappings.
Translation-invariant kernels have the form k(x, y) = g(x − y), supporting the kernel class used later for random-feature mechanisms.

3. Mechanism for Finite Feature Maps

For finite-dimensional feature maps, PrivateSVM-Finite adds Laplace noise to the SVM weight vector. Stability bounds its sensitivity, yielding differential privacy, while tail bounds provide sup-norm usefulness.

PrivateSVM-Finite forms the primal SVM solution and adds Laplace-distributed noise to its F-dimensional weight vector.
Algorithmic stability of regularized ERM is used to bound how the learned classifier changes between neighboring databases.
For neighboring databases, the weight-vector sensitivity satisfies ∥wD − wD′∥1 ≤ 4LCκ√F/n.
β-differential privacy is guaranteed when the Laplace noise parameter satisfies λ ≥ 4LCκ√F/(βn).
Exponential tails of the Laplace noise yield (ϵ, δ)-usefulness for PrivateSVM-Finite under the sup-norm on the data domain.
Privacy and utility compete because stronger privacy requires more noise, while utility requires the perturbation to remain small.

4. Mechanism for Translation-Invariant Kernels

PrivateSVM makes translation-invariant-kernel SVM learning privately encodable by replacing the potentially infinite-dimensional RKHS with a random finite-dimensional approximation, then perturbing its primal solution. Uniform kernel approximation and stability support privacy and pointwise utility guarantees.

Mechanism: The mechanism approximates the infinite-dimensional RKHS with a random finite-dimensional RKHS, avoiding disclosure of data-dependent basis vectors in the dual representation.The random feature map is built from Fourier-domain samples of the kernel.
Mechanism: PrivateSVM samples Fourier frequencies, solves regularized ERM using the induced approximate kernel, adds Laplace noise to the primal weight vector, and returns the noisy weights with the sampled frequencies.The response is finite and includes the data-independent feature-map parametrization.
Mechanism: Uniform approximation of the target kernel improves with feature dimension ˆd, while primal optimization in the random feature space provides a finite classifier representation.This repurposes a large-scale-learning technique for privacy rather than primarily for reducing dependence on n.
Privacy: Algorithmic stability of regularized ERM controls the data-dependent weight vector's sensitivity, enabling differential privacy through Laplace perturbation.The privacy analysis treats the sampled frequencies as public because they are independent of the database.
Implications: PrivateSVM supports privacy for regularized ERM over a function class of infinite VC dimension without returning the support-vector data needed by the obvious dual parametrization.Its computational overhead includes O(ˆd n^2) for kernel-matrix construction, on top of random-space SVM optimization.
Utility: The mechanism is useful in the sup-norm: kernel approximation and ERM smoothness make the intermediate classifier pointwise close to the non-private SVM, while noise contributes additional deviation.The result assumes bounded dual-variable L1 norm and applies on a compact set containing the data.

5. Hinge-Loss and an Upper Bound on Optimal Differential Privacy

For hinge-loss SVMs with translation-invariant kernels, the paper specializes its privacy and utility results and studies the resulting optimal differential privacy. Combining the noise needed for privacy with the feature dimension needed for utility yields an upper bound, while a lower-bound theorem gives an impossibility result.

Hinge-loss specialization: Hinge loss is inserted into the preceding privacy and utility theorems to obtain specialized guarantees for translation-invariant-kernel SVMs.The hinge-loss dual has box constraints 0 ≤ α_i ≤ C/n.
Privacy bound: For any β > 0, PrivateSVM guarantees β-differential privacy when its noise parameter satisfies λ ≥ 22.5C/(βn).The guarantee applies for any feature dimension ˆd and translation-invariant kernel.
Utility bound: The mechanism is (ϵ, δ)-useful with respect to hinge-loss SVM in the sup-norm on any compact set containing the database.The result uses hinge loss's convexity and 1-Lipschitz property.
Utility bound: For small ϵ, achieving (ϵ, δ)-usefulness requires ˆd = O(ϵ^4 2^-12 C^-4 log(1/δ)) under the stated parameterization.The feature dimension requirement is obtained by combining the kernel-approximation utility condition with the privacy analysis.
Optimal privacy: Combining competing noise requirements upper-bounds the optimal differential privacy of hinge-loss SVM, while Theorem 16 supplies a corresponding lower-bound impossibility result.The paper frames the lower bound as ruling out simultaneous high utility and privacy for sufficiently small parameters.

6. Lower Bounding Optimal Differential Privacy

The section derives lower bounds on optimal differential privacy by constructing neighboring databases whose non-private SVM classifiers are well separated. These separations imply that mechanisms retaining sufficient utility cannot provide strong differential privacy under stated conditions.

Linear-kernel lower bound: The proof begins by constructing neighboring databases whose SVM classifiers differ substantially in sup-norm.This establishes a negative sensitivity result used to lower bound privacy.
Linear-kernel lower bound: For hinge-loss SVMs with a linear kernel, the constructed pair of neighboring databases yields a classifier separation exceeding 2ϵ.The databases differ in one example while producing sufficiently different SVM functions.
Linear-kernel lower bound: The resulting theorem lower bounds optimal differential privacy for hinge-loss SVMs with a linear kernel, ruling out simultaneous (ϵ,δ)-usefulness and small β under its parameter conditions.The theorem applies for C > 0, n > 1, and the stated ε and δ ranges.
RBF-kernel lower bound: A stronger construction uses pairwise-neighboring databases and an RBF kernel to form a 2ϵ-packing of SVM outputs.The construction places positive examples at different points on a circle while keeping the remaining examples fixed.
RBF-kernel lower bound: Under the theorem's stated conditions, no mechanism that is (ϵ,δ)-useful for hinge-loss SVMs with any RBF-kernel parameter σ achieves differential privacy at any level.The lower bound depends on the RBF kernel's variance parameter and includes the condition n > C.

7. Conclusion & Open Problems

The paper presents two private SVM mechanisms and combines privacy, utility, and lower-bound results to characterize limits on private hinge-loss SVM learning. It identifies broader extensions and lower bounds for moderate to large ϵ as open problems.

Conclusion: The paper presents mechanisms for finite-dimensional and potentially infinite-dimensional feature mappings, establishing privacy through algorithmic stability of regularized ERM.For infinite-dimensional mappings, random RKHS features provide a finite classifier representation.
Conclusion: The random-RKHS mechanism combines kernel approximation with a smoothness result to establish high-probability, pointwise similarity to the non-private SVM classifier.This supports utility while retaining a finite response representation.
Conclusion: The privacy and utility bounds upper bound optimal differential privacy, while the RBF-kernel lower bound shows that sufficiently accurate mechanisms may have no nontrivial privacy guarantee.The lower bounds explicitly depend on the variance of the RBF kernel.
Open problems: Deriving lower bounds for moderate to large ϵ and extending the mechanisms to other kernel methods remain open problems.The paper also notes a broader connection between algorithmic stability and global sensitivity as a direction for practical mechanisms.

Appendix A. Proofs for Subdifferentiable Loss Functions

The appendix extends the paper's utility and sensitivity arguments from differentiable losses to subdifferentiable convex losses. The proofs use subdifferentials while preserving the corresponding stability and proximity conclusions.

Generalization to subdifferentiable losses: The appendix re-proves the relevant lemma for subdifferentiable losses because the main-text proof used differentiability.General convex losses are included as a special case.
Sensitivity: Lemma 21 generalizes the SVM primal weight-vector sensitivity result to convex, L-Lipschitz losses that may be nondifferentiable.For neighboring databases, it gives the stated L1 sensitivity bound under a bounded finite-dimensional feature map.
Sensitivity: The proof replaces gradients with subdifferentials and uses convexity, KKT conditions, the reproducing property, and Cauchy-Schwarz bounds.These steps control differences between minimizers on neighboring databases.
Utility: Lemma 22 extends the utility comparison between regularized empirical risk minimizers in the target and random RKHSs to convex L-Lipschitz losses.The argument first compares regularized risks and then derives uniform proximity of the functions.
Utility: The remaining utility proof is unchanged because it does not depend on differentiability of the loss.The appendix explicitly identifies this as the reason the generalization goes through.