PaperlayerView exact revision on arXiv

Source-linked AI summary

DP-ADMM: ADMM-based Distributed Learning with Differential Privacy

Zonghao Huang, Rui Hu, Yuanxiong Guo, Eric Chan-Tin, Yanmin Gong

arXiv:1808.10101v6cs.LGstat.ML

TL;DR

Differentially private ADMM-based distributed learning can suffer utility loss and relies on restrictive objective-function assumptions. This paper proposes DP-ADMM, combining an approximate augmented Lagrangian with time-varying Gaussian noise and moments accounting, with theoretical and empirical evidence of convergence, utility, and end-to-end privacy guarantees.

  • Problem

    Prior differentially private ADMM methods can have low utility under strong privacy guarantees and often assume smooth, strongly convex objectives.

  • Method

    DP-ADMM combines an approximate augmented Lagrangian with time-varying Gaussian noise and uses moments accounting to analyze total privacy loss.

  • Results

    Theoretical analysis provides end-to-end privacy, convergence, and utility guarantees, while real-world evaluations demonstrate effectiveness under high privacy guarantees.

  • Takeaways & Limitations

    DP-ADMM is presented as a noise-resilient, computation-efficient method applicable to convex regularized empirical risk minimization and a wider class of distributed learning problems.

Abstract

from arXiv · show

Alternating Direction Method of Multipliers (ADMM) is a widely used tool for machine learning in distributed settings, where a machine learning model is trained over distributed data sources through an interactive process of local computation and message passing. Such an iterative process could cause privacy concerns of data owners. The goal of this paper is to provide differential privacy for ADMM-based distributed machine learning. Prior approaches on differentially private ADMM exhibit low utility under high privacy guarantee and often assume the objective functions of the learning problems to be smooth and strongly convex. To address these concerns, we propose a novel differentially private ADMM-based distributed learning algorithm called DP-ADMM, which combines an approximate augmented Lagrangian function with time-varying Gaussian noise addition in the iterative process to achieve higher utility for general objective functions under the same differential privacy guarantee. We also apply the moments accountant method to bound the end-to-end privacy loss. The theoretical analysis shows that DP-ADMM can be applied to a wider class of distributed learning problems, is provably convergent, and offers an explicit utility-privacy tradeoff. To our knowledge, this is the first paper to provide explicit convergence and utility properties for differentially private ADMM-based distributed learning algorithms. The evaluation results demonstrate that our approach can achieve good convergence and model accuracy under high end-to-end differential privacy guarantee.

I. INTRODUCTION

Distributed learning uses ADMM to coordinate local optimization while sharing intermediate parameters, but repeated messages can leak private information. The paper proposes DP-ADMM to provide end-to-end differential privacy with convergence, utility, and broader objective-function applicability.

  • Motivation: Distributed learning lets multiple entities collaborate on a common objective through local computation and message passing while keeping datasets unexposed.It can reduce computational burden and improve robustness and scalability.
  • ADMM-Based Distributed Learning: ADMM-based distributed learning is motivated partly by its O(1/t) convergence rate, compared with the typical O(1/√t) rate of subgradient methods.Here, t denotes the number of iterations.
  • Privacy Concern: Iterative sharing of ADMM parameters can leak sensitive information, while noise-based privacy methods may severely degrade performance under strong privacy guarantees.Prior private ADMM approaches also typically require smooth and strongly convex objective functions.
  • DP-ADMM: DP-ADMM combines an approximate augmented Lagrangian with time-varying Gaussian noise and uses moments accounting to analyze total privacy loss.The paper provides convergence and utility analysis for a wider class of distributed learning problems.
  • ADMM-Based Distributed Learning: ADMM divides learning into locally solved sub-problems and shares only intermediate parameters, with consensus constraints linking local and global models.The reformulation decouples the objective across agents while requiring local models to reach consensus.

III. ADMM WITH DIFFERENTIAL PRIVACY

The paper introduces DP-ADMM, combining an approximate augmented Lagrangian with time-varying Gaussian noise to provide private distributed learning with broader applicability and improved utility-privacy tradeoffs.

  • B. Our Approach: DP-ADMM combines an approximate augmented Lagrangian function with time-varying Gaussian noise to achieve differential privacy in ADMM-based distributed learning.The method is presented as an alternative to directly combining standard ADMM with primal variable perturbation.
  • B. Our Approach: DP-ADMM performs local agent updates, aggregator global-variable updates, and dual-variable updates iteratively for t iterations.The aggregator receives noisy primal variables before updating the global model.
  • B. Our Approach: The first-order approximation can yield a closed-form local update even for non-smooth objective functions.It also provides bounded l2 sensitivity without requiring smoothness and strong convexity.
  • B. Our Approach: The prox-function and decreasing step size encourage consistency with the previous model and smoother updates as iterations increase.The paper identifies the time-varying step size as significant for the overall convergence guarantee.
  • B. Our Approach: The Gaussian noise variance decreases with iteration number to mitigate noise effects and support stable updates.The noise is added to the primal variables shared with the aggregator.

