Abstract
In this note, we extend the algorithms Extra and subgradient-push to a new algorithm ExtraPush for consensus optimization with convex differentiable objective functions over a directed network. When the stationary distribution of the network can be computed in advance, we propose a simplified algorithm called Normalized ExtraPush. Just like Extra, both ExtraPush and Normalized ExtraPush can iterate with a fixed step size. But unlike Extra, they can take a column-stochastic mixing matrix, which is not necessarily doubly stochastic. Therefore, they remove the undirected-network restriction of Extra. Subgradient-push, while also works for directed networks, is slower on the same type of problem because it must use a sequence of diminishing step sizes. We present preliminary analysis for ExtraPush under a bounded sequence assumption. For Normalized ExtraPush, we show that it naturally produces a bounded, linearly convergent sequence provided that the objective function is strongly convex. In our numerical experiments, ExtraPush and Normalized ExtraPush performed similarly well. They are significantly faster than subgradient-push, even when we hand-optimize the step sizes for the latter.
Introduction
Decentralized optimization involves a group of $n$ agents working together to minimize a global objective function $f(x) = \sum_{i=1}^n f_i(x)$. Each agent $i$ possesses only its local cost function $f_i$ and must communicate with neighbors to reach a consensus on the global optimal solution. While many efficient algorithms exist for undirected networks—where communication is symmetric—real-world scenarios often involve directed networks. In such environments, communication links may be unidirectional, such as a high-power transmitter broadcasting to a low-power receiver.
Standard fast algorithms like Extra rely on doubly stochastic mixing matrices, which are generally unavailable in directed graphs. Conversely, methods designed for directed graphs, such as subgradient-push, typically require diminishing step sizes to handle the bias introduced by asymmetric communication, leading to sublinear convergence rates. This paper introduces ExtraPush, an algorithm that achieves linear convergence on directed networks using a fixed step size.
The ExtraPush Algorithm
ExtraPush integrates the gradient-tracking mechanism of the Extra algorithm with the push-sum protocol. The core innovation lies in its ability to handle column-stochastic matrices, which only require each node to know its out-degree (or the weight it sends to neighbors), rather than requiring global symmetry.
Mechanism
- Gradient Tracking: ExtraPush utilizes the difference between gradients at consecutive iterations. This allows the agents to track the global gradient and reach consensus more effectively than standard subgradient methods.
- Push-Sum Normalization: The algorithm maintains a state variable $z_i$ and a scalar weight variable $w_i$. By computing the actual estimate as $x_i = z_i / w_i$, the algorithm cancels out the relative influence bias inherent in directed topologies.
For scenarios where the network's stationary distribution is known a priori, the authors propose Normalized ExtraPush, which simplifies the iteration by removing the need for dynamic weight updates.
Experimental Evaluation
The performance of ExtraPush was evaluated using synthetic benchmarks, including decentralized least squares and Huber-like regression. These tasks were performed over a strongly connected directed graph to demonstrate the algorithm's handling of asymmetric communication.
In these experiments, ExtraPush demonstrated a significant speed advantage over subgradient-push. For a least squares problem, ExtraPush achieved an iterative error of $10^{-8}$ within approximately 3,000 iterations. In contrast, even with hand-optimized step sizes, subgradient-push remained at an error level between $10^{-2}$ and $10^{-4}$ in the same timeframe. The results confirm that the fixed step size enabled by ExtraPush allows for geometric (linear) convergence, a substantial improvement over the sublinear rates of previous directed-graph methods.
Key Insights
- Bias Cancellation: The integration of push-sum normalization directly into the Extra framework allows for "re-centering" the optimization process in asymmetric networks.
- Linear Convergence: Under the assumption of strong convexity, Normalized ExtraPush is proven to converge linearly. This provides a rigorous theoretical foundation for the observed speedups.
- Robustness: Both the standard and normalized versions of ExtraPush performed similarly in simulations, indicating that the dynamic normalization is highly effective even when stationary distributions are unknown.
Conclusion and Future Work
ExtraPush successfully bridges the gap between high-speed undirected optimization and the practical constraints of directed networks. While the current analysis for the general ExtraPush algorithm relies on a bounded sequence assumption, future work aims to relax this requirement. Additionally, extending the framework to handle time-varying networks and non-smooth objective functions remains an active area of research.
Summary updated