PaperlayerView exact revision on arXiv

Source-linked AI summary

On Analog Gradient Descent Learning over Multiple Access Fading Channels

Tomer Sery, Kobi Cohen

arXiv:1908.07463v1cs.LGcs.ITstat.ML

TL;DR

Distributed learning over noisy fading MAC must aggregate many nodes’ local information without incurring centralized or orthogonal communication costs. The paper develops GBMA, which transmits analog local gradients over common waveforms and updates from their noisy superposition without power control or beamforming. Its finite-sample analysis and energy-scaling results show that centralized GD convergence rates can be approached as the network grows, with simulations supporting the theory.

  • Problem

    The paper asks whether gradient-based learning over noisy fading MAC can achieve centralized GD convergence rates and what transmission-energy scaling enables this.

  • Method

    GBMA transmits analog local gradients using common shaping waveforms, allowing the edge to update from their superposition without power control or beamforming.

  • Results

    Finite-sample bounds and energy-scaling laws establish convergence-rate guarantees for convex and strongly convex objectives as the number of nodes increases.

  • Takeaways & Limitations

    Increasing network size can make GBMA approach centralized convergence rates while reducing total transmission-energy consumption.

  • Takeaways & Limitations

    The energy-scaling discussion assumes B(N) = O(N^(1−ε)) for some ε > 0.

Abstract

from arXiv · show

We consider a distributed learning problem over multiple access channel (MAC) using a large wireless network. The computation is made by the network edge and is based on received data from a large number of distributed nodes which transmit over a noisy fading MAC. The objective function is a sum of the nodes' local loss functions. This problem has attracted a growing interest in distributed sensing systems, and more recently in federated learning. We develop a novel Gradient-Based Multiple Access (GBMA) algorithm to solve the distributed learning problem over MAC. Specifically, the nodes transmit an analog function of the local gradient using common shaping waveforms and the network edge receives a superposition of the analog transmitted signals used for updating the estimate. GBMA does not require power control or beamforming to cancel the fading effect as in other algorithms, and operates directly with noisy distorted gradients. We analyze the performance of GBMA theoretically, and prove that it can approach the convergence rate of the centralized gradient descent (GD) algorithm in large networks. Specifically, we establish a finite-sample bound of the error for both convex and strongly convex loss functions with Lipschitz gradient. Furthermore, we provide energy scaling laws for approaching the centralized convergence rate as the number of nodes increases. Finally, experimental results support the theoretical findings, and demonstrate strong performance of GBMA using synthetic and real data.

I. INTRODUCTION

Distributed learning over noisy MAC addresses the storage, latency, bandwidth, and energy costs of centralized or orthogonal communication by aggregating node information at the network edge. The paper positions analog MAC transmission as a resource-efficient approach for distributed sensing and federated learning.

  • Centralized learning becomes inefficient in storage and latency as data-intensive applications grow.
  • In federated learning, nodes optimize local loss functions while communicating with a parameter server that solves the global objective.
  • Orthogonal FDM/TDM communication requires bandwidth that increases linearly with the number of nodes.
  • Orthogonal schemes also incur energy costs from additive noise in each transmitted dimension and may converge slowly because of cycling messages.
  • Analog MAC lets nodes transmit functions of their data whose superposition can provide sufficient statistics while using dimensions independent of N.
  • Prior MAC learning methods include sparse gradient transmission, power control, channel scheduling, and receiver beamforming to address fading.

C. Main Results

The paper develops GBMA for online learning over noisy fading MAC and analyzes its convergence under convex and strongly convex objectives. Its finite-sample bounds and energy-scaling results show that increasing network size can approach centralized GD rates while retaining resource-efficient transmission.

  • Algorithm Development and Design Parameters: GBMA transmits each node’s local gradient over common shaping waveforms, and the edge updates the estimate from their noisy superposition.
  • Algorithm Development and Design Parameters: GBMA uses phase correction rather than power control or beamforming, and updates directly from the noisy distorted gradient.
  • Performance Analysis: Finite-sample error bounds cover convex and strongly convex loss functions with Lipschitz gradients under i.i.d. fading channels and data collections.
  • Performance Analysis: Ω(N^ε−2) transmission energy per node is sufficient for strongly convex objectives to achieve O(c^k) convergence as N →∞.
  • Performance Analysis: Ω(N^ε−2) transmission energy per node is sufficient for convex objectives to achieve O(1/k) convergence as N →∞.
  • Performance Analysis: The results imply that total network transmission energy can become arbitrarily small while approaching centralized convergence rates as network size increases.
  • Performance Analysis: Simulations in federated learning and distributed signal processing support the theory and show strong performance even outside the theoretical conditions.

D. Related Work