IV. PRIVACY GUARANTEE

The privacy analysis bounds the sensitivity of DP-ADMM’s shared local primal updates and uses Gaussian noise whose scale varies across iterations.

  • IV. Privacy Guarantee: The privacy analysis estimates local-update sensitivity, analyzes each shared noisy primal variable, and prepares the end-to-end privacy calculation.The shared messages are the noisy local primal variables released across iterations.
  • IV. Privacy Guarantee: Gaussian noise is calibrated to the l2-norm sensitivity of the local primal-variable update function.The paper denotes neighboring datasets by Di and D.
  • IV. Privacy Guarantee: The sensitivity depends on the time-varying ηk_i, so decreasing ηk_i makes the sensitivity and fixed-ǫ noise magnitude smaller as k increases.The paper states that this supports stable updates despite the added noise.

B. (ǫ, δ)-Differential Privacy Guarantee

Each DP-ADMM iteration is shown to satisfy (ǫ, δ)-differential privacy for the released noisy primal variable.

  • B. (ǫ, δ)-Differential Privacy Guarantee: Each iteration of DP-ADMM guarantees (ǫ, δ)-differential privacy.The guarantee is stated for neighboring datasets and the released noisy local primal variable.
  • B. (ǫ, δ)-Differential Privacy Guarantee: The proof bounds the privacy loss and the probability of exceeding the ǫ threshold using the Gaussian mechanism’s normal-tail bound.The argument concludes with the per-iteration differential privacy guarantee.

C. Total Privacy Leakage

The paper extends per-iteration privacy to total privacy leakage with moments accounting and analyzes convergence and the utility-privacy tradeoff.

  • C. Total Privacy Leakage: Because the algorithm is a t-fold adaptive process, the moments accountant method is used to analyze total privacy leakage.This extends the per-iteration guarantee to an end-to-end analysis.
  • C. Total Privacy Leakage: The total guarantee is expressed as (ε̄, δ)-differential privacy with ε̄ = c0√tε for a constant c0.The supplied theorem statement gives the dependence on the number of iterations and per-iteration privacy parameter.
  • Convergence Analysis: Under convex, non-smooth objectives, DP-ADMM achieves an O(1/t) convergence rate in objective value and constraint violation.The consensus measure reaches zero when local and global models agree.
  • Convergence Analysis: Theorem 3 states that weaker privacy guarantees, with larger ǫ and δ, provide better utility.The paper presents this as an explicit utility-privacy tradeoff.

B. Smooth Convex Objective Function

