Linear convergence in optimization over directed graphs with row-stochastic matrices

Motivation

• Distributed optimization asks agents to cooperatively minimize the sum of local objective functions using local information exchange.The framework includes strongly-connected networks in which each agent knows only its own objective function.Source: §I · p. 1
• Directed communication is practically relevant because agents may communicate asymmetrically or lose communication links.Such networks do not generally satisfy the undirected or balanced assumptions used by earlier methods.Source: §I · p. 1

Prior work

• Earlier directed-graph methods commonly require column-stochastic weights, which in turn require agents to know neighbors’ out-degrees.This requirement is identified as impractical in many situations.Source: §I · p. 1
• Row-stochastic matrices are easier to implement because each agent can locally choose its weights.Prior row-stochastic work cited here achieved O(√(ln k/k)) for arbitrary convex functions.Source: §I · pp. 1–2

Contribution

• The proposed algorithm uses only row-stochastic matrices, requires agent identifiers but no out-degree information, and achieves O(μ^k) convergence for strongly-convex functions.Here 0 < μ < 1 and k denotes the iteration count.Source: §I · p. 2

Problem formulation

• Agents cooperatively minimize the sum of differentiable local objectives over a strongly-connected directed graph.Each local objective is known only to its corresponding agent.Source: §II · p. 2

Assumptions

• The analysis assumes strongly-connected communication, known unique agent identifiers, and local objectives that are differentiable, strongly-convex, and have Lipschitz-continuous gradients.These assumptions support the stated optimization and convergence results.Source: §II · p. 2

Algorithm

• Each agent maintains xk,i, zk,i ∈ R^p and yk,i ∈ R^n, updating three vector states at every iteration.The initialization uses arbitrary x0,i, z0,i = ∇fi(x0,i), and y0,i = ei.Source: §II · pp. 2–3
• The weight matrix is row-stochastic, and the implementation does not require any agent’s out-degree.Agents use locally assigned weights rather than column-stochastic weights requiring out-degree information.Source: §II · p. 3
• The yk,i updates converge to the left eigenvector of the row-stochastic matrix, and gradient scaling by these iterates cancels communication imbalance.This modification enables convergence to the optimal solution using only row-stochastic weights.Source: §II · pp. 2–3

Error analysis

• The analysis reduces linear convergence to showing that the error sequence t_k converges linearly to zero.Because convergence of ||t_k||_2 implies convergence of x_k to x*, this sequence is the central object of the proof.Source: §III · p. 4
• Theorem 1 expresses the error recursion through matrices G and H_k, so convergence follows from ρ(G) < 1 and linear decay of H_k.The decay of H_k follows from 0 < γ_1 < 1, while the spectral-radius condition is established separately.Source: §III · p. 4

Spectral-radius condition

• For step-size α ∈ (0, ᾱ), Lemma 4 proves ρ(G_α) < 1 by analyzing how the eigenvalues change from α = 0.The eigenvalue equal to 1 decreases as α increases slightly, while the other two eigenvalues remain below 1; continuity then yields the result over the admissible interval.Source: §III · p. 4

Geometric decay

• Lemmas 4 and 5 show that G^k and H_k decay linearly for sufficiently small step-size α.The proof combines the spectral-radius bound for G with geometric bounds characterized by constants γ_1, γ_2, and γ.Source: §III · pp. 4–5

Main convergence result

• Theorem 2 establishes that the iterates x_k converge linearly to x* when α ∈ (0, ᾱ).The proof obtains ||t_k||_2 = O(μ^k) and then bounds ||x_k − x*||_2 by a constant multiple of (γ + ξ)^k.Source: §III · p. 5

Step-size requirement

• The admissible upper bound ᾱ depends on network parameters and cannot be computed locally, so agents must use a common sufficiently small step-size.The common value may need to be pre-programmed to avoid an additional agreement protocol.Source: §III · p. 5

• The proof begins by establishing relevant auxiliary relations.Source: §IV · p. 5
• These relations support the subsequent convergence analysis.Source: §IV · p. 5
• The section prepares the technical steps needed for the theorem proof.Source: §IV · p. 5

• Lemma 7 derives iterative equations governing the sequences bzk and bxk.Source: A. Auxiliary Relations · p. 5
• The updates include a transformed gradient sequence and an optimization iterate with step-size α.Source: A. Auxiliary Relations · p. 5
• The proof uses Y∞A = Y∞ to establish one of the sequence relations.Source: A. Auxiliary Relations · p. 5
• The analysis requires showing that the series P∞ k=0 skγk is finite.Source: A. Auxiliary Relations · p. 5
• For a strongly-convex function with Lipschitz-continuous gradient, fixed-step gradient descent contracts distance to the optimizer when 0 < α < 2/nl.Source: A. Auxiliary Relations · pp. 5–6

• The proof bounds three errors: ∥xk+1−bxk+1∥, ∥bxk+1−x∗∥2, and ∥zk+1−bzk+1∥.Source: B. Proof of Theorem 1 · p. 6
• Step 1 bounds the disagreement ∥xk+1−bxk+1∥ using the algorithm update and Lemma 7(b).Source: B. Proof of Theorem 1 · p. 6
• Step 2 bounds ∥bxk+1−x∗∥2 by relating the transformed update to centralized gradient descent.Source: B. Proof of Theorem 1 · p. 6
• The proof bounds additional terms by splitting the right-hand side and applying the relations from Lemma 7 and Lemma 3.Source: B. Proof of Theorem 1 · p. 6
• The final step combines the bounds from the preceding steps to complete the proof.Source: B. Proof of Theorem 1 · p. 6

• The experiments compare the proposed algorithm with DEXTRA, ADD-OPT, Push-DIGing, Subgradient-Push, Directed-Distributed Subgradient Descent, and Weight-Balancing Distributed Subgradient Descent.Source: §V · p. 7
• Fig. 1 depicts the directed graph used in the logistic-regression experiment.Source: Figure 1 · p. 7, §V · p. 7
• The proposed algorithm, DEXTRA, and ADD-OPT use constant step-sizes α = 0.008, α = 0.1, and α = 0.03, respectively.Source: §V · p. 7
• The proposed algorithm has linear convergence under strong convexity, unlike the sublinear convergence of the compared methods that support general convex functions.Source: §V · p. 7
• Compared with ADD-OPT, Push-DIGing, and DEXTRA, the proposed algorithm requires no knowledge of agents’ out-degree but requires unique identifiers.Source: §V · p. 7

• O(µk), 0 < µ < 1, is achieved as the algorithm’s convergence rate for the stated objective-function conditions.The passage identifies this as the best rate for this class of problems.Source: §VI · p. 7
• The algorithm requires no knowledge of neighbors’ out-degrees.Existing directed-graph algorithms require such knowledge because they use column-stochastic matrices.Source: §VI · p. 7
• The setting is distributed minimization of summed local objectives over a multi-agent network with directed communication.Source: §VI · p. 7