A Unified Convergence Analysis for Semi-Decentralized Learning: Sampled-to-Sampled vs. Sampled-to-All Communication

AI summary

Overview

Research area: Federated learning and distributed optimization theory, specifically semi-decentralized federated learning (FL) where device-to-device (D2D) communication is combined with periodic device-to-server (D2S) communication.

Technical level: Advanced. The paper is a convergence-analysis paper that builds on decentralized SGD theory, spectral graph arguments, and error-decomposition lemmas; the main results are iteration-complexity bounds.

Scope in one sentence: The paper develops a unified convergence framework for two server-dissemination strategies in semi-decentralized FL — sampled-to-sampled (S2S) and sampled-to-all (S2A) — and uses it, together with experiments on MNIST and CIFAR-10, to identify when each strategy is preferable.

What This Paper Is About

In semi-decentralized federated learning, devices mostly talk to their neighbors over cheap local links but occasionally send models to a central server, which averages a randomly sampled subset of them. The server can return that aggregate either only to the devices it sampled from (S2S) or to every device in the network (S2A). Both variants appear in prior work, but no rigorous theoretical or empirical comparison of the two existed. This paper supplies that comparison by analyzing both strategies inside one common convergence framework.

Key Contributions

1. A unified theoretical framework for semi-decentralized FL that simultaneously captures (i) intra-component and inter-component statistical heterogeneity, (ii) the sampling rate, (iii) the server aggregation period, and (iv) D2D network connectivity — extending prior decentralized convergence theory to the semi-decentralized setting.

2. Identification of a fundamental trade-off. S2A introduces a "broadcast-induced bias" (the global average model shifts after each D2S aggregation because sampled clients overwrite unsampled ones) but eliminates disagreement among local models. S2S has zero bias but leaves residual disagreement, since unsampled devices are not realigned with the aggregate.

3. Explicit convergence bounds and regime identification. Comparing the bounds yields conditions under which each primitive wins: S2A converges faster when both intra- and inter-component heterogeneity are low, whereas S2S wins as inter-component heterogeneity grows — especially at low sampling rates, short server periods, or sparse connectivity.

4. An extensive experimental comparison across sampling rates, aggregation periods, and D2D topologies on benchmark FL datasets, which reproduces the predicted regimes and yields practical configuration guidelines.

The paper also states that a convergence analysis of S2S under non-convex objectives was previously lacking, and that prior analyses assumed at least one device per connected component is sampled in every server round — an assumption requiring the server to know component membership, which the authors argue is hard to satisfy due to device count, mobility, and privacy.

Main Findings

• S2S generally has a faster theoretical convergence rate than S2A. Neglecting common factors, the dominant error terms scale as O(ε^(-3/2)) for S2S versus O(ε^(-2)) for S2A. The paper attributes S2A's slower rate primarily to the broadcast-induced bias.

• S2A carries an extra quadratic dependence on heterogeneity. S2A's bounds include quadratic terms in the intra- and inter-component heterogeneity constants ζ̄_intra and ζ̄_inter, which can dominate under statistically diverse data.

• Zero bias vs. zero disagreement. S2S preserves the global average exactly (the bias error vanishes), leaving a residual disagreement scaled by (n − K)/(n − 1). S2A enforces perfect consensus (disagreement is exactly zero) but introduces a bias scaled by (n − K)/(K(n − 1)).

• Sampling rate edge cases. When all devices are sampled (K = n), the two update rules coincide (W_S2A = W_S2S = Π) and the two algorithms share the same convergence rate. When only one device is sampled (K = 1), W_S2S = I, so S2S cannot mix the sampled model across components and its bounds diverge, whereas S2A still broadcasts the single sampled model and converges, albeit more slowly.

• Effect of the server period H. All ζ̄_inter terms carry a factor H in both bounds. As H → ∞, both bounds diverge, since components may reach consensus on their local optima but global convergence is not guaranteed. S2A grows quadratically in ζ̄_inter while S2S grows only linearly.

• Effect of the mixing parameter p. All ζ̄_intra terms are multiplied by the inverse of the mixing parameter p, reflecting that D2D rounds only mitigate intra-component heterogeneity.

• Three theoretical regimes (computed with n = 100, L = f_0 = 1, σ̄ = 0, target accuracy ε = 10⁻⁵):

  • R1 (low ζ̄_intra and ζ̄_inter): S2A converges faster for most sampling rates, server periods, and mixing parameters.
  • R2 (ζ̄_inter much smaller than ζ̄_intra): S2S converges slightly faster for low sampling rates (K/n < 0.2), low server periods (H < 5), and most mixing parameters (p < 1); S2A is slightly faster otherwise.
  • R3 (high ζ̄_inter): S2S converges faster for most values of K/n, H, and p, irrespective of ζ̄_intra.

