Privacy Amplification by Iteration for ADMM with (Strongly) Convex
  Objective Functions
T-H. Hubert Chan Hao Xie Mengshi Zhao
We examine a private ADMM variant for (strongly) convex objectives which is a
primal-dual iterative method. Each iteration has a user with a private function
used to update the primal variable, masked by Gaussian noise for local privacy,
without directly adding noise to the dual variable. Privacy amplification by
iteration explores if noises from later iterations can enhance the privacy
guarantee when releasing final variables after the last iteration. Cyffers et
al. [ICML 2023] explored privacy amplification by iteration for the proximal
ADMM variant, where a user's entire private function is accessed and noise is
added to the primal variable. In contrast, we examine a private ADMM variant
requiring just one gradient access to a user's function, but both primal and
dual variables must be passed between successive iterations. To apply Balle et
al.'s [NeurIPS 2019] coupling framework to the gradient ADMM variant, we tackle
technical challenges with novel ideas. First, we address the non-expansive
mapping issue in ADMM iterations by using a customized norm. Second, because
the dual variables are not masked with any noise directly, their privacy
guarantees are achieved by treating two consecutive noisy ADMM iterations as a
Markov operator. Our main result is that the privacy guarantee for the gradient
ADMM variant can be amplified proportionally to the number of iterations. For
strongly convex objective functions, this amplification exponentially increases
with the number of iterations. These amplification results align with the
previously studied special case of stochastic gradient descent.