PaperlayerView exact revision on arXiv

Source-linked AI summary

Protection Against Reconstruction and Its Applications in Private Federated Learning

Abhishek Bhowmick, John Duchi, Julien Freudiger, Gaurav Kapoor, Ryan Rogers

arXiv:1812.00984v2stat.MLcs.LG

TL;DR

Large-scale learning from peripheral devices creates a tension between strong local privacy and useful statistical estimation. The paper addresses this by targeting reconstruction by limited-information adversaries, developing minimax-optimal private mechanisms, and combining local with central privacy; it reports practical private federated learning with performance comparable to non-private federated procedures.

  • Problem

    Traditional local differential privacy can be too restrictive for practical high-dimensional learning, where privacy protections must coexist with accurate model fitting.

  • Method

    The paper models curious adversaries with limited prior information, designs minimax-optimal mechanisms for high-dimensional vectors, and combines local privacy with central differential privacy in federated learning.

  • Results

    The proposed procedures are minimax optimal for privacy parameters ε ≤ d and achieve performance comparable to federated learning without privacy safeguards.

  • Takeaways & Limitations

    Private federated learning can provide reconstruction protection and globally private model outputs while retaining useful large-scale model-fitting performance.

  • Takeaways & Limitations

    The experiments reduce the theoretically recommended σ for computational feasibility, requiring larger εα or a larger subsampling rate q.

Abstract

from arXiv · show

In large-scale statistical learning, data collection and model fitting are moving increasingly toward peripheral devices---phones, watches, fitness trackers---away from centralized data collection. Concomitant with this rise in decentralized data are increasing challenges of maintaining privacy while allowing enough information to fit accurate, useful statistical models. This motivates local notions of privacy---most significantly, local differential privacy, which provides strong protections against sensitive data disclosures---where data is obfuscated before a statistician or learner can even observe it, providing strong protections to individuals' data. Yet local privacy as traditionally employed may prove too stringent for practical use, especially in modern high-dimensional statistical and machine learning problems. Consequently, we revisit the types of disclosures and adversaries against which we provide protections, considering adversaries with limited prior information and ensuring that with high probability, ensuring they cannot reconstruct an individual's data within useful tolerances. By reconceptualizing these protections, we allow more useful data release---large privacy parameters in local differential privacy---and we design new (minimax) optimal locally differentially private mechanisms for statistical learning problems for \emph{all} privacy levels. We thus present practicable approaches to large-scale locally private model training that were previously impossible, showing theoretically and empirically that we can fit large-scale image classification and language models with little degradation in utility.

1 Introduction

The paper addresses privacy challenges in decentralized large-scale learning by revisiting local privacy guarantees and designing mechanisms for practical private model fitting. It combines reconstruction protection, minimax-optimal local mechanisms, and central differential privacy for federated learning.

  • Motivation: Peripheral devices make large-scale predictive modeling increasingly useful while creating computational, statistical, and privacy challenges.The motivating applications include remote sensors, phones, fitness monitors, watches, and other connected devices.
  • Motivation: Model updates can reveal private data directly, since generalized linear-model gradients are scalar multiples of a user’s data vector.For losses of the form φ(⟨θ,x⟩,y), the gradient is c · x.
  • Why local privacy makes model fitting challenging: Standard local differential privacy can make learning statistically difficult, with minimax sample-complexity degradation scaling as d/min{ε, ε2}.The cited results suggest that small constant ε is challenging for even moderately dimensional problems, while standard local privacy may restrict deployments.
  • Our approach and results: Empirical results show that private federated learning can achieve performance comparable to federated learning without privacy safeguards.The paper studies both models trained from scratch and models initialized with pretraining.
  • Our approach and results: The paper protects against reconstruction by modeling adversaries with little prior information, allowing substantially larger local privacy parameters while retaining guarantees for those adversaries.The approach departs from protection against arbitrary inferences and instead targets curious onlookers attempting to decode individual data.
  • Our approach and results: The authors develop minimax-optimal mechanisms for high-dimensional vectors and private federated learning schemes that combine local protection with central differential privacy.The mechanisms are claimed optimal for all ε ∈ [0,d], and the central layer protects broadcast model parameters.

2 Privacy protections

