acceptodds
Under review as a conference paper at ICLR 2027

Accelerated Consensus and Decentralized Optimization over Slowly Varying Networks

Abstract

We study average consensus over slowly time-varying networks and its application to decentralized optimization. We introduce WAVE, a windowed Chebyshev method that limits the accumulated effect of network variation by restarting the recurrence after finite windows. If bounds the network condition number and successive communication operators satisfy , WAVE reaches -consensus in communication rounds. This rate matches the fixed-network dependence when and smoothly interpolates across the full range of network variation. For piecewise-constant networks where each change is detected when it occurs and consecutive changes are at least rounds apart, WAVE reaches -consensus in communication rounds. Finally, we use WAVE as the consensus step in an accelerated decentralized optimization method for -smooth convex local objectives with a -strongly convex average. For sufficiently slow network variation, every agent obtains an -solution to the global optimization problem after communication rounds, matching the fixed-network dependence.

Primary area:
optimization
Keywords:
consensus, decentralized optimization, slowly time-varying network, Chebyshev acceleration, gossip matrix

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_v5jCOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper proposes WAVE, which generalizes Chebyshev acceleration — optimal for consensus over a fixed network (O(√χ) rounds) — to time-varying networks. The core mechanism is "windowed restarts": the Chebyshev recurrence is split into short windows and restarted after each one, so that the perturbation accumulated from non-commuting operators never outweighs the contraction gain. Under two models of network variation, the authors give explicit communication complexity bounds:

  • Metric drift: K = O((√χ + min{βχ², χ})·ln(1/ε));
  • Piecewise constant: K = O((√χ + χ/τ)·ln(1/ε)).

Both recover the fixed-network √χ rate when variation is slow enough and degrade smoothly to the robust χ rate under rapid variation. The paper further provides an in-network "flooding-and-rollback" detection protocol and extends the results to decentralized optimization (WAVE-STM).

Critical strengths
  1. First explicit interpolating bounds: it turns the qualitative intuition "the slower the network varies, the faster the convergence" into a quantitative function, filling a genuine gap between fixed and arbitrarily time-varying networks — a clear, if incremental, contribution.

  2. Clean and reproducible idea: "windowing + restart" is intuitive, and complete proofs are given in the main text and the appendix; the results are verifiable.

  3. Addresses the detection problem: for the piecewise-constant setting it provides an in-network detection protocol (flooding-and-rollback) that does not rely on an external detector and does not require a persistently connected subgraph.

  4. Extends to decentralized optimization: recovers the theoretically optimal communication complexity of the fixed-network setting under slowly varying networks, broadening the impact.

Critical weaknesses
  1. The novelty is largely analytic; the mechanism itself is not a new paradigm. Restarting/windowing accelerated first-order methods to cope with time-varying or ill-conditioned settings is a well-known technique (restart heuristics, hybrid restarting, etc.). The paper's contribution lies mainly in the analysis — making the "restart frequency ↔ network variation" mapping rigorous. As a natural, direct generalization, it lacks mechanism-level novelty, placing innovation at "moderate-to-low."

  2. The two models are essentially the same logic used forward and backward. Metric drift (given the global variation bound β → derive window/round count) and piecewise constant (given the change frequency τ → derive the perturbation cost) are structurally highly similar: both first assume the overall degree of variation, then partition into segments, apply the fixed-network Chebyshev formula within each segment, and amortize the cost across segments. Although computationally involved, the idea is straightforward and introduces no fundamentally new analytical tool.

  3. Constant factors and the large-χ dependence are not characterized. All bounds are big-O. The practical window selection and constant factors in the intermediate regime (where β is neither small nor large) are not characterized, and no lower bound is given to show the necessity of the βχ² / χ/τ terms. The tightness of the bounds at practical scales is therefore unclear.

Questions for authors

Q1. In the metric-drift model, can the scheduler estimate β adaptively (e.g., by doubling/trial windows) rather than receiving it as an input? If β is unknown or overestimated, is the loss of acceleration characterized?

Q2. Is there a lower bound establishing the necessity of the βχ² and χ/τ terms under the respective models? Currently only upper bounds are given, so tightness cannot be assessed.

Q3. Compared with known restart-heuristic / adaptive-restart methods, does WAVE offer an advantage beyond constant factors under fixed or moderately varying networks?

Q4. The in-network detection scheme requires τ ≥ √χ ln(2n)+2. What is the algorithm's behavior when this condition fails? Is a stronger assumption needed?

1 comment

