Search

Communication compression techniques are of growing interests for solving the decentralized optimization problem under limited communication, where the global objective is to minimize the average of local cost functions over a multiagent network using only local computation and peer-to-peer communication. In this article, we propose a novel compressed gradient tracking algorithm (C-GT) that combines gradient tracking technique with communication compression. In particular, C-GT is compatible with a general class of compression operators that unifies both unbiased and biased compressors. We show that C-GT inherits the advantages of gradient tracking-based algorithms and achieves linear convergence rate for strongly convex and smooth objective functions. Numerical examples complement the theoretical findings and demonstrate the efficiency and flexibility of the proposed algorithm. [ABSTRACT FROM AUTHOR]

This article studies the problem of distributed optimization in multiagent systems where each agent seeks to minimize the sum of all agents’ objective functions using only local information. Under the requirement of security, each agent needs to keep its objective function private from other agents and potential eavesdroppers. We first prove the impossibility of guaranteeing convergence and differential privacy simultaneously by perturbing states in exact distributed optimization algorithms. Motivated by this result, we design a completely distributed algorithm, Distributed algorithm via Direction and State Perturbation (DiaDSP), that achieves differential privacy by perturbing both states and directions with decaying Laplace noise. Different from most of the existing works that require decaying stepsizes to ensure convergence, we show that our DiaDSP algorithm converges in mean and almost surely even with a constant stepsize. In particular, we prove linear convergence in mean by only assuming that the sum of all cost functions is strongly convex. The R-linear convergence is proved under the assumption of Lipschitz gradients instead of that of bounded gradients. The optimal stepsize for the fastest convergence rate is also established. Moreover, we describe the privacy properties and characterize the tradeoff between differential privacy and convergence accuracy. Simulations are conducted on a typical sensor fusion problem to validate the theoretical results. [ABSTRACT FROM AUTHOR]

This article studies a class of nonsmooth decentralized multiagent optimization problems where the agents aim at minimizing a sum of local strongly-convex smooth components plus a common nonsmooth term. We propose a general primal-dual algorithmic framework that unifies many existing state-of-the-art algorithms. We establish linear convergence of the proposed method to the exact minimizer in the presence of the nonsmooth term. Moreover, for the more general class of problems with agent specific nonsmooth terms, we show that linear convergence cannot be achieved (in the worst case) for the class of algorithms that uses the gradients and the proximal mappings of the smooth and nonsmooth parts, respectively. We further provide a numerical counterexample that shows how some state-of-the-art algorithms fail to converge linearly for strongly convex objectives and different local non smooth terms. [ABSTRACT FROM AUTHOR]

In this paper, we focus on robust sparse M -estimation over decentralized networks in the presence of Byzantine attacks. In particular, a decentralized network is modeled as an undirected graph without a central node, while a small fraction of nodes usually behave arbitrarily and send erroneous information due to system breakdowns, cyber attacks and so on. To address the Byzantine issue, some pre-determined robust aggregation rules are applied. Moreover, the gradient tracking and proximal algorithm are combined to ensure convergence and sparsity simultaneously. Theoretically, our proposed algorithms are provably robust against Byzantine attacks and achieve linear convergence rates. The finite-sample performance is studied through numerical experiments under various settings and an application to Communities and Crime Data is also presented. [ABSTRACT FROM AUTHOR]