CS Paper Radar

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

Feiming Wang, Yutong He, Sulaiman Alghunaim, Kun Yuan

cs.LG math.OC ·submitted 2026-10-23 09:50 UTC · v1

Abstract

Stochastic Push-Pull achieves linear speedup with respect to the network size $n$ on static strongly connected digraphs, but whether this speedup persists on time-varying networks remains unclear. In this work, we construct a quadratic decentralized problem on period-two networks showing that stochastic Push-Pull may fail to attain linear speedup over time-varying digraphs. For $p$-periodic networks, we identify an effective node count $n_{\mathrm{eff}}\le n$ that governs the leading stochastic term. Specifically, for smooth nonconvex objectives, we establish convergence upper bounds and matching lower bounds for stochastic Push-Pull with constant stepsizes, both exhibiting the leading-order dependence $Θ(1/\sqrt{n_{\mathrm{eff}} T})$. When $p=1$, the identity $n_{\mathrm{eff}}=n$ recovers the usual linear speedup for static digraphs. However, periodic networks can have $n_{\mathrm{eff}}=o(n)$, demonstrating the loss of linear speedup under temporal variation. Numerical experiments illustrate effective-count scaling and the separation between static and periodic networks, consistent with our theoretical findings.

Comment
33 pages, 3 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Accelerated Push-Pull with Local Updates for Decentralized Stochastic Optimization

eess.SY math.OC ·2026-10-26 ·Sheng Dong, Weiguo Xia, Huijie Tao
theory similarity 0.63
Abstract · 38 pages, 4 figures

We consider decentralized stochastic nonconvex optimization over directed networks. Push--Pull provides an efficient decentralized optimization framework for such networks, but in the stochastic setting, gradient variance can slow its convergence and complicate the analysis of linear speedup. Motivated by this observation, we incorporate recursive momentum into stochastic Push--Pull for variance reduction, yielding the accelerated stochastic Push--Pull (ASPP) algorithm. Under mean-squared smoothness, we prove that ASPP improves the convergence rate of stochastic Push--Pull and achieves asymptotic linear speedup with respect to the number of agents. To further reduce communication, we develop LASPP, a local-update variant of ASPP that allows each agent to perform multiple local updates between communication rounds. We show that LASPP achieves an additional asymptotic linear speedup with respect to the number of local steps. With a suitable number of local steps, LASPP reduces communication complexity while maintaining the same stochastic gradient complexity as ASPP. Numerical experiments on real datasets demonstrate the effectiveness of the proposed algorithms.

0.25

The directed temporal exploration problem

cs.DS math.CO ·2026-09-28 ·Marcelo Garlet Milani, Lucas Picasarri-Arrieta, Chaoliang Tang, Hehui Wu
theory similarity 0.60
Abstract

We study the temporal exploration problem on temporal digraphs. We prove that a lifetime of $O(n^2)$ suffices to guarantee the existence of a temporal exploration on always-unilateral temporal digraphs. We complement this with a $Ω(n^2)$ lower bound, even in the case where each snapshot has maximum undirected degree 2; for always-strong temporal digraphs, the lower bound still holds even if the maximum undirected degree is 3. This stands in stark contrast with the undirected setting. For the large minimum degree setting, we show that a lifetime of $4n/3 - 1$ is sufficient and necessary for guaranteeing the existence of a temporal exploration on temporal digraphs where each snapshot is semicomplete. For always-strong temporal digraphs where each snapshot has minimum undirected degree at least $n - c - 1$, we prove that a lifetime of $O(cn)$ guarantees the existence of a temporal exploration, and we also prove that this is asymptotically tight. From a computational perspective, our results for temporal semicomplete digraphs also yield a polynomial-time, factor-$4/3$ algorithm for deciding if a temporal semicomplete digraph admits a temporal exploration within the first $\ell$ snapshots. We complement this showing that no polynomial-time, factor-$(4/3 - ε)$ approximation algorithm exists, even if every snapshot is a tournament, unless P$=$NP.

0.14

Structural Sign Herdability in Temporal Networks: A Sufficient Condition via $π_p$-Graphs

