PaperlayerView exact revision on arXiv

Source-linked AI summary

Adaptive Gradient Sparsification for Efficient Federated Learning: An Online Learning Approach

Pengchao Han, Shiqiang Wang, Kin K. Leung

arXiv:2001.04756v3cs.LGcs.DCmath.OCstat.ML

TL;DR

The paper addresses fixed-sparsity gradient sparsification designed mainly for i.i.d. settings, where FL tasks can instead involve heterogeneous resources and non-i.i.d. client data. It proposes fairness-aware bidirectional top-k sparsification and online learning based on an estimated derivative sign to adapt k for training-time efficiency. Experiments on FEMNIST and CIFAR-10 support the effectiveness of the approaches, including better performance than FedAvg and more stable adaptive-k behavior than alternative online methods.

  • Problem

    Existing gradient-sparsification methods generally use fixed sparsity and focus on i.i.d. client data, despite varying FL resources and non-i.i.d. datasets.

  • Method

    The paper combines fairness-aware bidirectional top-k gradient sparsification with online learning that adapts k using an estimated derivative sign and adjustable search interval.

  • Results

    Experiments on non-i.i.d. FEMNIST and CIFAR-10 data show better performance than FedAvg, while the proposed adaptive-k method outperforms alternatives and yields a more stable k.

  • Takeaways & Limitations

    Adaptive gradient sparsification can address communication–computation trade-offs in non-i.i.d. FL while fairness-aware selection ensures each client contributes gradient elements.

Abstract

from arXiv · show

Federated learning (FL) is an emerging technique for training machine learning models using geographically dispersed data collected by local entities. It includes local computation and synchronization steps. To reduce the communication overhead and improve the overall efficiency of FL, gradient sparsification (GS) can be applied, where instead of the full gradient, only a small subset of important elements of the gradient is communicated. Existing work on GS uses a fixed degree of gradient sparsity for i.i.d.-distributed data within a datacenter. In this paper, we consider adaptive degree of sparsity and non-i.i.d. local datasets. We first present a fairness-aware GS method which ensures that different clients provide a similar amount of updates. Then, with the goal of minimizing the overall training time, we propose a novel online learning formulation and algorithm for automatically determining the near-optimal communication and computation trade-off that is controlled by the degree of gradient sparsity. The online learning algorithm uses an estimated sign of the derivative of the objective function, which gives a regret bound that is asymptotically equal to the case where exact derivative is available. Experiments with real datasets confirm the benefits of our proposed approaches, showing up to $40\%$ improvement in model accuracy for a finite training time.

I. INTRODUCTION

Federated learning trains models from decentralized data without sharing raw data, but heterogeneous clients and non-i.i.d. data make fixed gradient sparsity inadequate. The paper addresses these challenges with fairness-aware sparsification and online adaptation of the sparsity level.

  • Federated learning shares model weights or gradients instead of raw client data, supporting training when data cannot be centrally shared because of privacy or bandwidth constraints.
  • Client resources and networks vary substantially across tasks, from mobile phones with fast networking and slow computation to micro-datacenters with the opposite profile.
  • Gradient sparsification sends important gradient subsets, offering finer communication–computation control than FedAvg’s send-all-or-nothing updates.
  • Existing GS methods commonly use fixed sparsity and mainly assume i.i.d. client data, although optimal sparsity depends on task, bandwidth, computation, model, and data distribution.
  • The paper asks how to choose sparsity optimally and apply GS to non-i.i.d. FL, then introduces fairness-aware bidirectional top-k GS and an online-learning formulation for adaptive k.
  • The proposed online method uses only the estimated derivative sign, addressing the difficulty of obtaining an unbiased exact derivative for the one-dimensional k decision.

A. Preliminaries

