On the Limits of Stochastic Push-Pull over Time-Varying Digraphs

1.2 Related work

• Prior work establishes the usual linear-speedup rate for static strongly connected digraphs, while time-varying variants have been studied in several settings.The paper frames whether that speedup persists on time-varying networks as an open question.Source: §1 · p. 1

1 Introduction and main results

• A constructed period-two problem shows stochastic Push-Pull can fail to achieve linear speedup in the number of workers n.For quadratic instances, the stepsize-optimized rate can be Θ(T^-1/2), with constants independent of n.Source: §1 · p. 1, §1.2 · p. 3
• The effective node count n_eff is determined by periodic mixing and summarizes the leading stochastic term through phase weights on gradient contributions.The phase weights account for each node’s immediate model update and subsequent propagation through the tracker; the paper interprets √q/h = 1/√n_eff as a noise-to-signal ratio.Source: §1 · p. 2

1.1 Stochastic Push-Pull

• Stochastic Push-Pull uses row-stochastic model mixing and column-stochastic gradient tracking, with stochastic-gradient noise governed by conditional-moment assumptions.The iterates stack local models, trackers, and stochastic gradients by rows.Source: §1.1 · p. 3

1 Introduction and main results

• Matching upper and lower bounds for smooth nonconvex objectives with constant stepsizes have leading-order dependence Θ(1/√(n_eff T)).The bounds apply to each fixed periodic network satisfying the assumptions.Source: §1 · p. 2, §1.2 · p. 4

• Each local objective is globally L-smooth, and the aggregate objective is bounded below.Source: §2 · p. 4
• Oracle noise is conditionally independent across agents given the pre-sampling filtration, with the stated noise condition applying to compatible predictable matrices.Source: §2 · p. 4
• The network sequence is fixed independently of the oracle, p-periodic, and uses row-stochastic R_t and column-stochastic C_t matrices with positive diagonals and strongly connected digraphs.Every nonzero matrix entry is at least w0 > 0.Source: §2 · p. 4
• Unless otherwise stated, results condition on the fixed network, take expectation only over oracle noise, and use a deterministic constant stepsize.Source: §2 · p. 4

• T^-1/2: on the constructed period-two networks, the stochastic convergence rate remains of this order as the number of nodes grows.Source: §3 · pp. 4–5
• The counterexample uses n = 2s^2 nodes and a deterministic period-two network satisfying Assumption 2.2.Source: §3 · p. 5
• The construction uses a symmetric doubly stochastic matrix C whose stated spectral properties support the period-two network example.The supplied theorem passage introduces C and the spectral condition, but does not state the condition's values.Source: §3 · p. 5
• For comparison, static mixing on the same objective and oracle has a bound yielding the usual n-dependent scaling.The supplied static result gives A_stat_n,T(α) ≤ 1/(αT) + α/n for 0 < α ≤ 1, and states the choice α = n/T.Source: §3 · p. 8
• In the periodic network, alternating weights transmit the noise difference between nodes one and two into the average, whose variance does not decrease with n.Source: §3 · p. 8

• Phase weights capture a gradient perturbation's direct effect on the next aggregate model state and its later effects through the tracker.Source: §4 · p. 10
• The periodic phase weights are used to define average descent gain h, noise energy q, and effective node count n_eff.Source: §4 · p. 10
• The effective node count satisfies 0 < n_eff ≤ n, with equality exactly when all phase-node weights are identical; equality holds for p = 1.Source: §4 · p. 10
• For a period-two network from Theorem 3.1, the phase weights satisfy 1^T b_r = 1 and the stated norm relation, yielding its effective node count.Source: §4 · pp. 10–11
• The section gives a finite cyclic linear-system procedure for computing phase weights and n_eff from the network matrices.It first computes a normalized left Perron vector, then solves for phase coordinates and recovers the weights.Source: §4 · p. 11

• The upper bound holds under Assumptions 2.1 and 2.2 when the stepsize is chosen properly.Its initial-state term is H0, and the stated constant depends on the network, LΔ, and H0.Source: §5 · p. 12
• The matching lower bound fixes any network satisfying Assumption 2.2 and uses a homogeneous quadratic objective with independent mean-zero node-time noise of variance σ^2 > 0.The common initialization has x0 ≠ 0.Source: §5 · p. 12
• The upper and lower bounds identify the sharp leading stochastic order as Θ(1/√(n_eff T)).Source: §5 · p. 12
• Periodic networks have the usual n-worker scaling if and only if n_eff = Θ(n).Source: §5 · p. 12

6 Auxiliary variables and lemmas

• At block boundaries, the auxiliary point follows a recursion using the averaged gradient and correction terms defined over one period.The period length is p, and the block start is s_k = kp.Source: §6 · pp. 12–13
• The auxiliary recursion is obtained by combining the primal and tracker-residual updates with the Perron relation and a Poisson identity..Source: §6 · p. 13
• A phase-weight lemma is established by applying a constant input to the tracker and controlling the residual contribution over time.The residual term vanishes after division by the horizon.Source: §6 · p. 13

