Turbo Aggregate: Breaking the Quadratic Aggregation Barrier in Secure Federated Learning
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 article, we propose the first secure aggregation framework, named Turbo Aggregate, that in a network with <inline formula> <tex math notation="LaTeX"$N$ /tex math>/inline formula> users achieves a secure aggregation overhead of <inline formula> <tex math notation="LaTeX"$O(N\log {N} /tex math>/inline formula> as opposed to <inline formula> <tex math notation="LaTeX"$O(N^{2} /tex math>/inline formula> 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 <inline formula> <tex math notation="LaTeX"$40\times /tex math>/inline formula> speedup over the state of the art protocols with up to <inline formula> <tex math notation="LaTeX"$N=200$ /tex math>/inline formula> users. Our experiments also demonstrate the impact of model size and bandwidth on the performance of Turbo Aggregate.
IEEE Journal on Selected Areas in Information Theory