Local Differential Privacy for Distributed Stochastic Aggregative Optimization with Guaranteed Optimality

Ziqin Chen, Yongqiang Wang

Abstract

Distributed aggregative optimization underpins many cooperative optimization and multi-agent control systems, where each agent's objective function depends both on its local optimization variable and an aggregate of all agents' optimization variables. Existing distributed aggregative optimization approaches typically require access to accurate gradients of the objective functions, which, however, are often hard to obtain in real-world applications. We propose an algorithm that can solve both problems with existing distributed aggregative optimization approaches: not only can the proposed algorithm guarantee mean-square convergence to an exact optimal solution when the gradients are subject to noise, it also simultaneously ensures rigorous differential privacy, with the cumulative privacy budget guaranteed to be finite even when the number of iterations tends to infinity. To the best of our knowledge, this is the first algorithm able to guarantee both accurate convergence and rigorous differential privacy in distributed aggregative optimization.

Introduction

In multi-agent systems such as electric vehicle charging coordination, warehouse robot surveillance, or personalized machine learning, an agent's objective function often depends on the aggregate behavior of the entire group. This framework, known as aggregative optimization, faces two critical real-world challenges: stochasticity and privacy.

In practice, agents operate with noisy gradients due to data sampling and imperfect estimates of the group's aggregate state. Furthermore, sharing updates can leak sensitive raw data. While Differential Privacy (DP) offers protection, the addition of DP noise typically degrades the final solution's accuracy. Moreover, in iterative algorithms, the "privacy budget" often grows boundlessly over time, eventually compromising privacy if the algorithm runs long enough.

Methodology: Algorithm 1

The proposed Algorithm 1 introduces a novel architecture to decouple noise accumulation from the optimization process. Unlike standard "gradient tracking" frameworks that accumulate Laplace noise, this approach utilizes a Robust Tracking Architecture. This architecture employs two robust tracking operations followed by a dynamic average-consensus-based gradient descent step.

Local Differential Privacy (LDP) and Diminishing Sensitivity

Privacy is managed at the agent level. Each agent perturbs their shared variables locally using Laplace noise. To ensure the cumulative privacy budget remains finite over an infinite time horizon, the algorithm utilizes meticulously designed decaying rates for stepsizes and DP-noise variances. As the algorithm converges, its sensitivity to individual data points drops faster than noise is added, effectively "capping" the total privacy leakage.

Figure 4: Training loss comparison showing how Algorithm 1 avoids the divergent behaviors caused by DP-noise accumulation in existing methods.

Experimental Evaluation

The algorithm was evaluated on a personalized machine learning task using the MNIST and CIFAR-10 datasets. In these simulations, agents had access to heterogeneous, biased subsets of data, requiring collaboration to build a robust global model.

Key Results

  • Convergence and Stability: Algorithm 1 achieves a convergence rate of approximately $O(T^{-0.5})$ across nonconvex, convex, and strongly convex functions. While state-of-the-art (SOTA) methods often diverge or suffer from massive steady-state errors when privacy noise is introduced, Algorithm 1 remains stable.
  • Privacy Efficiency: The algorithm maintains a tighter privacy guarantee compared to existing mechanisms. Crucially, it demonstrates that the "privacy tax" is quantifiable: stricter privacy requirements (smaller $\epsilon$) directly correlate to reduced convergence rates, yet exact convergence remains achievable.
Figure 2: Comparison of cumulative privacy budgets, demonstrating that Algorithm 1 achieves lower or equal privacy costs compared to SOTA mechanisms.

Conclusion

This work provides the first distributed aggregative optimization algorithm that guarantees both exact mean-square convergence and rigorous local differential privacy with a finite cumulative budget. By breaking the cycle of noise accumulation through robust tracking, the proposed method allows for long-term private distributed learning without sacrificing final model accuracy. Future work will explore extending this architecture to directed and time-varying network topologies.

Summary updated

Abstract

Distributed aggregative optimization underpins many cooperative optimization and multi-agent control systems, where each agent's objective function depends both on its local optimization variable and an aggregate of all agents' optimization variables. Existing distributed aggregative optimization approaches typically require access to accurate gradients of the objective functions, which, however, are often hard to obtain in real-world applications. For example, in machine learning, gradients are commonly contaminated by two main sources of noise: the randomness inherent in sampled data, and the additional variability introduced by mini-batch computations. In addition to the issue of relying on accurate gradients, existing distributed aggregative optimization approaches require agents to share explicit information, which could breach the privacy of participating agents. We propose an algorithm that can solve both problems with existing distributed aggregative optimization approaches: not only can the proposed algorithm guarantee mean-square convergence to an exact optimal solution when the gradients are subject to noise, it also simultaneously ensures rigorous differential privacy, with the cumulative privacy budget guaranteed to be finite even when the number of iterations tends to infinity. To the best of our knowledge, this is the first algorithm able to guarantee both accurate convergence and rigorous differential privacy in distributed aggregative optimization. Besides characterizing the convergence rates under nonconvex/convex/strongly convex conditions, we also rigorously quantify the cost of differential privacy in terms of convergence rates. Experimental results on personalized machine learning using benchmark datasets confirm the efficacy of the proposed algorithm.
BibTeX
@misc{chen2025local,
  author = {Ziqin Chen and Yongqiang Wang},
  title = {{Local Differential Privacy for Distributed Stochastic Aggregative Optimization with Guaranteed Optimality}},
  year = {2025},
  eprint = {2506.15106},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2506.15106},
}
Figure