7 Convergence upper bound

• A descent lemma bounds progress of the auxiliary sequence under Assumptions 2.1 and 2.2 for stepsizes satisfying the stated restriction.The sequence is used to derive the convergence upper bound.Source: §7 · p. 14
• The proof bounds cumulative error terms and recursive quantities before converting those estimates into nonrecursive bounds.The bounds are developed for N = pK iterations under the stated assumptions.Source: §7 · pp. 14, 16, 17
• Theorem 7.5 gives a convergence guarantee for any admissible fixed stepsize, and Corollary 7.6 states the resulting guarantee when a stepsize is chosen as specified.The corollary applies to time-varying stochastic Push-Pull for T ≥ p.Source: §7 · pp. 18–19

8 Convergence lower bound

• The lower-bound analysis considers stochastic Push-Pull on quadratic objectives with independent, zero-mean noise and nonzero initialization.The state updates are expressed in linear form for the quadratic problem.Source: §8 · p. 19
• For sufficiently small stepsizes, the period-iteration matrix has a simple eigenvalue near one, while the complementary component remains uniformly stable.The leading eigenvalue and eigenvectors vary analytically near zero stepsize.Source: §8 · pp. 19, 20, 23
• The proof reduces the leading component to a scalar autoregression and combines its expansion with bounds on the stable component.The resulting estimates are used to establish the lower-bound theorem.Source: §8 · pp. 22–24

9 Numerical verification

• The experiments validate the theory using a nonconvex logistic objective and a quadratic comparison across static and period-two networks.The finite-horizon logistic setup uses synthetic data and minibatches of size 32.Source: §9 · p. 25, §9.1 · p. 25, §9.3 · p. 26

9.1 Logistic regression with a finite horizon

• The effective-count model fits finite-horizon stationarity errors better than the physical-count model, with log-RMSE 0.0492 versus 0.4979.The fitted log-log slope on n_eff T is −0.4848; periodic-family curves flatten as physical worker count grows, while n_eff T brings the four families close to a common curve.Source: §9.1 · p. 25, Figure 1 · p. 25

9.2 Logistic regression with a fixed stepsize

• A log-log regression of final-quarter mean squared gradient norm against n_eff has slope −0.977 and log-RMSE 0.0316, consistent with 1/n_eff scaling.At the same physical worker count, larger n_eff corresponds to lower noise, while some networks with n_eff < 1 perform worse than the single-node baseline.Source: §9.2 · p. 26, Figure 2 · p. 26

9.3 Quadratic objective from Theorem 3.1

• As n increases, static-network errors decrease while period-two curves remain close; at T = 216, static minima shift to larger stepsizes and lower errors while period-two minima remain nearly unchanged.The stepsizes were numerically optimized for each network, n, and horizon.Source: §9.3 · p. 26, Figure 3 · p. 27

10 Discussion

• Stochastic Push-Pull need not achieve the usual linear speedup on time-varying networks.The result is established by constructing a decentralized problem on period-two networks.Source: §10 · p. 27
• Matching upper and lower bounds identify n_eff as the speedup factor for periodic networks.The experiments agree with these theoretical findings.Source: §10 · p. 27
• The work focuses on periodic networks, and its lower bound applies to Push-Pull with constant stepsizes.Extensions to non-periodic networks, adaptive stepsizes, or broader algorithm classes are future directions.Source: §10 · p. 27

A Upper bound for the counterexample

• The proof tracks disagreement through a recursion involving the mixing matrix and projected stochastic noise.The recursion is E_{t+1} = C E_t + (C − I)(δ_t + Πε_t), with δ_0 = E_0 = 0.Source: A Upper bound for the counterexample · p. 27
• An orthonormal eigenbasis of C on 1⊥ reduces the disagreement recursion to separate scalar modes.The appendix then bounds the absolute response coefficients of those modes.Source: A Upper bound for the counterexample · pp. 27–28
• The appendix concludes by proving the upper bound in Theorem 3.1.The proof uses uncorrelated noise coordinates with stated variances 1/n, 1, and 1.Source: A Upper bound for the counterexample · p. 29

B Additional numerical details

• For Figure 1, the final stepsize minimizes mean A_T over a refined 33-point grid, with evaluation trajectories using separate oracle seeds.All tuning and evaluation runs compute the full gradient at every iteration.Source: B Additional numerical details · p. 30
• For Figure 2, period-four network candidates are selected across worker counts and retained using SLEM and h criteria before choosing networks near target n_eff values.The worker counts are 4, 6, 8, 10, 12, and 16; retained candidates have one-period SLEM at most 0.4 and h in [0.8, 1.2].Source: B Additional numerical details · p. 30
• The period-two comparison in Figure 3 uses worker counts 8, 128, and 512; for the static comparison, the scalar average update is specified.The static case is identified as κ = 0, with R_r = C_r = B + J/2.Source: B Additional numerical details · pp. 30–31