PaperlayerView exact revision on arXiv

Source-linked AI summary

Federated Learning via Over-the-Air Computation

Kai Yang, Tao Jiang, Yuanming Shi, Zhi Ding

arXiv:1812.11750v3cs.LGcs.ITeess.SPstat.ML

TL;DR

Federated learning faces limited bandwidth when aggregating locally computed updates across mobile devices. This paper uses over-the-air computation with sparse and low-rank DC optimization for device selection and beamforming, achieving better prediction accuracy and faster convergence in experiments.

  • Problem

    Limited network bandwidth is the main bottleneck for globally aggregating locally computed updates in on-device federated learning.

  • Method

    The paper combines over-the-air computation with joint device selection and beamforming modeled through sparse and low-rank optimization, solved using a convergence-guaranteed DC algorithm.

  • Results

    Better prediction accuracy and faster convergence were achieved when training an SVM classifier on CIFAR-10 compared with state-of-the-art algorithms.

  • Takeaways & Limitations

    The proposed approach provides fast global model aggregation for federated learning while maximizing selected devices under model-aggregation MSE requirements.

  • Takeaways & Limitations

    Security issues in model aggregation, including robustness against malicious attacks, remain beyond the paper's scope.

Abstract

from arXiv · show

The stringent requirements for low-latency and privacy of the emerging high-stake applications with intelligent devices such as drones and smart vehicles make the cloud computing inapplicable in these scenarios. Instead, edge machine learning becomes increasingly attractive for performing training and inference directly at network edges without sending data to a centralized data center. This stimulates a nascent field termed as federated learning for training a machine learning model on computation, storage, energy and bandwidth limited mobile devices in a distributed manner. To preserve data privacy and address the issues of unbalanced and non-IID data points across different devices, the federated averaging algorithm has been proposed for global model aggregation by computing the weighted average of locally updated model at each selected device. However, the limited communication bandwidth becomes the main bottleneck for aggregating the locally computed updates. We thus propose a novel over-the-air computation based approach for fast global model aggregation via exploring the superposition property of a wireless multiple-access channel. This is achieved by joint device selection and beamforming design, which is modeled as a sparse and low-rank optimization problem to support efficient algorithms design. To achieve this goal, we provide a difference-of-convex-functions (DC) representation for the sparse and low-rank function to enhance sparsity and accurately detect the fixed-rank constraint in the procedure of device selection. A DC algorithm is further developed to solve the resulting DC program with global convergence guarantees. The algorithmic advantages and admirable performance of the proposed methodologies are demonstrated through extensive numerical results.

I. INTRODUCTION

Federated learning addresses privacy and edge-resource constraints by distributing training across devices, but limited bandwidth makes model aggregation a bottleneck. The paper proposes over-the-air aggregation with joint device selection and beamforming, formulated through sparse and low-rank optimization and solved using a convergent DC algorithm.

  • Motivation: Edge machine learning performs training and inference locally to meet low-latency and privacy requirements despite limited device resources.Federated learning distributes learning across mobile devices while retaining data locally.
  • Challenges: Federated learning faces statistical challenges from non-IID device data and communication bottlenecks from large model-update loads.FedAvg selects devices, performs local updates, and aggregates them at a central node.
  • Approach: Over-the-air computation uses wireless signal superposition to compute weighted averages of local updates through concurrent transmission.The approach targets faster FedAvg aggregation by co-designing computation and communication.
  • Optimization model: Joint device selection and beamforming is modeled as sparse and low-rank optimization because it combines combinatorial selection with nonconvex quadratic constraints.Matrix lifting introduces a rank-one matrix constraint alongside a sparse representation of device selection.
  • Algorithm: A unified difference-of-convex-functions representation induces sparsity and low-rankness, while successive convex relaxation yields a DC algorithm with global convergence guarantees.The method uses an ℓ1-norm minus Ky Fan k-norm representation and trace norm minus spectral norm for rank-one structure.
  • Evaluation: Numerical experiments report better prediction accuracy and faster convergence for SVM training on CIFAR-10 than state-of-the-art algorithms.The paper also reports admirable performance in simulations for the proposed feasibility detection and device-selection methods.

B. Over-the-Air Computation for Aggregation

