Privacy Aware Learning

John C. Duchi; Michael I. Jordan; Martin J. Wainwright

Source-linked AI summary

Privacy Aware Learning

John C. Duchi, Michael I. Jordan, Martin J. Wainwright

arXiv:1210.2085v2Oct 7, 2012stat.MLcs.ITcs.LG

TL;DR

The paper asks how much statistical learning utility is lost when data remains confidential even from the learner. It analyzes local privacy through statistical decision theory and information-theoretic techniques, deriving sharp upper and lower convergence-rate bounds. The results quantify privacy–utility tradeoffs, including effective sample-size reductions, while leaving questions about interactive protocols and individually guaranteed privacy open.

Problem
The paper addresses the difficulty of precisely quantifying the tradeoff between privacy and useful outputs in statistical learning when each provider must protect an individual datum.
Method
The paper uses statistical decision theory and classical information-theoretic minimax techniques to analyze mutual-information, interactive differential-privacy, and non-interactive local differential-privacy settings.
Results
The paper establishes sharp lower and upper convergence-rate bounds, with stochastic gradient descent achieving the upper bounds up to universal constant factors.
Takeaways & Limitations
Privacy and estimation utility form an explicit controllable tradeoff, with private observations reducing effective sample size to roughly nI∗/d or nα2/d in the two main settings.
Takeaways & Limitations
Whether interactivity can sharpen the general convex-case results remains open, and individually guaranteed privacy raises questions the authors leave for future work.

Abstract

from arXiv · show

We study statistical risk minimization problems under a privacy model in which the data is kept confidential even from the learner. In this local privacy framework, we establish sharp upper and lower bounds on the convergence rates of statistical estimation procedures. As a consequence, we exhibit a precise tradeoff between the amount of privacy the data preserves and the utility, as measured by convergence rate, of any statistical estimator or learning procedure.

1 Introduction

The paper studies learning when each datum is privately disguised from the learner, using statistical decision theory to quantify privacy–utility tradeoffs. It develops sharp lower and upper convergence-rate bounds for information-based and differential privacy, including effective sample-size reductions.

Decision-theoretic framework: The analysis formulates learning as statistical risk minimization over a convex loss, enabling bounds that apply across procedures rather than to one algorithm.The framework uses a parameter domain, loss function, and population risk under an unknown data distribution.
Privacy setting: Local privacy keeps each individual datum confidential from the learner by giving the method only a disguised view of that datum.The paper distinguishes this setting from privacy guarantees applied only to the released estimator or dataset.
Privacy measures: The paper studies three local privacy measures: worst-case mutual information, interactive differential privacy, and non-interactive local differential privacy.These measures constrain the private view communicated by each data provider.
Bounds: The authors derive minimax lower bounds and explicit upper bounds for excess risk under mutual-information and differential-privacy constraints.The upper bounds are achieved by explicit estimators, while the lower bounds apply to any estimator in the specified loss-function families.
Bounds: Stochastic gradient descent achieves the stated upper bounds up to universal constants, establishing a sharp tradeoff between privacy and estimation utility.The paper characterizes utility through convergence rate and excess risk rather than disclosure risk alone.
Implications: Under maximally privatized observations, effective sample size decreases from n to roughly nI∗/d for information-based privacy and nα2/d for differential privacy.The paper presents these reductions as concrete interpretations of its convergence-rate bounds.

2 Problem Formulation

The paper formulates locally private statistical learning as minimax risk minimization through perturbed subgradient communications. It defines privacy by limiting information about each sample while characterizing the resulting expected excess-risk error.

