PaperlayerView exact revision on arXiv

Source-linked AI summary

Polar Code Based Federated Learning: Convergence Analysis and Resource Allocation

Han Xiao, Wei Kang, Nan Liu

arXiv:2608.13961v1cs.LG

TL;DR

Federated learning must handle communication impairments while protecting quantization bits of unequal importance. This paper uses finite-blocklength polar codes for unequal error protection and optimizes quantization and block lengths, achieving substantial gains over uncoded and LDPC-based benchmarks.

  • Problem

    Quantization bits represent unequal intervals, motivating channel coding that provides unequal rather than equal error protection.

  • Method

    The scheme uses finite-blocklength polar-code UEP to protect quantized model bits by significance and optimizes quantization bits and block lengths across training iterations.

  • Results

    Polar-code schemes with constant or variable block lengths achieve faster convergence and higher accuracy than uncoded and LDPC benchmarks, especially at large erasure probabilities.

  • Takeaways & Limitations

    Constant block lengths may suffice when variable-length optimization is computationally prohibitive because the variable strategy provides only a modest additional gain.

Abstract

from arXiv · show

Federated learning (FL) enables collaborative model training across distributed devices without sharing raw data; however, it faces significant communication bottlenecks and channel impairments in practice. Conventional network layer treatments either idealize the channel as error free or apply equal error protection (EEP) to transmitted model updates, failing to account for the inherently unequal importance of quantization bits within a single local model. To address this limitation, we propose a cross layer polar code based FL scheme that leverages the unequal error protection (UEP) property of polar codes under finite block lengths. Specifically, the proposed design selectively protects more significant quantization bits, thereby mitigating the detrimental effects of channel noise. We further provide a rigorous convergence analysis of the proposed scheme, deriving an upper bound on the convergence gap, which we then jointly optimize over the number of quantization bits and the polar code block length across all training iterations. Experimental results demonstrate that both constant and variable block length configurations of our polar code based scheme consistently achieve substantial performance gains over uncoded and LDPC-based EEP benchmarks, with the advantage becoming increasingly pronounced as the channel quality deteriorating. These findings confirm the efficacy of our cross-layer design in enhancing FL robustness and efficiency under realistic channel conditions.

I. INTRODUCTION · II. SYSTEM MODEL

The paper motivates a cross-layer polar-code federated learning design that protects quantized model bits according to significance and optimizes convergence-related communication parameters. It models federated optimization over distributed users with local updates, binary-erasure transmissions, and server aggregation.

  • I. INTRODUCTION: Federated learning avoids direct raw-data transmission because privacy regulations and communication limitations constrain centralized training.
  • I. INTRODUCTION: Existing network-layer approaches either assume error-free channels or apply noisy-channel treatments without addressing the unequal importance of quantized model bits.
  • I. INTRODUCTION: The proposed scheme exploits finite-blocklength polarization to provide unequal error protection for quantized model bits according to their significance.
  • I. INTRODUCTION: The paper derives an upper bound on the convergence gap and jointly optimizes quantization-bit count and polar-code block length across training iterations.
  • II. SYSTEM MODEL: The system comprises M users and a server that minimize a federated objective built from strongly-convex local losses and disjoint user datasets.
  • II. SYSTEM MODEL: At each round, the server uniformly selects K of M users, broadcasts the current global model, and selected users perform mini-batch stochastic-gradient updates.
  • II. SYSTEM MODEL: Users transmit local gradients rather than updated model parameters, and the server reconstructs received gradients before aggregating them to update the global model.
  • II. SYSTEM MODEL: The communication model uses repeated binary erasure channel transmissions with erasure probability ϵ and output alphabet {0, 1, E}.

III. PROPOSED POLAR CODE BASED FL SCHEME · A. Quantization · B. Polar codes and Bhattacharyya parameters

