Turbo-Aggregate: Breaking the Quadratic Aggregation Barrier in Secure Federated Learning

Jinhyun So; Basak Guler; A. Salman Avestimehr

Source-linked AI summary

Turbo-Aggregate: Breaking the Quadratic Aggregation Barrier in Secure Federated Learning

Jinhyun So, Basak Guler, A. Salman Avestimehr

arXiv:2002.04156v3Feb 11, 2020cs.LGcs.CRcs.DCcs.ITstat.ML

TL;DR

Secure federated learning is constrained by secure-aggregation overhead that grows quadratically with user count. Turbo-Aggregate replaces this bottleneck with grouped circular aggregation, secret sharing, and coding redundancy, achieving O(Nlog N) overhead and up to 50% dropout tolerance. Experiments report almost-linear runtime growth and up to 40× speedup at N=200.

Problem
Quadratic secure-aggregation overhead limits federated learning scalability, while dropped or delayed users can threaten robustness and privacy.
Method
Turbo-Aggregate combines multi-group circular aggregation with additive secret sharing and Lagrange-coding redundancy for private, dropout-resilient aggregation.
Results
O(Nlog N) aggregation overhead, 50% dropout tolerance, almost-linear runtime growth, and up to 40× speedup over the state-of-the-art at N=200.
Takeaways & Limitations
Turbo-Aggregate provides a secure aggregation framework suited to scaling federated learning across unreliable wireless users while preserving aggregate-only privacy.
Takeaways & Limitations
The work protects individual models against an honest-but-curious server and up to T colluding users, but differential privacy is left as future work for protecting individual data points.

Abstract

from arXiv · show

Federated learning is a distributed framework for training machine learning models over the data residing at mobile devices, while protecting the privacy of individual users. A major bottleneck in scaling federated learning to a large number of users is the overhead of secure model aggregation across many users. In particular, the overhead of the state-of-the-art protocols for secure model aggregation grows quadratically with the number of users. In this paper, we propose the first secure aggregation framework, named Turbo-Aggregate, that in a network with $N$ users achieves a secure aggregation overhead of $O(N\log{N})$, as opposed to $O(N^2)$, while tolerating up to a user dropout rate of $50\%$. Turbo-Aggregate employs a multi-group circular strategy for efficient model aggregation, and leverages additive secret sharing and novel coding techniques for injecting aggregation redundancy in order to handle user dropouts while guaranteeing user privacy. We experimentally demonstrate that Turbo-Aggregate achieves a total running time that grows almost linear in the number of users, and provides up to $40\times$ speedup over the state-of-the-art protocols with up to $N=200$ users. Our experiments also demonstrate the impact of model size and bandwidth on the performance of Turbo-Aggregate.

I. INTRODUCTION

Federated learning keeps training data on mobile devices but requires privacy-preserving aggregation of local models. Turbo-Aggregate addresses secure-aggregation scalability and dropout challenges with a multi-group circular design, secret sharing, and coding redundancy.

Federated learning trains models over decentralized mobile data while keeping training data on devices and aggregating local models privately.
O(N^2) secure-aggregation overhead from pairwise masks limits practical systems to hundreds of users despite mobile systems operating at tens-of-millions scale.
User dropouts caused by connectivity, calls, or low battery require protocols that remain robust throughout execution and preserve privacy when users are dropped or delayed.
Turbo-Aggregate reduces aggregation overhead to O(Nlog N), tolerates up to a 50% dropout rate, and provides information-theoretic privacy for individual updates.
The framework combines a multi-group circular aggregation strategy, additive secret sharing, and Lagrange coding to aggregate efficiently while handling dropouts.
Turbo-Aggregate supports centralized or decentralized communication and experimentally achieves almost-linear runtime growth with up to 40× speedup over the state-of-the-art at N=200.

B. Secure Aggregation Protocol for Federated Learning and Key Parameters

The paper targets secure aggregation that preserves privacy and dropout robustness without the quadratic overhead of prior protocols. Turbo-Aggregate uses grouped circular communication, additive masking, and coded redundancy to compute surviving-user aggregates efficiently.

