acceptodds
Under review as a conference paper at ICLR 2027

LFHE: Local-First Heuristic Evolution for Bounded Local Topology Search in Decentralized Learning with Non-IID Data

Abstract

Decentralized learning is highly sensitive to communication topology under non-IID data. Adaptive peer-selection methods can exploit local model information, but broader peer discovery may require increasingly large control state, whereas direct spectral optimization typically relies on graph-wide information. We study the intermediate setting of bounded local topology search and propose , a representation-driven rewiring framework whose candidate discovery and scoring use only ego-neighborhood and friend-of-a-friend (FoF) information. The structural score admits an exact interpretation through graph Dirichlet energy: its sum across clients equals twice the representation Dirichlet energy, which under standard linear consensus dynamics governs the instantaneous dissipation of representation disagreement. LFHE combines this state-dependent structural signal with early exploration and degree control, while algebraic connectivity remains an offline graph diagnostic. Under bounded sparse degree, its FoF candidate state remains local rather than expanding toward population-wide peer tracking. Across four image, speech, and text benchmarks, LFHE achieves competitive decentralized learning performance. Matched-protocol controls identify the structural term as the principal empirical topology-selection signal, while comparison with broader peer discovery exposes a trade-off between predictive performance and discovery-state locality. Together, these results motivate state-aware bounded local topology search between pairwise peer selection and globally informed topology optimization.

Primary area:
optimization
Keywords:
decentralized learning, topology adaptation, non-IID data, distributed optimization, peer-to-peer learning, adaptive communication topology, local topology search

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_7ZX3OpenReview ↗
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
AuthorsOpenReview ↗

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\rho_t=\|W_t-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}N\in\{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}N\in\{10,50,100\}, while additional diagnostics examine local candidate discovery up to N=500N=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.

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 RR, let WGW_G be the MH mixing matrix and define the realized one-step contraction factor qG(R)=∥PWGR∥F2/∥PR∥F2q_G(R)=\|PW_GR\|_F^2/\|PR\|_F^2, where P=I−11⊤/NP=I-\mathbf1\mathbf1^\top/N.

For an FoF-induced edge swap (i,j)→(i,k)(i,j)\to(i,k), the structural gain is exactly ΔCi=∥ri−rk∥22−∥ri−rj∥22\Delta C_i=\|r_i-r_k\|_2^2-\|r_i-r_j\|_2^2. 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.
Reviewer_cEoNOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper introduces LFHE, a heuristic algorithm that improves the communication graph in decentralized learning by locally adding or replacing edges. It uses information from neighbors and friends-of-friends to guide topology changes and shows competitive performance across several datasets.

Critical strengths

The paper addresses a valid and interesting problem, as improving communication topology is important for decentralized learning. The idea of using only local information to improve the graph is also more practical and worth exploring.

Critical weaknesses
  1. Local vs. global improvement: The method only evaluates whether a topology change improves the initiating client's fitness. However, adding or replacing an edge also affects other clients and may negatively impact their fitness. Therefore, local improvements do not necessarily lead to better global topology or overall learning performance. And no notion of guarantee is provided.

  2. Unfair communication comparison: Ring D-PSGD has only two neighbors per client, while LFHE starts with around four and can add more connections. Comparing these methods solely based on communication rounds may be unfair, as their communication costs differ. A comparison under matched communication budgets would be more meaningful.

  3. Communication cost of rewiring: Repeated FoF rewiring can gradually connect nodes that were originally far apart in the network. While candidate selection is limited to two-hop neighbors, the resulting connections may introduce additional communication costs that are not considered in the evaluation.

  4. Additional communication overhead: Computing the fitness function requires representations from neighboring nodes and FoF candidates. However, the paper does not clearly explain how this information is exchanged or quantify the additional communication overhead in the experiments.

  5. Decentralized implementation: The topology updates are processed sequentially, which raises concerns about the practicality of the method in a fully decentralized setting. It is unclear how concurrent topology changes, synchronization, and potential conflicts between clients would be handled.

  6. Writing clarity: The presentation could be improved in some places. For example, Equation (1) introduces CiC_i, DiD_i, and several other parameters before defining them. Introducing these terms earlier would make the method easier to follow.

Questions for authors

Please check Weaknesses.