eess.SY ·2026-09-09 ·Pradeep M, Twinkle Tripathy
similarity 0.59
Abstract

In this letter, we study the herdability of temporally switching directed networks. A temporal network is modeled as a switched system with a fixed switching sequence, which imposes more restrictive herdability conditions than those of conventional switched systems. By exploiting the relationship between temporal walks and the entries of the controllability matrix, we derive sufficient conditions for herdability. We further show that the magnitude of edge weights influences the sign pattern of the controllability matrix, thereby affecting herdability. Consequently, herdability in temporal networks depends not only on the network topology and switching durations, but also on the magnitude of the edge weights. Motivated by this observation, we establish equivalent graph-theoretic conditions for structural sign ($\mathcal{SS}$) herdability in temporal networks. In particular, we introduce the union multigraph of temporal subsystems and propose the notion of a $π$-graph. We show that the existence of a $π_p$-graph, which is a temporally evolving $π$-graph, is sufficient to guarantee $\mathcal{SS}$ herdability. Illustrative examples are provided to demonstrate the proposed results.

0.36

Reachability Diameter: Beyond the Square-Root Barrier, with Polynomial Hardness

cs.DS ·2026-11-03 ·Hector Tierno, Shuang Yang
theory similarity 0.58
Abstract

The reachability diameter of a directed graph is the maximum finite shortest-path distance across all pairs of vertices. It has received recent attention under this name, although the underlying quantity has long played a central role in shortcut set and parallel reachability. Notably, Bals et al. establish hardness for every polynomial-factor approximation in nearly-linear time for weighted digraphs. Yet they give $n^{1/2+o(1)}$-approximation in the unweighted regime with nearly-linear running time, and their conditional lower bounds rule out certain constants only, leaving open whether polynomial loss is necessary. We give a randomized algorithm that estimates the reachability diameter of an unweighted digraph within a factor $n^{1/3+o(1)}$, with high probability, in $\widetilde{O}(m+n)$ time. We complement our algorithm with a lower bound conditional on the 3-uniform Hyperclique hypothesis, ruling out an $n^{2/15-\varepsilon}$-approximation in $\widetilde{O}(m+n)$ time for every fixed $\varepsilon\in(0,2/15)$, establishing the necessity of polynomial loss for nearly-linear time algorithms.

0.25

Stochastic Gradient Tracking over Time-Varying Networks: One-Step Lyapunov Analysis

cs.DC math.OCeess.SY ·2026-08-17 ·Sulaiman A. Alghunaim
similarity 0.58
Abstract

We study decentralized stochastic gradient tracking over a time-varying network of $N$ agents under a uniform window-mixing condition. Products of $τ$ consecutive doubly stochastic mixing matrices contract disagreement by a factor $λ<1$, although individual matrices need not contract disagreement strictly and individual communication graphs may be disconnected. We construct a time-varying quadratic norm that turns this window contraction into an exact one-step Lyapunov identity. This leads to coupled one-step recursions for the centroid and disagreement errors, without unrolling the dynamics over communication windows. For smooth strongly convex objectives, the leading stochastic term is $\widetilde{\mathcal O}(1/(NK))$; for smooth convex objectives, it is $\mathcal O(1/\sqrt{NK})$. Both match their centralized mini-batch counterparts and yield linear speedup after a network-dependent transient.

0.39

Dimension-Free Decentralized Nonsmooth Nonconvex Stochastic Optimization

cs.LG math.OC ·2026-10-05 ·Yuanyu Wan, Lan Xue, Haomin Bai, Tong Wei, Mingli Song
hot direction similarity 0.57
Abstract

