PaperlayerView exact revision on arXiv

Source-linked AI summary

Secure Aggregation with Heterogeneous Quantization in Federated Learning

Ahmed Roushdy Elkordy, A. Salman Avestimehr

arXiv:2009.14388v3cs.ITcs.SYeess.SYmath.IT

TL;DR

Existing secure aggregation requires users to quantize updates uniformly, limiting adaptation to differing communication resources. HeteroSAg uses group and segment structure for secure aggregation with heterogeneous quantization. The paper reports improved accuracy–communication trade-offs, Byzantine mitigation, and reduced bandwidth expansion.

  • Problem

    Additive-masking secure aggregation requires a common quantization level despite users’ differing communication resources, and its bandwidth expansion can make aggressive quantization ineffective.

    Source: §1 · pp. 2–3

  • Method

    HeteroSAg enables heterogeneous quantization in secure aggregation through user grouping and coordinated aggregation of update segments.

    Source: §1 · p. 3, §3.3 · p. 8

  • Results

    HeteroSAg is reported to provide a better accuracy–communication-time trade-off, mitigate Byzantine users, and significantly reduce bandwidth expansion.

    Source: §6 · p. 16

  • Takeaways & Limitations

    HeteroSAg allows users to adjust quantization to their communication resources while retaining secure aggregation.

    Source: §6 · p. 16

    Optimal user clustering by transmission rate and optimal quantizer assignment are outside the paper’s scope.

    Source: §3.2 · p. 6

Abstract

from arXiv · show

Secure model aggregation across many users is a key component of federated learning systems. The state-of-the-art protocols for secure model aggregation, which are based on additive masking, require all users to quantize their model updates to the same level of quantization. This severely degrades their performance due to lack of adaptation to available bandwidth at different users. We propose three schemes that allow secure model aggregation while using heterogeneous quantization. This enables the users to adjust their quantization proportional to their available bandwidth, which can provide a substantially better trade-off between the accuracy of training and the communication time. The proposed schemes are based on a grouping strategy by partitioning the network into groups, and partitioning the local model updates of users into segments. Instead of applying aggregation protocol to the entire local model update vector, it is applied on segments with specific coordination between users. We theoretically evaluate the quantization error for our schemes, and also demonstrate how our schemes can be utilized to overcome Byzantine users.

1 Introduction

Federated learning trains a global model from updates computed on users’ local data, but secure aggregation protocols face a trade-off between communication time and accuracy when users have heterogeneous resources. HeteroSAg is proposed to support heterogeneous quantization, Byzantine robustness, and reduced bandwidth expansion.

1 Introduction

  • The introduction frames communication bottlenecks as arising from sending large models from each user to the server at every training iteration, with quantization and sparsification among proposed compression approaches.It also describes Byzantine users as sending arbitrary or malicious values that can severely degrade convergence.Source: §1 · p. 2
  • Existing additive-masking secure aggregation protocols require all users to use the same quantization level, trading shorter communication time for lower test accuracy or higher accuracy for longer communication time.Their bandwidth expansion includes additional O(log N) bits per model scalar, making them ineffective with aggressive quantization, especially for large N.Source: §1 · pp. 2–3

1.1 Main contributions

  • HeteroSAg partitions users into groups and local updates into segments to support secure aggregation with quantization adjusted to users’ communication resources.The paper presents this as a general method for heterogeneous quantization, not as a new quantization scheme.Source: §1 · p. 3, §1.2 · p. 3
  • For N = 210 users with single-bit quantization, HeteroSAg’s bandwidth expansion is 4×, compared with 11× for SecAg.The paper also claims zero mutual information between each masked update and its clear model update.Source: §1.1 · p. 3
  • HeteroSAg incorporates distance-based defenses such as coordinate-wise median, while the server observes some unmasked averaged segments that can support robust aggregation.The paper contrasts this with protocols where the server receives only masked individual updates and their aggregate.Source: §1.1 · p. 3
  • HeteroSAg’s experiments report accuracy close to the no-quantization baseline at the communication time of all users using 1-bit quantization, and about 15% higher test accuracy than homogeneous 1-bit quantization at equal communication time.The paper also reports experiments under three Byzantine attacks on two datasets and theoretical convergence guarantees for convex loss in the non-Byzantine setting.Source: §1.1 · p. 3