The paper distinguishes protection against reconstruction by curious onlookers from protection against powerful adversaries, using prior uncertainty and reconstruction loss to formalize useful privacy. This framework supports larger local privacy parameters when priors are diffuse, while identifying stricter conditions for uniformly preventing breaches.

  • Threat model: The paper models a curious onlooker who observes individual communications and seeks to reconstruct private data, distinguishing this threat from powerful adversaries targeting shared models.Protection against powerful external adversaries generally requires small privacy parameters, whereas reconstruction protection targets onlookers with limited prior information.
  • Reconstruction breach: A reconstruction breach occurs when an estimator, after observing a privatized output, reconstructs a target function within loss tolerance α with conditional probability exceeding p.The definition uses a prior on X, a Markov chain X → W → Z, a target f(X), and a reconstruction loss Lrec.
  • Reconstruction breach: The breach definition applies uniformly to every possible mechanism observation, excluding rare privacy breaches but imposing stringent conditions on mechanisms.This uniformity also rules out relaxed privacy definitions beyond differential privacy within the stated framework.
  • Diffuse priors: For diffuse priors, private views can preserve low reconstruction success even when ε is large, because the adversary is initially unlikely to reconstruct the target accurately.The paper motivates this regime using low-dimensional image reconstructions and formalizes it through posterior and prior comparisons.
  • Protection guarantee: Differential privacy preserves reconstruction difficulty up to an e^ε factor: if the prior reconstruction probability is p(α), the private mechanism guarantees protection probability e^ε · p(α).The result follows from posterior stability under differential privacy and holds for any estimator based on the privatized output.
  • Sparse data: For sparse dictionary-like data, the paper recommends aggregating at least m = d^ρ signals and using local privacy budgets no larger than ε = c_m, with c near zero.The recommendation is revisited in the language-modeling experiments.

3 Applications in federated learning

The federated-learning procedure privatizes local updates before communication and applies centralized privacy during aggregation. Its analysis establishes unbiased private updates, asymptotic behavior, and a dimension- and privacy-dependent covariance scaling described as minimax optimal.

  • Federated-learning procedure: Federated learning distributes a centralized parameter to workers, which compute local updates that are aggregated into a global model update.The basic loop consists of distributing θ, computing ∆i := θi − θ, and updating θ with an aggregate ∆.
  • Federated-learning procedure: The private procedure protects individual data during local updates and applies centralized differential privacy to communicated model parameters during aggregation.Thus, raw user data is not transmitted clearly, while intermediate and final parameters receive centralized privacy guarantees.
  • Private optimization: Each sampled individual computes a local update from local data and the current central parameter, after which the update is privatized, projected onto an ℓ2-ball, and averaged.Projection uses a fixed radius ρ and limits each individual update’s contribution.
  • Privacy accounting: The aggregation noise is analyzed using subsampling and a moments-accountant approach based on Rényi differential privacy across T iterations.The stated privacy analysis relates the cumulative privacy loss to the sampling rate, noise scale, batch size, and update radius.
  • Asymptotic analysis: Under bounded-gradient assumptions, the private stochastic updates are unbiased and have a covariance term Σ_priv that governs their asymptotic behavior.The bounded-gradient condition holds, for example, for logistic regression with bounded data vectors.
  • Asymptotic analysis: The resulting privacy-induced covariance has the correct scaling with dimension and local privacy ε and is minimax optimal, contrasting with previous local-privacy work.The paper presents this scaling as the key consequence of its mechanism design.

4 Separated Private Mechanisms for High Dimensional Vectors

The paper develops separated mechanisms that privatize vector direction and magnitude independently, yielding unbiased, accurate estimates for high-dimensional learning updates. PrivUnit2 and PrivUnit∞ achieve minimax or order-optimal accuracy across privacy regimes, supporting private stochastic optimization and federated learning.

  • Separated mechanisms: Private updates separately encode a vector’s direction and magnitude, enabling unbiased estimates for Euclidean and non-Euclidean learning problems.The framework targets ℓ2 and ℓ∞ balls and combines unit-vector and scalar mechanisms to release vector estimates.
  • PrivUnit2: PrivUnit2 samples from a spherical cap or its complement, with parameters chosen to ensure differential privacy and unbiasedness.The mechanism returns Z satisfying E[Z | u] = u, while γ and p trade accuracy against privacy.
  • PrivUnit2: PrivUnit2 is order optimal for privacy levels ε ≤ d log 2 − log 4/3 and improves previously known locally private vector-release mechanisms.The result establishes optimal dependence on dimension and privacy in the stated regime.
  • PrivUnit2: PrivUnit2 achieves unimprovable dependence on dimension d and privacy level ε, extending order-optimal guarantees beyond the earlier ε ≲ 1 regime.The mechanism substantially improves earlier guarantees that were order optimal only for small privacy levels.
  • PrivUnit∞: PrivUnit∞ is no worse than earlier mechanisms for all ε and has substantially better ε-dependence when ε ≥ log d.Its ℓ∞ error bounds are unimprovable except possibly for ε ∈ [1, log d].
  • Learning guarantees: Separately encoding gradient magnitude and direction allows covariance bounds to adapt to the scale of Σ⋆ rather than the worst-case gradient norm.The resulting mechanisms are minimax rate optimal, with bounded efficiency loss under the stated conditions.