3 comments
AuthorsOpenReview ↗

Response to Reviewer cEoN: Theoretical Scope, Decentralization, and Additional Evidence

We thank the reviewer for the detailed feedback. We address the concerns by distinguishing LFHE's technical claims from stronger global optimization and deployment guarantees, and by providing substantial new experimental evidence.

1. Local versus global improvement. We agree that local improvement does not guarantee monotonic global improvement, but LFHE does not rely on such a guarantee. Our structural score has an exact local-to-global relationship: for fixed representations, an edge swap satisfies ΔEG=ΔCi\Delta\mathcal{E}_G=\Delta C_i, where EG\mathcal{E}_G denotes global Dirichlet energy (Section 3.5 and Appendix D). Thus, structural-only improvement increases instantaneous disagreement dissipation under standard linear consensus, without guaranteeing monotonic improvement in λ2\lambda_2 or SGD convergence. Matched controls in Appendix H further show that Structural-only achieves higher final connectivity (λ2=2.306\lambda_2=2.306) than Exploration-only (1.038) and Static (0.592). These results provide empirical evidence of aggregate improvement without assuming global monotonicity.

2. Communication locality. Local-first refers to the information required for candidate discovery and fitness evaluation, not physical network proximity. FoF discovery requires no global graph knowledge, establishing the claimed information-locality property. We acknowledge that new connections may incur physical communication costs. Accordingly, Appendices I and J report model-state traffic and topology-control operations while explicitly distinguishing them from unmeasured physical latency and complete network costs. We do not claim that information locality guarantees lower physical communication cost.

3. Decentralized implementation. LFHE's candidate discovery and fitness evaluation use only local neighborhood information, whereas the reference simulator serializes topology commits. This establishes information decentralization, not fully asynchronous execution. To investigate concurrency, we evaluated parallel proposal/commit protocols with conflict resolution. Across 1,098 graph-only snapshots at N∈{30,100}N\in\{30,100\}, connectivity and maximum degree four were preserved. These results support concurrent topology-update feasibility under the tested protocol without claiming asynchronous learning guarantees.

4. Stronger baselines and communication fairness. We completed a 58-configuration CIFAR-10 evaluation suite, adding Ring-4 and MATCHA [1] at four activation budgets. Across five seeds, LFHE achieves 72.69 ± 1.06%, compared with 70.76 ± 1.71% for Ring-4 and 68.56 ± 1.69% for MATCHA-100%. 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 is a separate common-pipeline comparison, not pooled with the original multi-dataset results.

We explicitly report that the original ER initializer may exceed the nominal degree threshold and that saturated four-regular graphs prevent rewiring under the current rule. These results strengthen baseline fairness without implying strict degree matching or complete physical communication-cost equivalence.

5. Presentation. The revised manuscript clarifies the objective formulation, fitness components, and distinction between online degree thresholds and hard graph-degree constraints (Sections 3.1–3.3).

In summary, the absence of guaranteed global monotonicity does not invalidate LFHE's stated local-search contribution. The revised manuscript now provides stronger baseline comparisons, controlled mechanism evidence, communication accounting, and parallel topology diagnostics.

We believe these additions materially strengthen the paper and warrant reconsideration of the original 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.

I appreciate the response.

However, I’m still concerned about the fairness of the comparison. There’s overhead in LFHE that’s not present in some baselines, which makes comparing solely based on rounds unfair.

Secondly, the new links essentially act as an overlay, and the data needs to go through multiple hops, which further complicates the comparison based on rounds.

I’ll maintain the current rating.

Thank you for the follow-up. We would like to clarify the remaining concerns regarding communication fairness and overlay routing.

1. Our revised evaluation is not based solely on communication rounds. As detailed in our previous response, Appendix J introduces Ring-4 and MATCHA under a common learning protocol. At an identical observed cumulative model-state payload of 23.85 GB, LFHE achieves 64.31% accuracy, compared with 61.08% for Ring-4 and 62.26% for MATCHA-50% (within-range interpolation). We also transparently report that LFHE incurs higher model-state traffic at 300 rounds (53.85 GB versus 47.71 GB for Ring-4). Thus, our evidence supports favorable accuracy under a matched measured model-state budget, rather than a claim of lower total communication cost.