Prior distributed inference and learning methods use MAC, orthogonal transmissions, or model-dependent information, motivating GBMA for bandwidth- and energy-efficient online learning with unknown observation distributions.

  • MAC-based inference avoids bandwidth scaling that is linear in the number of nodes under orthogonal channels.
  • LBMA and TBMA require nodes to transform local observations into likelihood-based or quantized waveform transmissions.
  • Several prior MAC inference studies assume observation distributions are known to the nodes or network edge, whereas this paper treats them as unknown.
  • The paper applies MAC to online learning to address the bandwidth and energy costs of orthogonal federated-learning transmissions.
  • Orthogonal node transmissions can impose high bandwidth and energy consumption in distributed learning.
  • The network optimizes a sum of local loss functions using node-specific gradients and a shared parameter vector.

III. GRADIENT-BASED LEARNING OVER MAC

GBMA lets nodes transmit analog local-gradient functions simultaneously over a fading MAC, after which the edge forms a noisy gradient estimate and updates the shared parameter. The method uses feedback for iterative operation and can match centralized GD in the noiseless equal-gain case.

  • GBMA has all nodes simultaneously transmit linear combinations of local gradients using common analog waveforms.
  • The edge updates the parameter with the received distorted gradient and broadcasts the new estimate back to nodes for the next iteration.
  • The fading MAC produces a noisy superposition of transmitted gradients, which matched filtering converts into a projected gradient estimate.
  • The procedure uses d orthogonal waveforms and can extend larger parameter dimensions across consecutive slots with slight analytical modifications.
  • Phase correction is unnecessary when channel gains have nonzero means, while phase error below π/4 suffices to produce nonzero-mean gains when channel means are zero.
  • In noiseless channels with equal gains, the received vector is the true global gradient and GBMA achieves centralized GD's convergence rate.

A. Implementation Discussion of the GBMA Algorithm

GBMA is designed to reduce communication costs by aggregating analog transmissions over the MAC, while its analysis uses standard convexity and smoothness concepts to characterize convergence rates.

  • GBMA's bandwidth requirement is independent of the number of nodes, unlike TDM/FDM schemes whose requirement increases linearly with node count.
  • Aggregated channel noise is independent of the number of nodes, yielding energy savings relative to TDM/FDM schemes.
  • GBMA does not require prior knowledge of observation distributions, unlike LBMA and TBMA.
  • The paper defines linear convergence as O(c^k) for 0 < c < 1 and sublinear convergence as O(1/k).
  • The analysis uses Lipschitz-gradient and strong-convexity properties, including their behavior under weighted sums of functions.

V. PERFORMANCE ANALYSIS

The performance analysis studies how GBMA error decreases with iterations, node count, and transmission energy. It derives finite-sample bounds for strongly convex and convex objectives and identifies energy scaling needed to approach centralized GD rates.

  • The analysis considers excess risk as the objective-value gap from the optimum and studies its dependence on iterations, node count, and transmission energy.
  • Strongly convex objectives: Finite-sample error bounds are established for finite iteration count k and node count N under strongly convex objectives with Lipschitz gradients.
  • Strongly convex objectives: As N increases, the analysis targets the linear convergence rate associated with centralized GD under strongly convex, Lipschitz-gradient objectives.
  • Convex objectives: Finite-sample error bounds are also established for convex objectives with Lipschitz gradients.
  • Convex objectives: As N increases, the required transmission-energy scaling is analyzed for achieving the sublinear rate O(1/k).

C. Discussion on the Main Theorems 1, and 2

The discussion explains how gradient distortion and channel noise affect GBMA’s error bounds, while increasing network size and transmission energy makes its convergence approach centralized GD. It also identifies constant-step-size behavior and energy scaling laws for convex and strongly convex objectives.

  • Error components: The error bound contains initial-distance, gradient-distortion, and additive-noise terms, with noise increasing with σw and dimension d and decreasing with N and EN.The analysis allows expected squared gradients to be arbitrarily large under its stated conditions.
  • Convergence and distortion: In noiseless channels with equal gains, GBMA uses the same data as centralized GD and achieves the same performance.The theorem bounds coincide with this observation under the corresponding parameter settings.
  • Convergence and distortion: Channel distortion decreases the admissible stepsize and decelerates strongly convex linear convergence, but its effect vanishes as N →∞.Under convex objectives, the distortion contribution also diminishes with network growth.
  • Convergence and distortion: GBMA’s error bound approaches centralized GD as the number of nodes increases and the distortion term diminishes.This applies to the theorem-based analysis of the distributed algorithm.
  • Energy scaling: Setting EN = Ω(N^ε−2) yields the centralized convergence rate as N →∞, while suitable scaling can make total network transmission energy arbitrarily close to zero.These laws are presented for distributed learning under resource constraints.
  • Comparison with SGD: With constant stepsize, GBMA approaches O(c^k) and O(1/k) convergence orders for strongly convex and convex functions, respectively, as N increases.The comparison concerns noisy distorted gradients and Lipschitz-gradient objectives.