• Experiments confirm the regimes. With 100 devices in 2 components of 50, accuracy improves for both methods as the sampling rate increases, with an average gain of +2 percentage points between K/n = 0.2 and K/n = 1.

  • R1 (intra IID, inter IID): S2A outperforms S2S in over 80% of configurations, though the gain is modest (up to 1 p.p. on the ring at K/n = 0.2).
  • R2 (intra non-IID, inter IID): S2A wins in 40% of cases (up to +0.5 p.p. on the complete graph at high K/n), while S2S prevails in the remaining 60% (up to +8.4 p.p. on the ring at K/n = 0.2).
  • R3 (inter non-IID): S2S outperforms S2A in over 90% of settings, largest gain at K/n = 0.2 (+2.4 p.p. on MNIST, +7 p.p. on CIFAR-10).
  • Across the 96 evaluated configurations reported in the excerpt, S2S outperforms S2A in about 60% of cases and S2A in 30% (the remainder of that sentence is truncated in the provided content).

Methodology in Plain English

The authors set up a network of n devices split into C disconnected components, where each component is an undirected, time-varying graph. Every round, each device takes one local stochastic gradient step, then averages models with its D2D neighbors using a mixing matrix W. Every H rounds, the server samples K devices uniformly at random without replacement, averages their models, and returns the result according to either S2S or S2A.

To compare the two, the authors define two error quantities after each server round: a bias error (how much the global average model shifts) and a disagreement error (how far local models are from that global average). They show S2S makes the bias zero but leaves disagreement, while S2A does the opposite.

The technical core is an orthogonal decomposition that splits total disagreement into an intra-component part (reducible only by D2D mixing) and an inter-component part (reducible only by server aggregation). This required departing from standard decentralized-SGD analyses because the S2A update is column-stochastic but not row-stochastic — so the usual spectral-gap argument for doubly stochastic W does not apply — and because the S2S analysis needs to reflect that D2D rounds cannot reduce inter-component heterogeneity.

Under standard assumptions (L-smoothness, convexity for the convex results, bounded stochastic variance, doubly stochastic block-diagonal mixing matrix, and bounded intra- and inter-component heterogeneity), they derive iteration complexities for S2S and S2A in both convex and non-convex settings, then evaluate those bounds numerically and validate them with experiments.

Why This Matters

Research impact. The paper provides the first convergence analysis of the S2S primitive for non-convex objectives and the first systematic theoretical and empirical comparison of S2S versus S2A in a single framework. It also removes a restrictive assumption in prior work (that at least one device per component is sampled each round), which previously required the server to know component membership — problematic given device count, mobility, and privacy. The orthogonal decomposition into intra- and inter-component disagreement is a reusable analytical tool for hybrid D2D/D2S systems.

Real-world applications. The setting matches the hierarchical structure of modern networks, so the design guidance applies to:

• Federated training across fleets of smartphones, where D2D links are cheap and wide-area uplinks are expensive.
• Wireless sensor networks with clustered topology and periodic gateway connectivity.
• Edge deployments with time-varying, disconnected local-area clusters that must still learn a shared global model.
• Any environment with privacy constraints where the server cannot learn which devices share a local network.

Industry relevance. The practical decision — should the server broadcast an aggregate to everyone, or return it only to the devices it sampled? — is a concrete configuration choice with measurable accuracy consequences (up to +8.4 p.p. reported between strategies in one setting). The paper's guidelines let practitioners choose based on heterogeneity, sampling rate, server period, and connectivity rather than by default.

Future Directions

• Extending the analysis to dynamic communication graphs. The paper states that all results extend to time-varying mixing matrices, with details deferred to an appendix; a fuller treatment of mobility-driven topology changes would be a natural next step.
• Designing adaptive strategies. Since no single primitive wins in all regimes, a method that switches between S2S and S2A based on estimated heterogeneity or connectivity could be explored.
• Estimating heterogeneity in practice. The regime boundaries depend on ζ̄_intra and ζ̄_inter, which are theoretical constants; practical estimators for them would make the guidelines directly actionable.
• Broadening beyond the studied settings. The experiments use two components, two datasets, three topologies, and a fixed set of sampling rates, periods, and stepsizes; other component counts, larger heterogeneity levels, and different optimization objectives remain open.

Target Audience

Researchers and graduate students in distributed optimization and federated learning, especially those working on decentralized or hierarchically structured training; engineers designing semi-decentralized FL deployments who need to choose between server dissemination strategies; and theoretically inclined practitioners interested in how sampling rate, aggregation period, and network connectivity interact with data heterogeneity.

Authors’ abstract

In semi-decentralized federated learning, devices primarily rely on device-to-device communication but occasionally interact with a central server. Periodically, a sampled subset of devices uploads their local models to the server, which computes an aggregate model. The server can then either (i) share this aggregate model only with the sampled clients (sampled-to-sampled, S2S) or (ii) broadcast it to all clients (sampled-to-all, S2A). Despite their practical significance, a rigorous theoretical and empirical comparison of these two strategies remains absent. We address this gap by analyzing S2S and S2A within a unified convergence framework that accounts for key system parameters: sampling rate, server aggregation frequency, and network connectivity. Our results, both analytical and experimental, reveal distinct regimes where one strategy outperforms the other, depending primarily on the degree of data heterogeneity across devices. These insights lead to concrete design guidelines for practical semi-decentralized FL deployments.