- Rating
- 2
- Confidence
- 3
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper studies Local-First Heuristic Evolution (LFHE), an adaptive communication topology optimization method for communication-efficient decentralized learning under non-IID data. LFHE restricts the search for candidate peers within local neighborhoods and friend-of-friend (FoF) connections, without requiring global graph information. This method adaptively adds or swaps communication edges based on a local objective that combines structural disagreement, exploration, and degree regularization. Experiments on four image, speech, and text classification benchmarks demonstrate competitive learning performance compared with existing decentralized learning methods.
Critical strengths
Practical and computationally efficient algorithm. LFHE provides a simple and practical topology adaptation mechanism that relies only on local neighborhood information, without requiring global graph information. Its strategy of connecting clients with dissimilar models is also consistent with the insights from the convergence analyses of decentralized SGD (e.g., by Koloskova et al. 2020), which highlight the importance of reducing disagreement among local models for improving convergence.
Critical weaknesses
W1. Insufficient theoretical evidence supporting the effectiveness of the proposed adaptive topology.
First, I understand that Section 3.5 provides a theoretical interpretation of the proposed local structural score through graph Dirichlet energy and consensus dissipation. However, I find the significance of this theoretical contribution somewhat unclear, as the analysis does not directly establish the effectiveness of the proposed adaptive topology mechanism.
What I would have expected, although I am not certain whether such an analysis is feasible, is a theoretical investigation of how the proposed adaptive topology could improve the convergence rate of decentralized learning. As suggested by the convergence analyses of decentralized SGD by Koloskova et al., controlling disagreement among local models is a key factor in achieving efficient decentralized learning. In conventional analyses, the communication graph is typically characterized by a spectral gap, which determines the contraction rate of disagreement among local models. However, in the proposed method, the communication topology changes over time, making it difficult to characterize the contraction through a fixed spectral gap, since the mixing matrices form a time-varying product.
Nevertheless, the proposed mechanism appears to directly target disagreement among local models by adaptively connecting clients with dissimilar representations. Although the distribution of model disagreement may need to be characterized/measured empirically, I wonder whether it would be possible to derive theoretical insights into what properties of this distribution, or under what assumptions on model disagreement, would allow the proposed adaptive topology to improve the convergence rate.
W2. Limited topology baselines and insufficient evaluation under heterogeneous network structures.
Although this paper includes several topology baselines, such as Static Random and Epidemic Learning, I believe the experimental comparison could be strengthened by including additional topology strategies. For example, MATCHA (Wang et al., 2019), which employs randomized matching-based communication over a given network, would be a relevant baseline. While Epidemic Learning also uses randomized communication, its peer-selection mechanism differs substantially from that of MATCHA and the proposed LFHE. Such comparisons under matched communication budgets would help clarify the advantages of the proposed adaptive topology.
Questions for authors
As stated in the Weaknesses.
6 comments
Thank you for the detailed responses and additional experiments.
Regarding W2, I appreciate the additional comparisons with MATCHA and Ring-4, which have substantially alleviated my concerns about the experimental evaluation.
Regarding W1, however, my main concern remains. What I had expected was a theoretical analysis of how the proposed FoF-based exploration and structural scoring mechanism could improve the contraction factor. I believe that such theoretical evidence would further highlight the effectiveness of LFHE.
I will maintain my original rating at this stage.
Thank you for clarifying the remaining concern. We have updated the revised manuscript with additional theoretical analysis and empirical validation to directly address W1, establishing how and under what conditions LFHE's FoF-based structural scoring can improve disagreement contraction under the implemented Metropolis–Hastings (MH) mixing rule.
1. Mechanism-specific contraction guarantee. For fixed representations , let be the MH mixing matrix and define the realized one-step contraction factor , where .
For an FoF-induced edge swap , the structural gain is exactly . Our discrete-time analysis establishes
\;\Longrightarrow\; q_{G'}(R)<q_G(R).$$ Here, $B_{\mathrm{MH}}$ accounts for degree-dependent MH reweighting, while $Q_{\mathrm{disc}}$ is the exact discrete-time correction. **Thus, FoF structural rewiring provably strengthens realized contraction whenever its weighted disagreement gain exceeds these corrections.** **2. Why FoF exploration matters.** FoF expands the locally accessible candidate set. Our distributional analysis shows that accepted FoF swaps achieve positive expected contraction improvement when their expected structural disagreement margin is sufficiently large relative to the MH and discrete-time corrections. This characterizes the conditions under which LFHE's local search can improve consensus. **3. Supporting evidence.** Replaying 889 accepted graph-only topology updates under actual MH weights, **671 (75.5%) improve realized one-step contraction**. Among 505 edge swaps, 215 satisfy our sufficient condition, and all 215 improve contraction. These fixed-representation diagnostics complement the trained-model disagreement results in Appendix H. **The revised paper now provides an explicit theoretical connection from FoF structural selection to stronger state-dependent contraction, supported by empirical validation.** This directly addresses the requested mechanism beyond our original Dirichlet-energy interpretation. The guarantee is conditional and does not imply universal improvement in worst-case spectral contraction or the full non-IID SGD convergence rate. We appreciate the reviewer's constructive suggestion, which motivated this substantial theoretical extension.
Response to Reviewer 7ZX3: Theoretical Justification and Stronger Baselines
We thank the reviewer for recognizing LFHE's practical efficiency and local-information design. We have substantially strengthened both the theoretical interpretation and empirical comparisons.
W1. Time-varying topology and theoretical justification. We agree that a fixed spectral gap cannot fully characterize adaptive mixing. LFHE instead uses a state-dependent structural score with an exact graph Dirichlet-energy interpretation (Section 3.5 and Appendix D). For time-varying doubly stochastic mixing matrices, communication-only disagreement admits a contraction bound involving ρt=∥Wt−J∥2 (Appendix J).
This establishes a consensus-theoretic interpretation, rather than an LFHE-specific SGD convergence-rate guarantee. Importantly, matched mechanism controls (Appendix H) show that structural scoring improves connectivity and reduces model disagreement relative to alternative local objectives. Additional graph-only experiments at N∈{30,100} demonstrate improved algebraic connectivity over static topologies. These results provide complementary theoretical and empirical evidence without assuming monotonic global improvement.
W2. Stronger baselines. To directly address the reviewer's concern, we completed 58 CIFAR-10 training configurations, including Ring-4 and an adapted MATCHA [1] implementation at four activation budgets. Across five seeds, LFHE achieves 72.69 ± 1.06%, outperforming Ring-4 (70.76 ± 1.71%) and MATCHA-100% (68.56 ± 1.69%).
At a common observed model-state payload of 23.85 GB, LFHE retains an advantage (64.31%) over Ring-4 (61.08%) and MATCHA-50% (62.26%), using within-range interpolation (Appendix J). This separate common-pipeline comparison is reported independently of the original multi-dataset results.
The MATCHA baseline adapts the original matching-based method rather than reproducing its MPI implementation. We also explicitly acknowledge that the original ER initialization may exceed the nominal degree threshold and that logical model-state traffic excludes complete physical and control-communication costs.
Scalability. Our moderate-scale experiments evaluate LFHE at N∈{10,50,100}, while additional diagnostics examine local candidate discovery up to N=500 (Appendix G). These results support the scalability of LFHE's information-local design under sparse connectivity, without claiming a general large-scale convergence guarantee.
In summary, the new Ring-4 and MATCHA comparisons directly address the missing-baseline concern, while the Dirichlet-energy analysis and matched mechanism controls provide a clearer theoretical and empirical foundation for LFHE's topology adaptation.
We believe these substantial additions warrant a more favorable assessment.
Reference
[1] Wang, J., Sahu, A. K., Yang, Z., Joshi, G., and Kar, S. (2019). MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling. arXiv:1905.09435.