Local models can expose information about users’ private datasets, motivating secure aggregation of the models rather than transmission of raw data.
Prior secure aggregation has quadratic overhead, while the paper seeks comparable robustness and privacy with almost-linear aggregation cost.
Turbo-Aggregate targets p=0.5 dropout tolerance, privacy against up to T=N/2 colluding users, and C=O(Nlog N) aggregation overhead.
Additive secret sharing masks individual models, while Lagrange-polynomial redundancy supports reconstruction amid user dropouts.
Users are partitioned into L groups, and sequential stages encode local and partial aggregate models, decode missing information, and aggregate messages across groups.
The protocol can use centralized server communication or decentralized peer-to-peer links, with the same aggregation steps in either setting.

B. Masking with additive secret sharing

Turbo-Aggregate combines additive masking, secret sharing, and Lagrange coding in a multi-group aggregation process. These mechanisms preserve privacy and reconstruct missing intermediate values when users drop out, provided enough evaluations remain.

Masking and sharing: Additive masks hide each local model, while secret shares cancel in aggregate to preserve the accuracy of the summed data.The protocol uses randomness and additive secret sharing to protect models against collusions while maintaining the original aggregate.
Multi-group aggregation: Users in successive groups recursively update and propagate masked aggregate variables to the next group.Each active group computes partial sums and forwards updated masked values through the circular process.
Coded recovery: Lagrange coding embeds secret-shared values in polynomials so missing evaluations can be reconstructed through interpolation.A polynomial of degree at most N_l−1 can be recovered from sufficient evaluation points, enabling recovery after dropouts.
Coded recovery: Each next-stage group can reconstruct missing terms after receiving at least N_l evaluations from 2N_l evaluations.This threshold lets each stage proceed when at least half of its users remain active.
Robustness: As long as fewer than 50% of users drop out, Turbo-Aggregate can continue model aggregation with high probability.The stage-wise reconstruction condition supports robustness below the 50% dropout rate.

D. Final aggregation and the overall Turbo-Aggregate protocol

The final protocol adds a dummy aggregation stage to securely combine the last group’s models. Reconstruction and mask removal yield the aggregate of all surviving users.

Final aggregation: A dummy final stage receives and aggregates encoded models from the last protocol group to protect those users’ local models.The final-stage users may be any surviving participants who participated earlier.
Final aggregation: Final-stage users reconstruct missing terms before sending the resulting masked aggregates to the server.This preserves the dropout-recovery mechanism through the last aggregation step.
Server output: The server reconstructs missing final terms, averages the final summations, and removes the random masks.The resulting value equals the aggregate of the individual models of all surviving users.
Protocol overview: Algorithm 1 presents the complete Turbo-Aggregate protocol after these stages.The algorithm specifies the overall sequence from masked and encoded models through final server aggregation.

V. THEORETICAL GUARANTEES OF TURBO-AGGREGATE

Turbo-Aggregate provides theoretical guarantees for low aggregation overhead, dropout robustness, and privacy. Its guarantees involve explicit trade-offs between robustness, privacy, and group-size choices.

Main guarantees: The protocol guarantees privacy against collusion involving the server and up to N/2 users under the stated theorem.The result is framed as protection of each individual model against such collusions.
Main guarantees: Turbo-Aggregate achieves aggregation overhead O(Nlog N) and tolerates up to a 50% user dropout rate.The theorem states these guarantees as simultaneous properties of the protocol.
Trade-offs: Increasing robustness beyond the baseline can reduce privacy guarantees, establishing a robustness–privacy trade-off.With additional evaluation points, higher dropout tolerance is possible, but individual models may be revealed under corresponding conditions.
Group-size boundary: Choosing group size O(log N) cannot guarantee robustness to any dropout rate p<0.5 with probability approaching one as N grows.The converse result applies when 0 < D(0.5||p) < 1 and N_l=log N for all groups.

A. Generalized Turbo-Aggregate