5 Empirical Results

The experiments evaluate private federated learning across simulated optimization, image classification, and distributed model-fitting settings. Utility is nearly comparable to non-private training at large local privacy parameters, but smaller parameters can substantially degrade performance.

  • The experiments vary ε1 as the dominant term in the asymptotic convergence while fixing ε2 = 10 so its contribution is negligible relative to sampling error.This parameterization is used with separated differentially private mechanisms.
  • Large local privacy parameters ε can yield accuracy nearly comparable to non-private methods, whereas smaller ε can cause substantial performance degradation.The comparison spans simulated and real-data settings, including models trained from random initialization.
  • Simulated logistic regression experiments: Without ε ≥d/8 in the high-dimensional logistic regression simulation, performance is essentially no better than the θ = 0 random-guessing model.The experiment uses d = 500 and N = 105; alternative stepsize choices do not help.
  • Simulated logistic regression experiments: The logistic regression study evaluates optimization error and parameter-recovery error across iterations and privacy levels, comparing averaged stochastic-gradient iterates with the maximum likelihood estimator.Figure 3 reports 95% error bars for optimization error and box plots for ∥θ −θ⋆∥2.
  • Fitting deep models tabula rasa: The deep-model experiments train a 3,274,634-parameter MNIST CNN and a 1,068,298-parameter CIFAR-10 CNN using private stochastic updates and centralized noise.The MNIST setup uses 100 rounds with (εcent = 1.9, δ = 10^-9)-central differential privacy; the CIFAR-10 setup uses 200 rounds with (εcent = 1.76, δ = 10^-9).
  • Pretrained models: The empirical program includes pretrained-model refitting as a realistic private federated learning use case for adapting models to new populations.The reported pretrained tasks include image classification and next-word prediction.

6 Discussion and conclusion

The paper argues that small local privacy parameters make model fitting extremely challenging, motivating protections based on reconstruction risk and large-ε regimes. It presents minimax-optimal privatization mechanisms and a distributed model-fitting system while acknowledging looseness in some covariance guarantees.

  • The paper studies large-ε local privacy regimes because small ε-local differential privacy makes model fitting extremely challenging.Its privacy justification uses prior beliefs and reconstruction probabilities from oblivious adversaries.
  • The proposed system combines minimax-optimal privatization mechanisms with large-scale distributed model fitting, or federated learning.The system is designed for users who prefer local privacy protections.
  • The privacy framework targets reconstruction protections for curious adversaries while preserving stronger global privacy guarantees for the procedure’s output.The paper motivates a distinction between local protections and global differential privacy guarantees.

A.2 Proof of Theorem 2

The proof bounds the privacy ratio of the binary-vector mechanism by comparing output probabilities under different inputs. This establishes a sufficient privacy bound involving ε and ε0.

  • The mechanism samples a binary vector V from a distribution determined by an input sign vector u and a uniformly random sign vector U.The proof analyzes the resulting probability mass function.
  • Monotonicity of P(⟨U, u⟩ > κ) bounds the ratio of output probabilities for two inputs.The argument compares the probabilities of matching and nonmatching threshold events.
  • The resulting bound is at most e^(ε+ε0), which yields the claimed differential-privacy guarantee.The proof obtains this by bounding the relevant binomial-tail expression.

A.3 Proof of Corollary 4.1