We investigate decentralized nonsmooth nonconvex stochastic optimization over a network of $n$ nodes, with the goal of finding an $(δ,ε)$-Goldstein stationary point. The best existing algorithm achieves $O(δ^{-1}(ε^{-3}+dε^{-1}))$ sample complexity and $\widetilde{O}(γ^{-1/2}δ^{-1}(ε^{-3}+dε^{-1}))$ communication complexity, where $d$ is the problem dimension and $γ$ is the spectral gap of the communication matrix. However, the polynomial dependence on $d$ can be a major bottleneck in high-dimensional regimes. In this paper, we propose a novel algorithm that achieves $O(δ^{-1}ε^{-3})$ sample complexity and $\widetilde{O}(γ^{-1/2}δ^{-1}ε^{-3})$ communication complexity. The primary technique is an elegant decentralized online-to-nonconvex conversion that reduces the original problem to a decentralized online convex optimization (D-OCO) problem. A key property of our conversion is that its consensus requirements can be inherited directly from the consensus of the underlying D-OCO decisions. In particular, this property enables us to establish an explicit connection between the dimension dependence and the consensus error, which in turn shows that the polynomial dependence on $d$ can be removed with only logarithmic additional communication.

0.33

Adaptivity, Anchoring, and the Exact Oracle Complexity of Stochastic Fixed-Point Iterations

cs.IT math.OC ·2026-09-26 ·Yekini Shehu
theory similarity 0.56
Abstract · 55 pages, 5 figures

We study stochastic fixed-point iterations $x_{n+1}=θ_nx_0+(1-θ_n)\widehat T(x_n)$ for nonexpansive and contractive operators on Hilbert spaces, with a single-point unbiased oracle of bounded variance. Deterministically, every anchor schedule $θ_n=c_n/(n+2)$ whose density $c_n\in(0,1]$ does not oscillate between scales is either polynomially suboptimal on contractions or super-polynomially slow on rotations; for constant densities $θ_n=c/(n+2)$ the tradeoff is exact, with $\norm{x_n}\asympΓ(c+1)(n\varphi)^{-c}$ on rotations by angle $\varphi$ ($\varphi\to0$, $n\varphi\to\infty$) and, for the classical schedule, $\norm{x_n}=\frac{2|\sin(n\varphi/2)|}{n\varphi}+O(\frac1n)$. The dichotomy fails exactly under lacunary anchor concentration: an explicit $γ$-oblivious schedule, one per target accuracy, is simultaneously contraction-optimal and rotation-polynomial with exponent $1/α_0$, $α_0=\log_2(3/2)$, and, for each fixed target accuracy, the matching lower bound holds for Lebesgue-a.e.\ angle. For stochastic contractions, the minimax rate is $Θ(σ^2\eps^{-2}(1-γ)^{-2})$ on affine maps, and within the anchored class $Θ(σ^2\eps^{-2}(1-γ)^{-2}+(1-γ)^{-1}\ln(D/\eps))$ for known modulus via geometric batching; without a certified modulus bound no sound distance certificate exists, and a certified ceiling is the exact boundary. For nonexpansive maps we prove $O(Kσ^2D^2\eps^{-4})$ in every $2$-uniformly smooth Banach space and the Hilbert rate $\tildeΘ(σ^2\eps^{-2}+D\eps^{-1})$ by reduction to monotone inclusions. Numerical experiments are consistent with every scaling prediction.

0.21

Fully Dynamic Random-Walk Quantities on Undirected Expanders and $κ$-Uniform Directed Graphs

cs.DS ·2026-10-13 ·Richard Peng, Sushant Sachdeva, Junzhao Yang, Yibin Zhao
similarity 0.56
Abstract

We study fully dynamic data structures for random-walk quantities on undirected expanders and fast-mixing directed graphs. For an unweighted graph whose normalized Laplacian has spectral gap at least $γ$, we give a $(1\pm\varepsilon)$ effective-resistance data structure with expected update time $O(γ^{-4}\varepsilon^{-2}\log n\log^4(n/\varepsilon))$ and expected $O(1)$ query time. For directed graphs, somewhat surprisingly, the OMv conjecture precludes a fast data structure based on rapid mixing conditions alone. To address this, we introduce the notion of $κ$-uniform directed graphs, which requires the stationary distribution to $κ$-approximate the uniform distribution, and show that in this setting, random walk based data structures with $\text{poly}(κ, \log{n}, \varepsilon^{-1})$ update/query times are possible.

0.21