Machine Learning at the Wireless Edge: Distributed Stochastic Gradient Descent Over-the-Air

I. INTRODUCTION

• Wireless edge learning avoids transmitting all local data centrally because such communication can be costly in energy and bandwidth, introduce delay, and infringe user constraints.The paper therefore studies federated learning with local datasets and computation coordinated by a parameter server.Source: §I · pp. 1–2
• Distributed SGD parallelizes stochastic-gradient computation across devices, which send local gradients to a parameter server for global updates.Stochastic gradients provide unbiased estimates of the full loss gradient, enabling distributed processing of partitioned datasets.Source: §I · p. 1

A. Prior Works

• Prior federated-learning methods mainly reduce communication through quantization, sparsification, or local updates while often ignoring physical-layer and shared-wireless-channel constraints.The paper addresses these constraints directly over a wireless multiple access channel.Source: A. Prior Works · p. 2, B. Our Contributions · p. 2

B. Our Contributions

• D-DSGD quantizes gradients, uses error accumulation and capacity-achieving channel coding, and adapts transmitted bits and power across iterations.Allocating more power to later iterations compensates for decreasing gradient variance and improves noise protection.Source: B. Our Contributions · p. 2
• A-DSGD sparsifies gradients, projects them into the available channel bandwidth, and transmits the projections simultaneously so the MAC computes their sum.The PS reconstructs the summed sparse gradients from noisy observations, using approximate message passing.Source: B. Our Contributions · p. 2
• Over-the-air A-DSGD converges better than its digital counterpart, while D-DSGD outperforms the digital schemes studied in [2], [16].A-DSGD also degrades less under biased data distributions, and both methods improve as the number of devices increases with fixed total dataset size.Source: B. Our Contributions · pp. 2–3

II. SYSTEM MODEL

• Federated SGD sends local gradient estimates from M devices to a parameter server over a noisy Gaussian MAC, which returns a consistent global parameter vector.The PS uses a noisy gradient estimate to update the model, while its downlink is assumed error-free and unconstrained.Source: §II · p. 3
• The communication objective is to recover the average local gradient rather than individual gradients, motivating distributed function computation over the MAC.The paper compares separate digital communication with uncoded analog transmission for this objective.Source: §II · p. 3
• The Gaussian MAC is a deliberately simple bandwidth-limited uplink model whose proposed digital and analog schemes can extend to more complicated channels.The paper notes extensions to other channel models in follow-up work –.Source: §II · pp. 3–4

III. DIGITAL DSGD (D-DSGD)

• D-DSGD compresses gradients through sparsification and quantization, accumulates compression error locally, and transmits the resulting representation digitally over the MAC.Devices retain the highest and lowest entries, represent mean magnitudes and signs, and encode nonzero positions.Source: §III · p. 4
• D-DSGD allocates equal per-device power and allows the transmitted bit budget to vary across iterations according to the available sum power.The scheme can send more information early, when gradient variance is higher, and fewer bits later; this empirically improves performance over fixed compression [21].Source: §III · p. 4
• The proposed digital scheme uses log2-based enumeration to encode sparsity patterns independently of the nonzero-position distribution and is compared with S-DSGD [16] and Q-DSGD [2].The comparison is designed to assess D-DSGD against other digital schemes over a limited-capacity MAC.Source: §III · p. 4

IV. ANALOG DSGD (A-DSGD)

