PaperlayerView exact revision on arXiv

Source-linked AI summary

Local Differential Privacy based Federated Learning for Internet of Things

Yang Zhao, Jun Zhao, Mengmeng Yang, Teng Wang, Ning Wang, Lingjuan Lyu, Dusit Niyato, Kwok-Yan Lam

arXiv:2004.08856v2cs.CRcs.LG

TL;DR

The paper addresses location privacy and communication costs in IoV crowdsourcing by integrating federated learning with local differential privacy. It proposes four gradient-perturbation mechanisms, including Three-Outputs, PM-OPT, PM-SUB, and a hybrid, to balance privacy, utility, and communication. Experiments report that the proposed mechanisms outperform existing solutions across mean estimation and machine-learning tasks, with Three-Outputs favoring small ε and PM-SUB favoring large ε.

  • Problem

    IoV crowdsourcing can expose users’ location information and incur high vehicle-server communication costs, while existing LDP mechanisms have utility or encoding limitations.

  • Method

    The paper integrates LDP with FedSGD and proposes Three-Outputs, PM-OPT, PM-SUB, and hybrid HM-TP mechanisms for perturbing vehicle gradients.

  • Results

    The proposed mechanisms outperform existing solutions across mean estimation, classification, and regression experiments; Three-Outputs is better for small ε, while PM-SUB has higher utility for large ε.

  • Takeaways & Limitations

    LDP-FedSGD enables vehicular crowdsourcing applications to train traffic-status models while avoiding gradient-based privacy threats and reducing communication cost.

Abstract

from arXiv · show

Internet of Vehicles (IoV) is a promising branch of the Internet of Things. IoV simulates a large variety of crowdsourcing applications such as Waze, Uber, and Amazon Mechanical Turk, etc. Users of these applications report the real-time traffic information to the cloud server which trains a machine learning model based on traffic information reported by users for intelligent traffic management. However, crowdsourcing application owners can easily infer users' location information, which raises severe location privacy concerns of the users. In addition, as the number of vehicles increases, the frequent communication between vehicles and the cloud server incurs unexpected amount of communication cost. To avoid the privacy threat and reduce the communication cost, in this paper, we propose to integrate federated learning and local differential privacy (LDP) to facilitate the crowdsourcing applications to achieve the machine learning model. Specifically, we propose four LDP mechanisms to perturb gradients generated by vehicles. The Three-Outputs mechanism is proposed which introduces three different output possibilities to deliver a high accuracy when the privacy budget is small. The output possibilities of Three-Outputs can be encoded with two bits to reduce the communication cost. Besides, to maximize the performance when the privacy budget is large, an optimal piecewise mechanism (PM-OPT) is proposed. We further propose a suboptimal mechanism (PM-SUB) with a simple formula and comparable utility to PM-OPT. Then, we build a novel hybrid mechanism by combining Three-Outputs and PM-SUB.

I. PRELIMINARIES

The preliminaries introduce local differential privacy and position LDP-FedSGD as a privacy-preserving federated-learning framework for connected vehicles. Users perturb gradients locally before transmission, while the server averages noisy gradients; the paper focuses on user-level distributed privacy.

  • Local Differential Privacy: Local differential privacy has users perturb their data locally before sending randomized results to an aggregator, with ε controlling the privacy-utility trade-off.A higher privacy budget means lower privacy protection.
  • Existing LDP Mechanisms: Prior numeric-data mechanisms include Laplace, Duchi’s two-output method, and the continuous-output piecewise mechanism.Laplace adds noise directly, Duchi outputs values from {−C, C}, and PM provides infinitely many possible outputs over a continuous range.
  • Existing LDP Mechanisms: Existing mechanisms have different utility regimes: Laplace can outperform Duchi at larger ε, while PM has lower worst-case variance when ε is large.The hybrid HM combines Duchi’s small-ε behavior with PM’s large-ε behavior, but PM and HM outputs are difficult to encode.
  • LDP-FedSGD: Federated learning keeps vehicle datasets local, but attackers may reverse uploaded gradients; LDP-FedSGD perturbs gradients before the server averages them.Vehicles upload noisy gradients rather than model parameters, and the server updates the global model from group averages.
  • Privacy Paradigms: The framework uses distributed perturbation for user-level privacy because a vehicle may have multiple records and protecting the whole user is stronger than protecting individual records.The paper distinguishes user-level and record-level privacy according to how neighboring datasets are defined.

