Push-Pull and G-Push-Pull Gradient Methods for Distributed Optimization

Under Assumptions 1-4 — requiring only that the induced digraphs G_R and G_{C^T} share at least one common spanning-tree root i in R_R cap R_{C^T} with positive local step size alpha_i > 0 rather than strong connectivity — the left Perron eigenvector u^T R = u^T and right Perron eigenvector C v = v satisfy u^T v > 0 and effective step size alpha' = (1/n) sum_{i=1}^n u_i v_i alpha_i > 0 (Lemma 1, Remark 4), proving global linear convergence O(rho(A)^k) of both ||bar_x_k - x^*||_2 and ||x_k - 1 bar_x_k||_R while unifying peer-to-peer decentralized, master-slave centralized, and leader-follower semi-centralized architectures (Section II-B, Theorem 1).

In G-Push-Pull (Section IV, Algorithm 2), randomly waking agents pull state variables from in-neighbors and push scaled tracker updates along active outgoing links using random matrices R_k and C_k with row-stochastic E[R_k] and column-stochastic E[C_k], achieving linear convergence in expectation for strongly convex smooth objectives (Theorem 2).

Constructing the column-stochastic push matrix C requires each agent i to know its out-degree |N_{C,i}^{out}| (or broadcast weights summing to 1 across out-neighbors), and the exact linear convergence rate O(rho(A)^k) requires deterministic local gradients.

Applied to distributed ridge regression and l_2-regularized logistic regression over directed cyclic and random networks under decentralized and semi-centralized leader-follower topologies.