1.2 Related works

  • The paper distinguishes its objective from heterogeneous-quantization algorithms without privacy guarantees in a different network setup, which it says are not comparable.It also contrasts HeteroSAg’s single-server Byzantine-resilient aggregation with approaches requiring two non-colluding servers and with BREA.Source: §1.2 · p. 3
  • HeteroSAg’s per-user communication cost is O(m + N), versus O(N^2 + Nm) for BREA and O(N + Nm) for generalized BREA; its Byzantine-node bound is lower than that for coordinate-wise median.The paper says Byzantine resilience is an added feature to its primary goal of secure aggregation with heterogeneous quantization.Source: §1.2 · p. 4

2 Background

Secure aggregation masks individual users’ updates so the server can learn their aggregate. The background describes key sharing, quantization, encoding, and decoding steps used to make aggregation possible.

2 Background

  • Users establish pairwise keys and random seeds, then share private keys and private masks with other users through Shamir secret sharing.The private random seed protects privacy if a user is delayed but treated as dropped, since pairwise masks alone are insufficient in that case.Source: §2 · p. 4
  • Model updates are quantized because secure aggregation and cryptographic protocols require integer inputs for modular transmission.The background assumes update elements lie in [r1, r2] and describes a K-level quantizer.Source: §2 · p. 4
  • During encoding, quantized values are mapped to integers and users apply pairwise random masks to protect individual models.The integer range is chosen so every possible aggregate from the users can be represented without server-side overflow.Source: §2 · p. 5
  • During decoding, the server reconstructs seeds for surviving or dropped users, removes dropped users’ masks, and maps the aggregate back to real-valued updates.The protocol distinguishes users whose models were received from those whose updates were dropped or delayed.Source: §2 · pp. 4–5
  • A private mask protects a delayed user’s model even when the server can reconstruct that user’s pairwise seeds.The background says the private mask remains necessary because the server may consider delayed users dropped.Source: §2 · p. 5

3 Problem Formulation

Section 3 formalizes secure aggregation when users use different quantizers and explains why conventional additive-masking SecAg does not directly support that setting.

3.1 System Model

  • Users are grouped by communication resources and assigned quantizers up to their group’s level; the threat model includes a curious server, colluding users, and B malicious users.The system assumes the server follows the protocol but may try to infer information from received models.Source: §3.1 · pp. 5–6

3.2 Challenges

  • With 2-level and 4-level quantizers, using moduli 2 and 4 decoded the example’s sum as 2 instead of the true 4.The mismatch between users’ integer spaces causes incorrect decoding.Source: §3.2 · p. 6
  • Optimizing user clustering by transmission rate and assigning quantizers optimally are outside the paper’s scope.The focus is an approach to secure aggregation when users can use different quantizers.Source: §3.2 · p. 6
  • Even with uniformly distributed per-user masks and information-theoretic privacy, overflow at any user can prevent mask cancellation and distort the aggregate.The passage gives an example in which the decoded sum is 5 rather than 1.Source: §3.2 · p. 7
  • Independent SecAg across resource groups reveals each group’s average model, which can strengthen membership-inference and gradient-inversion attacks, especially for small groups.The server can use a small group’s average to infer information about users or reconstruct training images.Source: §3.2 · p. 7
  • HeteroSAg coordinates segments from different users for joint aggregation, allowing heterogeneous quantizers while limiting subset-average decoding to at most 2/G segments.Its feasibility conditions also require zero mutual information between each user’s clear and masked model, and decoding the average over all users.Source: §3.2 · p. 8, §3.3 · p. 8

3.3 Performance metric

  • Inference robustness δ is the minimum hidden fraction across proper user subsets, where hidden segments interfere with segments from users outside the subset.The metric is defined as δ(A) = min {1 − αS : S ⊊ {1, . . . , N}}.Source: §3.3 · p. 8
  • HeteroSAg’s worst-case inference robustness approaches one as the number of segments G grows.The passage states this result for a sufficiently large number of segments.Source: §3.3 · p. 8

4 The proposed HeteroSAg

HeteroSAg partitions users into resource-based groups and model updates into segments, then coordinates secure aggregation on selected segment groups using different quantizers. It also integrates coordinate-wise median for Byzantine resilience and provides theoretical guarantees for convergence, inference robustness, quantization error, privacy leakage, and costs.