The proof of Corollary 4.1 handles separate privacy regimes by bounding binomial-tail terms. These bounds provide sufficient thresholds for ε-differential privacy, including a logarithmic-dimension regime.

  • The proof first analyzes the regime κ ≤ 3/2d + 1 using a binomial-sum bound for the privacy expression.A separate claim supplies the needed estimate for even d ≥ 2.
  • In this regime, the derived threshold is sufficient to ensure ε-differential privacy.The corollary follows after substituting the bound into the privacy inequality.
  • The proof separately treats ε = Ω(log(d)) using a binomial-tail bound for Z ∼ Bin(d, 1/2).This establishes the second privacy regime required by the corollary.
  • Applying the binomial bound yields the final sufficient condition for the logarithmic-dimension regime.The argument concludes by substituting the resulting bound into the privacy requirement.

A.4 Proof of Lemma 4.5

The proof bounds the conditional second moment of the privatized vector using rotational symmetry and the normalization of the PrivUnit2 mechanism. The resulting bound scales with dimension and the privacy parameters.

  • A.4 Proof of Lemma 4.5: The proof represents the gradient as RU, where R is its norm and U is its normalized direction.This shorthand is introduced before the conditional-moment calculation.
  • A.4 Proof of Lemma 4.5: Rotational symmetry expresses the conditional second moment of V as a mixture of moments over a spherical cap and its complement.The two components are weighted by one-half in the displayed decomposition.
  • A.4 Proof of Lemma 4.5: Both conditional moment terms are bounded by uu⊤ + (1/d)Id, yielding a direction-dependent and isotropic decomposition.The normalization constant m then scales these terms by m^-2.
  • A.4 Proof of Lemma 4.5: The final matrix bound is controlled by d divided by the minimum of ε1 and ε2.The cited display gives the bound in compact notation as d ε1 ∧ε2.
  • A.4 Proof of Lemma 4.5: The lemma follows by applying the preceding bound to the random vector W.This is the proof’s final step.

B.1 Proof of Lemma 4.3

The proof establishes privacy through randomized response and derives unbiasedness and variance expressions for the scalar mechanism. It then bounds the resulting terms using the distribution of the auxiliary Bernoulli variable J.

  • B.1 Proof of Lemma 4.3: Randomized response immediately gives ε-differential privacy for the scalar mechanism.The proof invokes the privacy of randomized response directly.
  • B.1 Proof of Lemma 4.3: The estimator is unbiased because its expectation satisfies r E[J] = r.The proof uses this identity as the starting point for the variance analysis.
  • B.1 Proof of Lemma 4.3: The variance is decomposed into expected conditional variance plus the variance of the conditional expectation.The displayed identity is Var(Z) = E[Var[Z | J]] + Var[E[Z | J]].
  • B.1 Proof of Lemma 4.3: Conditioning on J reduces the variance calculation to the variance of the randomized-response variable bJ.The proof writes Var[Z | J] = a^2 · Var[bJ | J].
  • B.1 Proof of Lemma 4.3: The remaining algebra combines conditional moments, the variance identity, and the Bernoulli support of J to obtain the stated bound.J takes values in {⌊kr/rmax⌋, ⌈kr/rmax⌉}, which determines Var(J).
  • B.1 Proof of Lemma 4.3: The final inequality is obtained by discarding negative terms in the preceding expression.The proof explicitly states this simplification before concluding.

B.2 Sampling scalars with relative error

ScalarRelDP privatizes a bounded scalar by geometrically binning its magnitude, unbiasedly rounding within the selected interval, and applying debiased randomized response. The mechanism provides ε-differential privacy, unbiasedness, and a relative-error guarantee.

  • B.2 Sampling scalars with relative error: Relative-error privatization is motivated by the need to identify low-variance problems and release scalars with error proportional to their magnitude.The mechanism is designed for settings where relative accuracy matters.
  • B.2 Sampling scalars with relative error: The range [0, rmax] is partitioned into intervals E0 = [0, να] and Ei = [νiα, νi+1α].The intervals have increasing geometric length controlled by α and ν.
  • B.2 Sampling scalars with relative error: ScalarRelDP clips r at rmax, selects its interval, and samples an endpoint through unbiased random rounding.The algorithm then applies randomized response to the endpoint index.
  • B.2 Sampling scalars with relative error: Randomized response outputs the selected index with probability eε/(eε+k) and another index with probability k/(eε+k).The resulting response is subsequently debiased.
  • B.2 Sampling scalars with relative error: ScalarRelDP is ε-differentially private and unbiased for r < rmax.These properties are stated in Lemma B.1.
  • B.2 Sampling scalars with relative error: For α0 = e−ε/4, the mechanism has mean-squared error O(r2 maxe−5ε/6) when r ≤ rmaxe−ε/4 and O(r2e−ε/3) otherwise.The comparison is presented as stronger than the former inequality in the small-r regime.