Generalized Turbo-Aggregate strengthens privacy for partial aggregates while retaining the protocol’s main overhead, robustness, and privacy guarantees. It uses user-generated masks and a second random partitioning to support this extension.

Modified masking: Users, rather than the server, generate the random masks in the modified protocol.The protocol otherwise follows the same main aggregation steps.
Second partitioning: A second random partitioning organizes users into groups that secret-share masks and aggregate them across successive groups.Shamir’s secret sharing is used for this additional mask-aggregation process.
Privacy of partial aggregates: The server reconstructs the mask sums and subtracts them to recover aggregates while preserving privacy of partial aggregates.The guarantee depends on collusion not revealing the relevant aggregation of random masks.
Generalized guarantees: The generalized protocol retains the main Turbo-Aggregate guarantees and additionally protects partial aggregates against server–user collusion.The added guarantee applies to up to T=(0.5−ε)N colluding users with probability approaching one as N grows.

VI. EXPERIMENTS

Turbo-Aggregate’s experiments evaluate scalability, dropout robustness, and deployment conditions against a state-of-the-art benchmark. Its running time grows almost linearly with users, remains stable under dropouts, and reaches up to 40× speedup at 200 users.

Experiment setup: Experiments implement the schemes for up to 200 users on Amazon EC2 under varied dropout rates and bandwidth conditions.The evaluation uses FedML, MPI4Py, and m3.medium instances.
Implementation: Turbo-Aggregate+ reduces execution stages from L−1 to log L by parallelizing stages through a tree-based information-flooding structure.The implementation requires only 3 stages in the illustrated configuration.
Scalability: Turbo-Aggregate and Turbo-Aggregate+ have total running times that grow almost linearly with users, unlike the benchmark’s quadratic growth.
Dropout robustness: Turbo-Aggregate and Turbo-Aggregate+ maintain stable total running time as user dropout rates increase.Their encoding and decoding costs change little, and remaining users need not transmit additional information when users drop or are delayed.
Performance comparison: 5.8× and 40× speedups are achieved by Turbo-Aggregate and Turbo-Aggregate+, respectively, over the benchmark with 200 users and up to 50% dropout.
Real-world evaluation: Turbo-Aggregate remains substantially faster than the benchmark in real-world federated learning setups that include both training and aggregation phases.

APPENDIX

The illustrative protocol propagates masked and encoded models through user groups, reconstructing missing values when a user drops. Lagrange coding supports recovery, while the server ultimately obtains the aggregate of surviving users’ models.

Illustrative example: In a nine-user, three-group example, user 3 in group 2 drops during execution and later groups recover the missing contribution.
Illustrative example: Users in group 1 apply additive masking and Lagrange coding before sending encoded models to group 2.
Illustrative example: Group 2 users aggregate messages from group 1 and forward encoded aggregates to the next group.
Dropout recovery: Group 3 users reconstruct a missing group-2 value from four received evaluations using Lagrange coding, then aggregate the recovered value.
Final aggregation: The final group sends aggregated values to the server, which removes added randomness to recover the aggregate of surviving users’ original models.
Security properties: The protocol’s privacy and robustness rely on secret sharing, which reconstructs seeds only from sufficient shares while withholding information from smaller subsets.

C. Proof of Theorem 1

Theorem 1 analyzes Turbo-Aggregate’s robustness, privacy, and overhead under random user partitioning. Its aggregation overhead is O(Nlog N), while robustness and privacy leakage are characterized through group-level tail bounds and asymptotic probabilities.

Robustness guarantee: 2(N_l−D_l) ≥ N_l in every group is sufficient to reconstruct missing information and compute the aggregate despite dropouts.Here D_l denotes the number of dropped users in group l.
Robustness guarantee: D_l follows a binomial distribution with parameters N_l and p, enabling tail-probability bounds for the robustness analysis.The proof considers dropout probability p<0.5 and applies bounds across groups.
Privacy guarantee: Colluding users in lower groups cannot learn earlier users’ information, while higher groups learn no more than partial summations under the directed communication structure.The privacy proof then bounds the probability that collusion reveals an individual model.
Privacy guarantee: lim_N→∞P[privacy leakage] = 0 under the theorem’s random-partitioning analysis.The bound is obtained by replacing the dropout-rate constant with a collusion-related constant.
Aggregation overhead: O(Nlog N) is the overall aggregation overhead, combining communication with parallel masking, coding, and reconstruction computations.The computation analysis includes additive secret sharing, Lagrange coding, and decoding of missing information.

