Differentially Private Distributed Online Convex Optimization Towards Low Regret and Communication Cost
Jiandong Liu, Lan Zhang, Xiaojing Yu, Xiang‐Yang Li · 2023
Distributed online convex optimization (DOCO) has emerged as a promising approach in scenarios where multiple learners collaboratively serve sequential (possibly untrusted) clients using AI models. However, ensuring clients' privacy and minimizing regret while keeping the communication cost reasonable poses a significant challenge. To address this issue, we propose private DOCO algorithms, termed PDOM, for both oblivious and stochastic settings. Our approach involves a mini-batch strategy that optimally balances the effects of slower model updates and differential privacy (DP) perturbation. Our theoretical analysis shows that compared to state-of-the-art algorithms, PDOM reduces the regret bounds and communication cost by an O(d/ε) factor for the oblivious setting. For the stochastic setting, the impact of DP perturbation becomes negligible if the learning time T = Ω(d4/(nε4)) provided that the loss functions are Lipschitz, convex, and smooth, where d is the model dimension, n is the number of learners, and ε is the privacy budget. Our evaluations validate these results, demonstrating that PDOM can reduce classification error rates of the state-of-the-art methods by up to 20% in distributed online logistic regression tasks while achieving communication savings of above 90%.