Online learning has been in the spotlight from the machine learning society for a long time. To handle massive data in Big Data era, one single learner could never efficiently finish this heavy task. Hence, in this paper, we propose a novel distributed online learning algorithm to solve the problem. Comparing to typical centralized online learner, the distributed learners optimize their own learning parameters based on local data sources and timely communicate with neighbors. However, communication may lead to a privacy breach. Thus, we use differential privacy to preserve the privacy of learners, and study the influence of guaranteeing differential privacy on the utility of the distributed online learning algorithm. Furthermore, by using the results from Kakade and Tewari (2009), we use the regret bounds of online learning to achieve fast convergence rates for offline learning algorithms in distributed scenarios, which provides tighter utility performance than the existing state-of-the-art results. In simulation, we demonstrate that the differentially private offline learning algorithm has high variance, but we can use mini-batch to improve the performance. Finally, the simulations show that the analytical results of our proposed theorems are right and our private distributed online learning algorithm is a general framework.
The method to solve distributed online learning was pioneered in distributed optimization. Hazan has studied online convex optimization in his book @cite_5 . They proposed that the framework of convex online learning is closely tied to statistical learning theory and convex optimization. @cite_11 developed an efficient algorithm for distributed optimization based on dual averaging of subgradients method. They demonstrated that their algorithm could work, even the communication matrix is random and not fixed. Nedic and Ozdaglar @cite_6 considered a subgradient method for distributed convex optimization, where the functions are convex but not necessarily smooth. They demonstrated that a time-variant communication could ensure the convergence of the distributed optimization algorithm. @cite_1 tried to analyze the influence of stochastic subgradient errors on distributed convex optimization based on a time-variant network topology. They studied the convergence rate of their distributed optimization algorithm. Our work extends the works of Nedic and Ozdaglar @cite_6 and @cite_1 . All these papers have made great contributions to distributed convex optimization, but they did not consider the privacy-preserving problem.
@cite_5 @cite_1 @cite_6 @cite_11
2066332749 2044212084 2556913586
We consider a distributed multi-agent network system where the goal is to minimize a sum of convex objective functions of the agents subject to a common convex constraint set. Each agent maintains an iterate sequence and communicates the iterates to its neighbors. Then, each agent combines weighted averages of the received iterates with its own iterate, and adjusts the iterate by using subgradient information (known with stochastic errors) of its own function and by projecting onto the constraint set. We study a distributed computation model for optimizing a sum of convex objective functions corresponding to multiple agents. For solving this (not necessarily smooth) optimization problem, we consider a subgradient method that is distributed among the agents. The method involves every agent minimizing his her own objective function while exchanging information locally with other agents in the network over a time-varying topology. We provide convergence results and convergence rate estimates for the subgradient method. Our convergence rate results explicitly characterize the tradeoff between a desired accuracy of the generated approximate optimal solutions and the number of iterations needed to achieve the accuracy. The focus of this paper is the development and analysis of distributed algorithms for solving convex optimization problems that are defined over networks. Such network-structured optimization problems arise in a variety of application domains within the information sciences and engineering. For instance, problems such as multi-agent coordination, distributed tracking and localization, estimation problems in sensor networks and packet routing are all naturally cast as distributed convex minimization [2], [11], [10], [16], [20]. Common to these problems is the necessity for completely decentralized computation that is locally light — so as to avoid overburdening small sensors or flooding busy networks — and robust to periodic link or node failures. As a second example, data sets that are too large to be processed quickly by any single processor present related challenges. A canonical example that arises in statistical machine learning is the problem of minimizing a loss function averaged over a large dataset (e.g., optimization in support vector machines [5]). With terabytes of data, it is desirable to assign smaller subsets of the data to different processors, and the processors must communicate to find parameters that minimize the loss over the entire dataset. However, the communication should be efficient enough that network latencies do not offset computational gains.