2. FoF discovery is distinct from physical multi-hop routing. FoF uses two logical hops to discover candidate peers. Once a new overlay edge is established, model aggregation takes place over that logical peer connection, without requiring forwarding through the original FoF intermediary. We acknowledge that the underlying physical route may still involve multiple hops. Appendix I quantifies topology-control operations and simulator overhead, while complete control-message bytes and physical routing costs remain outside the measured communication budget.

3. We respectfully emphasize the scope of our contribution. LFHE addresses bounded, information-local topology adaptation without global graph knowledge, rather than end-to-end physical-network cost minimization. The unmeasured deployment costs limit conclusions about total network efficiency, but do not invalidate the local-search mechanism, its theoretical foundations, or the explicitly scoped model-state communication comparison.

We believe the revised experiments meaningfully address the original round-based fairness concern, while clearly acknowledging the remaining deployment limitations. We respectfully ask that the contribution be evaluated within this stated scope.

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

This paper studies decentralized federated learning, meaning federated learning without a central server, under non-IID data, where each node holds data from a different distribution. In the proposed algorithm, each node runs local SGD, and a heuristic local search algorithm iteratively updates the graph topology during training: every K steps, the topology is revised, and each node uses the updated topology to set its model-averaging weights with other clients. Local SGD tends to pull the models apart, while model averaging pulls them together. Running both is meant to improve accuracy while the node weights gradually converge.

The topology search itself is a heuristic. Candidate neighbors are drawn from friends-of-friends (FoF), that is, the neighbors of a node's current neighbors. Each node's current model weights are then summarized by a representation vector r_i, and each node gets a score JiJ_i defined as a weighted sum of three terms: (1) CiC_i, which measures how different the node is from its neighbors; (2) DiD_i, which measures how far the node is from the average direction of its neighbors; and (3) a degree penalty that controls the number of neighbors. Each node then improves its score by edge addition or one-edge swap.

The paper gives some theoretical analysis of this local search, but it covers mainly the first term, CiC_i. There are no clear guarantees for DiD_i or the degree penalty. Empirically, the method performs well. It beats standard topologies such as the ring and static random graphs, and, as expected, falls short of a fully connected graph. Although the method is heuristic, the experiments show that λ2\lambda_2 increases, which suggests it improves network connectivity

Critical strengths
  1. The method outperforms the baselines in the experiments. Even though it is heuristic, the role of each component is clear and well motivated.
Critical weaknesses

One confusing point is that the problem setup states the objective as ∑ipiFi\sum_i p_i F_i, yet the method never uses pip_i. There is also no theoretical convergence analysis for the objective ∑ipiFi\sum_i p_i F_i.

Questions for authors
  1. Does the method use the pip_i from the objective ∑ipiFi\sum_i p_i F_i stated in the problem setup?
  2. The method only selects the graph topology, but the edge weights aija_{ij} still follow the standard rule 1/(1+max⁡(di,dj))1 / (1 + \max(d_i, d_j)). Given the design of your heuristic, could aija_{ij} also be adapted to further improve performance?
2 comments
AuthorsOpenReview ↗

Response to Reviewer FYGq: Objective, Theoretical Foundation, and Mixing Weights

We thank the reviewer for the positive assessment of LFHE's empirical performance and technical soundness.

Objective formulation. LFHE adapts the communication topology rather than the client weights pip_i. Our experiments use uniform client weighting (pi=1/Np_i=1/N) and standard Metropolis–Hastings (MH) aggregation. This distinction is now explicit in Section 3.1.

Theoretical contribution. Our structural score admits an exact graph Dirichlet-energy interpretation, connecting locally measurable representation disagreement to instantaneous consensus dissipation (Section 3.5 and Appendix D). This establishes a principled local-to-global relationship without claiming an end-to-end convergence guarantee for time-varying decentralized SGD.

Adaptive mixing weights. We deliberately retain standard MH weights to isolate the contribution of topology adaptation. Jointly optimizing topology and mixing weights is a complementary research direction beyond the current scope.

We appreciate the reviewer's constructive suggestions. The revised manuscript clarifies these theoretical and methodological distinctions.

Thank you for your clarification. The formula involving pip_i and theoretical part of your paper look clearer to me now. I will maintain the rating

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.