2.1 Communication protocol: The communication protocol sends a parameter to each data owner, who privately returns a perturbed subgradient vector.The owner computes a subgradient and communicates a masked vector constrained by the privacy mechanism.
2.1 Communication protocol: The protocol assumes bounded subgradients in a compact set C and disguises them with outputs in a larger compact set D.A norm-ball example uses radius L for C and radius M > L for D.
2.2 Optimal local privacy: The conditional channel Q maps each sample or subgradient to a communicated variable Z, with its marginal distribution obtained by averaging over P.Mutual information I(P,Q) is defined as the expected KL divergence between Q(· | X) and Q(·).
2.2 Optimal local privacy: Privacy is measured worst-case over data distributions by requiring supP I(P,Q) ≤ I*, so the released variable reveals at most I* about a sample.The paper frames privacy as a game between an adversary selecting P and data owners selecting Q.
2.2 Optimal local privacy: Optimal local privacy selects a channel Q* that minimizes worst-case mutual information over admissible communicating distributions.The admissible sets constrain source gradients to C and communicated variables to D while preserving the required conditional mean.
2.2 Optimal local privacy: Optimal local differential privacy additionally requires Q* to attain the prescribed differential-privacy level and minimize worst-case mutual information among such channels.This defines the privacy mechanism through both an α⋆(C,D)-differential-privacy constraint and a mutual-information comparison.
2.3 Minimax error: The minimax framework evaluates any method M by the expected excess risk of its estimate after receiving n perturbed stochastic gradients.Randomness comes from both sampling under P and perturbation through the channel Q.
2.3 Minimax error: For several loss-function classes, the paper characterizes minimax error and gives sharp results when Q provides optimal local privacy.The expectation is taken over samples X drawn from P and communicated variables Z drawn conditionally through Q.

3 Optimal Learning Rates and Tradeoffs

The paper establishes sharp minimax convergence-rate bounds under information-based and differential privacy, with matching upper bounds in several settings. These results quantify privacy–utility tradeoffs through dimension-dependent effective sample-size reductions.

Mirror descent and stochastic gradient methods attain the optimal convergence rates up to constant factors in the analyzed settings.For the linear and general convex cases described, the resulting bounds are sharp; in one setting the lower bound loses a factor of √log d.
The lower bounds can apply to disguising the individual data directly, because for linear losses the gradient equals the datum.With ℓ(x, θ)=⟨x, θ⟩, one has ∇ℓ(x, θ)=x, so the communication scheme masks exactly Xi.
The stated results depend on specific geometric properties of the loss functions, although the techniques can support alternative results after computing appropriate optimal privacy distributions.The paper presents this dependence as a scope limitation of the stated theorems.
For α-differential privacy, the dimension-dependent penalty changes the effective sample size by α^2/d rather than only logarithmically in d.The paper describes this linear dependence on dimension as unavoidable under the conditions of the relevant theorems.
Information-based privacy reduces effective sample size from n to approximately nI∗/d, while α-differential privacy reduces it to approximately nα^2/d.The paper notes that the correspondence I∗≈α^2 is informal rather than an explicit general mapping.

4 Optimal privacy-preserving distributions

The paper characterizes privacy-optimal channels through saddle-point and maximum-entropy distributions under geometric constraints on C and D. It gives explicit constructions for ℓ1, ℓ∞, and locally differentially private settings.

General saddle-point characterization: Maximum-entropy conditional distributions characterize optimal local privacy for compact convex polytopes with rotationally invariant extreme points.Theorem 6 states that the optimal channel is unique up to measure-zero sets and uses outputs supported on scaled extreme points.
General saddle-point characterization: A two-phase Markov chain X → X′ → Z extends the optimal construction from extreme points to arbitrary X while preserving the minimax information bound.X′ is sampled so that E[X′ | X] = X, then the optimal channel is applied on the extreme points.
Specific saddle-point computations: For ℓ1-balls, the optimal channel is supported on the signed scaled basis vectors, with arbitrary interior inputs reduced to extreme points before sampling.Scaling extends the result from unit-radius inputs to ℓ1-balls of radii L and M.
Specific saddle-point computations: For ℓ∞-balls, independent coordinatewise outputs at the boundary satisfy optimal local privacy under the unbiasedness constraint E[Z | X] = X.The coordinates of Z take values in {−M, M} and are chosen independently according to X.
Differentially private communication: Under optimal local differential privacy for ℓ∞-balls, outputs lie in {−M, M}^d and receive one of two masses, q+ or q−, determined by the input-output relation.All optimal channels are characterized as convex combinations of the distributions described by Proposition 3.

5 Proofs of Statistical Rates

The proofs convert estimation into hypothesis testing over well-separated risks, then use information-theoretic testing lower bounds and privacy-induced information bounds. This yields minimax convergence-rate lower bounds and matching private procedures.