The proposed scheme jointly designs unbiased quantization and polar coding to reduce communication overhead while providing unequal error protection for quantization bits. Uniform quantization maps bounded gradients to binary sequences, and finite-length polar codes exploit synthesized-channel quality differences characterized by Bhattacharyya parameters.

  • III. PROPOSED POLAR CODE BASED FL SCHEME: The scheme jointly designs unbiased quantization and polar codes, replacing separated quantization and channel-coding functions with a cross-layer approach.Quantization reduces communication overhead, while polar codes provide unequal error protection.
  • A. Quantization: Gradient updates bounded in [Bmin, Bmax] are quantized using n bits into 2^n uniformly spaced levels.The interval width is determined by the range and the number of quantization levels.
  • A. Quantization: Each gradient component is quantized separately, and the resulting stochastic quantization is unbiased.The paper states this unbiasedness in Lemma 1 and maps each quantized component to a binary sequence of length n.
  • A. Quantization: The quantization interval represented by bit i is 2^(i−1)∆, so different bits represent unequal intervals and require unequal error protection.The unequal interval sizes make bit importance inherently nonuniform within each quantized value.
  • B. Polar codes and Bhattacharyya parameters: Polar codes achieve channel capacity asymptotically, but finite block lengths produce synthesized channels whose qualities polarize only mildly.At finite lengths, channels do not reach the ideal error-free or totally blocked extremes.
  • B. Polar codes and Bhattacharyya parameters: The Bhattacharyya parameter Z(W) quantifies synthesized-channel performance and upper-bounds the bit-error probability under successive cancellation decoding.This parameter is used to compare the reliability of individual synthesized channels.
  • B. Polar codes and Bhattacharyya parameters: Reordering synthesized channels by ascending Bhattacharyya parameters reveals the finite-blocklength unequal error protection property required by quantization.The ordering associates lower Bhattacharyya parameters with better channel quality.

C. Joint design of quantization and channel coding · IV. CONVERGENCE ANALYSIS

The scheme assigns quantization bits to polar-code synthesized channels according to their unequal protection needs and compensates decoding bias before reconstruction. Its convergence analysis bounds the effects of scheduling, quantization, and transmission, showing how coding resources and quantization resolution influence the optimality gap.

  • C. Joint design of quantization and channel coding: Quantized gradient components are represented as binary sequences and mapped to polar-code synthesized channels, with fixed inputs used as frozen bits.The channel output is decoded for each bit before reconstruction.
  • C. Joint design of quantization and channel coding: Because quantization bits represent unequal intervals, the scheme uses polar-code UEP to protect the more consequential bits.This cross-layer assignment links quantization significance to channel-coding protection.
  • C. Joint design of quantization and channel coding: Before reconstruction, the channel output is shifted by Z_l as a soft-output compensation for decoding bias.Z_l is experimentally estimated to satisfy P_l ≤ Z_l ≤ Z(W^(l)_N).
  • IV. CONVERGENCE ANALYSIS: The convergence analysis jointly examines client scheduling, quantization, and polar coding over BEC under L-smoothness, strong convexity, unbiased gradients, and bounded stochastic-gradient conditions.These assumptions are introduced to analyze the proposed SGD algorithm.
  • IV. CONVERGENCE ANALYSIS: Theorem 1 provides an upper bound on the expected squared distance to the optimum when the step size satisfies the stated condition.The bound is expressed using quantization bits, the minimal quantization interval, and polar-channel error parameters.
  • IV. CONVERGENCE ANALYSIS: Increasing the number of subchannels N decreases Bhattacharyya parameters, while increasing quantization bits n decreases Δ; both reduce the optimality gap.The theorem identifies transmission loss and quantization error as corresponding contributors to the bound.
  • IV. CONVERGENCE ANALYSIS: The initial optimality gap vanishes as the number of iterations increases, while residual distance reflects SGD, scheduling, quantization, and transmission effects.The analysis attributes the residual distance to these four sources and describes the initial-gap shrinkage over iterations.
  • IV. CONVERGENCE ANALYSIS: The proof derives a recursive upper bound by separating hypothetical aggregation stages and using independence of channel noise, quantization noise, and training data across users.The resulting recursion leads to the bound on Θ_T used to complete Theorem 1.

A. Proof of Lemma 4

The proof of Lemma 4 models quantized-gradient bits through independent binary components and bit-flip indicators, then uses channel symmetry and client independence to establish the required inequality. Cross-bit terms vanish under independent channel inputs, completing the proof.

  • Bit-error model: The derivation represents each quantized-gradient component as a binary sequence and models its l-th bit error with indicator I_l, satisfying E[I_l] = P_l.I_l = 0 denotes correct decoding and I_l = 1 denotes a flipped bit.
  • Symmetry assumptions: The proof assumes independent, uniformly distributed gradient components and uses channel symmetry to express correct and erroneous bit-decoding probabilities as 1 − P_l and P_l.The soft channel output is uniformly distributed over {P_l, 1 − P_l}.
  • Expectation simplification: Independent client gradients and channel inputs make cross-bit expectations vanish, allowing the proof to simplify the mixed terms in the target inequality.For distinct bits, the relevant expectation is shown to equal zero under the stated independence assumptions.
  • Conclusion: Combining the derived expectation identities proves inequality (39), completing the proof of Lemma 4.The final step explicitly combines equations (63) and (70).

