PaperlayerView exact revision on arXiv

Source-linked AI summary

Communication-Efficient Stochastic Zeroth-Order Optimization for Federated Learning

Wenzhi Fang, Ziyi Yu, Yuning Jiang, Yuanming Shi, Colin N. Jones, Yong Zhou

arXiv:2201.09531v2cs.LGcs.AIeess.SP

TL;DR

Federated optimization is needed for settings where gradients are unavailable, including black-box attacks and hyperparameter tuning. The paper proposes FedZO, which uses local stochastic zeroth-order updates and partial participation, and extends it with AirComp. Simulations report FedZO performance comparable to FedAvg and AirComp-assisted convergence under appropriate SNR conditions.

Abstract

from arXiv · show

Federated learning (FL), as an emerging edge artificial intelligence paradigm, enables many edge devices to collaboratively train a global model without sharing their private data. To enhance the training efficiency of FL, various algorithms have been proposed, ranging from first-order to second-order methods. However, these algorithms cannot be applied in scenarios where the gradient information is not available, e.g., federated black-box attack and federated hyperparameter tuning. To address this issue, in this paper we propose a derivative-free federated zeroth-order optimization (FedZO) algorithm featured by performing multiple local updates based on stochastic gradient estimators in each communication round and enabling partial device participation. Under non-convex settings, we derive the convergence performance of the FedZO algorithm on non-independent and identically distributed data and characterize the impact of the numbers of local iterates and participating edge devices on the convergence. To enable communication-efficient FedZO over wireless networks, we further propose an over-the-air computation (AirComp) assisted FedZO algorithm. With an appropriate transceiver design, we show that the convergence of AirComp-assisted FedZO can still be preserved under certain signal-to-noise ratio conditions. Simulation results demonstrate the effectiveness of the FedZO algorithm and validate the theoretical observations.

I. INTRODUCTION

Federated optimization methods commonly rely on gradients or Hessians, which are unavailable in tasks such as black-box attacks and hyperparameter tuning. The paper introduces FedZO and analyzes its convergence, wireless implementation, and relation to existing federated and distributed zeroth-order methods.

I. INTRODUCTION

  • Existing federated first- and second-order methods generally require gradient or Hessian information, limiting their use when losses lack analytic expressions.The paper identifies federated hyperparameter tuning and distributed black-box attacks as examples where gradient information is unavailable.Source: §I · p. 1, A. Problem Formulation · p. 3
  • AirComp can mitigate wireless FL's communication bottleneck, but prior AirComp-assisted FL algorithms used first-order methods, leaving zeroth-order AirComp under-investigated.OMA participation is constrained by available time/frequency resource blocks; AirComp supports concurrent transmissions over the same channel.Source: §I · pp. 1–2

A. Main Contributions

  • FedZO uses stochastic gradient estimates and multiple local updates, permits partial device participation, and is analyzed for non-convex, non-i.i.d. data and AirComp-assisted wireless aggregation.The analysis characterizes convergence and linear speedup with local iterates and participating devices; simulations report comparable performance to FedAvg and convergence under an appropriate SNR setting.Source: A. Main Contributions · p. 2

B. Related Works

  • Earlier distributed zeroth-order work includes peer-to-peer methods, while central-server studies and methods allowing partial device participation are limited.The cited literature also includes methods with high sampling complexity, deterministic settings, or strongly convex analyses.Source: B. Related Works · pp. 2–3

C. Organization

  • The paper proceeds from problem formulation and FedZO to convergence analysis, AirComp implementation, simulations, and conclusions.It also introduces notation for norms, unit spheres and balls, uniform sampling, and gradient estimators.Source: C. Organization · p. 3

A. Problem Formulation

  • The formulation assigns each device a local expected loss and defines the global loss over devices, while assuming analytic loss expressions and gradients are unavailable.Devices can query sample loss values, which serve as stochastic approximations of their expected local losses.Source: A. Problem Formulation · p. 3