For smooth convex objectives, the paper states convergence results under bounded second derivatives and relates privacy budgets to utility. It evaluates DP-ADMM on distributed logistic regression using convergence, accuracy, and computation-cost measures.

  • Smooth Convex Objective Function: Under convexity, smoothness, and bounded Hessians, Lemma 3 and Theorem 4 establish the assumptions used for the smooth-objective analysis.The stated bounds are ∥∇2ℓ(·)∥≤c3 and ∥∇2R(·)∥≤c4.
  • Smooth Convex Objective Function: Theorem 4 relates the privacy budget, represented by ǫ and δ, to DP-ADMM’s utility under smoothness.The paper also states that the algorithm converges toward the optimal result at rate O(1/.
  • Performance Evaluation: The experiments evaluate DP-ADMM on logistic regression with l1-norm and l2-norm regularizers, covering both non-smooth and smooth objectives.The evaluation considers convergence, accuracy, and computation cost.
  • Performance Evaluation: The study uses the Adult dataset and compares DP-ADMM with centralized, ADMM, PVP, DVP, and DPSGD baselines.The Adult dataset contains 48,842 instances and 14 attributes before preprocessing.
  • Performance Evaluation: With more distributed data sources, training accuracy decreases because smaller local datasets require more noise to maintain the same differential privacy level.This comparison is reported for l1-regularized logistic regression.

A. L1-Regularized Logistic Regression

For l1-regularized logistic regression, DP-ADMM handles the non-smooth convex objective and evaluates how distributed sources, privacy parameters, convergence, and accuracy affect performance.

  • Method: DP-ADMM applies to l1-regularized logistic regression, whose objective is convex but non-smooth.The method uses Theorem 3 for this setting.
  • Distributed sources: More distributed data sources reduce accuracy because smaller local datasets require more noise for the same differential privacy guarantee.The noise magnitude is scaled by 1/mi.
  • Convergence: Larger ǫ and larger δ produce better convergence of the augmented objective value.The observed behavior is reported as consistent with Theorem 3.
  • Accuracy: The evaluation compares DP-ADMM with ADMM and DPSGD using empirical loss and classification error rate.The comparison is conducted after fixing the number of agents at 100.
  • Conclusion: The paper presents DP-ADMM as noise-resilient, convergent, and computation-efficient under high privacy guarantee.Its design combines an approximate augmented Lagrangian with time-varying Gaussian noise and moments-accountant analysis of end-to-end privacy loss.

APPENDIX A LEMMA 4 (l2 SENSITIVITY OF PRIMAL VARIABLE UPDATE IN ALGORITHM 2)

The appendix derives the l2 sensitivity of DP-ADMM’s primal update under smoothness and strong-convexity assumptions, then uses log moments to bound total privacy loss.

  • Sensitivity assumptions: Lemma 4 assumes a smooth objective, a 1-strongly convex regularizer, and bounded loss gradients to analyze primal-update sensitivity.The sensitivity is expressed through neighboring datasets and the regularization and penalty parameters.
  • Sensitivity derivation: The proof combines smoothness, strong convexity, Cauchy–Schwarz, and bounded gradients to obtain the sensitivity result.The bound follows after dividing by the strong-convexity factor λ/n + ρ.
  • Privacy accounting: The moments accountant composes per-iteration privacy losses through their τth log moments to bound the overall privacy loss.A tail bound and minimization over τ yield the final bound on overall privacy loss.
  • Privacy mechanism: DP-ADMM uses a Gaussian mechanism with iteration-dependent variance σ^2_i,k to provide (ǫ, δ)-differential privacy.The proof represents the mechanism through Gaussian probability densities for adjacent outputs.

APPENDIX C LEMMA 5 USED IN THE PROOF OF LEMMA 2

Lemma 5 establishes a Bregman-divergence relation for convex differentiable functions, which the proof uses alongside optimality and convexity arguments.

  • Lemma statement: Lemma 5 defines Bregman divergence using a continuously differentiable, strictly convex function h.The scalar s is assumed nonnegative, and the vectors lie in R^d.
  • Proof setup: The proof begins from the optimality condition and the convexity of the local objective fi.These properties supply the inequalities used in the lemma’s derivation.
  • Proof steps: The derivation applies Algorithm 3’s update relations, separates the final three terms, and bounds them using Young’s inequality.Combining the resulting inequalities establishes the lemma’s stated result.
  • Proof conclusion: Combining inequalities (69)–(71) yields the result in Lemma 2.The appendix identifies this combination as the final step of the lemma proof.

APPENDIX E PROOF OF THEOREM 3

The proof of Theorem 3 uses convexity and operator monotonicity to relate DP-ADMM iterates to the optimal solution and derive the theorem’s convergence result.

  • Proof strategy: The proof invokes convexity of fi, monotonicity of F, and Lemma 2 to establish an inequality for DP-ADMM iterates.These properties provide the main analytic route to the theorem.
  • Optimality comparison: The argument evaluates the inequality at the optimal solution and then maximizes both sides over bounded dual variables.The feasible dual set is defined by ∥γi∥≤β.
  • Theorem conclusion: Taking expectations of the resulting inequality leads to the conclusion of Theorem 3.The theorem’s result follows after combining the deterministic inequality with the algorithm’s randomness.

APPENDIX F PROOF OF LEMMA 3

The proof of Lemma 3 uses smoothness, convexity, monotonicity, and standard inequalities to derive the stated result. It characterizes the relevant optimum and extends the inequality over a bounded set of γ_i values.

  • The proof assumes that ℓ(·) and R(·) are smooth and convex.
  • f_i(·) is established as (c3 + λc4/n)-Lipschitz smooth.The proof then invokes the property of Lipschitz smoothness.
  • Young’s inequality and earlier numbered relations are used to obtain the desired result.The cited proof step combines equations (86), (70), and (71).
  • Convexity of f_i(·), monotonicity of F(·), and Lemma 3 are combined to derive an intermediate inequality.
  • The inequality holds for all γ_i, including γ_i with ∥γ_i∥≤β, and γ_i is then chosen optimally.The proof identifies (w_i, w) with the optimal solution before this optimization step.
Loading 1808.10101v6…