Reduction to hypothesis testing: Well-separated risk families reduce statistical estimation to testing the underlying index from privatized observations.If an estimator approximately minimizes the risk indexed by v, separation prevents it from simultaneously minimizing another risk indexed by w.
Information-theoretic lower bounds: Fano’s inequality handles multiway testing, while Le Cam’s method handles binary testing, linking estimation error to mutual information or total variation.The choice depends on whether the index set has more than two elements or exactly two elements.
Proof blueprint: The lower-bound proofs construct separated losses, bound the information available through private communication, and apply the testing inequalities to obtain estimation-rate bounds.For locally private schemes, the information bound is derived from the privacy definition or from bounds for non-interactive locally differentially private mechanisms.
Constructing well-separated losses: For ℓ1-based constructions, loss separation is established through bounded Lipschitz losses and explicit discrepancy calculations between risk functions.The resulting families support the testing reductions used in the minimax lower bounds.
Upper bounds: The paper also supplies upper-bound analyses using optimal private distributions, mirror descent, and stochastic gradient descent.These procedures connect privacy parameters to effective gradient noise and achieve the stated private convergence bounds.
Upper bounds: Under optimal local privacy, the allowed mutual information and effective gradient-noise level are in bijection, enabling privacy-rate tradeoff calculations.The analysis states M∞ ≍ L√(d/I∗) up to the notation shown in the supplied passages.

6 Discussion

The paper develops sharp privacy–estimation tradeoffs for statistical risk minimization and identifies several directions for extending the framework. These include broader data access patterns, alternative channel constraints, selective privacy goals, and guarantees for individual data providers.

Sharp tradeoffs between privacy protection and estimation rates provide a measure of utility for statistical problems.
The analysis studies procedures that access each datum once through a perturbed view of a subgradient.The paper asks whether transformed data could instead be sufficient for inference in restricted loss-function classes.
Dataset-wide transformations can have good statistical properties for linear regression and PCA but require the entire dataset to compute.Current nonparametric data-release approaches likewise require aggregation by a trusted curator before release.
The privacy-inducing channel is constrained to have compact support, although moment conditions might permit faster estimation rates.The paper calls for better understanding of privacy-preserving channels under alternative constraints.
Selective privacy could protect a function φ(X) rather than all of X, allowing less-sensitive attributes such as gender to remain known.The paper contrasts such attributes with more personal features of the data.
Guaranteeing privacy for each provider of a single datum raises questions that the paper describes as lacking easy answers.

A Unbiasedness

This appendix examines how biased subgradients can undermine optimization and develops information-theoretic machinery for analyzing the resulting observations. The proof strategy reduces joint information to single-sample quantities and uses entropy calculations under coordinate-wise sampling.

Arbitrarily wrong optimization can result when an oracle returns biased subgradients.A one-dimensional construction makes the biased and true minimizers occur at opposite endpoints, producing the worst possible error.
A parameter-independent bias communicates only bounded mutual information about the risk parameters.Fano’s inequality then bounds every procedure’s estimation accuracy away from zero.
The appendix tensorizes mutual information so that the analysis requires computing only the information in a single observation.The observations are constructed from subgradient evaluations on independent samples.
Conditional independence and entropy conditioning yield a representation used to calculate the information bounds.The point θ_i is determined by preceding observations, while Z_i is conditionally independent of them given the relevant variables.
The proof completes the information bounds through Bernoulli entropy inequalities, convexity, and concavity of logarithms.
Coordinate-wise sampling and bounded subgradient magnitude reduce the single-sample calculation to coordinate-level entropy terms.The analysis introduces M = M∞/L and uses independent coordinates of Z.

B.3 Proof of Lemma 7

The proof of Lemma 7 bounds mutual information by comparing entropy inside and outside the interior parameter region. The minimum conditional entropy occurs in the interior, enabling the stated upper bound.

Within the interior, the proof computes the marginal distribution Q(z | v) using the conditional distributions defining the sampling scheme.
For hinge-loss SVM risk, the subgradient depends on whether each coordinate θ_i is inside or beyond the interval boundary.When X = e_i, the loss is L[r − θ_i]+, and the corresponding subgradient is L e_i or 0 depending on θ_i ≤ r.
The conditional entropy H(Z | θ, V) is lower when θ lies in int[−r, r]^d than when θ lies outside it.
For an upper bound on mutual information, the proof may therefore assume θ ∈ int[−r, r]^d.
The entropy calculation, combined with the earlier information representation, establishes the claimed mutual-information bound.

B.4 Proof of Lemma 8