Thank you for recognizing the explicit interpolation and its optimization consequences.

Novelty, the two models, and Q3: comparison with restart heuristics

The contribution is an explicit complexity guarantee throughout the transition between fixed and arbitrarily changing networks. Classical Chebyshev analysis applies to a polynomial of one matrix. Section 4 bounds the error accumulated when different, possibly noncommuting operators are used within one window. The resulting contraction bound holds for every admissible sequence. This determines the restart length and the resulting communication bound. Figure 1(a) of the original submission illustrates why restarting matters: the unrestarted recurrence diverges.

Section 5 addresses a different mechanism. Changes may be arbitrarily large within the common spectral bound, while the operator is fixed between changes. The proof accounts for interrupted windows and a doubling schedule that does not know the spacing τ\tau. The algorithm adjusts to observed change times without needing a bound on jump sizes.

These guarantees give more than a constant-factor improvement. For example, β=Θ(χ−5/4)\beta=\Theta(\chi^{-5/4}) yields an O(χ3/4)O(\chi^{3/4}) network factor instead of O(χ)O(\chi). On fixed networks, WAVE recovers classical Chebyshev scaling.

Explicit constants and intermediate window lengths

The original submission specifies mβ=max⁡{1,⌊min⁡{χ,(3βχ)−1}⌋}m_\beta=\max\lbrace1,\lfloor\min\lbrace\sqrt\chi,(3\beta\chi)^{-1}\rbrace\rfloor\rbrace, with the inverse interpreted as +∞+\infty when β=0\beta=0. Theorem 4.2 gives contraction exp⁡(−m2/(5χ))\exp(-m^2/(5\chi)) and the round bound K≤(5χ/m)ln⁡(1/ε)+mK\le(5\chi/m)\ln(1/\varepsilon)+m for each admissible length mm. These constants apply throughout the intermediate regime, not only at the accelerated endpoint.

Q1: Unknown or overestimated drift

WAVE needs a valid upper bound, not the exact drift. If the supplied bound is β^≥β\widehat\beta\ge\beta, the communication bound holds with β^\widehat\beta in place of β\beta. This also quantifies the cost of overestimating drift. A bound can follow from limits on per-round link-weight updates under a fixed common normalization. Empirical estimates can guide tuning, but past observations alone do not certify future drift. Without further drift information, β^=1\widehat\beta=1 gives the robust degree-one method.

The schedule for detected piecewise-constant changes needs neither β\beta nor τ\tau. For example, it applies to scheduled network reconfigurations with announced boundaries. Our optimization experiment uses this schedule. Both versions of WAVE use a conservative spectral bound χ\chi, as in standard spectrally tuned Chebyshev acceleration.

Q2: Lower bounds

The optimality claims concern the fixed-network and unrestricted-variation endpoints. We do not establish matching lower bounds for the intermediate βχ2\beta\chi^2 and χ/τ\chi/\tau terms. The results give explicit achievable rates between those endpoints and sufficient conditions for recovering fixed-network acceleration.

Q4: Changes faster than the flooding time

The condition τ≥χln⁡(2n)+2\tau\ge\sqrt\chi\ln(2n)+2 applies to the flooding-and-rollback implementation in Proposition 5.1. It ensures that change reports propagate before the next change. With immediate change reports, Theorem 3.3 holds for every τ≥1\tau\ge1 and approaches the robust O(χln⁡(e/ε))O(\chi\ln(e/\varepsilon)) rate as changes become frequent. When neither timely reporting nor sufficient spacing is available, degree-one gossip remains valid under the common spectral bound.

Reviewer_rWSbOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes WAVE, a windowed Chebyshev consensus method for slowly varying networks. Finite-window restarts control accumulated operator perturbations. Under bounded one-step operator drift, the communication bound depends explicitly on the drift magnitude; under detected piecewise-constant changes, it depends on the minimum spacing between changes. Both recover the fixed-network square-root dependence under sufficiently slow variation. The paper also develops an in-network detection protocol and extensions to decentralized optimization. Numerical experiments evaluate consensus convergence on constructed and randomly generated networks (Secs. 2–7; Appendices E–H).

