Research On Privacy-preserving Distributed Optimization Algorithms

Distributed optimization is a hot issue in current research,which is widely used in largescale machine learning,smart grid,wireless sensor networks and other fields.Communication between the agents is required in the distributed optimization algorithms,which on the one hand will bring about the privacy leakage problem and on the other hand,the communication in large scale network always suffers from excessive energy consumption,limited communication bandwidth and some other problems.Therefore,the privacy preserving and communication efficiency have become important indicators to measure the performance of the algorithm.However,the existing privacy-preserving algorithms often face the problems of high communication cost and high computation burden in a single iteration.To overcome the above problems,this thesis considers privacy preserving,communication efficiency and reducing computation burden comprehensively in design of distributed optimization algorithms.Based on the distributed alternating direction multiplier method(ADMM)and using event-triggered communication mechanisms,function approximation methods,random disturbance strategies,this thesis proposed two types of privacy-preserving distributed optimization algorithms.Specifically,1.In this thesis,a second-order privacy-preserving algorithm with high communication efficiency,PC-DQM,is proposed for the scenario with limited communication.To reduce the communication cost,PC-DQM uses the event-triggered communication mechanism to censor each communication.Moreover,by the second-order approximation of the objective function and perturbing the Hessian of the approximated objective function,PC-DQM can achieve privacy preserving and avoid excessive computation burden caused by solving subproblems.Theoretical analysis shows that PC-DQM can linearly converge to the optimal solution and preserve the privacy.Experiments show that PC-DQM can not only solve the distributed optimization problem correctly but also preserve privacy and reduce communication burden at the same time.Compared with the existing privacy-preserving algorithms,PC-DQM can preserve privacy while reduce communication burden.Moreover,compared with the second-order approximation ADMM algorithm,PC-DQM not only achieves privacy preserving,but the communication cost is smaller.2.To further reduce the computation burden of a single iteration in the privacy-preserving algorithm,this thesis proposes a differentially private first-order algorithm DP-DLM.In order to reduce the computation burden,DP-DLM performs a first-order approximation on the objective function,so that the primal update shares a closed-form solution that only requires gradient information.Moreover,to achieve differential privacy while ensuring a faster convergence rate,DP-DLM inserts Gaussian noise with linearly(sublinearly)decaying variance to the primal variables.Theoretical analysis shows that DP-DLM can linearly(sublinearly)converge to the optimal solution and is differentially private.The experimental results show that dispite of the existence of privacy preserving and first-order approximation,the accuracy of DP-DLM does not decrease too much in the scenarios where privacy-preserving requirements are not very strict.In the scenarios with high privacy-preserving requirements,compared with the existing differential privacy algorithms based on ADMM,DP-DLM has certain advantages in accuracy and computation burden.The research results of this thesis provide feasible ideas for privacy-preserving distributed optimization algorithms to improve communication efficiency and reduce computation burden,enrich the research on privacy preserving of distributed optimization algorithms,improve the practicability of the privacy-preserving algorithms,and have important theoretical and practical significance.