B. Proof of Lemma 5

The proof of Lemma 5 invokes Lemma 1 and a similar argument as in (81), with Jensen’s inequality justifying one step. It also considers unbiased stochastic quantization before completing the proof.

  • Proof of Lemma 5: The proof begins by applying Lemma 1.
  • Proof of Lemma 5: A subsequent step follows a similar argument as in (81).
  • Proof of Lemma 5: Jensen’s inequality justifies step (a).
  • Proof of Lemma 5: The proof assumes an unbiased stochastic quantization method.
  • Proof of Lemma 5: These steps complete the proof of Lemma 5.

C. Proof of Lemma 6

The proof of Lemma 6 uses an indicator for membership in S_{t+1}, whose sum over k equals K. Its intermediate steps rely on Lemma 4 in, PM^2, and Assumption 4.

  • C. Proof of Lemma 6: The indicator I{k ∈ S_{t+1}} equals 1 for k ∈ S_{t+1} and 0 otherwise.This function encodes membership in S_{t+1}.
  • C. Proof of Lemma 6: The indicators over k sum to K: Σ_{k=1} I{k ∈ S_{t+1}} = K.The passage states this identity immediately before the proof.
  • C. Proof of Lemma 6: Proof step (a) follows from Lemma 4 in, step (b) from PM^2, and step (c) from Assumption 4.These cited results and assumptions justify the corresponding transitions in the lemma proof.

D. Proof of Lemma 7

The proof upper-bounds D1 by decomposing it into constituent terms and applying smoothness, strong convexity, Jensen, Cauchy, and AM-GM inequalities under the stated assumptions. It then uses the step-size conditions to obtain the desired bound.

  • Bounding D1: The proof first isolates D1 as the remaining term requiring an upper bound.D1 is expressed through the expected squared distance and an inner product involving ∇F(wt).
  • Bounding D1: The bound on D1 controls P2 using Jensen’s inequality and the L-smooth property of Fk(·).The derivation explicitly identifies Jensen’s inequality and smoothness as the basis for the substitution.
  • Bounding D1: The proof further invokes the µ-strongly convex property of Fk(·), Jensen’s inequality, Cauchy inequality, and AM-GM inequality.These inequalities are applied sequentially when substituting intermediate equations into the bound.
  • Bounding D1: Because F(wt) −F(w∗) ≥0 and ηt+1 ≤ 1 2L, the proof simplifies the resulting expression and then applies the non-increasing step-size condition ηt ≤2ηt+1.The final substitutions also use E ∥X −E [X]∥2 ≤E ∥X∥2 with X = wk t −wt−1.

V. ALLOCATION OF CHANNELS USES AND QUANTIZATION BITS

The section optimizes channel uses and quantization bits across training iterations to reduce the convergence bound, while approximating BEC Bhattacharyya parameters with a Gaussian CDF. The allocation enforces fixed total channel use, power-of-two per-iteration channel uses, and iteration-dependent parameters.

  • Iteration-dependent allocation: Because later iterations contribute more through hQ_T, the number of channels N and quantization bits n should vary with t so H_t decreases over time.The preceding analysis assumes fixed N and n across all iterations.
  • Optimization formulation: The optimization minimizes the convergence-bound loss over N and n, which affect transmission loss and quantization loss.A constant step size η simplifies the objective by removing iteration-independent terms.
  • Optimization constraints: The allocation fixes total channel uses through Nave and restricts each iteration’s channel uses to powers of 2, matching polar-code structure.Nave denotes the average number of channel uses per iteration.
  • Bhattacharyya-parameter approximation: A Gaussian cumulative distribution function approximates BEC Bhattacharyya parameters because their recursive computation lacks an explicit closed form.The approximation is applied to parameters appearing in the optimization loss.
  • Bhattacharyya-parameter approximation: The Gaussian approximation fits Bhattacharyya parameters very accurately across block lengths and erasure probabilities according to SSE, R2, AR2, and RMSE evaluations.The fitting parameters’ mean and variance are approximated as linear functions of block length N, with coefficients depending on erasure probability ϵ.

A. Optimization of number of quantization bits nt