Over-the-air computation aggregates locally updated models by exploiting wireless signal superposition, while beamforming and power control determine the aggregation distortion. The section formulates the received estimate and its MSE for FedAvg aggregation.

  • Over-the-air computation computes distributed functions such as arithmetic means through concurrent transmission over a multiple-access channel.This integrates communication and computation to improve communication efficiency relative to orthogonal transmission.
  • The FedAvg target is a weighted aggregation of local models, with device-specific preprocessing and base-station post-processing scalars.The local model zi is scaled by φi = |Di|, and ψ = 1/Σk∈S|Dk| is applied at the base station.
  • Each selected device transmits normalized local-model symbols across d time slots, and the base station receives their superposition through device channels plus noise.The transmitter scalar is bi, the channel vector is hi, and the noise follows n ∼ CN(0, σ2I).
  • The base station applies receiver beamforming and normalization to estimate the aggregated vector before post-processing into the global model.The receiver beamforming vector is m, the normalizing factor is η, and each target-vector element is obtained as ẑ = ψ(ĝ).
  • The MSE between the over-the-air estimate and target aggregation value quantifies model-aggregation distortion and is minimized by a zero-forcing transmitter for fixed receiver beamforming.The transmitter design is constrained by each device’s maximum transmit power.

C. Problem Formulation

The formulation maximizes the number of selected devices while satisfying an over-the-air aggregation MSE requirement. It converts the coupled selection and beamforming problem into sparse and low-rank optimization, then identifies feasible devices through the sparse representation.

  • C. Problem Formulation: The objective is to maximize selected devices while guaranteeing an MSE requirement for over-the-air aggregation.The resulting problem couples the combinatorial selected set S with continuous receiver beamforming variables.
  • C. Problem Formulation: The original optimization is difficult because its objective is combinatorial and its MSE constraint is nonconvex and quadratic.The nonconvexity arises with coupled device-selection and beamforming variables.
  • C. Problem Formulation: The paper proposes sparse and low-rank modeling to support efficient algorithms for joint device selection and beamforming.The modeling approach is introduced specifically for on-device distributed federated learning.
  • A. Sparse and Low-Rank Optimization: Problem (11) is equivalently rewritten as a mixed combinatorial optimization problem with nonconvex quadratic constraints.The reformulation expresses device feasibility through constraints associated with individual devices.
  • A. Sparse and Low-Rank Optimization: The reformulated target is to maximize feasible MSE constraints under the regularity condition ∥m∥2 ≥ 1.The regularity condition avoids the singular solution m = 0.
  • A. Sparse and Low-Rank Optimization: The sparsity pattern of x encodes device feasibility: xi = 0 means device i can be selected while satisfying the MSE requirement.Maximizing feasible devices is therefore represented by minimizing the number of nonzero xk values.
  • A. Sparse and Low-Rank Optimization: Matrix lifting replaces beamforming vector m with the PSD matrix M = mmH, while retaining rank(M) = 1 to represent the original formulation.This produces a sparse and low-rank optimization problem, but the resulting problem remains nonconvex.

B. Problem Analysis

The problem combines sparse optimization with a low-rank constraint, making it nonconvex and computationally difficult. The paper addresses these structures with unified DC representations designed to improve device selection and rank-one feasibility detection.

  • Problem P has a sparse objective and a low-rank constraint, so both central structures are nonconvex and computationally difficult.These structures arise in machine learning, signal processing, statistics, and wireless communication.
  • The paper introduces a unified DC programming approach to solve the sparse and low-rank optimization problem.The approach is intended to improve over existing algorithms while preserving efficient optimization.
  • A parameter-free DC approach enhances sparsity to maximize the number of selected devices.This avoids choosing a smoothing parameter for the sparsity-inducing procedure.
  • Instead of dropping the rank-one constraint as in semidefinite relaxation, the paper proposes a DC approach intended to guarantee the exact rank-one constraint.This targets the deterioration of Gaussian-randomization performance as antenna number N increases.
  • The rank-one DC construction uses the difference between the trace norm and spectral norm set to zero.The paper links this construction to accurate feasibility detection for nonconvex quadratic constraints.

IV. DC REPRESENTATION FOR THE SPARSE AND LOW-RANK FUNCTIONS

The framework represents device selection through separate sparse and low-rank structures, using DC formulations to prioritize devices and enforce rank-one feasibility.

  • IV. DC REPRESENTATION FOR THE SPARSE AND LOW-RANK FUNCTIONS: The ℓ0-norm is represented as the minimum k for which the difference between the ℓ1-norm and Ky Fan k-norm is zero.The Ky Fan k-norm sums the largest k absolute values.
  • IV. DC REPRESENTATION FOR THE SPARSE AND LOW-RANK FUNCTIONS: For a positive semidefinite matrix, the rank-one constraint is equivalently expressed by zero difference between its trace norm and spectral norm.The proof uses the vanishing of all singular values except the largest.
  • IV. DC REPRESENTATION FOR THE SPARSE AND LOW-RANK FUNCTIONS: The two-step framework first induces sparsity to guide device-selection priority, then solves feasibility problems to identify the maximum feasible device set.Each step is formulated as a DC program.

1) Step I: Sparsity Inducing:

Step I solves a DC program to induce sparsity, then orders devices by the resulting values so smaller values receive higher selection priority.

  • 1) Step I: Sparsity Inducing:: Sequentially increasing k yields a sparse vector x⋆ when the Step I objective reaches zero while satisfying the rank-one condition.The procedure increases k from 0 to M.
  • 1) Step I: Sparsity Inducing:: The vector x characterizes each device’s gap between the MSE requirement and achievable MSE, so devices with smaller x_k receive higher priority.The elements are ordered in descending order before forming candidate device sets.
  • 1) Step I: Sparsity Inducing:: Candidate sets S[k] retain devices from position k onward in the descending ordering x_π(1) ≥ ··· ≥ x_π(M).The set is defined as {π(k), π(k + 1), ···, π(M)}.
  • 1) Step I: Sparsity Inducing:: The framework is implemented as Algorithm 2, alternating sparsity induction with feasibility detection using DC programs.Step II increments k until the feasibility objective reaches zero.

A. Difference-of-Strongly-Convex-Functions Representation

The DC programs are rewritten as differences of strongly convex functions, enabling iterative convex approximations based on primal-dual updates and subgradient linearization.

  • A. Difference-of-Strongly-Convex-Functions Representation: Quadratic terms are added so the component functions become strongly convex without changing their differences.This creates a uniform strongly convex difference structure for PS1 and PS2.
  • A. Difference-of-Strongly-Convex-Functions Representation: The algorithm constructs primal and dual candidate sequences, using convex relaxation because both corresponding problems remain nonconvex.Wirtinger calculus is applied for complex-domain variables.
  • A. Difference-of-Strongly-Convex-Functions Representation: Each iteration solves convex approximations by linearizing the concave component at the current iterate using a subgradient.The same procedure is applied to the sparse and feasibility-detection programs.
  • A. Difference-of-Strongly-Convex-Functions Representation: The subgradient of the spectral norm is formed from v_1v_1^H, where v_1 is an eigenvector associated with the largest eigenvalue.The largest singular value determines the relevant spectral direction for the PSD matrix.

C. Convergence Analysis

The convergence analysis establishes descent and convergence properties for the iterative DC procedures applied to both sparse-inducing and feasibility-detection problems.

  • C. Convergence Analysis: For PS2, the corresponding sequence converges to a critical point from any initial point, and its objective sequence is strictly decreasing and convergent.The supplied proposition states the convergence property for the feasibility-detection objective.
  • C. Convergence Analysis: For PS1, the generated sequence converges to a critical point from any initial point, while its objective sequence is strictly decreasing and convergent.The proposition also characterizes the limiting objective value as the global minimum of f1.
  • C. Convergence Analysis: The convergence results are stated as propositions for the sequences generated by iterative solutions of PS1 and PS2.The proof is referred to the appendix.

VI. SIMULATION RESULTS

The simulations compare the proposed DC method with state-of-the-art approaches under specified channel, SNR, device, and antenna settings.

  • Experiments use i.i.d. complex-normal channels, average transmit SNR of 20 dB, and equal data counts across devices.

A. Probability of Feasibility

The simulations evaluate feasibility detection, antenna scaling, device selection, and federated-learning performance of the proposed DC approach.

  • A. Probability of Feasibility: The proposed DC feasibility-detection approach significantly outperforms SDR and achieves near-optimal performance relative to global optimization.Results average 100 trials and support accurate feasibility detection.
  • B. Number of Selected Devices over Target MSE: Increasing BS antennas enables fast aggregation under more stringent target MSE requirements.
  • B. Number of Selected Devices over Target MSE: The proposed DC sparsity and low-rankness inducing approach selects more devices than the compared state-of-the-art approaches.The comparison averages results over 100 channel realizations.
  • VII. CONCLUSION: The paper concludes that its proposed approaches show admirable performance compared with state-of-the-art algorithms.

APPENDIX A PROOF OF PROPOSITION 1

The proof states that the zero-forcing transmitter beamforming vectors minimize the mean-square error.

  • The sequence {b_i} has a zero-forcing structure that enforces the relevant beamforming condition.
  • The mean-square error satisfies the expression established in the proof.
  • Therefore, the zero-forcing transmitter beamforming vectors given in Proposition 1 minimize the mean-square error.

APPENDIX B PROOF OF PROPOSITION 5

The proof analyzes the iterates generated by repeatedly solving the stated problem and establishes decreasing objective behavior, convergence, and critical-point properties.

  • The proof studies the sequence {(M^[t], x^[t])} generated by iteratively solving problem (40).
  • The objective sequence is non-increasing and, in the stated result, strictly decreasing until convergence.
  • Each limit point is shown to satisfy the relevant critical-point condition for the difference-of-convex objective.
Loading 1812.11750v3…