Distributed Optimization Over Time-Varying Directed Graphs

TLDR

Distributed optimization seeks to minimize the sum of convex functions held by a network of nodes. The authors propose a broadcast‑based subgradient‑push algorithm that drives all nodes to the global optimum when each node knows its out‑degree. The algorithm operates over a uniformly strongly connected, time‑varying directed graph, using local subgradients and out‑degree information to update node states. The subgradient‑push converges at rate O(ln t √t) without requiring knowledge of the agent count or graph sequence, with the convergence constant influenced by initial states, subgradient norms, network diffusion speed, and node influence imbalances.

Abstract

We consider distributed optimization by a collection of nodes, each having access to its own convex function, whose collective goal is to minimize the sum of the functions. The communications between nodes are described by a time-varying sequence of directed graphs, which is uniformly strongly connected. For such communications, assuming that every node knows its out-degree, we develop a broadcast-based algorithm, termed the subgradient-push, which steers every node to an optimal value under a standard assumption of subgradient boundedness. The subgradient-push requires no knowledge of either the number of agents or the graph sequence to implement. Our analysis shows that the subgradient-push algorithm converges at a rate of O(\ln t √t). The proportionality constant in the convergence rate depends on the initial values at the nodes, the subgradient norms and, more interestingly, on both the speed of the network information diffusion and the imbalances of influence among the nodes.