B. Preliminaries on Stochastic Gradient Estimator

  • The paper's mini-batch stochastic gradient estimator is biased for the actual gradient, has lower variance than the cited two-point estimator, and uses batch sizes independent of model dimension.Its computation complexity therefore does not scale with the dimension of the model parameter.Source: B. Preliminaries on Stochastic… · p. 3

C. FedZO Algorithm

FedZO reduces reliance on frequent model exchanges by taking multiple stochastic zeroth-order updates locally in each communication round. The server samples participating devices, distributes the global model, and aggregates their uploaded local-model changes; the number of local updates must be controlled to preserve convergence.

C. FedZO Algorithm

  • Each round samples M devices, sends them the global model, performs H stochastic zeroth-order local updates, and uploads the resulting model changes.The local models start from the received global model, and each update uses a stochastic gradient estimator.Source: C. FedZO Algorithm · p. 4
  • The server averages uploaded updates and adds the aggregate to the global model.This follows the FedAvg framework, but its convergence analysis cannot be directly transferred because FedZO's estimator is biased and its algorithm includes multiple local steps and partial participation.Source: C. FedZO Algorithm · p. 4
  • More local iterates reduce communication overhead but increase local-model discrepancies under heterogeneous data, potentially causing divergence.FedZO therefore must bound these discrepancies by choosing H appropriately.Source: C. FedZO Algorithm · p. 4

III. CONVERGENCE ANALYSIS FOR FEDZO

The analysis establishes FedZO convergence for non-convex objectives and non-i.i.d. data, first with full device participation. Its bounds relate convergence to data heterogeneity and zeroth-order estimator step size, and characterize the effects of local updates and device participation.

III. CONVERGENCE ANALYSIS FOR FEDZO

  • The convergence analysis assumes a lower-bounded, L-smooth objective, bounded stochastic-gradient second moments, and bounded local-to-global gradient dissimilarity.The gradient-dissimilarity condition is used to characterize the non-i.i.d. extent of local data.Source: §III · pp. 4–5

A. Full Device Participation

  • FedZO’s full-participation convergence bound contains terms for initial optimality, non-i.i.d. data heterogeneity, and the zeroth-order estimator step size.An appropriate estimator step size can be selected to attain the desired accuracy.Source: A. Full Device Participation · p. 5
  • The full-participation convergence rate can be dimension-independent and match FedAvg’s rate, while mini-batch sizes b1 and b2 balance dimension and iteration effects by improving estimator accuracy.The passage also notes that zeroth-order methods can be √d-times slower than first-order counterparts.Source: A. Full Device Participation · p. 5
  • Increasing local updates H can reduce communication rounds for the same accuracy, but H cannot be arbitrarily large if convergence is to be preserved.The analysis identifies an optimal upper choice for H, though its expression is not available in the supplied passage.Source: A. Full Device Participation · p. 5
  • FedZO attains linear speedup in local iterates and participating devices relative to centralized zeroth-order optimization, and requires H-fold fewer communication rounds than DZOPA.The analysis also states that the learning rate is lower than FedAvg’s, allowing more local updates while preserving convergence.Source: A. Full Device Participation · pp. 5–6

B. Partial Device Participation

With partial device participation, FedZO’s convergence bound includes an additional term from random device sampling. The analysis also constrains local updates to preserve the stated speedups.

B. Partial Device Participation

  • Theorem 2 states a result for FedZO with partial device participation, under Assumptions 1–4 and a learning-rate condition; the excerpt also says its constants are defined in Theorem 1.Source: B. Partial Device Participation · p. 6
  • Random device sampling adds an optimality-gap term absent under full participation, where sampling randomness is eliminated.The comparison is between the partial-participation bound (11) and full-participation bound (8).Source: B. Partial Device Participation · p. 6
  • To preserve linear speedup in local iterates and participating devices, the number of local iterates must stay within the derived bound and the constraint in (10).Together, these conditions determine the largest permissible H.Source: B. Partial Device Participation · p. 6