IV. PROBLEM FORMATION

The paper formulates unbiased local randomization for numeric data as minimizing worst-case output variance under LDP, then introduces Three-Outputs with three possible outputs and optimized probabilities.

  • IV. PROBLEM FORMATION: The design problem minimizes MaxVar(M), the worst-case conditional variance of a perturbed value, subject to LDP and unbiasedness constraints.The output distribution must also be valid over its randomized range.
  • A. Three-Outputs Mechanism: Three-Outputs returns one of −C, 0, or C, providing three discrete output possibilities for numeric input x.The mechanism is specified for x ∈[−1, 1] and outputs Y ∈{−C, 0, C}.
  • A. Three-Outputs Mechanism: The mechanism uses symmetric probability relationships and piecewise linear probabilities in x to preserve unbiased estimation while reducing worst-case variance.Symmetrization does not increase worst-case variance, and the resulting probabilities are designed as piecewise linear functions.
  • A. Three-Outputs Mechanism: The optimization enforces P0←0 = e^ǫP0←1 and chooses P0←0 through Eq. (5) to minimize Three-Outputs’ worst-case noise variance.The optimal value changes with the privacy budget and is zero when the budget is small.
  • A. Three-Outputs Mechanism: When the privacy budget is small, Three-Outputs is equivalent to Duchi’s mechanism; as ǫ increases, its probability of outputting the true value increases.Fig. 3 reports the optimal P0←0 over ǫ ∈[0, 8].
  • A. Three-Outputs Mechanism: The mechanism’s probabilities are derived from the optimized P0←0 and used to instantiate the random output through the stated sampling procedure.The algorithm samples according to P0←x and PC←x, with P−C←x, P0←x, and PC←x defined by the mechanism equations.

B. PM-OPT Mechanism

PM-OPT is an optimal mechanism within the piecewise framework, designed to reduce worst-case noise variance when the privacy budget is large while maintaining LDP and unbiasedness.

  • B. PM-OPT Mechanism: PM-OPT improves on PM by achieving a smaller worst-case noise variance, especially when ǫ is large.Three-Outputs has lower worst-case noise variance than PM when ǫ < 3.2, but PM-OPT is proposed for the larger-budget regime.
  • B. PM-OPT Mechanism: PM-OPT takes x ∈[−1, 1] and ǫ as input and returns a randomized output Y ∈[−A, A].The mechanism samples an intermediate output using the parameter t calculated from Eq. (30).
  • B. PM-OPT Mechanism: Its output density has a higher-probability center interval [L(ǫ, x, t), R(ǫ, x, t)] and lower-probability outer intervals.The density therefore consists of three pieces over the output range.
  • B. PM-OPT Mechanism: The parameter t controls the center interval, whose boundaries converge from opposite sides as t approaches zero and coincide as t approaches infinity.The center interval length is R(ǫ,1,t)−L(ǫ,1,t) when x=1.
  • B. PM-OPT Mechanism: Algorithm 3 satisfies ǫ-LDP and produces an unbiased output with E[Y|x] = x.Lemma 6 states the privacy and expectation properties.
  • B. PM-OPT Mechanism: The optimal t is obtained by minimizing maxx∈[−1,1] Var[Y|x].Lemma 7 identifies the optimal t through the variance optimization problem.

C. PM-SUB Mechanism

PM-SUB replaces PM-OPT’s complicated optimization with a simple parameter choice while retaining comparable utility and lower worst-case noise variance than PM.

  • C. PM-SUB Mechanism: PM-SUB is proposed to simplify PM-OPT’s sophisticated computation of t.Its mechanism is specified in Algorithm 4.
  • C. PM-SUB Mechanism: PM-SUB takes x ∈[−1, 1] and ǫ as input and returns Y ∈[−A, A] through randomized sampling.The algorithm samples a uniform random variable and then samples Y from the corresponding interval.
  • C. PM-SUB Mechanism: PM-SUB sets t = e^ǫ/3 instead of computing PM-OPT’s optimal t.This choice yields a simple expression for implementation.
  • C. PM-SUB Mechanism: PM-SUB’s worst-case noise variance is close to PM-OPT’s and smaller than PM’s.The comparison is reported in Fig. 5 and observed in Fig. 1.