• A-DSGD transmits sparse, projected gradients simultaneously and without digital coding because the MAC directly supplies their superposition for averaging.The devices use local error accumulation before sparsification and transmission.Source: §IV · pp. 4–5
• When d ≫s, A-DSGD retains the k largest-magnitude entries, applies a shared random projection, and sends the resulting low-dimensional vector over the MAC.This avoids separately transmitting the indices of nonzero entries.Source: §IV · p. 5
• The PS uses a scaling side channel and the known projection matrix to estimate the average gradient with AMP, then updates θt+1 = θt −ηt · ˆg(θt).The received projected signals are noisy weighted sums of device gradients, while the scaling information supports compensation.Source: §IV · pp. 5–6
• A-DSGD’s power allocation accounts for decreasing stochastic-gradient variance, while uniform power across iterations provides a noise-resistant special case.The scaling factors can also be stabilized using variance-reduction techniques.Source: §IV · p. 6
• Increasing the device count can accelerate A-DSGD because more superposed signals improve robustness to noise, especially when P̄/sσ2 is small.Larger device populations also provide more information for estimating the average gradient.Source: §IV · p. 6
• The sparsification level k trades communication efficiency against the accuracy of the recovered average gradient.Small k reduces transmitted information but may make the projected estimate less accurate.Source: §IV · p. 6

A. Mean-Removal for Efficient Transmission

• A-DSGD can subtract each device’s projected-gradient mean before scaling and transmission to use available power more efficiently.The centered vector is defined as ˜gaz_m(θt) = ˜gm(θt) −µm(t)1˜s.Source: A. Mean-Removal for Efficient… · p. 6
• For s ≥ 3, removing the mean reduces transmit power relative to the transmit power in (12) by αaz_m(t)(s − 3)µ2_m(t).Source: A. Mean-Removal for Efficient… · p. 6

V. CONVERGENCE ANALYSIS OF A-DSGD ALGORITHM

• The analysis assumes ηt = η for all t and a differentiable, c-strongly convex loss.Source: §V · p. 6

• The convergence analysis begins by establishing preliminary background and essential analytical instruments.Source: A. Preliminaries · p. 7
• Assumption 1 bounds the average first moment of gradients across devices.Source: A. Preliminaries · p. 7
• Assumption 2 concerns the scaling factors used in the analysis.Source: A. Preliminaries · p. 7

• The model update accounts for scaling factors and assumes that device gradient norms are not highly skewed.Source: in (13), we approximate · p. 7
• AMP transforms a noisy compressed observation into an effective signal x̂ = x + σω as its state evolution converges toward the channel-noise level.The observation is y = Asx + z, with a measurement matrix and Gaussian noise.Source: in (13), we approximate · p. 7
• With sufficiently small sparsity level k relative to s, the assumed sparsity-pattern condition can be guaranteed in general.The condition holds trivially when all sparse gradients share a pattern and k < s −1.Source: in (13), we approximate · p. 7
• Sparsification incurs an approximation error bounded by λ||x||, with equality when all entries of x have equal magnitude.Source: in (13), we approximate · p. 7
• A Gaussian norm bound ensures that ||u|| is at most σuρ(δ) with probability arbitrarily close to one when δ is chosen appropriately.Source: in (13), we approximate · p. 7

• The success region contains parameter vectors within ε of the optimum, and convergence is established using rate supermartingale processes.Source: B. Convergence Rate · p. 7
• The rate-supermartingale construction is nonincreasing in expectation, grows with the horizon when the algorithm avoids the success region, and is Lipschitz in its first coordinate.Source: B. Convergence Rate · p. 8
• Theorem 1 bounds the probability that A-DSGD does not enter the success region by time T under the stated assumptions.Source: B. Convergence Rate · p. 8
• The denominator in the convergence bound reflects sparsification, random projection, and wireless-channel noise.Source: B. Convergence Rate · p. 8
• For a bounded learning rate, the probability of not reaching the success region tends to zero as T tends to infinity.Source: B. Convergence Rate · p. 8

Data distribution

• On MNIST, A-DSGD is nearly as effective under non-IID data as IID data, while D-DSGD degrades less than SignSGD and QSGD but remains less robust than A-DSGD.The non-IID convergence-rate reduction for A-DSGD is mainly attributed to mismatched gradient sparsity patterns across devices.Source: §VI · pp. 8–9

Power allocation

• A-DSGD outperforms D-DSGD across the considered power-allocation schemes, while time-varying power can improve D-DSGD accuracy by emphasizing later iterations.The experiments also report that A-DSGD maintains nearly its Fig. 2a performance despite a 60% reduction in average transmit power.Source: §VI · pp. 9–10, Figure 3 · p. 9