IV. AIRCOMP-ASSISTED FEDZO ALGORITHM

The AirComp-assisted design aggregates scheduled devices’ model updates over wireless uplinks. Its transceiver design addresses channel distortion while accounting for update magnitude and noise.

A. Over-the-Air Aggregation

  • AirComp lets scheduled devices transmit updates concurrently, making uplink communication resources independent of the number of participating devices, unlike OMA’s linear growth in resource blocks or latency.The server seeks the average local model update rather than each device’s update separately.Source: A. Over-the-Air Aggregation · p. 6
  • A channel-magnitude threshold selects participating devices to limit fading distortion; the analysis assumes channel coefficients are i.i.d. across devices and rounds.The scheduling strategy is treated as uniform sampling.Source: A. Over-the-Air Aggregation · p. 6

B. Transceiver Design

  • The transmitter design accounts for update magnitude, making distortion proportional to the maximum squared norm of local updates and allowing noise’s detrimental effect to diminish as the model converges.The wireless setup assumes error-free downlink dissemination, available channel-state information, and synchronization among devices.Source: §IV · p. 6, B. Transceiver Design · p. 7, A. Over-the-Air Aggregation · p. 7

C. Convergence Analysis for AirComp-Assisted FedZO

The analysis relates AirComp-assisted FedZO convergence to minimum receive SNR and identifies conditions for retaining the noise-free convergence order. Black-box attack simulations show how local updates, device participation, and SNR affect convergence, while attack accuracy varies against the baselines with the number of local updates.

C. Convergence Analysis for AirComp-Assisted FedZO

  • With communication quality satisfying 8 M̃γ ≥ NH, AirComp-assisted FedZO can attain the same-order convergence rate as the noise-free case.The rate depends on minimum receive SNR γ; lower SNR slows convergence.Source: C. Convergence Analysis for… · p. 7
  • Unlike existing AirComp methods whose bounds allow a non-diminishing optimality gap, this analysis shows a diminishing bound and uses a transceiver design that avoids optimization.The design follows COTAF’s principle and does not require the restrictive bounded-second-moment assumption noted for.Source: C. Convergence Analysis for… · p. 8

A. Federated Black-Box Attack

  • FedZO reduces attack loss for H ∈ {5, 10, 20, 50}, with faster convergence as local updates increase and lower loss than DZOPA and ZONE-S, even at H = 5.With more local updates, its attack loss decreases much faster than the baselines.Source: A. Federated Black-Box Attack · p. 8, Figure 1 · p. 9
  • Increasing participating devices among M ∈ {5, 10, 25, 50} improves FedZO’s attack-loss convergence speed.The experiment fixes H = 20.Source: A. Federated Black-Box Attack · p. 8, Figure 1 · p. 9
  • When H > 10, FedZO achieves better attack accuracy than ZONE-S and DZOPA; at H = 5, ZONE-S has higher accuracy but incurs higher attack loss.The authors attribute ZONE-S’s higher loss to distortion from its perturbation.Source: Figure 2 · p. 9, A. Federated Black-Box Attack · p. 9
  • For AirComp-assisted FedZO, convergence is preserved at −10, −5, and 0 dB SNR; 0 dB gives performance comparable to noise-free aggregation.Higher SNR accelerates convergence.Source: A. Federated Black-Box Attack · p. 9

B. Softmax Regression

On Fashion-MNIST softmax regression, FedZO converges slightly more slowly than FedAvg at the same number of local updates, but more FedZO updates narrow that performance gap. The experiments also show speedup with more participating devices, and the conclusion presents FedZO as an alternative when first-order information is unavailable.