4.1 HeteroSAg for heterogeneous quantization

  • HeteroSAg partitions users by communication resources and updates into segments, applying secure aggregation to coordinated segment groups quantized at different levels.The segment-selection matrix B specifies which groups jointly quantize, encode, and decode each set of segments.Source: §4.1 · p. 9
  • In the five-group example, HeteroSAg achieves inference robustness δ(AHeteroSAg) = 4/5 = 0.8, decoding only one clear segment from each group.Segments encoded together must be decoded together; for group 0, the first segment combines segments from groups 0 and 1.Source: §4.1 · p. 11

4.2 HeteroSAg for Byzantine-Resilience

  • HeteroSAg integrates coordinate-wise median by exposing multiple unmasked segments at each level, each formed by averaging segments encoded together.The paper contrasts this with protocols that expose only masked individual updates and the aggregate, complicating outlier removal.Source: §4.2 · pp. 11–12
  • Under the stated worst-case uniform distribution of Byzantine users across groups, the median requires B ≤ ⌈0.25G⌉−1 to keep benign decoded segments in the majority.A Byzantine user can make all segments of its group faulty, and some decoded segments combine contributions from two groups.Source: §4.2 · p. 12

4.3 Theoretical guarantees of HeteroSAg

  • Under the stated assumptions and step size η = 1/L, HeteroSAg guarantees convergence at O(1/J), with a residual error reducible by decreasing the learning rate or using higher-level quantizers.The theorem considers equally partitioned gradient vectors quantized according to the segment-selection matrix.Source: §4.3 · p. 13
  • Further dividing each group into L subgroups increases the tolerated Byzantine count while leaving total quantization error unchanged.Inference robustness approaches 1 as the number of groups increases; the subgroup result extends this strategy when the quantizer set is small.Source: §4.3 · pp. 12–13
  • The probability of privacy leakage from a subgroup approaches zero with lower dropout probability or more users per subgroup; for 8 users and p = 0.1, it is 7.2 × 10^-7.The paper also states that adapting quantizers to transmission rates decreases users’ probabilities of being delayed and treated as dropouts.Source: §4.3 · p. 13
  • Per-user computation is O(N^2 + m nbar) versus O(N^2 + mN) for SecAg, while communication is O(N + m); HeteroSAg supports heterogeneous quantizers and Byzantine robustness.The comparison states that server communication and computation complexities match SecAg.Source: §4.3 · p. 14

5 Numerical Experiments

The experiments compare heterogeneous quantization with homogeneous and unquantized settings, then test HeteroSAg with coordinate-wise median against Byzantine attacks. Heterogeneous quantization retains accuracy close to the unquantized baseline with less communication time, while the Byzantine experiment reports robustness to three attacks.

5.1 Experiment 1 (Heterogeneous quantization)

  • The experiments evaluate heterogeneous quantization with 25 users, five groups, and five model-update segments, comparing it with homogeneous K = 2 and unquantized updates.The non-IID MNIST setup assigns users class-sorted data partitions and treats group 0 as the low-bandwidth straggler group.Source: §5.1 · pp. 14–15
  • Heterogeneous quantization achieves accuracy close to no quantization, uses 5.2× less communication time after 200 rounds, and improves test accuracy by more than 15% over homogeneous K = 2 at the same communication time.The experiment uses a non-IID setting; Figure 5 shows performance under different quantization schemes.Source: §5.1 · p. 15, Figure 5 · p. 15

5.2 Experiment 2 (Byzantine robustness)

  • With 18 Byzantine users among 300, HeteroSAg with coordinate-wise median performs almost like the no-Byzantine case under Gaussian, sign-flip, and label-flip attacks, while FedAvg performs very poorly.The comparison uses an IID setting and distributes the Byzantine users over 18 groups.Source: Figure 6 · p. 15, §5.2 · p. 16

6 Conclusion

The conclusion presents HeteroSAg as secure aggregation with heterogeneous quantization, adapting quantization to users’ communication resources. It also identifies improved accuracy–communication-time trade-offs, Byzantine mitigation, and reduced bandwidth expansion as benefits.

6 Conclusion

  • HeteroSAg supports secure aggregation with heterogeneous quantization, allowing users to adjust quantization to their communication resources.The conclusion says this can provide a better trade-off between training accuracy and communication time.Source: §6 · p. 16
  • The conclusion says HeteroSAg’s strategy can be used to mitigate Byzantine users.Source: §6 · p. 16
  • The conclusion reports that HeteroSAg can significantly reduce the bandwidth expansion of state-of-the-art secure aggregation.Source: §6 · p. 16

Appendices