D. Discretization Post-Processing

The paper discretizes continuous PM outputs into finitely many values so vehicles can encode them, while preserving unbiasedness and not increasing worst-case noise variance.

  • D. Discretization Post-Processing: PM-OPT and PM-SUB have continuous output ranges with infinitely many possibilities, making their outputs difficult for vehicles to encode.The paper therefore applies post-processing discretization.
  • D. Discretization Post-Processing: Algorithm 5 implements the discretization post-processing that converts the continuous perturbed output into discrete data Z.The algorithm’s output is discrete data after the range partitioning and randomized boundary assignment.
  • D. Discretization Post-Processing: The discretization divides the symmetric range [−C, C] into 2m segments and produces 2m + 1 possible boundary outputs.The integer m controls the number of discrete output possibilities.
  • D. Discretization Post-Processing: For an intermediate output y, the algorithm assigns a neighboring left or right boundary using Bernoulli sampling.This random assignment is chosen so the conditional expectation after discretization equals y.
  • D. Discretization Post-Processing: The discretized variable Z is constructed so E[Z|Y=y] = y, which preserves the original unbiased expectation with respect to x.The paper explains that this conditional expectation ensures the expectation given the original input remains x.
  • D. Discretization Post-Processing: After discretization, the worst-case noise variance does not change or worsen under the stated mechanism assumptions.Lemma 9 formally compares an unbiased continuous mechanism M1 with an unbiased discretization mechanism M2 whose output set is a subset of M1’s.

E. HM-TP Mechanism

HM-TP combines Three-Outputs and PM-SUB, selecting between them according to the privacy budget to reduce worst-case noise variance. The section extends these mechanisms to multidimensional numeric attributes and vehicle-compatible discrete communication.

  • HM-TP combines Three-Outputs and PM-SUB, using PM-SUB with probability β and Three-Outputs otherwise.Its noisy variance is β·VarP[Y |x] + (1−β)·VarT[Y |x].
  • Three-Outputs is preferable at small privacy budgets, whereas PM-SUB has lower variance at large privacy budgets.HM-TP combines both regimes and achieves lower worst-case noise variance than the other solutions.
  • The probability β is chosen to minimize HM-TP’s maximum variance over x ∈ [−1,1].The minimizing expression for β is given in an appendix.
  • For d-dimensional tuples, the extension samples k attributes without replacement and perturbs each selected value using PM-SUB, Three-Outputs, or HM-TP.The output tuple has non-zero values on k attributes, with k selected to achieve asymptotically optimal performance while preserving privacy.
  • Three-Outputs uses two-bit-compatible finite outputs, while continuous-output mechanisms require discretization for vehicle communication.The paper reports that discretization can preserve similar performance while enabling vehicle-compatible encoding.
  • The multidimensional algorithm satisfies ε-local differential privacy and produces unbiased estimates for selected attributes.For each selected attribute tj, the expected noisy output equals x[tj].

VII. EXPERIMENTS

Experiments compare the proposed mechanisms with existing LDP methods across mean estimation, regression, and classification tasks. The proposed approaches generally outperform existing solutions, and discretization retains similar performance to continuous outputs.

  • The evaluation compares PM-SUB, Three-Outputs, HM-TP, PM, HM, Duchi’s mechanism, Laplace, and non-private settings across real and synthetic datasets.The real datasets include WISDM, MX, BR, and Vehicle; synthetic datasets contain numeric attributes generated from Gaussian distributions.
  • Mean estimation: HM-TP outperforms existing solutions in all reported mean-estimation settings, while PM-SUB is better than PM at large privacy budgets and Three-Outputs at small budgets.Mean estimation uses MSE as a function of the total privacy budget ε.
  • Mean estimation: PM-SUB, Three-Outputs, and HM-TP outperform existing solutions on synthetic mean-estimation datasets.The comparison evaluates MSE for numeric attributes across four synthetic datasets.
  • Empirical risk minimization: The proposed mechanisms have lower misclassification rates than other mechanisms in logistic regression and SVM, and lower MSE in linear regression at selected privacy budgets.The experiments use vehicle-generated noisy gradients and repeated 10-fold cross-validation.
  • Discretization: The paper applies discretization post processing to PM, PM-SUB, HM, and HM-TP for the evaluated continuous-output mechanisms.The discretized mechanisms are tested in mean estimation, linear regression, logistic regression, and SVM-related experiments.
  • Discretization: After discretizing continuous outputs into 2000 segments, the proposed approaches outperform existing solutions for mean estimation on WISDM, MX, and BR.This produces 2001 possible outputs for an initial input x.
  • Discretization: With discretization, regression performance is similar to continuous-output performance, and error generally decreases as the number of output possibilities increases.With many output possibilities, PM-SUB outperforms Three-Outputs; 2000 segments provide satisfactory performance.