B. Softmax Regression

  • FedZO with H = 20 achieves performance comparable to FedAvg with H = 5, although FedZO is slightly slower at the same number of local updates.The authors attribute the gap to uncertainty in FedZO’s gradient estimator.Source: B. Softmax Regression · p. 9, Figure 3 · p. 10
  • With H = 5, increasing participating devices speeds up FedZO in both training loss and testing accuracy; M = 50 gives performance comparable to FedAvg.The comparison uses FedAvg as the benchmark at H = 5 and M = 50.Source: B. Softmax Regression · p. 9, Figure 4 · p. 10

VI. CONCLUSION

  • The paper concludes that FedZO can serve as a satisfactory alternative to FedAvg when first-order information is unavailable.The conclusion also reports that AirComp-assisted FedZO can attain performance comparable to noise-free operation under certain SNR conditions.Source: §VI · p. 10

APPENDIX

The appendix proves the FedZO convergence theorems by bounding progress over communication rounds and client drift during local iterations. The partial-participation proof follows the full-participation argument, while the AirComp proof additionally bounds wireless noise.

APPENDIX

A. Proof of Theorem 1

  • For full participation, Lemma 1 bounds global-loss evolution, and Lemma 2 bounds the client-drift term needed to establish Theorem 1.The proof takes expectations and telescopes over communication rounds.Source: A. Proof of Theorem 1 · pp. 10–11

B. Proof of Theorem 2

  • For partial participation, Lemma 3 bounds global-loss evolution; combining it with Lemma 2 yields Theorem 2.The proof then follows the same steps as the full-participation proof.Source: B. Proof of Theorem 2 · p. 11

C. Proof of Theorem 3

Theorem 3’s proof adapts the earlier convergence argument by accounting for wireless aggregation noise. It bounds that noise, combines the resulting bound with the earlier lemmas, and derives the theorem.

C. Proof of Theorem 3

  • The proof represents the aggregated model as the noise-free aggregate plus a wireless-noise term, then uses smoothness to bound its effect on loss.The displayed proof conditions an expectation on the history at the start of the round.Source: C. Proof of Theorem 3 · p. 11
  • Under Assumptions 1–4, Lemma 4 states a result; combining Lemmas 2, 3, and 4 yields a result, and a similar derivation to Appendix A obtains Theorem 3.Source: C. Proof of Theorem 3 · pp. 11–12

D. Proof of Lemmas

The appendix proves Lemma 3 by bounding intermediate terms, using sampling properties and stated assumptions, then combining those bounds. It also notes that Lemma 1 is a simplified version of Lemma 3.

D. Proof of Lemmas

1) Proof of Lemma 3:

  • The proof uses uniform device sampling to bound T6 and the estimator’s expected gradient to bound T8.It also uses independence of sampled devices and Assumption 4.Source: 1) Proof of Lemma 3 · pp. 12, 14
  • Lemma 3 follows by combining the bounds in (31), (35), (36), (46), and (51).The proof bounds intermediate terms using sampling properties and assumptions.Source: 1) Proof of Lemma 3 · pp. 12–14

2) Proof of Lemma 1:

The proof of Lemma 1 reuses most intermediate results from Lemma 3, replacing M with N. Full participation removes randomness in M_t, so no upper bound for T5 is needed.

2) Proof of Lemma 1:

  • Lemma 1 reuses most intermediary results from Lemma 3 by replacing M with N; full participation removes randomness in M_t, so bounding T5 is unnecessary.Combining (31), (35), (36), and (46) yields Lemma 1.Source: 2) Proof of Lemma 1 · p. 14
  • The proof invokes the condition η ≤ 1/(3HL√˜cg) to obtain 3(1 − 3˜cgH^2L^2η^2) ≥ 2.Source: 2) Proof of Lemma 1 · p. 14

4) Proof of Lemma 4:

Lemma 4 follows from the derivation of Lemma 2 by setting τ = H.

4) Proof of Lemma 4:

Related papers

Loading 2201.09531v2…