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.
Our paper is also related to reference @cite_42 , which considers diffusion algorithms with two types of nodes -- informed and uninformed. The informed nodes both: 1) acquire measurements and perform in-network processing (which translates into computing gradients in our scenario); and 2) perform consultation with neighbors (which translates into weight-averaging the estimates across neighborhoods), while the uninformed nodes only perform the latter task. The authors study the effect of the proportion of informed nodes and their distribution in space. A key difference with respect to our work is that the uninformed nodes in @cite_42 still perform weight-averaging, while the idle nodes here perform no processing. Finally, we comment on reference @cite_38 which introduces an adaptive policy for each node to decide whether it will communicate with its neighbors or not and demonstrate significant savings in communications with respect to the always-communicating scenario. A major difference of @cite_38 from our paper is that, with @cite_38 , nodes always perform local gradients, i.e., they do not stay idle (in the sense defined here).
@cite_38 @cite_42
2541688248 2112827165
Methods for distributed optimization are necessary to solve large-scale problems such as those becoming more common in machine learning. The communication cost associated with transmitting large messages can become a serious performance bottleneck. We propose a consensus-based distributed algorithm to minimize a convex separable objective. Each node holds one component of the objective function, and the nodes alternate between a computation phase, where local gradient steps are performed based on the local objective, and a communication phase, where consensus steps are performed to bring the local states into agreement. The nodes use local decision rules to adaptively determine when communication is not necessary. This results in significantly lower communication costs and allows a user to tradeoff the amount of communication with the accuracy of the final output. Experiments on a cluster using simulated and real datasets illustrate the tradeoff. Adaptive networks consist of a collection of agents with adaptation and learning abilities. The agents interact with each other on a local level and diffuse information across the network through their collaboration. In this work, we consider two types of agents: informed agents and uninformed agents. The former receive new data regularly and perform consultation and in-network processing, while the latter do not collect data and only participate in the consultation tasks. We examine the performance of LMS diffusion strategies for distributed estimation over networks as a function of the proportion of informed agents and their distribution in space. The results reveal some interesting trade-offs between convergence rate and mean-square performance. In particular, among other results, it is shown that the mean-square performance of adaptive networks does not necessarily improve with a larger proportion of informed agents. Instead, it is established that if the set of informed agents is enlarged, the convergence rate of the network becomes faster albeit at the expense of some deterioration in mean-square performance. The results further establish that uninformed agents play an important role in determining the steady-state performance of the network and that it is preferable to keep some of the highly noisy or highly connected agents uninformed. The arguments reveal an important interplay among three factors: the number and distribution of informed agents in the network, the convergence rate of the learning process, and the estimation accuracy in steady-state. Expressions that quantify these relations are derived, and simulations are included to support the theoretical findings. We illustrate application of the results to two network models, namely, the Erdos-Renyi and scale-free models.