B.3 Proof of Lemma B.1

The proof of Lemma B.1 verifies privacy by post-processing randomized response and verifies unbiasedness through conditional expectations. Rotational symmetry supplies the normalization needed for the vector mechanism’s expectation.

  • B.3 Proof of Lemma B.1: Privacy follows because randomized response is ε-differentially private and differential privacy is closed under post-processing.The scalar mechanism applies debiasing after randomized response.
  • B.3 Proof of Lemma B.1: The unbiasedness calculation reduces to showing that the conditional endpoint expectation equals r.The proof records this identity explicitly.
  • B.3 Proof of Lemma B.1: The proof analyzes the conditional variance of Z given the selected interval index J = i∗.For r in Ei∗, the magnitude is bounded between νi∗α and νi∗+1α.
  • B.3 Proof of Lemma B.1: Rotational symmetry implies that conditional expectations of a uniform sphere vector lie along u, with coefficients γ+ and γ− for the cap and complement.The coefficients are defined through the corresponding conditional expectations.
  • B.3 Proof of Lemma B.1: The mixture expectation is proportional to u, and the mechanism’s normalization makes E[Z] = u.The proof combines the two conditional regions with probability p and 1 − p.
  • B.3 Proof of Lemma B.1: The normalization calculation uses rotational symmetry to set u = e1 and represents sphere coordinates through a Beta distribution.The resulting coefficients are computed from Beta-function expressions.

C.2 Proof of Proposition 4

The proof analyzes the mechanism through conditional expectations and normalization, then handles three privacy regimes to establish the proposition’s bounds. A symmetry argument shows that the debiased output recovers the target vector in expectation.

  • Conditional-expectation analysis: Conditional expectations on spherical caps express the mechanism’s components as γ+·u and γ−·u, with γ+ positive and |γ+|>|γ−|.These relations yield γ+≥γ and γ−≤0, supporting the subsequent norm analysis.
  • Normalization bound: The normalization satisfies ∥Z∥2 = 1/(pγ+ + (1−p)γ−), allowing the proof to assume p = 1/2 without loss of generality.The bound is obtained using ∥V∥2 = 1 and the monotonicity of the denominator as p increases.
  • Case analysis: Three cases for ε are analyzed to lower-bound γ+ + γ− and obtain the first result of the proposition.The cases cover 5 ≤ ε ≤ 2 log d, d ≥ ε ≥ 5, and ε ≤ 5.
  • Debiasing: For the discrete hypercube mechanism, symmetry gives E[V | u = u] = m·u, where m = pκ+ + (1−p)κ−.Consequently, dividing by m debiases the output: E[(1/m)V | u = u] = u.

C.4 Proof of Proposition 5

The proof bounds the debiasing normalizer for the hypercube mechanism by splitting the analysis according to whether ε is at least log d. It also develops spherical-cap probability bounds used in the analysis of PrivUnit2.

  • Normalizer analysis: The debiasing multiplier obeys 1/m = 1/(pκ+ + (1−p)κ−), and the proof lower-bounds κ+ + κ− in two ε regimes.The regimes are ε ≥ log d and ε < log d.
  • Case 1: ε ≥ log d: For ε ≥ log d, the proof bounds κ+ and κ− separately and shows that choosing κ proportional to √(d/ε) satisfies the privacy condition.The resulting normalizer bound follows from the lower bounds on κ+ and κ−.
  • Case 2: ε < log d: For ε < log d, choosing κ proportional to √d min{1, ε} yields the second result of Proposition 5.The proof chooses κ to saturate the relevant bound and uses Stirling’s approximation in the calculation.
  • Spherical-cap bounds: Spherical-cap lemmas characterize probabilities for U uniform on S^(d−1), including a Beta-distributed representation of ⟨U,u⟩.These bounds support the concentration analysis of PrivUnit2 for vectors in the ℓ2 ball.
Loading 1812.00984v2…