APPENDIX

The appendix derives variance expressions and optimization conditions for the proposed mechanisms. It proves that symmetrization can reduce worst-case variance and analyzes the quartic equation used to optimize the mechanism parameter.

  • The appendix establishes that M2 satisfies ε-LDP and unbiased estimation requirements.The proof uses probability constraints and verifies that the relevant probability ratio lies between e^-ε and e^ε.
  • Symmetrization produces mechanism M3 with smaller worst-case noise variance than M2 over x ∈ [−1,1].The appendix compares the variances of M2 and M3 through their output probabilities.
  • The appendix derives Var[Y |X = x] from the second moment and unbiasedness constraints for three-output mechanisms.The variance is expressed as E[Y^2|X = x] − (E[Y|X = x])^2 and expanded using endpoint probabilities.
  • For fixed P0←0, the output variance decreases strictly as P0←1 increases, so the minimum occurs when P0←1 = P0←0.This condition follows from the derivative of Var[Y |X = x].
  • The optimal parameter t is obtained by solving a quartic equation whose second derivative is positive at the minimizer.The optimization targets maxx∈[−1,1] Var[Y |x].
  • The quartic is transformed into a depressed quartic and solved through an auxiliary cubic, retaining the real positive root.The resulting root yields the parameter expression used in the mechanism.

E. Proof of Lemma 4

The proof partitions the privacy-budget range to analyze cubic roots and derivative signs, identifying the optimal parameter a for Three-Outputs. The resulting choice is a=0 below ln 2 and a root-based choice at larger budgets up to ln 5.53.

  • Root analysis: The discriminant changes at ǫ=0.629598: below it the cubic has one real root, at it a multiple root, and above it three distinct real roots.These cases determine which roots can lie in the feasible domain for a.
  • Optimal parameter: For 0<ǫ≤0.629598, f1(a) increases monotonically, so the optimal parameter is a=0.The proof uses the sign of f′1(a) to establish this monotonicity.
  • Optimal parameter: When 0.629598<ǫ<ln 2, the relevant positive root lies above 2, so the feasible-domain optimum remains a=0.The other roots are outside the domain considered for a.
  • Optimal parameter: For ln 2≤ǫ≤ln 5.53, the proof identifies a positive root in (0,2), selects a1 as the correct root, and uses it for a.The remaining roots are negative or exceed the relevant domain.
  • Optimal parameter: For ǫ>ln 5.53, the analysis shows the derivative is negative over the feasible interval, so the optimum is attained at the interval boundary.The supplied passage identifies monotonic decrease but does not show the boundary value explicitly.

F. Proof of Lemma 5

The proof derives the worst-case variance of Three-Outputs by splitting the privacy budget at ln 4 and selecting the parameter regime that minimizes the variance.

  • Variance expression: The resulting worst-case variance is expressed piecewise, including 4(e^ǫ−1)^2 for ǫ>ln 5.53.The supplied passage shows the high-privacy-budget branch of the variance expression.

H. Proof of 2(eǫ −a)2(eǫ + t) −aeǫ(eǫ + 1)2 > 0.

