Source-linked AI summary
Accelerated Push-Pull with Local Updates for Decentralized Stochastic Optimization
Sheng Dong, Weiguo Xia, Huijie Tao
TL;DR
Sampling noise in stochastic Push–Pull can slow convergence and complicate linear-speedup analysis. The paper introduces ASPP with recursive momentum and LASPP with local updates; its results establish asymptotic linear speedup with respect to agents and local steps, while suitably chosen local steps reduce communication complexity without increasing stochastic gradient complexity.
Problem
In stochastic Push–Pull, sampling noise can slow convergence, while its tracking-error analysis can make linear speedup difficult to establish.
Source: §3.1 · p. 5Method
ASPP adds recursive momentum to Push–Pull for variance reduction, and LASPP extends ASPP with multiple local updates between communication rounds.
Source: §1.2 · p. 3, §4.1 · p. 11Results
ASPP achieves asymptotic linear speedup with respect to the number of agents, and LASPP achieves additional asymptotic linear speedup with respect to local steps.
Source: §6 · p. 18Takeaways & Limitations
With a suitable number of local steps, LASPP reduces communication complexity without increasing stochastic gradient complexity compared with ASPP.
Source: §6 · p. 18The stated analysis assumes that every agent’s local stochastic gradient satisfies mean-squared smoothness.
Source: §2 · p. 4
Abstract
from arXiv · showhide
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.
1 Introduction
The paper targets stochastic optimization over directed networks, where gradient noise and communication costs complicate convergence and speedup. It introduces ASPP and local-update LASPP, with theoretical guarantees and numerical support for their effectiveness.
1 Introduction
- Communication costs motivate accelerating decentralized optimization and allowing multiple local updates between communication rounds.The introduction notes that frequent high-dimensional exchanges can consume training time, while faster convergence can reduce communication rounds to a target accuracy.Source: §1 · p. 2
1.1 Related Work
- Prior SPP analyses struggle to establish agent speedup with general row- and column-stochastic mixing, while existing directed-network local-update guarantees do not establish speedup in the number of local steps.Data heterogeneity can also make local iterates drift apart.Source: §1.1 · pp. 2–3
1.2 Contributions and Organization
- ASPP adds recursive momentum to SPP for variance reduction and establishes O(n^-1ϵ^-3) communication and per-agent stochastic-gradient complexities, improving on SPP's O(n^-1ϵ^-4) guarantee [16].The guarantees hold under mean-squared smoothness without requiring doubly stochastic mixing matrices.Source: §1.2 · p. 3
- LASPP allows K local updates between communication rounds and achieves O(n^-1K^-1ϵ^-3) communication complexity, with suitable K reducing complexity to O(ϵ^-2) without increasing per-agent stochastic-gradient complexity.The stated guarantees provide asymptotic linear speedup with respect to both agent count and local-step count.Source: §1.2 · p. 3
- The paper presents refined ASPP analysis, LASPP convergence guarantees, additional numerical experiments, and proofs extending its preliminary conference version.The authors suggest recursive momentum may also reveal convergence properties that are difficult to establish over directed networks, with local updates retaining benefits under less frequent communication.Source: §1.2 · p. 3
2 Preliminaries and Assumptions
This section specifies the directed communication model and assumptions on local objectives and stochastic gradients. These include unbiased gradients with bounded variance, lower-bounded local losses, and mean-squared smoothness.
2 Preliminaries and Assumptions
- Agents communicate over a directed graph, where an edge (j, i) means agent j can send information directly to agent i.The graph is specified through directed edges and induced graphs of nonnegative mixing matrices.Source: §2 · p. 4
- Each agent's stochastic gradient is assumed unbiased with bounded variance, and samples drawn by agents are mutually independent.The variance is bounded by a shared constant σ.Source: §2 · p. 4
- Each local loss is bounded below, with its initial objective gap bounded by Δf.The stated gap compares the starting-point loss to that agent's infimum.Source: §2 · p. 4
- Local stochastic gradients satisfy mean-squared smoothness, and the assumptions imply that each local objective is L-smooth.The section introduces these conditions for the local objectives and stochastic gradients.Source: §2 · p. 4
3 Accelerated Stochastic Push–Pull
ASPP adds recursive momentum to stochastic Push–Pull to control gradient variance and improve convergence over directed graphs. Its analysis establishes faster convergence than SPP and asymptotic linear speedup under mean-squared smoothness.
3.1 Algorithm Design
- ASPP incorporates a recursive momentum estimator into stochastic Push–Pull to reduce sampling-noise effects on update directions and accelerate convergence.The estimator uses two stochastic gradients computed from the same sample.Source: §3.1 · pp. 5–6
- The analysis assumes row-stochastic A and column-stochastic B with positive diagonal entries, whose induced directed graphs are strongly connected.When the communication graph is strongly connected and has a self-loop at every node, the weights can be constructed locally using in-degree and out-degree information.Source: §3.1 · p. 6
3.2.1 Preliminaries
- For nonconvex objectives, the analysis targets ϵ-accurate first-order stationary points and treats ˆx(t) as the consensus output of the local iterates.The consensus value is defined under the row-stochastic mixing matrix A.Source: §3.2.1 · p. 7
3.2 Convergence Analysis
- Recursive momentum controls ASPP’s tracking-error variance contribution, enabling single-step descent analysis to establish linear speedup and faster convergence than SPP.Under mean-squared smoothness, the resulting variance term is of order nTs_B^2(1−β)^2σ^2.Source: §3.2.2 · pp. 7–8
4 Accelerated Stochastic Push–Pull with Local Updates
LASPP extends ASPP with multiple local updates between communication rounds. Its convergence guarantees show that suitably chosen local steps reduce communication complexity while preserving stochastic-gradient complexity.
4.1 Algorithm Design
- Each agent performs K communication-free local updates using recursive momentum, then communicates and applies ASPP's Push–Pull recursions; K = 1 recovers ASPP.LASPP's updates are designed for multiple local steps rather than simply skipping communication rounds.Source: §4.1 · p. 11
4.2 Convergence Analysis
- Gradient averaging preserves a 1/K variance factor after accounting for local drift, while recursive momentum also controls the drift's variance contribution.The convergence bounds retain variance terms of orders (1 −β)σ2/(nK) and h2(1 −β)2σ2/(c2K).Source: §4.2 · p. 14
- LASPP achieves communication complexity O(n^-1K^-1ϵ^-3), with asymptotic linear speedup in both agents n and local steps K.This holds in the stated sufficient regime for the leading term.Source: §4.2 · p. 15
- LASPP improves asymptotic communication complexity from O(ϵ^-3) for ASPP to O(ϵ^-2), while maintaining the same per-agent stochastic-gradient complexity as ASPP for every integer 1 ≤ K ≤ K̄.Source: §4.2 · p. 15
5 Numerical Experiments
Experiments compare ASPP and LASPP with SPP and a centralized baseline on MNIST logistic regression and CIFAR-10 CNN training. LASPP improves on ASPP in both tasks, while increasing agents or local steps improves optimization progress per communication round.
5 Numerical Experiments
- The evaluation covers multiclass logistic regression on MNIST and CNN image classification on CIFAR-10, using heterogeneous agent data distributions.The data are partitioned by Dirichlet sampling with parameter 0.9 in both tasks.Source: §5 · p. 15, §5.1 · p. 16, §5.2 · p. 18
- Decentralized methods are evaluated using the average of local models and compared with SPP; SCAFFOLD-MVR provides a centralized reference.SCAFFOLD-MVR is an accelerated SCAFFOLD variant based on recursive momentum.Source: §5 · p. 15
- On MNIST, LASPP improves on ASPP and performs comparably to centralized SCAFFOLD-MVR; on CIFAR-10, it achieves higher test accuracy than ASPP in fewer communication rounds and approaches SCAFFOLD-MVR.ASPP also converges faster than SPP on MNIST and consistently outperforms SPP on CIFAR-10.Source: §5.1 · p. 16, Figure 1 · p. 16, §5.2 · p. 18
5.1 Nonconvex Logistic Regression
- With more ASPP agents or LASPP local steps, lower gradient norms are attained for the same communication rounds, with benefits becoming more pronounced as optimization proceeds.The experiments vary ASPP agents n = 8, 16, 32 and LASPP local steps K = 5, 10, 20.Source: §5.1 · p. 16, Figure 2 · p. 17, Figure 3 · p. 17
6 Conclusion
The paper introduces ASPP and its local-update variant LASPP for decentralized stochastic nonconvex optimization over directed networks. Its analysis establishes speedups with agents and local steps, and experiments support the theoretical findings.
6 Conclusion
- ASPP uses recursive momentum for variance reduction, improving on SPP and achieving asymptotic linear speedup with the number of agents under mean-squared smoothness.LASPP adds asymptotic linear speedup with local steps and can reduce communication complexity without increasing stochastic-gradient complexity when K is suitably chosen.Source: §6 · p. 18
A Supporting Lemmas
The appendix collects supporting bounds for mixing matrices, initialization errors, and iterates generated by both algorithms.
A Supporting Lemmas
- Lemma 11 gives a bound for sequences mixed by a row-stochastic matrix, with an analogous bound for column-stochastic mixing.The lemma assumes the matrix satisfies Assumption 4.Source: A Supporting Lemmas · pp. 18–19
- Lemma 12 bounds initialization errors for both ASPP and LASPP.Source: A Supporting Lemmas · p. 19
- Lemmas 13–16 provide bounds for iterates generated by ASPP and LASPP under Assumptions 1–4 and β ∈[0, 1).Lemma 13 concerns Algorithm 1; Lemmas 14–16 concern Algorithm 2.Source: A Supporting Lemmas · p. 19
B Proofs for ASPP
The ASPP proof sets up a filtration for communication rounds, establishes that the iterates are measurable with respect to past samples, and assumes current samples are independent of that history.
B Proofs for ASPP
- F_t is defined by the samples drawn before communication round t, with F_0 the trivial σ-algebra.Source: B Proofs for ASPP · p. 20
- The update rules make x(t), y(t), and m(t−1) measurable with respect to F_t for t ≥ 1.Source: B Proofs for ASPP · p. 20
- Assumption 1 gives mutual independence among the samples at round t and independence from F_t.Source: B Proofs for ASPP · p. 20
B.1 Proof of Lemma 2
The proof uses smoothness-based descent estimates and sums them over iterations to establish the lemma’s bound.
B.1 Proof of Lemma 2
- The proof begins with the descent lemma, using L-smoothness of f.Source: §B.1 · p. 20
- The argument substitutes the update into the descent bound, then applies component smoothness and Young’s inequality.Source: §B.1 · p. 20
- The proof uses α ≤ 1/(4cL), sums over t = 0 to T − 1, and applies the initial objective-gap bound before taking expectation.Source: §B.1 · p. 20
B.2 Proof of Lemma 3
These proofs combine lemma bounds, initialization conditions, stochastic-gradient properties, and step-size restrictions to establish Theorem 1.
B.2 Proof of Lemma 3
- Lemma 3’s proof combines two preceding bounds with the initialization, sums over iterations, and takes expectation.Source: §B.2 · p. 21
B.3 Proof of Lemma 4
- Lemma 4’s proof unrolls the y(t) recurrence from y(0) = 0 and applies prior lemmas, including a bound on the initial gradient norm.Source: §B.3 · pp. 21–22
B.4 Proof of Lemma 5
- Lemma 5’s proof uses stochastic-gradient unbiasedness, sample independence, the variance bound, and mean-squared smoothness to control the momentum recurrence.Source: §B.4 · pp. 22–23
B.5 Proof of Lemma 6
- Lemma 6’s proof unrolls the update from the common initialization and uses α ≤ 1/(20hL) to complete its bound.Source: §B.5 · p. 24
B.6 Proof of Theorem 1
- Theorem 1’s proof combines Lemmas 3–6 and applies step-size and network-parameter conditions before dividing by T.Source: §B.6 · p. 25
C Proofs for LASPP
The LASPP proofs extend the stochastic analysis to local steps, using per-step filtration and bounds for the local-update dynamics to establish Theorem 2.
C Proofs for LASPP
- The proof defines a filtration over samples drawn before each local step and uses it to establish measurability and sample independence.Source: C Proofs for LASPP · p. 25
C.1 Proof of Lemma 7
- Lemma 7’s proof reuses the argument for ASPP and applies Lemma 16.Source: §C.1 · p. 26
C.2 Proof of Lemma 8
- Lemma 8’s proof bounds stochastic-gradient terms using unbiasedness, independence, the variance bound, and mean-squared smoothness, then unrolls the recurrence.Source: §C.2 · pp. 26–28
C.3 Proof of Lemma 9
- Lemma 9’s proof adapts the ASPP argument and uses α ≤ 1/(25hL) to complete the bound.Source: §C.3 · pp. 28–29
C.4 Proof of Lemma 10
- Lemma 10’s proof bounds local updates, averages over local steps, then sums over agents and communication rounds.Source: §C.4 · pp. 29–30
C.5 Proof of Theorem 2
- Theorem 2’s proof combines Lemmas 7–10 and applies conditions on nK and the step sizes before dividing by T.Source: §C.5 · p. 31
D Proof of Supporting Lemmas
Appendix D proves five supporting lemmas using stochastic-gradient properties and bounds accumulated across agents and iterations. The proofs invoke unbiasedness, variance bounds, smoothness, and independence where applicable.
D.1 Proof of Lemma 12
- Lemma 12’s proof uses stochastic-gradient unbiasedness, independent initialization samples, and a variance bound.The excerpt states these properties as the basis for the proof and says the variance bound yields the final inequalities.Source: §D.1 · p. 32
D.2 Proof of Lemma 13
- Lemma 13’s proof combines unbiasedness, measurability, variance bounds, and mean-squared smoothness before summing over agents and iterations.It bounds geometric sums, applies Lemma 12, and uses β ∈ [0, 1) to complete the proof.Source: §D.2 · pp. 32–33
D.3 Proof of Lemma 14
- Lemma 14’s proof uses mean-squared smoothness and bounded variance, then substitutes the Lemma 13 bound and uses β ∈ [0, 1).The argument sums over agents and iterations before applying Lemma 13.Source: §D.3 · p. 33
D.4 Proof of Lemma 15
- Lemma 15’s proof bounds terms using unbiasedness, sample independence, bounded variance, mean-squared smoothness, and inequalities including Jensen’s.It unrolls the resulting bound, sums over agents and iterations, applies Lemma 12, and uses β2 ≤ 1.Source: §D.4 · pp. 34–35
D.5 Proof of Lemma 16
- Lemma 16’s proof combines conditional expectation, mean-squared smoothness, unbiased gradients, sample independence, and a variance bound.It sums over agents and iterations, applies Lemma 15, and uses K ≥ 1 and β ∈ [0, 1).Source: §D.5 · pp. 35–36