The paper frames federated learning as synchronized distributed training and replaces full model-weight aggregation with sparse-gradient aggregation. Its FAB-top-k method selects sparse updates bidirectionally while preserving client participation and model synchronization.

  • Federated Learning: Federated learning trains models from local client data through repeated local computation and central aggregation without sharing the training data.The global loss is not directly observable because training data remains local at each client.
  • Gradient Sparsification: Gradient sparsification communicates only important gradient elements, reducing communication compared with FedAvg’s send-all-or-nothing approach.The paper aggregates sparsified gradients after every local update step rather than aggregating model weights.
  • Synchronized Updates: All clients remain synchronized because they receive the same sparse gradient and apply the same update rule to their weights.Sorting client gradients takes O(D log D) time, while server-side union computation and binary search take O(ND log D) time.
  • Fairness-Aware Bidirectional Top-k GS: FAB-top-k transmits k gradient elements in both uplink and downlink communication, avoiding the potentially kN-element downlink of unidirectional top-k GS.This saves downlink overhead by up to a factor of N.
  • Fairness-Aware Gradient Element Selection: Each client accumulates local gradients, selects its top-k absolute-value elements, and sends their index-value pairs to the server.The server forms a union of candidate indices, selects the downlink set, aggregates values, and broadcasts the sparse gradient.
  • Fairness-Aware Gradient Element Selection: FAB-top-k guarantees that each client contributes at least floor(k/N) elements to the sparse global gradient.The fairness guarantee follows from selecting client contributions with κ = floor(k/N).
  • Convergence: FAB-top-k’s convergence is supported experimentally, while a theoretical convergence analysis is left for future work.The proposed intuition is that omitted gradient elements continue accumulating until they become large enough for selection.
  • Generalization: The adaptive-k framework applies beyond FAB-top-k to any gradient-sparsification method with a defined sparsity degree.The paper uses “k-element GS” as a general term for such methods.

IV. ONLINE LEARNING TO DETERMINE k

Choosing k requires balancing communication savings against learning speed: smaller k reduces communication but can slow learning, while larger k improves gradient fidelity at greater communication cost. The paper therefore seeks an optimal k that minimizes total convergence time.

  • Communication–Learning Trade-off: Small k reduces communication but can slow learning because the sparse-gradient direction may differ substantially from the full-gradient direction.The trade-off concerns both communication efficiency and learning efficiency.
  • Communication–Learning Trade-off: Large k captures the gradient more accurately but incurs greater communication overhead.The relevant objective is total training convergence time, including computation and communication.

A. Problem Formulation

The paper formulates training time for reaching a target loss as the cost optimized over the sparsity degree k. It extends this cost to continuous k through randomized rounding and analyzes adaptive selection under stated structural assumptions.

  • 1) Cost Definition:: Training time, including computation and communication, to reach a desired global loss is defined as the cost minimized by choosing k.The formulation can also extend to other costs, such as energy consumption, although the paper focuses on training time.
  • 1) Cost Definition:: Assumption 1 states that future loss progression from a given loss is independent of the sparsity choices used before reaching that loss.This treats the current loss as sufficient to represent the model state for subsequent progression.
  • 1) Cost Definition:: Assumption 1 is empirically supported on FEMNIST with 156 clients because post-ψ losses remain almost identical after all curves switch to k = 1000.Different k values are used before reaching the target global loss ψ.
  • 1) Cost Definition:: For integer k, ˜t(k,l) represents the total computation and communication time associated with a training round over a specified loss interval.The interval is bounded by the optimal global loss L* and the initialization loss L0.
  • 1) Cost Definition:: The loss-interval formulation permits comparing schedules that use different k values over time by expressing total training time as an integral across the corresponding loss intervals.Different k values may produce different round-end losses, but the total time remains expressible in this form.
  • 1) Cost Definition:: A suitable ˜t(k,l) exists when per-round computation-plus-communication time is fixed for each k and the loss transition is differentiable and monotonically increasing in starting loss.The proposition supplies conditions for the cost representation rather than a convergence theorem.
  • 2) Extension to Continuous k:: Continuous k is implemented by stochastic rounding between floor(k)-element and ceiling(k)-element GS with probabilities ceiling(k)−k and k−floor(k).When k is integer, randomized k-element GS equals standard k-element GS.
  • 2) Extension to Continuous k:: The expected continuous-k training time is the probability-weighted interpolation of the neighboring integer-k training times.The paper assumes convexity in k, bounded partial derivatives, and a common minimizing k across loss values for its online-learning analysis.

3) Online Learning Formulation:

The paper formulates adaptive selection of the gradient-sparsity parameter k as an online learning problem that minimizes training time to a target loss. Decisions are made sequentially as information about training-time functions is revealed, and the proposed approach uses derivative signs rather than exact derivatives.

  • 3) Online Learning Formulation:: The objective is to find a static k∗ minimizing total training time to reach target loss LM.
  • 3) Online Learning Formulation:: Training time is modeled through an unknown function t(k, l), whose information is revealed over successive loss levels l.
  • 3) Online Learning Formulation:: In round m, the system chooses km using information revealed for earlier loss intervals, then observes a new loss Lm.
  • 3) Online Learning Formulation:: For alternative k values, τm(k) evaluates time over the same loss interval produced by the selected km, possibly corresponding to a fractional number of rounds.
  • 3) Online Learning Formulation:: Regret compares the sequential choices {km} with the best fixed k∗ chosen in hindsight.
  • 3) Online Learning Formulation:: The goal is sublinear regret, so average regret converges to zero as the number of rounds M grows.
  • B. Online Learning Based on the Sign of Derivative: A continuous online-gradient approach is difficult because unbiased derivative estimates are hard to obtain, motivating an algorithm requiring only the derivative sign.

1) Online Learning Procedure for Determining km:

The proposed online procedure searches over a bounded interval of sparsity values and updates k opposite the estimated derivative sign. Its regret remains asymptotically comparable to gradient descent, even when only noisy sign estimates are available.

  • The algorithm searches for k∗ within a continuous interval K = [kmin, kmax], whose width is B = kmax − kmin.
  • At round m, it uses the derivative-sign value sm and step size δm to update k in the opposite direction of the sign.
  • Only the sign of τ′m(km) is required; the full function τm(·) and the endpoint losses need not be known.
  • The exact-sign procedure satisfies the regret bound stated in Theorem 1.
  • With estimated signs ŝm, the method assumes the expected estimate has the correct derivative sign and controls estimation quality using Hm and H.
  • Theorem 2 gives an expected regret bound for the estimated-sign algorithm, with the exact- and estimated-sign bounds differing only by constant factor H.
  • The resulting asymptotic bound matches online gradient descent with exact gradients and gradient descent on an unchanging cost function.
  • Compared with bandit formulations, the method is theoretically better than continuous bandits and empirically outperforms tested MAB algorithms.

D. Extension to Varying Search Intervals

The extended algorithm adapts its search interval when the original range causes excessive fluctuation or when a narrower range is justified. Restarting with a smaller interval can preserve the theoretical regret bound and improve the actual bound.

  • When communication dominates computation, a large search range can cause overly large updates and fluctuation in k, increasing communication time.
  • Algorithm 3 is equivalent to running multiple Algorithm 2 instances with different search intervals and widths.
  • Starting a second instance with B′ can lower cumulative regret when both intervals contain k∗ and the interval-shrinkage condition is met.
  • Algorithm 3 estimates a narrower interval from recent minimum and maximum k values, scaled by coefficient α.
  • A new instance starts when the reduced range satisfies B′ < B and has run for at least as many rounds as the previous instance.
  • If the final-round condition holds, Algorithm 3 remains bounded by Theorem 2, or Theorem 1 when exact derivative signs are used.

E. Implementation of Derivative Sign Estimation

The implementation estimates the derivative sign by comparing losses under the current and a smaller sparsity choice. These extra measurements use one sample per client and are integrated with communication and computation so their overhead remains small.

  • Each client evaluates three losses on one randomly selected minibatch sample using the previous, current, and alternative model weights.
  • The alternative k′m-element sparsification tests whether reducing k is beneficial.
  • Figure 3 separates client-server communication steps 1⃝–5⃝ from client computation steps (A)–(D).
  • The server averages the client losses and maps the alternative update to the same loss interval used to define τm(k).
  • The sign estimate is computed from the mapped loss comparison, with the expression inside sign(·) representing the estimated derivative.
  • If the loss comparisons do not satisfy the expected decrease conditions, the estimate is unavailable and k remains unchanged.
  • Additional losses require only one sample per client, making their computation small relative to minibatch gradient computation.
  • Because k′m < km, only difference information between the two sparsified gradients is transmitted, and loss reporting can overlap with the next round’s computation.