Critical strengths
  • The metric-drift result provides a substantive quantitative contribution. Theorem 3.1 explicitly relates communication complexity to the one-step operator change, allows changes at every round, and does not require consecutive operators to commute. The perturbation analysis explains the window-length choice and the sufficient condition for retaining square-root acceleration (Sec. 4; Appendix D).

  • The theoretical treatment is comprehensive. The piecewise-constant schedule adapts without knowing the minimum change spacing, and the analysis handles interrupted windows and arbitrary call starts. The flooding-and-rollback extension addresses delayed change information under additional assumptions. The main proof chains appear coherent, with no substantive error identified in the portions checked (Theorem 3.3; Proposition 5.1; Appendices C–F).

  • The consensus experiments are aligned with the central theoretical claims. They examine continuous drift, abrupt switching, sensitivity to switching frequency, and condition-number scaling. Comparisons use the same operator sequences and spectral bounds, and evaluate worst-case consensus error rather than a selected initial vector (Fig. 1; Appendix H).

Critical weaknesses
  • The relevance of the specific variation assumptions and accelerated parameter regimes is insufficiently established. The introduction motivates interpolation between fixed and arbitrary time-varying networks and distinguishes related theoretical models, but it does not develop a concrete application linking network evolution to the bounded operator drift or detected minimum-spacing assumptions. In particular, the practical meaning of the conditions for retaining acceleration remains unclear. A representative scenario explaining the variation mechanism, parameter scales, and detection requirements would strengthen the significance argument (Sec. 1; Assumptions 2.2–2.4; Corollary 3.2; Theorem 3.3).

  • The numerical evaluation does not cover the decentralized optimization extension. Section 6 and Appendix F establish optimization guarantees, whereas Section 7 and Appendix H evaluate consensus alone. Thus the experiments do not show whether the consensus improvements translate into fewer communication rounds for reaching a target optimization accuracy. An optimization-level comparison, even on a controlled regression problem, would provide more direct support for this part of the contribution. This concern is about coverage of the claimed extension, rather than a requirement to use a particular real-world dataset (Sec. 6–7; Appendices F and H).

Questions for authors
  1. Can you give a representative application in which the communication operators satisfy one of the proposed variation models, and explain the meaning of the acceleration threshold and the required parameter or change-detection information? A concrete mechanism and parameter interpretation would be more informative than a general list of distributed applications.

  2. Are any optimization-level numerical results available in the submitted supplementary material or existing experiments? If so, please identify them and summarize whether WAVE reduces communication to a specified objective accuracy relative to the corresponding optimization method with conventional mixing. If none are available, please clarify the intended empirical scope of the optimization contribution.

1 comment

Thank you for the careful assessment of our theory and consensus experiments.

Q1: Applications and parameter choices

Consider drones averaging sensor measurements with symmetric communication weights that vary smoothly with distance. Bounded relative motion produces bounded operator drift under a fixed normalization, provided the common spectral bound is maintained. Here β\beta bounds the change between consecutive rounds. When β≤(3χ3/2)−1\beta\le(3\chi^{3/2})^{-1}, the operator stays within 1/(3χ)1/(3\chi) of its initial value over a χ\sqrt\chi-round window. This is small enough to retain the fixed-network communication rate even though the weights change at every round.

A second example is a wireless mesh reconfigured at announced times, with fixed weights between reconfigurations. Consecutive configurations may have entirely different edge sets within the common spectral bound. Here τ\tau is the shortest unchanged interval. Intervals of order χ\sqrt\chi suffice for acceleration, and WAVE adapts without knowing τ\tau.

Both models use a conservative spectral bound χ\chi. For metric drift, a bound on per-round normalized weight updates can supply a valid β\beta. Scheduled reconfiguration makes change times available to the agents. For unannounced failures, Proposition 5.1 instead provides in-network flooding and rollback under its additional spacing condition.

Q2: Comparison on decentralized optimization

We have added decentralized logistic regression on the Adult data set, with 32,000 examples split across 32 agents with different label proportions (Figure 2). The network experiences temporary link failures, reported to WAVE before the next round. All methods use the same eight network sequences, and their parameters are tuned on separate runs.

Theorem 6.1 concerns WAVE-STM. For these experiments, we also use WAVE to approximately average local iterates and gradient estimates within gradient tracking, and call this implementation WAVE-GT. This lets us compare WAVE and conventional gossip within the same optimization framework.

WAVE-GT reduces the median number of rounds needed to reach normalized worst-agent objective gap 10−610^{-6} from 768 to 435, a 43% saving over GT + gossip. WAVE-GT also reaches this accuracy before the other implementations shown: Acc-GT, DIGing, DAccGD, and ADOM+. The WAVE schedule adjusts its window length as changes occur and requires neither β\beta nor τ\tau.

