Privacy-Preserving Distributed Zeroth-Order Optimization

Cristiano Gratton, Naveen K. D. Venkategowda, Reza Arablouei, Stefan WernerarXiv 2020 · DOI · arXiv

Abstract

We develop a privacy-preserving distributed algorithm to minimize a regularized empirical risk function when the first-order information is not available and data is distributed over a multi-agent network. We employ a zeroth-order method to minimize the associated augmented Lagrangian function in the primal domain using the alternating direction method of multipliers (ADMM). We show that the proposed algorithm, named distributed zeroth-order ADMM (D-ZOA), has intrinsic privacy-preserving properties. Unlike the existing privacy-preserving methods based on the ADMM where the primal or the dual variables are perturbed with noise, the inherent randomness due to the use of a zeroth-order method endows D-ZOA with intrinsic differential privacy. By analyzing the perturbation of the primal variable, we show that the privacy leakage of the proposed D-ZOA algorithm is bounded. In addition, we employ the moments accountant method to show that the total privacy leakage grows sublinearly with the number of ADMM iterations. D-ZOA outperforms the existing differentially private approaches in terms of accuracy while yielding the same privacy guarantee. We prove that D-ZOA converges to the optimal solution at a rate of $\mathcal{O}(1/M)$ where $M$ is the number of ADMM iterations. The convergence analysis also reveals a practically important trade-off between privacy and accuracy. Simulation results verify the desirable privacy-preserving properties of D-ZOA and its superiority over a state-of-the-art algorithm as well as its network-wide convergence to the optimal solution.

Introduction

In modern distributed learning, such as training models across thousands of edge devices, two major hurdles often collide: maintaining data privacy and handling "black-box" models where gradients are unavailable. Traditional privacy-preserving methods typically inject artificial noise into model updates, which acts like "static," making the final model less accurate.

This paper introduces D-ZOA (Distributed Zeroth-Order ADMM), a novel algorithm that addresses these hurdles simultaneously. By cleverly "recycling" the inherent randomness required for zeroth-order gradient estimation, D-ZOA provides differential privacy (DP) "for free," achieving significantly higher accuracy than existing methods that rely on external noise injection.

Methodology

The D-ZOA algorithm integrates three powerful mathematical frameworks:

  • ADMM (Alternating Direction Method of Multipliers): Decomposes large optimization problems into local sub-problems solvable by individual agents in a network.
  • Zeroth-Order (ZO) Optimization: Estimates gradients by comparing function values at perturbed points, a process that is naturally stochastic.
  • Intrinsic Differential Privacy: The authors prove that the noise inherent in ZO estimation is sufficient to satisfy DP requirements without adding extra artificial noise.

The total privacy leakage over multiple communication rounds is tracked using the Moments Accountant method, ensuring it grows sublinearly. For evaluation, the researchers used a synthetic distributed Lasso regression task on a 5-agent network topology.

Key Insights: The Privacy-Accuracy Trade-off

A central insight of this work is "noise recycling" — using a single source of randomness for both gradient estimation and privacy protection. However, this creates a fundamental trade-off: parameters that improve gradient estimation accuracy (like increasing the number of random samples $J$) can weaken the privacy guarantee.

Normalized error as a function of privacy parameters epsilon and delta, comparing D-ZOA and DP-ADMM.

As shown in the figure above, D-ZOA consistently maintains a lower error profile across various privacy regimes ($\epsilon$ and $\delta$) compared to the state-of-the-art DP-ADMM baseline. This demonstrates that D-ZOA can provide the same level of privacy while maintaining much higher model utility.

Experimental Results and Convergence

D-ZOA is mathematically proven to converge to the optimal global solution at a rate of $O(1/M)$, where $M$ is the number of iterations. Simulations confirm this theoretical result, showing robust performance even for non-smooth objective functions.

Convergence of D-ZOA vs DP-ADMM over 200 iterations for different delta values.

The convergence plots demonstrate that D-ZOA not only reaches a lower error floor than DP-ADMM but also does so efficiently, maintaining its advantage across different privacy budgets. The algorithm successfully converged even when the objective functions were non-smooth, a scenario where traditional gradient-based methods often fail.

Conclusion and Future Directions

D-ZOA represents a significant step forward in privacy-preserving distributed optimization by leveraging intrinsic noise. While currently focused on convex problems and small-scale networks, future research could extend these principles to non-convex deep learning tasks and larger, dynamic IoT environments. Additionally, refining the sensitivity of privacy to smoothing constants remains an area for further optimization to ensure high precision does not compromise data protection.

Summary updated

Abstract

We develop a privacy-preserving distributed algorithm to minimize a regularized empirical risk function when the first-order information is not available and data is distributed over a multi-agent network. We employ a zeroth-order method to minimize the associated augmented Lagrangian function in the primal domain using the alternating direction method of multipliers (ADMM). We show that the proposed algorithm, named distributed zeroth-order ADMM (D-ZOA), has intrinsic privacy-preserving properties. Unlike the existing privacy-preserving methods based on the ADMM where the primal or the dual variables are perturbed with noise, the inherent randomness due to the use of a zeroth-order method endows D-ZOA with intrinsic differential privacy. By analyzing the perturbation of the primal variable, we show that the privacy leakage of the proposed D-ZOA algorithm is bounded. In addition, we employ the moments accountant method to show that the total privacy leakage grows sublinearly with the number of ADMM iterations. D-ZOA outperforms the existing differentially private approaches in terms of accuracy while yielding the same privacy guarantee. We prove that D-ZOA converges to the optimal solution at a rate of $\mathcal{O}(1/M)$ where $M$ is the number of ADMM iterations. The convergence analysis also reveals a practically important trade-off between privacy and accuracy. Simulation results verify the desirable privacy-preserving properties of D-ZOA and its superiority over a state-of-the-art algorithm as well as its network-wide convergence to the optimal solution.
BibTeX
@misc{gratton2020privacy,
  author = {Cristiano Gratton and Naveen K. D. Venkategowda and Reza Arablouei and Stefan Werner},
  title = {{Privacy-Preserving Distributed Zeroth-Order Optimization}},
  year = {2020},
  eprint = {2008.13468},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2008.13468},
}
Figure