V. EXPERIMENTATION RESULTS

The experiments evaluate gradient-sparsification methods on non-i.i.d. FEMNIST and compare fixed- and adaptive-k approaches under controlled communication settings. FAB-top-k outperforms FedAvg while providing fairness advantages over fairness-unaware bidirectional top-k.

  • Experimental setup: Experiments use non-i.i.d. FEMNIST data, partitioned by writer across 156 clients, with 34,659 training and 4,073 test samples.FEMNIST contains 62 handwritten digit and letter classes.
  • Fixed-k comparison: Fixed-k evaluation compares FAB-top-k with unidirectional top-k, FUB-top-k, Periodic-k, FedAvg, and always-send-all approaches.The fixed-k comparison uses k = 1000 and communication time of 10.
  • Experimental setup: Communication time scales proportionally with the number of gradient elements transmitted relative to the full D-dimensional gradient.The setup assumes equal uplink and downlink speeds.
  • Adaptive-k comparison: Figure 5 evaluates adaptive k with different online learning methods on FEMNIST using communication time 10.The compared adaptive-k methods include value-based gradient descent, EXP3, and continuous bandit approaches.
  • Results: FAB-top-k performs better than FedAvg and provides fairness advantages over FUB-top-k by guaranteeing updates from every client.This reduces the possibility that some clients’ data are completely ignored during training.

B. Performance of Online Learning for Adaptive k

The proposed online learning method adaptively selects k and performs better than comparison methods while producing more stable sparsity choices. Experiments show that matching k to communication time, data, and model characteristics improves performance.

  • Online-learning comparison: The proposed approach outperforms value-based descent, EXP3, and continuous bandit methods, while producing a more stable k than EXP3 and continuous bandit.The comparison uses Algorithm 3 with α = 1.5, Mu = 20, kmin = 0.002·D, and kmax = D.
  • Adaptive k: The algorithm uses larger k when communication time is smaller, as expected.The evaluation considers communication times 0.1, 1, 10, and 100 on FEMNIST and CIFAR-10.
  • Adaptive k: For each communication time β, the sequence k_m,β learned for β gives the best performance for that same communication time.For example, k_m,0.1 outperforms k_m,100 at communication time 0.1, while k_m,100 outperforms k_m,0.1 at communication time 100.
  • Dataset effects: CIFAR-10 shows smaller differences among k sequences at low communication time because its highly non-i.i.d. assignment requires relatively large k.
  • Method summary: The conclusion reports that FAB-top-k guarantees each client contributes at least ⌊k/N⌋ gradient elements, while the online algorithm determines k using an estimated derivative sign.

APPENDIX

The appendix establishes properties of the adaptive-k update and develops the supporting lemmas used in the theorem analysis. The proofs rely on convexity, projection onto the feasible interval, and sign agreement between the estimated and true derivatives.

  • Auxiliary construction: The proof constructs the auxiliary function t̃(k,l) recursively so the defining relation holds across loss values and all k.
  • Supporting lemmas: For every iteration m, the sign term s_m and the deviation k_m − k* have a nonnegative product.This follows because convexity makes s_m nonnegative above k* and nonpositive below k*.
  • Theorem analysis: The appendix derives additional bounds from convexity and the update rule before combining the lemmas in the proof of Theorem 1.
  • Supporting lemmas: The update is defined by projecting k_m − δ_m s_m onto the feasible set, with k_M+1 included for later analysis although Algorithm 2 stops at M.

C. Proof of Theorem 2

The proof of Theorem 2 expresses expected regret through conditional expectations and bounds it using the estimated derivative sign and the established lemma inequalities.

  • Sign control: The proof uses that the estimated derivative sign matches the true sign and that s_m(k_m − k*) is nonnegative.
  • Regret derivation: The expected-regret derivation uses conditional expectation, linearity of expectation, and the law of total expectation.
  • Regret derivation: Replacing the true sign s_m with the estimated sign ŝ_m preserves the relevant Lemma 3 result for the regret bound.
Loading 2001.04756v3…