The proof of Lemma 8 analyzes a locally private binary-coordinate mechanism through conditional entropy and marginal distributions. Symmetry and product structure reduce the calculation to one distinguished coordinate and yield the information bound.

Conditional on V, the randomized observation Z has independent coordinates, with probabilities determined by whether a coordinate aligns with V.
The mechanism parameters q+ and q− satisfy a normalization equation with q− = e^−αq+.
Marginally, Z is uniform on {−M, M}^d, while conditioning on V changes only the coordinate associated with the nonzero component of V.
The conditional entropy calculation leads to I(Z; V) ≤ d log 2 − 1.
The achievability mechanisms perturb subgradients while preserving conditional unbiasedness under α-local differential privacy.For a gradient or subgradient g, the construction produces Z with E[Z | g] = g.

C.1 Achievability in Theorem 4

The achievability construction samples a privatized sign vector and then selects an output according to a randomized half-space rule. The resulting scheme is α-differentially private and supports the stated mirror-descent bound.

Sampling strategy: The scheme samples each coordinate of eg independently from {−L, L} using probabilities determined by gj, then applies a Bernoulli-controlled half-space selection.The Bernoulli parameter is πα = eα/(eα + 1), and the output z is drawn from {−B, B}d according to the sign of ⟨z, eg⟩.
Privacy: The sampling scheme (49) is α-differentially private.
Optimization guarantee: Applying mirror descent to gradients generated by (49) yields bound (14a) with M∞ = B = O(1)(L/α).

C.2 Achievability in Theorem 5

The second achievability construction uses a norm-constrained randomized direction and a spherical half-space sampler. It produces an unbiased privatized gradient with controlled ℓ2 norm, enabling the stated stochastic-gradient bound.

Sampling strategy: For gradients with ∥g∥2 ≤ L, eg is set to either Lg/∥g∥2 or its negative with probabilities determined by ∥g∥2.
Sampling strategy: The output is sampled uniformly from the radius-B sphere within one of two half-spaces selected by the Bernoulli variable T.The two regions are defined by ⟨z, eg⟩ > 0 and ⟨z, eg⟩ ≤ 0, with ∥z∥2 = B.
Estimator properties: The scheme satisfies E[Z | g] = g and ∥Z∥2 ≤ B = O(1)(L/α).
Optimization guarantee: Applying stochastic gradient descent yields bound (14b) with M2 = B for Θ ⊂ B2(r2).
Conclusion: The resulting bound completes the achievability proof for Theorem 5.

D Background on Conditional Probabilities

This background develops measurable conditional distributions and shows how replacing outputs by extreme-point mixtures can reduce mutual information without worsening differential privacy. It also introduces maximum-entropy conditional distributions used later.

Data processing: The data-processing inequality gives I(X;Y) ≤ I(X;Z) for a Markov chain X → Z → Y.
Role in the proofs: These lemmas reduce entropy and mutual-information calculations to finite-dimensional convex programs over extreme points.
Extreme-point representations: A compact convex set admits a measurable probability measure on its extreme points whose expectation equals any point in the set.
Extreme-point representations: The resulting Markov kernel is supported on Ext(D) and satisfies ∫ yν(x,dy) = x.
Mutual-information reduction: If a conditional distribution assigns positive probability to non-extreme points on a positive-probability input set, an extreme-point-supported replacement strictly lowers mutual information.
Privacy preservation: In the private setting, the extreme-point replacement has no worse differential privacy than the original conditional distribution.
Maximum entropy: The maximum-entropy conditional mass function under a mean constraint has an exponential form determined by a vector satisfying that constraint.

E.1 Proof of Theorem 6

The proof of Theorem 6 reduces the optimization over conditional distributions to extreme-point-supported finite-dimensional programs. It then verifies a maximum-entropy distribution through entropy bounds, symmetry, and KKT conditions.

Convex reduction: The proof restricts candidate conditional distributions to the extreme points of D and formulates mutual-information minimization as a finite-dimensional convex program.
Information bound: The proof upper-bounds I(P,Q*) by log(m) − H(Z | X = ui) and compares it with the optimized mutual-information value.
Information bound: Symmetry and a uniform distribution over the extreme points attain equality in the upper bound.
Convex reduction: The objective is strictly convex except when conditional distributions coincide with the corresponding marginal distribution.
Extension beyond extreme inputs: The construction extends from extreme inputs to all x by choosing entropy-maximizing distributions supported on Ext(D), with continuity ensuring measurability.
Maximum-entropy verification: KKT conditions verify that the maximum-entropy conditional distribution is optimal for the entropy program.
Hypercube specialization: For the hypercube, the conditional distribution uses independent coordinates with Bernoulli parameters 1/2 + xi/(2M).