The proof establishes that the expression 2(e^ǫ−a)^2(e^ǫ+t)−ae^ǫ(e^ǫ+1)^2 is positive for every ǫ>0. It then uses this result in the mechanism’s privacy and variance analysis.

  • Sign analysis: The proof divides the sign analysis into 0<ǫ≤ln 5.53 and ǫ>ln 5.53.Figure 20 is cited for the first range, while an algebraic argument handles the second.
  • Sign analysis: For 0<ǫ≤ln 5.53, the target expression is positive according to the case analysis and Figure 20.This is the first privacy-budget range considered in the proof.
  • Sign analysis: For ǫ>ln 5.53, the proof derives positivity from the corresponding factorized terms, completing the result for all ǫ>0.The conclusion is stated explicitly at the end of the proof.
  • Mechanism implications: The subsequent mechanism analysis uses exp(ǫ) as the privacy-dependent parameter and states that Algorithm 3 satisfies local differential privacy.The distribution is normalized using the defined interval endpoints and privacy parameter.
  • Mechanism implications: The discretization step preserves unbiasedness and does not increase conditional variance under the stated two-output construction.The proof uses p1+p2=1, unbiasedness, and the Cauchy–Schwarz inequality.

M. Proof of Lemma 10

The proof minimizes Hybrid’s worst-case variance by analyzing the coefficient and slope signs across privacy-budget intervals. The optimizer changes among β=0, β1, β3, and β4 according to the interval.

  • 0<ǫ<ln 2: For 0<ǫ<0.610986, the minimizing parameter is β=0; for 0.610986≤ǫ<ln 2, it is β=β1.The threshold is where slope2 changes sign.
  • 0<ǫ<ln 2: When 0<ǫ<0.610986, slope2>0; it equals zero at ǫ=0.610986 and becomes negative above that threshold.This sign change determines the low-budget optimizer transition.
  • ln 2≤ǫ≤ln 5.53: For ln 2≤ǫ≤ln 5.53, the proof selects β=β3 because its variance is lower than the variance at β=β1.The comparison is made after analyzing slope signs and the relevant root interval.
  • ǫ>ln 5.53: For ǫ>ln 5.53, the minimizing parameter is β=β4 in one interval and β=β1 when β lies in [β1,β2].The proof reports positive slope1 and slope2 in the latter interval.
  • Coefficient analysis: The coefficient A is positive below 0.610986, zero at 0.610986, and negative above it through the analyzed higher-budget ranges.The signs are established using derivative and figure-based arguments.

P. The sign of slope1 when ǫ > ln 5.53

For ǫ > ln 5.53, the analysis establishes the sign behavior of slope1 and slope2 and identifies numerical choices used to minimize worst-case variance.

  • For ǫ > ln 5.53, slope1 decreases monotonically when slope′1 < 0.The limiting value is lim ǫ→∞ slope1 = 0.
  • For slope2, the analysis likewise concludes slope2 > 0 for ǫ > ln 5.53.Its limit as ǫ approaches infinity is also zero.
  • For PM-SUB, minimizing f(s) and the maximum variance gives s = 2.5, corresponding to k = ǫ/2.5.This value is obtained from numerical experiments shown in Fig. 28.
  • The numerical experiments select s ≈ 2.5 for ln 2 < ǫ < ln 5.5 and for ǫ ≥ ln 5.5.The smaller-privacy range 0 < ǫ < ln 2 instead yields a root near s ≈ 2.18.

U. Proof of Lemma 11

The proof analyzes the hybrid mechanism’s worst-case variance by comparing endpoint variances and their dependence on β, then selects β according to slope and intersection cases.

  • The hybrid variance is evaluated as a maximum over x ∈ [−1,1], with interior and endpoint cases determined by the mechanism parameters.The analysis summarizes several parameter-dependent cases for maxx∈[−1,1] VarH[Y |x].
  • When both endpoint variances increase with β, the minimizing choice is β = β1; analogous monotonic cases select a boundary value.The proof also gives β = 1 in one corresponding case.
  • When endpoint variances change in opposite directions, the minimum occurs at βintersection when that intersection lies within [β1, β2].At the intersection, VarH[Y |1] and VarH[Y |0] are equal.
  • If the intersection lies outside the admissible interval, the minimizing β is selected from β1 or β2 according to which endpoint variance dominates.The proof handles the cases βintersection < β1 and βintersection > β2 separately.
  • If endpoint variances remain unchanged across β ∈ [β1, β2], any admissible β gives the same worst-case variance.This is stated as the proof’s Case 3.
Loading 2004.08856v2…