VI. EXPERIMENTS

The experiments evaluate GBMA in two distributed settings: federated prediction using song data and source localization using wireless sensor networks. The simulations are designed to support the theoretical analysis.

  • Experimental settings: The experiments cover federated learning for song-release-year prediction and distributed source localization in wireless sensor networks.The first setting uses real data, while the second concerns sensing-system estimation.

A. Federated Learning over the Million Song Dataset

The Million Song Dataset experiment distributes song samples across devices and uses regularized linear least squares to predict release years. Under equal gains and Rayleigh fading, empirical errors follow the theoretical characterization, while increasing nodes or energy reduces error and GBMA outperforms orthogonal-channel GD in the reported comparison.

  • Dataset and model: Each device stores one Million Song Dataset sample, containing a release year and 90 audio attributes used for prediction.The dataset covers mostly western commercial tracks released from 1922 to 2011.
  • Dataset and model: The devices use regularized linear least squares losses that are strongly convex with Lipschitz gradients.The stated loss satisfies the conditions of Theorem 1.
  • Equal-gain results: With equal channel gains, empirical error supports the theoretical bound: it initially decreases linearly, then becomes dominated by a variance term.The experiment varies N with EN = 1 and varies ε with N = 500 and EN = N^ε−2.
  • Rayleigh-fading results: Under i.i.d. Rayleigh fading, empirical error again supports the theoretical bound, with distortion and variance dominating at larger iteration counts.The error decreases when either N or EN increases.

B. Source Localization using a Wireless Sensor Network

The source-localization experiment models noisy acoustic measurements from wireless sensors and evaluates GBMA against distributed and centralized gradient methods. GBMA achieves lower empirical error while reducing transmission energy, and its energy scaling behavior approaches zero energy at fixed error as the network grows.

  • Problem setup: The local loss is neither convex nor Lipschitz, so the conditions of Theorems 1 and 2 do not hold.Despite this limitation, convergence is demonstrated when the source is sufficiently distant and the initial estimate is close to the true value.
  • Performance comparison: GBMA achieves significant empirical-error gains while saving significant transmission energy relative to FDM-GD and centralized GD.The comparison uses GBMA at −50dB, FDM-GD at −6dB, and centralized GD as a benchmark.
  • Energy scaling: With E_N = N−1.5, total transmission energy decreases to zero as N increases while maintaining error 10−2.This numerical experiment directly examines the predicted energy scaling behavior.
  • Overall findings: Across the paper’s experiments, results support the theoretical analysis and demonstrate strong GBMA performance in distributed learning and signal-processing applications.The conclusion connects the source-localization experiment with the broader MAC learning setting.

VIII. APPENDIX

The appendix proves the main convergence results by analyzing the expected update and squared update norm under channel gains and additive noise, then applying convexity and smoothness assumptions. The proofs use independence, Lipschitz-gradient bounds, recursive inequalities, and telescoping sums.

  • Proof strategy: The appendix provides proofs for Theorems 1 and 2 by analyzing the squared distance from the optimum after each GBMA update.The iterate relation is θ_k+1 = θ_k − βv_k.
  • Moment bounds: The expected update E[v_k] and expected squared update norm E[||v_k||2] are evaluated over additive noise and channel-gain processes.The derivation uses independence between channel gains, gradients, and iterates.
  • Strongly convex case: The strongly convex proof combines Lipschitz-gradient and strong-convexity properties with the condition ∇F(θ*) = 0.These bounds yield a recursive inequality for the expected objective or distance to the optimum.

2. Hence,

This proof section derives convergence bounds by enforcing expected objective decrease and recursively controlling the fading-channel update variance. The argument uses convexity, monotonicity, telescoping, and a bounded-gradient assumption.

  • Convex convergence: The expected objective sequence {E[F(θ_i)]} is monotonically decreasing when the stated condition holds.This monotonicity supports the subsequent telescoping argument.
  • Fading-channel convergence: For fading channels, the proof bounds E[F(θ_k+1)] using the update relation θ_k+1 − θ_k = −βv_k.The expected squared update norm contributes an additional variance term to the bound.
  • Convex convergence: The convex proof obtains its bound by combining the recursive inequality with convexity and a telescoping sum.The proof concludes after applying the relevant condition and induction.
  • Fading-channel convergence: The fading-channel bound assumes E[||∇f_n(θ)||2] < B(N) before using monotonicity to complete the result.The assumption controls the gradient contribution in the recursive analysis.
Loading 1908.07463v1…