Recycled ADMM: Improve Privacy and Accuracy with Less Computation in Distributed Algorithms.

Xueru Zhang, Mohammad Mahdi Khalili, Mingyan Liu

Introduction

Distributed machine learning enables multiple nodes to collaborate on training a global model without sharing raw datasets. While the Alternating Direction Method of Multipliers (ADMM) is a popular tool for this due to its fast convergence, its iterative nature presents two major challenges: significant privacy leakage under Differential Privacy (DP) frameworks and high computational costs for resource-constrained devices.

The Recycled ADMM Framework

To address these issues, we propose Recycled ADMM (R-ADMM). The core innovation is an alternating update scheme that "recycles" information to minimize data access. In odd iterations, nodes perform a standard private ADMM update using raw local data. In even iterations, nodes use a linear approximation of the objective function, recycling the gradient from the previous step.

Convergence of average loss for different network sizes ($N=5, 20$) and penalty parameters ($\gamma$).

Because even iterations do not touch raw data, they incur zero additional privacy loss due to the post-processing property of DP. This effectively doubles the training progress possible for a fixed privacy budget while reducing the computational load per iteration.

Experimental Evaluation

R-ADMM was evaluated using the UCI Adult dataset for binary classification, predicting whether an individual's annual income exceeds $50,000. The dataset, comprising 45,223 individuals with 105 features, was distributed across networks of $N=5$ and $N=20$ nodes.

Results and Discussion

Experimental results demonstrate that R-ADMM significantly outperforms existing methods such as standard Private ADMM (DVP) and M-ADMM.

Accuracy and Privacy Tradeoff

R-ADMM consistently achieves lower average loss for the same total privacy budget. By halving the frequency of raw data access, the algorithm allows for more iterations before reaching the privacy limit, leading to superior model utility.

Accuracy and privacy comparison of R-ADMM against ADMM (DVP) and M-ADMM across different privacy levels ($\alpha$).

Stability and Efficiency

The linear approximation used in even steps replaces complex optimization sub-problems with direct calculations, drastically reducing per-iteration costs. While these approximations can introduce minor oscillations, the standard updates in odd steps ensure the algorithm remains stable and converges reliably.

Conclusion

R-ADMM provides a robust framework for private distributed learning, offering a superior privacy-utility tradeoff and reduced computational requirements. Future work will explore extending this recycling strategy to non-convex objectives, such as deep neural networks.

Summary updated

Abstract

Alternating direction method of multiplier (ADMM) is a powerful method to solve decentralized convex optimization problems. In distributed settings, each node performs computation with its local data and the local results are exchanged among neighboring nodes in an iterative fashion. During this iterative process the leakage of data privacy arises and can accumulate significantly over many iterations, making it difficult to balance the privacy-utility tradeoff. In this study we propose Recycled ADMM (R-ADMM), where a linear approximation is applied to every even iteration, its solution directly calculated using only results from the previous, odd iteration. It turns out that under such a scheme, half of the updates incur no privacy loss and require much less computation compared to the conventional ADMM. We obtain a sufficient condition for the convergence of R-ADMM and provide the privacy analysis based on objective perturbation.
BibTeX
@inproceedings{zhang2018recycled,
  author = {Xueru Zhang and Mohammad Mahdi Khalili and Mingyan Liu},
  title = {{Recycled ADMM: Improve Privacy and Accuracy with Less Computation in Distributed Algorithms.}},
  booktitle = {Allerton},
  year = {2018},
  url = {https://openreview.net/forum?id=jrc_Io-FK7o},
}
Figure