The optimal number of quantization bits balances decreasing quantization loss against declining reliability of extra bits. Thus, nt depends on erasure probability ϵ, not polar-code block length N or iteration t.

  • Optimization of number of quantization bits nt: Increasing nt lowers quantization loss but makes channels carrying extra bits less reliable, producing competing effects measured by NMSE.For low channel erasure probability, larger n yields lower NMSE; as erasure probability increases, smaller n performs better.
  • Optimization of number of quantization bits nt: The objective first decreases and then increases with nt; for Nt = 32 and ϵ = 0.6, the optimum is nt = 4.nt values in {3, 4, 5} provide approximately the same objective value and are considered “good” choices.
  • Optimization of number of quantization bits nt: For a given ϵ, a constant n can be “good” across block lengths N = 16, 32, 64, 128, although increasing ϵ reduces the number of such choices.At ϵ = 0.8, no constant n is “good” for all listed block lengths, so n = 3 is used as a compromise.
  • Optimization of number of quantization bits nt: The parameter nt depends only on ϵ and does not depend on block length N or iteration t.The subsequent optimization keeps n fixed while optimizing Nt.

B. Optimization of the block length Nt

The block-length allocation is formulated as a mixed-integer nonlinear program with per-iteration constraints and solved using particle swarm optimization. Compared with a constant-length benchmark at the same average block length, the proposed variable allocation converges better and faster by using shorter early-stage and longer late-stage blocks.

  • Optimization formulation: The optimized block lengths satisfy 4 ≤ P_t ≤ 7 for every iteration t.These constraints are imposed for all t ∈ {1, . . . , T}.
  • Optimization formulation: The resulting problem is a mixed-integer nonlinear program solved using particle swarm optimization.The method optimizes the block-length allocation under the stated formulation.
  • Comparison setup: For T = 35, the proposed scheme uses the optimized solution with average block length N_ave = 16, whereas the benchmark fixes N = 16 throughout.The comparison uses the second term in the convergence upper bound as its performance criterion.
  • Convergence comparison: At ϵ = 0.6, the proposed scheme’s superiority over the benchmark becomes apparent in the later iteration stage.The analysis attributes this to weaker suppression of the relevant convergence-bound term in that stage, motivating additional resource allocation.
  • Convergence comparison: During 35×16 channel uses, the proposed allocation converges better and faster by using shorter blocks early and longer blocks later.The channel-use coordinate makes the convergence-speed difference more evident than the iteration-based plot.

VI. NUMERICAL RESULTS · VII. CONCLUSION

Numerical results on MNIST show that constant- and variable-block-length polar-coded FL converges faster and achieves higher test accuracy than uncoded and LDPC benchmarks, especially at high erasure probabilities. The conclusion emphasizes finite-blocklength polar-code UEP for significance-aware quantization-bit protection and joint optimization of quantization bits and block length.

  • VI. NUMERICAL RESULTS: Experiments use MNIST gray images and a CNN for ten-class handwritten-digit classification.MNIST contains 70,000 images: 60,000 training samples and 10,000 testing samples, each sized 28 × 28.
  • VI. NUMERICAL RESULTS: The experimental setup uses 20 IID clients with 3,000 samples each, selects 20% per global iteration, and runs T = 40 iterations.Training data are shuffled and randomly assigned across clients.
  • VI. NUMERICAL RESULTS: Variable-length polar coding selects n = 5 for 0 ≤ ϵ ≤ 0.4, n = 4 for 0.5 ≤ ϵ ≤ 0.6, and n = 3 for ϵ ≥ 0.7, with block lengths optimized by P3.The block-length sequence {N_t} follows the optimization solution from Section V.
  • VI. NUMERICAL RESULTS: Both polar-coded schemes converge faster and reach higher testing accuracy than uncoded and LDPC schemes, particularly when the erasure probability is large.The convergence comparison evaluates accuracy on testing data for the converging CNN under different erasure probabilities.
  • VI. NUMERICAL RESULTS: Both constant- and variable-length polar schemes consistently achieve substantial gains over uncoded and LDPC benchmarks in converged-CNN test accuracy.The improvement is attributed largely to polar codes’ unequal error protection property.
  • VII. CONCLUSION: The proposed FL scheme protects quantization bits according to relative significance using finite-blocklength polar-code UEP and jointly optimizes quantization bits and block length across training iterations.The paper also provides convergence analysis and optimizes an upper bound on the convergence gap.
Loading 2608.13961v1…