Graph-Homomorphic Perturbations for Private Decentralized Learning
  Decentralized algorithms for stochastic optimization and learning rely on the
diffusion of information as a result of repeated local exchanges of
intermediate estimates. Such structures are particularly appealing in
situations where agents may be hesitant to share raw data due to privacy
concerns. Nevertheless, in the absence of additional privacy-preserving
mechanisms, the exchange of local estimates, which are generated based on
private data can allow for the inference of the data itself. The most common
mechanism for guaranteeing privacy is the addition of perturbations to local
estimates before broadcasting. These perturbations are generally chosen
independently at every agent, resulting in a significant performance loss. We
propose an alternative scheme, which constructs perturbations according to a
particular nullspace condition, allowing them to be invisible (to first order
in the step-size) to the network centroid, while preserving privacy guarantees.
The analysis allows for general nonconvex loss functions, and is hence
applicable to a large number of machine learning and signal processing
problems, including deep learning.
