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.
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.
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