Budget-Constrained Multi-Consensus Decentralized Gradient Descent

I. INTRODUCTION

• Communication and computation both consume resources, and their relative costs depend on hardware, network conditions, synchronization latency, and local-objective complexity.The paper presents a two-stage perspective: first allocate a fixed number of consensus rounds across a fixed number of gradient updates, then choose those totals under an overall budget.Source: §I · p. 1
• mcDGD varies consensus steps across iterations and uses a convergence analysis requiring strongly convex global and convex local objectives.The analysis leverages the Mean Hessian Theorem and contraction-mapping framework in, with a specific time-varying stepsize choice.Source: §I · p. 1
• Prior multi-consensus methods – analyze prescribed allocation policies, while this work optimizes consensus allocation under a communication budget.The prior bounds also include stepsize-independent asymptotic error terms, which the authors say may be conservative in the small-stepsize regime –.Source: §I · pp. 1–2
• The proposed analysis yields an asymptotic error that can be made arbitrarily small with proper stepsize selection and provides budget-aware consensus allocation based on finite-time bounds.The allocation optimizes a prescribed consensus budget across iterations; the paper focuses primarily on this first stage of the broader resource-allocation problem.Source: §I · pp. 1–2
• Experiments vary the available budget and computation and communication operations to illustrate the allocation strategy; the paper reports performance gains over.The contribution statement describes the gains as clear, while the experiment description says the strategy makes effective use of available resources.Source: §I · p. 2
• The analysis assumes one gradient evaluation per iteration, leaving arbitrary numbers of consensus and local-gradient updates per iteration for future generalization.This is framed as a first step toward the more general design problem.Source: §I · p. 2

A. System Model

• A network of N agents is represented by a weight matrix W, and each agent has a local objective f_n; the analysis takes scalar variables for notational simplicity.The results extend to M > 1 by representing agent variables as a matrix or stacked vector.Source: A. System Model · p. 2
• In standard DGD, agents maintain local iterates and apply neighbor consensus averaging followed by a local gradient-descent step.The update uses a positive stepsize η.Source: A. System Model · p. 2
• Exactly one consensus round per iteration may not be resource-efficient, motivating a DGD variant that adapts communication across the optimization horizon.The stated motivation is communication and computation resource efficiency.Source: A. System Model · p. 2

B. Multi-consensus DGD

• At iteration t, mcDGD performs k_t consensus rounds before the local gradient update.The rounds are represented by W raised to the k_t power, corresponding to k_t consecutive consensus rounds.Source: B. Multi-consensus DGD · p. 2
• The resource model charges c_comp for each gradient update and c_comm for each consensus step.For T iterations, the total cost includes T computation costs and the communication costs from the iteration-specific consensus rounds.Source: B. Multi-consensus DGD · p. 2
• The convergence bound is used to choose the sequence of consensus rounds to minimize convergence error under an overall resource budget.The passage describes this as a principled choice of {k_t}.Source: B. Multi-consensus DGD · pp. 2–3

C. Notation and assumptions

• The vector x⋆1 stacks identical copies of the global minimizer x⋆, where the global objective has zero derivative.The sum of the agents’ gradients is zero there, although individual local gradients need not be zero.Source: C. Notation and assumptions · p. 3
• The network is connected, undirected, and non-bipartite, with W symmetric and W1 = 1.The eigenvalues are ordered 1 = λ1 > λ2 ≥ ··· ≥ λN > −1; W need not be non-negative or positive semidefinite.Source: C. Notation and assumptions · p. 3
• Each local objective is convex and L-smooth, while the global objective is L-smooth and μ-strongly convex.For example, local least-squares objectives may be flat in some directions while their aggregate is strongly convex if the projections span the whole space.Source: C. Notation and assumptions · p. 3

III. CONVERGENCE ANALYSIS OF MCDGD

• Under the stated assumptions and stepsize condition, mcDGD’s error evolution is bounded by a two-dimensional system coupling optimization error and consensus error.The diagonal terms represent individual contractions and the off-diagonal terms their coupling; contractivity at each iteration suffices for a convergent error bound.Source: §III · pp. 3–4
• Proposition 1 holds for stepsize choice (8); when the number of consensus rounds per iteration is constant, k_t ≡ k, that choice yields a constant stepsize, η_t ≡ η, across iterations.Extending Proposition 1 to more general fixed stepsizes satisfying (7) is left for future work.Source: §III · p. 5
• The iteration-varying stepsize isolates time variation in a scalar factor, leaving a fixed positive-definite coupling matrix whose eigenstructure makes accumulated error propagation explicit.The shared eigenvectors decouple the original dynamics into scalar products dependent on the consensus schedule.Source: §III · p. 4
• Unlike prior multi-consensus analyses, the asymptotic error can be made arbitrarily small through stepsize selection rather than being fixed by network topology and consensus rounds.The comparison is with prior analyses whose asymptotic error floor cannot generally be made arbitrarily small through stepsize selection.Source: §III · p. 5
• The convergence bound separates communication’s effect on transient error decay from the residual error induced by local objective heterogeneity.The residual scales as O(κ) and can be reduced by choosing a smaller κ; larger κ accelerates transient decay while increasing that residual.Source: §III · p. 5

IV. OPTIMIZING THE NUMBER OF CONSENSUS ROUNDS

• For fixed κ and T, allocating more consensus rounds reduces the transient contraction term, so schedule design minimizes that product under the resource budget.The schedule objective is invariant to reordering the consensus-round sequence, so the order of resource use does not affect worst-case optimality for the bound.Source: §IV · pp. 5–6
• The optimal schedule uses at most two adjacent integer consensus-round counts, time-sharing between the average allocation’s neighboring values.The schedule uses the available communication budget fully up to the integer constraint.Source: §IV · p. 6
• The allocation is as constant as possible because the objective is strictly convex: transferring a round from a larger allocation to a smaller one decreases the objective without changing total communication cost.The strict convexity property is stated for 0 < ξ1 < 1 and 0 < ν < 1.Source: §IV · p. 6

• The experiments use decentralized least-squares regression with 10 agents and dimension 5, and select κ empirically from tested admissible values.The chosen κ is held fixed across allocation strategies; joint theoretical optimization of κ and {k_t} is outside the work's scope.Source: §V · p. 6
• At a fixed resource budget, mcDGD achieves lower optimization error than fixed-consensus baselines after sufficiently many iterations.Source: §V · p. 7
• Random and permuted schedules achieve identical final performance, while random allocation has inferior transient performance to optimized allocation despite similar final accuracy.Source: §V · p. 7
• Optimized mcDGD achieves the best overall communication-computation efficiency across all considered network topologies.Source: §V · p. 7

• The analysis requires smoothness and strong convexity of the global objective, but only convexity of the local objectives.Source: §VI · pp. 7–8
• Finite-time convergence bounds characterize the interplay between consensus quality and stepsize selection, supporting principled communication allocation under resource constraints.Source: §VI · p. 8
• Under the analyzed stepsize rule, the optimal allocation assigns consensus rounds as evenly as possible across iterations.Source: §VI · p. 8
• Numerical experiments corroborate the theory and show consistent performance gains over other methods across different network topologies.Source: §VI · p. 8
• Future work includes allowing iterations without consensus updates and optimizing additional parameters such as κ and T.Source: §VI · p. 8