We consider distributed optimization where @math nodes in a connected network minimize the sum of their local costs subject to a common constraint set. We propose a distributed projected gradient method where each node, at each iteration @math , performs an update (is active) with probability @math , and stays idle (is inactive) with probability @math . Whenever active, each node performs an update by weight-averaging its solution estimate with the estimates of its active neighbors, taking a negative gradient step with respect to its local cost, and performing a projection onto the constraint set; inactive nodes perform no updates. Assuming that nodes' local costs are strongly convex, with Lipschitz continuous gradients, we show that, as long as activation probability @math grows to one asymptotically, our algorithm converges in the mean square sense (MSS) to the same solution as the standard distributed gradient method, i.e., as if all the nodes were active at all iterations. Moreover, when @math grows to one linearly, with an appropriately set convergence factor, the algorithm has a linear MSS convergence, with practically the same factor as the standard distributed gradient method. Simulations on both synthetic and real world data sets demonstrate that, when compared with the standard distributed gradient method, the proposed algorithm significantly reduces the overall number of per-node communications and per-node gradient evaluations (computational cost) for the same required accuracy.
. Distributed methods of this type date back at least to the 80s, e.g., @cite_52 , and have received renewed interest in the past decade, e.g., @cite_18 . Reference @cite_18 proposes the distributed (sub)gradient method with a constant step-size, and analyzes its performance under time-varying communication networks. Reference @cite_50 considers distributed (sub)gradient methods under random communication networks with failing links and establishes almost sure convergence under a diminishing step-size rule. A major difference of our paper from the above works is that, in @cite_52 @cite_18 @cite_50 , only inter-node communications over iterations are sparsified,'' while each node performs gradient evaluations at each iteration @math . @cite_32 , the authors propose a gossip-like scheme where, at each @math , only two neighboring nodes in the network wake up and perform weight-averaging (communication among them) and a negative gradient step with respect to their respective local costs, while the remaining nodes stay idle. The key difference with respect to our paper is that, with our method, the number of active nodes over iterations @math (on average) is increasing, while in @cite_32 it remains equal to two for all @math . Consequently, the established convergence properties of the two methods are very different.
@cite_18 @cite_32 @cite_52 @cite_50
2782375002 1997250627 2962782955 2291950750
Recently, there has been significant progress in the development of distributed first-order methods. In particular, (2015) on the one hand and Qu and Li (2017) and (2016) on the other hand propose two different types of methods that are designed from very different perspectives. They achieve both exact and linear convergence when a constant step size is used—a favorable feature that was not achievable by most prior methods. In this paper, we unify, generalize, and improve convergence speed of the methods by (2015), Qu and Li (2017), and (2016), when the underlying network is static and undirected. We first carry out a unifying primal-dual analysis that sheds light on how these methods compare. The analysis reveals that a major difference between the methods is on how the primal error affects the dual error along iterations. We, then, capitalize on the insights from the analysis to derive a novel method that can reduce the negative effect of the primal error on the dual error. We establish for the proposed generalized method global R-linear convergence rate under strongly convex costs with Lipschitz continuous gradients. We present a distributed proximal-gradient method for optimizing the average of convex functions, each of which is the private local objective of an agent in a network with time-varying topology. The local objectives have distinct differentiable components, but they share a common nondifferentiable component, which has a favorable structure suitable for effective computation of the proximal operator. In our method, each agent iteratively updates its estimate of the global minimum by optimizing its local objective function, and exchanging estimates with others via communication in the network. Using Nesterov-type acceleration techniques and multiple communication steps per iteration, we show that this method converges at the rate 1 k (where k is the number of communication rounds between the agents), which is faster than the convergence rate of the existing distributed methods for solving this problem. The superior convergence rate of our method is also verified by numerical experiments. We propose a new distributed algorithm based on alternating direction method of multipliers (ADMM) to minimize sum of locally known convex functions using communication over a network. This optimization problem emerges in many applications in distributed machine learning and statistical estimation. Our algorithm allows for a general choice of the communication weight matrix, which is used to combine the iterates at different nodes. We show that when functions are convex, both the objective function values and the feasibility violation converge with rate @math , where @math is the number of iterations. We then show that when functions are strongly convex and have Lipschitz continuous gradients, the sequence generated by our algorithm converges linearly to the optimal solution. In particular, an @math -optimal solution can be computed with @math iterations, where @math is the condition number of the problem. Our analysis highlights the effect of network and communication weights on the convergence rate through degrees of the nodes, the smallest nonzero eigenvalue, and operator norm of the communication matrix. In this paper we propose a distributed version of a randomized block-coordinate descent method for minimizing the sum of a partially separable smooth convex function and a fully separable non-smooth convex function. Under the assumption of block Lipschitz continuity of the gradient of the smooth function, this method is shown to have a sublinear convergence rate. Linear convergence rate of the method is obtained for the newly introduced class of generalized error bound functions. We prove that the new class of generalized error bound functions encompasses both global local error bound functions and smooth strongly convex functions. We also show that the theoretical estimates on the convergence rate depend on the number of blocks chosen randomly and a natural measure of separability of the objective function.