Transmit power

• A-DSGD outperforms D-DSGD at both tested average powers, whereas reducing power substantially deteriorates D-DSGD but has little effect on A-DSGD.The analog scheme is particularly attractive for low-power devices because superposed transmissions align their limited power against noise.Source: Figure 4 · p. 9, §VI · p. 10

Channel bandwidth

• Reducing channel bandwidth causes notable D-DSGD deterioration, while A-DSGD remains robust when s decreases from d/2 to 3d/10.This experiment supports an advantage of analog over-the-air computation under bandwidth constraints.Source: §VI · p. 10, Figure 5 · p. 10

Number of devices

• With total dataset size fixed, increasing the number of devices improves A-DSGD convergence and also improves D-DSGD at higher power; at very low power, D-DSGD fails to transmit information bits.A-DSGD benefits from additional superposed device power, despite smaller local datasets and less accurate individual gradients.Source: §VI · p. 10, Figure 6 · p. 10

Symbol budget

• For A-DSGD under a fixed symbol budget, reducing s from d/2 to d/5 improves performance, while further reduction to d/10 yields little additional benefit.When iterations are compared directly, larger s improves convergence speed and final accuracy; the symbol-budget comparison favors more iterations with lower-dimensional gradients.Source: §VI · pp. 10–11, Figure 7 · p. 11

Contributions

• The paper models DSGD over a wireless MAC and compares D-DSGD, which separates computation and communication, with A-DSGD, which computes average gradients over the air.The wireless model assumes noiseless downlink sharing of the updated parameter vector.Source: §VII · p. 11

Digital approach

• D-DSGD adapts transmitted bits to power constraints and can improve by allocating more power to later iterations as gradient variance decreases.Its devices quantize gradients and use capacity-achieving channel coding.Source: §VII · p. 11

Analog approach

• A-DSGD sparsifies gradients, applies a shared random projection to match channel bandwidth, and transmits compressed vectors simultaneously over the MAC.The shared projection reduces the parameter dimension while exploiting signal superposition for efficient bandwidth use.Source: §VII · p. 11

Results

• A-DSGD shows the largest improvements in low-power and low-bandwidth regimes, is more robust to non-IID bias, and both A-DSGD and D-DSGD improve as device count increases.D-DSGD still outperforms SignSGD and QSGD under biased data.Source: §VII · p. 11

APPENDIX A PROOF OF LEMMA 3

• Lemma 3 bounds the projected-gradient norm using the largest singular value of the random projection matrix and an upper bound on the accumulated error.The proof estimates the singular value asymptotically for high-dimensional random matrices and iterates the error bound recursively.Source: Appendix A · p. 12
• The proof combines independence across devices and time with the singular-value and error bounds to derive the lemma’s stated inequality.The resulting inequalities are substituted sequentially into earlier bounds.Source: Appendix A · p. 12

APPENDIX B PROOF OF INEQUALITY (52)

• The proof of inequality (52) reduces the claim to an inequality for positive scalars and concludes once that scalar inequality is established.This argument is presented as a separate appendix subsection.Source: Appendix B · p. 12

APPENDIX C PROOF OF LEMMA 4

• Lemma 4 follows by taking expectations over gradients and applying the definition of Δm(t), the preceding error inequality, Assumption 1, and Lemma 3.These steps provide the bound needed for the subsequent convergence proof.Source: Appendix C · p. 12

APPENDIX D PROOF OF THEOREM 1

• Theorem 1 defines a process for A-DSGD and analyzes it before the iterates enter the success region, using Lipschitzness and conditional expectation inequalities.The proof also introduces the complement of the success event and bounds its evolution.Source: Appendix D · p. 13
• The convergence argument uses the rate-supermartingale property together with Lemma 4 and the prescribed bound on η to complete Theorem 1.The final step replaces the initial process value to obtain the theorem’s stated result.Source: Appendix D · p. 13