Reviewer_CojhOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper considers speeding up the standard consensus protocol in slowly varying networks (discussed in two different scenarios). For fixed networks, mixing in time with Chebyshev polynomial coefficients is well-known to lead to acceleration. In this work, the same coefficients are calculated and used in an interval of time and then restarted based on a new observed network. By providing an upper bound on the speed of convergence, it is shown that such a strategy can still lead to acceleration provided that the change is sufficiently slow. Based on this protocol, a distributed optimization algorithm is also proposed and speeds of convergence are obtained.

Critical strengths

Although time-varying consensus protocols is a well-known subject, accelerating it with mixing in time (e.g. by Chebyshev coefficients) is an interesting new idea. The paper shows that there can be potential gains in this approach. Some rigorous mathematical results are provided and a new optimization algorithm is derived based on it.

Critical weaknesses

1- My first concern is about the novelty of the approach. The use of Chebyshev polynomials in this context is not entirely new and the way that they are used over time-varying networks is straightforward. The main novelty seems to be in the theoretical results establishing that the gain may still exist for sufficiently slow networks, which is not surprising.

2- For the optimization algorithm, there should be a comparison to other existing methods that handle time-varying networks. There are few different solutions with a comprehensive convergence analysis.

3- The structure of the paper is not completely clear to me and there is no natural logical continuation in Section 4 and 5. The optimization algorithm is vaguely defined in the main paper.

Questions for authors

What is the purpose of Section 4 and 5? If I am correct, they present the analysis of the error accumulated by time varying channels as compared to a fixed channel, but why is it interesting? Is it for example related to the proof of the main results?

1 comment

Thank you for recognizing the soundness of our results.

Novelty and the role of Sections 4 and 5

Fixed-network Chebyshev acceleration relies on a polynomial of one matrix. Changing, noncommuting operators invalidate that argument, and the unrestarted recurrence can diverge despite a common spectral bound, as Figure 1(a) of the original submission demonstrates. Our results determine how much acceleration survives throughout the intermediate regimes: the network factors are χ+min⁡{βχ2,χ}\sqrt\chi+\min\lbrace\beta\chi^2,\chi\rbrace for gradual changes and χ+χ/τ\sqrt\chi+\chi/\tau for separated changes.

Earlier results impose different restrictions. Montijano et al. prove convergence under switching without this interpolation. Rogozin et al. restrict the number of changing rounds, while the acceleration of Metelev et al. (2023) relies on a persistent connected subgraph. WAVE permits changes at every round or arbitrary detected reconfigurations separated in time, without requiring a persistent connected subgraph.

Sections 4 and 5 prove the two main bounds, Theorems 3.1 and 3.3. Section 4 controls perturbations within changing windows. Section 5 accounts for complete and interrupted windows between abrupt changes. The second analysis also proves that the scheduler needs no knowledge of the spacing τ\tau.

Why the network models matter in practice

For gradual changes, consider drones averaging sensor measurements with symmetric weights that vary smoothly with distance. Bounded relative motion gives bounded operator drift under a fixed normalization, provided the common spectral bound is maintained. Communication weights can change every round. The condition β≤(3χ3/2)−1\beta\le(3\chi^{3/2})^{-1} identifies when this network still supports the fixed-network χ\sqrt\chi rate.

For piecewise-constant changes, consider a wireless mesh reconfigured at announced times, with weights held fixed between them. Successive configurations may have entirely different edge sets within the common spectral bound. Unchanged periods of order χ\sqrt\chi suffice for acceleration, independently of the target accuracy. The network need not stay fixed until consensus is reached.

WAVE uses a conservative spectral bound χ\chi. In the gradual-change model, a bound on per-round weight updates can supply β\beta. In the detected-change model, neither β\beta nor τ\tau is an input.

Decentralized optimization and comparison

The submitted WAVE-STM uses local gradients and WAVE averaging within restarted Similar Triangles iterations. Algorithm 3 specifies the updates. Theorem 6.1 transfers both network factors to optimization with a O~(κ)\widetilde O(\sqrt\kappa) multiplier, where κ=α/μ\kappa=\alpha/\mu, and guarantees an ε\varepsilon-solution at every agent when only the average objective is strongly convex. We have made the update and restart description explicit in Section 6.

We have added experiments on decentralized logistic regression using the Adult data set and a network with temporary link failures (Figure 2). We use WAVE for communication within gradient tracking and compare it with Acc-GT, DIGing, DAccGD, ADOM+, and gradient tracking with conventional gossip. In this comparison, WAVE-GT reaches the tested objective accuracy in the fewest communication rounds, using 43% fewer rounds than GT + gossip.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.