TL;DR
ExtraPush is a new algorithm that brings the high-speed performance of the "Extra" algorithm to directed networks. By combining gradient tracking with the push-sum protocol, it allows agents to solve decentralized optimization problems with a fixed step size, achieving linear convergence where previous methods were stuck with much slower sublinear rates.
What Problem Does This Paper Address?
In decentralized optimization, a group of agents (like sensors or robots) wants to minimize a global function $f(x) = \sum f_i(x)$, where each agent $i$ only knows its own local function $f_i$. To find the global minimum, they must communicate with their neighbors.
Most fast algorithms assume undirected communication—if I can talk to you, you can talk to me. This allows for "doubly stochastic" mixing matrices, which keep the system balanced. However, real-world networks are often directed (e.g., a powerful transmitter broadcasting to a weak receiver). In directed networks, the communication matrix is typically only "column-stochastic." This asymmetry introduces a bias that causes standard gradient methods to converge to the wrong solution or requires them to use vanishingly small step sizes, making them painfully slow.
The authors aim to bridge this gap: How can we get the fast, fixed-step-size convergence of state-of-the-art undirected methods (like Extra) on a directed graph?
Methods
The authors introduce two primary algorithms: ExtraPush and Normalized ExtraPush.
- ExtraPush: This algorithm combines the "two-step" iteration structure of the Extra algorithm with the push-sum protocol.
- The "Extra" part: Instead of just moving in the direction of the current gradient, it uses the difference between gradients at consecutive steps. This "gradient tracking" helps the agents reach a consensus on the optimal solution.
- The "Push" part: It maintains a secondary scalar variable ($w$) that tracks the cumulative weight of the communication. By dividing the main state variable ($z$) by this weight ($x = z/w$), the algorithm cancels out the bias created by the directed network.
- Normalized ExtraPush: A simplified version used when the network's stationary distribution (the long-term relative "influence" of each node) is known in advance. This removes the need to update the $w$ variable at every step.
The key innovation is that these algorithms can use a fixed step size ($\alpha$), whereas the previous standard for directed networks (subgradient-push) required a diminishing step size ($1/\sqrt{t}$), which is much slower.
Datasets
The paper evaluates the algorithms using synthetic numerical experiments rather than large-scale public datasets:
- Decentralized Least Squares: A standard benchmark where agents try to fit a linear model to distributed data points.
- Decentralized Huber-like Regression: A robust regression task that is less sensitive to outliers than standard least squares.
- Network Topology: The experiments use a specific 5-node strongly connected directed graph (shown in Fig 2.1 of the paper) to demonstrate the handling of asymmetric communication.
Key Insights and Ideas
- Bias Cancellation via Normalization: The "aha moment" is realizing that the push-sum normalization ($z/w$) can be integrated directly into the gradient-tracking structure of Extra. This allows the algorithm to "re-center" itself even when some nodes are much more influential than others.
- Fixed Step Size is the Speed King: By using a fixed step size, the error can drop geometrically (linearly on a log scale). Diminishing step sizes, used in older methods, act like a "brake" that prevents the algorithm from ever reaching high precision quickly.
- Strong Convexity = Linear Convergence: The authors provide a rigorous proof that if the objective functions are strongly convex, Normalized ExtraPush will converge at a linear rate. This is a significant theoretical upgrade over the sublinear rates of previous directed-graph methods.
Key Results
- Speedup: In numerical simulations, ExtraPush and Normalized ExtraPush were significantly faster than subgradient-push.
- Precision: For the Least Squares problem, ExtraPush reached an iterative error of $10^{-8}$ in about 3,000 iterations. In the same timeframe, the hand-optimized subgradient-push method was still struggling at an error level of $10^{-2}$ to $10^{-4}$.
- Robustness: Both versions of the algorithm (standard and normalized) performed almost identically, suggesting that the dynamic normalization in ExtraPush is highly effective.
Limitations and Future Work
- Boundedness Assumption: The convergence proof for the general ExtraPush algorithm currently relies on a "bounded sequence assumption." While this is common in the field, a proof that doesn't require this assumption would be stronger.
- Time-Varying Networks: While the authors mention that the algorithm can be applied to time-varying directed networks (where links appear and disappear), the convergence proof in this paper is specifically for stationary (fixed) networks.
- Non-Smooth Functions: The current work focuses on "smooth" (differentiable) functions. Extending this to "proximable" or non-smooth functions (like those using L1 regularization) is a noted direction for future research.
Summary updated