D. Proof of Theorem 2

Theorem 2 analyzes the asymptotic robustness probability using binomial dropout counts and tail bounds. The proof concludes with the stated asymptotic behavior of the robustness expression.

Robustness guarantee: D_l follows a binomial distribution with parameters N_l and p, forming the basis of the dropout robustness bound.The analysis examines the probability that information from a group cannot be reconstructed.
Robustness guarantee: The probability that Turbo-Aggregate provides robustness against user dropouts is expressed through the group-level reconstruction events.The proof combines these events across groups using independence.
Asymptotic conclusion: lim_N→∞P[robustness] = 0 is the asymptotic conclusion stated at the end of the proof.This follows from the preceding upper-bound analysis in the supplied proof text.

E. Proof of Theorem 3

Generalized Turbo-Aggregate uses two independent random user partitionings to extend privacy, robustness, and aggregation-overhead guarantees. The analysis shows privacy for partial aggregates and retains O(Nlog N) overhead.

Protocol construction: Two independent random partitionings assign users into groups, supporting privacy analysis for individual models and aggregates of arbitrary subsets.Both partitionings use group sizes N_l=O(log N).
Privacy guarantee: Privacy leakage for any partial aggregation has probability approaching 0 as N→∞.The proof bounds two collusion events and shows both upper bounds vanish asymptotically.
Robustness guarantee: The generalized protocol has the same level of robustness guarantee as Theorem 1, with a union-bound failure probability that also goes to zero as N→∞.The two partitionings contribute twice the corresponding bound from Theorem 1.
Aggregation overhead: O(Nlog N) is the aggregation overhead of generalized Turbo-Aggregate, including additional secret sharing and decoding operations.The overhead analysis accounts for Shamir secret sharing, communication of shares, and server-side reconstruction.

F. Additional Experiments

Additional experiments examine how user dropouts affect Turbo-Aggregate’s total running time. At N=200, encoding remains constant with dropout rate while decoding grows linearly but remains a small component.

Dropout impact: At N=200, encoding time stays constant as the user dropout rate changes for Turbo-Aggregate and Turbo-Aggregate+.The comparison uses running-time breakdowns in Tables II and III.
Dropout impact: At N=200, decoding time increases linearly with the number of dropout users but occupies only a small portion of total running time.The breakdown is compared with the benchmark protocol in Table IV.

1) Breakdown of the total running time:

Turbo-Aggregate maintains relatively stable running time as dropouts and stragglers increase, while bandwidth constraints reduce its speedup; Turbo-Aggregate+ remains more resilient in low-bandwidth settings.

Dropouts and stragglers: Turbo-Aggregate and Turbo-Aggregate+ have relatively stable running time as user dropout rates increase, unlike the benchmark protocol.The benchmark slows because reconstructing pairwise masks for dropped users becomes increasingly dominant.
Bandwidth: Turbo-Aggregate continues to provide substantial gains under more severe bandwidth constraints.The bandwidth study varies communication links from 1 Gbps to 100 Mbps.
Bandwidth: 1.9× speedup is achieved by Turbo-Aggregate over the benchmark at 100 Mbps maximum bandwidth.Its total running time is communication-dominated, so the gain decreases as bandwidth falls.
Bandwidth: 12.1× speedup is achieved by Turbo-Aggregate+ over the benchmark at 100 Mbps maximum bandwidth.Turbo-Aggregate+ increases only moderately as bandwidth decreases because its communication time is lower than the benchmark’s.
Dropouts and stragglers: Turbo-Aggregate handles stragglers by treating delayed users as dropouts and decoding their messages without waiting for them.This has negligible impact on total running time under the reported design.