The appendices illustrate standard secure aggregation and give structural properties of HeteroSAg’s SS matrix used in the inference-robustness proof. The proof cases bound which segments the server can decode from selected groups.

A Illustrative example for SecAg

  • A three-user secure-aggregation example shares pairwise seeds and private masks, quantizes updates, masks them before transmission, and reconstructs masks to recover the surviving users’ aggregate after dropout.The example uses a secret-sharing threshold of two; a delayed user’s model remains protected by its private mask.Source: A Illustrative example for SecAg · pp. 18–19

B.1 Main properties for the SS matrix of HeteroSAg

  • Each SS-matrix column contains one asterisk, so each group independently applies secure aggregation to one update segment.Distinct columns share at most one row containing the same number, limiting each pair of groups to one jointly aggregated segment.Source: §B.1 · p. 19
  • For odd group counts, each row has one asterisk; for even counts, asterisk pairs can occur in odd rows and align for pairs of groups.The stated properties also distinguish paired numbers and unpaired numbers across rows.Source: §B.1 · pp. 19–20, Figure 7 · p. 19

B.2 Proof of Theorem 1

  • From a single group the server decodes at most the asterisk-marked segment; from a pair it decodes at most one segment for odd group counts and two for even counts.Source: §B.2 · p. 20
  • From an even set of at least four groups, the server decodes only one segment; from a proper odd-sized set of at least three groups, it decodes none.These cases complete the proof of Theorem 1.Source: §B.2 · p. 20

C Proof of Lemma 1

The lemma proof establishes unbiasedness and bounds quantization error, then counts how many segments use each quantizer under HeteroSAg’s SS matrix.

C Proof of Lemma 1

  • Random quantization is unbiased, and the proof gives a variance bound for the quantized update before stating the total quantization error.Source: C Proof of Lemma 1 · p. 20
  • For a user in group g, the SS matrix assigns G − g segments to Q_Kg and one segment per lower-level quantizer across the remaining g segments.Source: C Proof of Lemma 1 · p. 21

D Proof of Theorem 2

Theorem 2’s proof uses the expected quantized gradient and bounds its variance to establish the convergence argument. Theorem 3’s privacy guarantee relies on segment encoding across subgroup users and a dropout setting that rules out exactly one survivor in a subgroup.

D Proof of Theorem 2

  • The convergence proof bounds quantized-gradient variance by σ²_HeteroSAg while its expectation equals the objective gradient under Lemma 1-(i) and Assumption 1.The proof then uses the step-size condition η ≤ 1/L and convexity of F(.) in its convergence argument.Source: D Proof of Theorem 2 · p. 21

E Proof of Theorem 3

  • For Theorem 3, each user’s model update is partitioned into Z segments, and privacy requires the server cannot decode any individual segment after recovering specified keys.Each segment is jointly encoded with other users’ segments in its subgroup or in its subgroup and an additional subgroup.Source: E Proof of Theorem 3 · p. 21
  • Theorem 3’s dropout argument assumes users drop independently with probability p and excludes cases with exactly one survivor in a subgroup.The number of survivors in each subgroup is modeled as binomial with subgroup size n̄ and success probability 1−p.Source: E Proof of Theorem 3 · p. 22

F Proof of Proposition 3

HeteroSAg reduces per-user computation and transmitted bits relative to SecAg by grouping users and executing secure aggregation on model segments. The section also extends the method to groups of unequal sizes.

F Proof of Proposition 3

  • With n̄ = log N, HeteroSAg’s per-user computation is O(N² + m log N), compared with O(N² + mN) for SecAg.The model elements are masked by n̄−1 or 2n̄−1 masks rather than N−1 pairwise masks.Source: F Proof of Proposition 3 · p. 22
  • HeteroSAg has O(N + m) user communication complexity like secure aggregation, but fewer transmitted bits per user than SecAg.The comparison of bandwidth expansion excludes key-sharing, masking, and other cryptographic costs, which the authors state are the same as SecAg.Source: F Proof of Proposition 3 · p. 22, G HeteroSAg for Heterogeneous group Size · p. 22
  • For N = 2¹⁰, n̄ = 8, and K = 2¹⁶, the bandwidth expansion factor is 1.25× for HeteroSAg versus 1.625× for SecAg.For single-bit quantization, the reported expansion factors are 4× for HeteroSAg and 11× for SecAg.Source: F Proof of Proposition 3 · p. 22