E.3 Proof of Proposition 2

The proof constructs the maximum-entropy distribution on the extreme points of the ℓ1-ball under a mean constraint, using symmetry to reduce the problem to x = ±e_i. It then verifies the constraints and computes the conditional entropy.

Entropy maximization: The maximum-entropy problem restricts Z to the extreme points ±Me_i of the ℓ1-ball and reduces, by symmetry, to x = ±e_i.The coordinates are treated independently in the entropy-maximization formulation.
Distribution form: The Lagrangian yields an exponential-family distribution with q(Me_i) proportional to e^-μ_i and q(-Me_i) proportional to e^μ_i.For coordinates j ≠ i, the corresponding probabilities are equal by symmetry.
Constraint verification: The parameter is chosen so that M[q(Me_i) − q(−Me_i)] = 1 while q(Me_j) − q(−Me_j) = 0 for j ≠ i.These moment constraints enforce the required mean while preserving symmetry across the other coordinates.
Conclusion: Because the resulting distribution belongs to the exponential family and satisfies the constraints, it maximizes the entropy H(Z).The remaining proposition statement follows from algebraic manipulation and computing H(Z | X = e_i).

E.4 Proof of Proposition 3

The proof reduces the optimally locally private channel to a symmetry-constrained linear program. It identifies a unique two-level probability vector, which determines the channel and its perturbation radius.

Privacy-radius tradeoff: Increasing M enlarges the set of available privacy channels and decreases the optimal privacy parameter α⋆.Equivalently, for fixed α, the proof seeks the smallest feasible M.
Linear-program formulation: The smallest perturbation radius M for a given privacy level α is obtained by a linear program with mean, normalization, nonnegativity, and privacy-ratio constraints.The substitution t = 1/M converts minimizing M into solving for the optimal t.
Channel construction: The solution vectors define the probability mass function of an α-differentially private channel from [−1, 1]^d to [−M, M]^d.The resulting channel is optimally locally differentially private at α = α⋆([−1, 1]^d, [−M, M]^d).
Symmetry reduction: Optimal local differential privacy requires each conditional distribution q(· | x) to be a permutation of one fixed vector q.This symmetry reduces the channel optimization from a matrix-valued problem to a single-vector problem.
Solution structure: For α < α∗, the linear program has a two-valued solution vector q, with probabilities q+ and q− assigned according to the sign of z⊤x.The values satisfy 0 < q− < q+ and are normalized to sum to one.
Optimality verification: The proposed q satisfies the KKT conditions because symmetry gives Zq = tx for some t > 0.Strict inequalities in the dual variables establish optimality for α < α∗.
Uniqueness: The two-valued solution is unique for α < α∗, using perturbations of the KKT certificate and a uniqueness result for linear programs.The strict positivity conditions permit suitably small perturbations while preserving the KKT conditions.

E.5 Proof of Corollary 4

The proof of Corollary 4 uses a Taylor expansion of the entropy-related function f(γ) around γ = 0. Bounding higher derivatives and evaluating the second derivative yields the stated asymptotic expression.

Expansion setup: The proof begins by expanding the relevant expression as γ → 0 after scaling to M ≥ L = 1.This expansion is then used to establish Corollary 4.
Mutual information: The resulting expansion is substituted into the mutual-information expression from Proposition 2.The proof explicitly connects the Taylor calculation to the mutual information in that proposition.
Taylor expansion: Defining f(γ) = log(e^γ + e^-γ + 2d − 2) enables the proof to express the needed quantity through derivatives of f.The argument uses f^(1), f^(2), and f^(3) in the Taylor expansion.
Remainder control: f^(3)(γ) = O(γ/d), so the third-order Taylor remainder is controlled near γ = 0.The remaining calculation focuses on the second derivative.
Asymptotic evaluation: (γ^2/2)f^(2)(γ) = γ^2/(2d) + O(γ^4/d), which yields the result used in the corollary.This follows from f^(2)(γ) = (4d + O(dγ^2))/4d^2.