G HeteroSAg for Heterogeneous group Size

  • The heterogeneous-group-size extension allows the user groups to contain different numbers of users rather than requiring equal-sized groups.The paper states that the preceding main-submission analysis considered uniform group sizes.Source: G HeteroSAg for Heterogeneous group Size · p. 22

G.1 Execution of HeteroSAg for heterogeneous group size

For unequal group sizes, HeteroSAg partitions groups into equal-sized subgroups and partitions each model update into segments, coordinating quantization and decoding through a segment-selection matrix. The section gives inference-robustness and quantization-error guarantees for this construction.

G.1 Execution of HeteroSAg for heterogeneous group size

  • The construction splits each group into Lg equal-sized subgroups and each user update into Z equal segments, where Z is the total subgroup count.When Z exceeds the model size m, the number of subgroups may be restricted to Z = m.Source: §G.1 · p. 23
  • The segment-selection matrix indexes model segments by rows and user subgroups by columns, specifying which sets of segments are quantized, encoded, and decoded together.A star denotes a subgroup quantizing and encoding its segments together; matching entries coordinate joint encoding and decoding across subgroups.Source: §G.1 · pp. 23–24
  • Inference robustness is (Z−2)/Z for an even number of subgroups and (Z−1)/Z for an odd number.Here Z is the total number of subgroups formed across the groups.Source: §G.1 · p. 24
  • Lemma 2 bounds quantization error for vectors with elements in [r1, r2], equally divided into Z segments and quantized using Q with the segment-selection matrix.The convergence rate remains that of Theorem 2 with σ_HeteroSAg replaced by σ_HeteroSAg+.Source: §G.1 · p. 24

H Proof of Proposition 1

When each group is partitioned equally into L subgroups of size n̄, extra partitioning does not change the quantization-error bound.

H Proof of Proposition 1

  • With equal group partitioning into L subgroups of size n̄, extra partitioning leaves the quantization-error bound unchanged.The stated result uses Zg−1 = gL and Z = GL.Source: H Proof of Proposition 1 · p. 24

I Byzantine robustness of HeteroSAg

The appendix examines HeteroSAg’s Byzantine-robustness rationale, communication-cost calculations, and non-IID dataset experiments. Its CIFAR10 results report accuracy comparable to no quantization with substantially less communication time than that baseline.

I Byzantine robustness of HeteroSAg

  • Median robustness relies on benign updates becoming more similar as data become IID; HeteroSAg takes medians over coordinates averaging subsets’ model elements, which may become outliers if any contributor is faulty.Source: I Byzantine robustness of HeteroSAg · pp. 24–25

J.1 Evaluating the results in Figure 5(b)

  • Per-user communication cost sums masked-model uploads and global-model downloads; communication time divides that cost by each user’s transmission rate, excluding equal key and mask costs.The calculations compare heterogeneous levels (2, 6, 8, 10, 12), homogeneous K=2, and no quantization after 200 rounds.Source: §J.1 · p. 25, Table 4 · p. 25

J.2.1 MNIST dataset

J.2.2 CIFAR10 dataset

  • 5.4× less total communication time than no-quantization after 250 rounds, while HeteroSAg achieved comparable accuracy and exceeded homogeneous K=2 across three CIFAR10 distributions.The higher accuracy over homogeneous K=2 came at no extra communication time.Source: §J.2.2 · p. 26

J.3 Additional experiment (Byzantine robustness)

In a non-IID CIFAR10 experiment with 18 Byzantine users among 300, HeteroSAg with coordinate-wise median performed almost like the no-Byzantine case under Gaussian and sign-flip attacks.

J.3 Additional experiment (Byzantine robustness)

  • The non-IID CIFAR10 experiment used 300 users, including 18 Byzantines, and generated data distributions with Dirichlet parameters.Source: §J.3 · p. 27, Figure 12 · p. 28
  • HeteroSAg with coordinate-wise median performed almost like the no-Byzantine case under Gaussian and sign-flip attacks, while FedAvg performed very poorly.Source: §J.3 · p. 27, Figure 13 · p. 29

J.4 Models

  • MNIST uses two fully connected layers, while CIFAR10 uses two convolutional and three fully connected layers; biases are zero-initialized, with Glorot convolutional and default PyTorch fully connected weight initialization.Source: §J.4 · pp. 27–28, Table 5 · p. 27, Table 6 · p. 28

Related papers

Loading 2009.14388v3…