PaperlayerView exact revision on arXiv

Source-linked AI summary

Robust Aggregation for Federated Learning

Krishna Pillutla, Sham M. Kakade, Zaid Harchaoui

arXiv:1912.13445v2stat.MLcs.CRcs.LG

TL;DR

Federated learning needs aggregation that remains robust when device updates are corrupted without abandoning privacy preservation. The paper uses a geometric-median robust aggregation oracle built from secure averaging, establishes convergence, and evaluates RFA across models and tasks. RFA is more robust than FedAvg under high corruption while remaining competitive under low corruption, with one-step and personalization variants.

  • Problem

    Standard arithmetic-mean aggregation is vulnerable because even one corrupted update can arbitrarily change the aggregate in a round.

  • Method

    RFA replaces arithmetic-mean aggregation with an approximate geometric median computed iteratively through privacy-preserving secure aggregation.

  • Results

    RFA outperforms FedAvg under high corruption and nearly matches FedAvg under low corruption across computer-vision and natural-language-processing tasks.

  • Takeaways & Limitations

    Federated learning can be made robust to corrupted updates while preserving privacy and using 1-3 times the non-robust communication cost.

  • Takeaways & Limitations

    Exact convergence is impossible with corruption, and RFA can be marginally worse than FedAvg in corruption-free heterogeneous datasets.

Abstract

from arXiv · show

Federated learning is the centralized training of statistical models from decentralized data on mobile devices while preserving the privacy of each device. We present a robust aggregation approach to make federated learning robust to settings when a fraction of the devices may be sending corrupted updates to the server. The approach relies on a robust aggregation oracle based on the geometric median, which returns a robust aggregate using a constant number of iterations of a regular non-robust averaging oracle. The robust aggregation oracle is privacy-preserving, similar to the non-robust secure average oracle it builds upon. We establish its convergence for least squares estimation of additive models. We provide experimental results with linear models and deep networks for three tasks in computer vision and natural language processing. The robust aggregation approach is agnostic to the level of corruption; it outperforms the classical aggregation approach in terms of robustness when the level of corruption is high, while being competitive in the regime of low corruption. Two variants, a faster one with one-step robust aggregation and another one with on-device personalization, round off the paper.

1 Introduction

The paper addresses corrupted device updates in privacy-preserving federated learning by replacing arithmetic-mean aggregation with a robust geometric-median approach. It develops a practical, privacy-preserving algorithm and evaluates its robustness across models and tasks.

  • Motivation: A single corrupted update can degrade the global model because standard arithmetic-mean aggregation is not robust.The vulnerability may arise from adversarial attacks or hardware failures.
  • Algorithmic implementation: RFA preserves device-update privacy while using a scalable secure aggregation implementation and supporting practical communication costs.The underlying secure aggregation algorithms are implemented in production systems across millions of mobile users.
  • Robust aggregation: The proposed approach replaces weighted arithmetic-mean aggregation with an approximate geometric median at 1-3 times the communication cost.The robust aggregation oracle is built from secure multi-party computation primitives used by non-robust federated learning.
  • Contributions: The paper designs a geometric-median-based robust aggregation oracle and analyzes the convergence of the resulting RFA algorithm for least-squares estimation.The analysis covers corruption in up to half the devices under bounded heterogeneity and describes personalization for arbitrary heterogeneity.
  • Experiments: RFA outperforms FedAvg under high corruption and nearly matches it under low corruption across computer-vision and natural-language-processing tasks.The comparison applies to linear, convolutional, and recurrent neural networks, at 1-3 times the communication cost.

2 Related Work

Related work spans federated learning, distributed optimization, robust estimation, Byzantine robustness, and privacy-preserving computation. The paper distinguishes its focus on privacy-preserving distributed optimization from neighboring robustness settings.

  • Federated learning: Federated learning builds on distributed optimization and secure multi-party averaging for decentralized machine learning.The paper positions robustness to corrupted updates as broadly applicable to these federated settings.
  • Distributed optimization: Prior distributed-optimization work includes primal-dual, decentralized, asynchronous, and network-learning frameworks relevant to federated systems.Federated learning is characterized as a star network with private devices connected to a coordinating server.
  • Robust estimation: Robust-estimation research studies robust statistics, while this paper focuses on distributed optimization with privacy preservation.The cited robust-estimation works primarily consider the i.i.d. case.
  • Byzantine robustness: Byzantine-robust distributed optimization addresses arbitrary device behavior, whereas this paper considers faithful participation with corrupted updates.The paper notes that secure multi-party computation requires faithful participation and that securely implementing nonlinear alternatives is unclear.
  • Geometric median and privacy: The method is related to Weiszfeld-based geometric-median algorithms but is distinguished by numerical stability.The paper also treats differential privacy and homomorphic encryption as orthogonal directions that could be combined with its approach.

3 Problem Setup: Federated Learning with Corruptions

Federated learning coordinates local model training through synchronized communication rounds and server aggregation, but standard mean aggregation is vulnerable to corrupted updates. The paper frames robust aggregation as a trade-off among robustness, communication efficiency, privacy, and heterogeneity.

  • Federated learning trains a shared model from decentralized device data under central-server orchestration.
  • FedAvg samples clients, broadcasts the current model, performs local gradient steps, and aggregates client updates at the server.
  • Communication Efficiency: Communication rounds are the key efficiency measure because repeated model exchange over resource-limited wireless networks can bottleneck training.
  • Privacy: Secure average oracles aggregate weighted updates without revealing individual vectors or weights to the server or other devices.
  • Robustness: A single corrupted update can arbitrarily change mean aggregation, motivating a multidimensional median while preserving communication efficiency and privacy.The paper identifies robustness, communication efficiency, and privacy as competing desiderata, and approximates a nonlinear robust aggregate through adaptively weighted secure averages.
  • Corruption Model and Trade-offs: The proposed framework models heterogeneity through a distribution family D and guarantees convergence up to its width, while allowing corruption of up to half the devices under bounded heterogeneity.In the i.i.d. case, width(D) = 0; greater inlier variance makes robust mean estimation harder in ℓ2 error.

4 Robust Aggregation and the RFA Algorithm

This section replaces FedAvg’s mean aggregation with a geometric-median-based robust aggregation oracle implemented through iterative secure averages. RFA provides corruption robustness and convergence guarantees while trading additional communication for privacy-preserving aggregation.

  • Robust Aggregation with the Geometric Median: RFA replaces FedAvg’s mean aggregation with a geometric median computed by an iterative secure aggregation oracle.The oracle uses the smoothed Weiszfeld algorithm, which iteratively reweights device updates and calls secure averaging.
  • Geometric Median as an Iterative Secure Aggregate: The smoothed Weiszfeld algorithm uses distance-based weights with a tolerance ν to prevent division by zero and improve numerical stability.Its convergence guarantee bounds the surrogate objective gap after R iterations.
  • Geometric Median as an Iterative Secure Aggregate: 3 iterations empirically provide a high-quality approximate geometric median, requiring a 3× communication increase over regular mean aggregation.The algorithm’s rapid convergence motivates the practical communication budget used by RFA.
  • Convergence Analysis: The convergence analysis includes tail-averaged local updates and achieves near-linear convergence O(T/2^T) up to approximation and heterogeneity error terms when corruption is bounded away from 1/2.The approximation error is ϵ^2/m^2, while heterogeneity contributes the Ω^2 term; exact convergence is impossible under corruption.
  • Robustness and Privacy: RFA preserves privacy because the server observes only secure averages with effective weights bounded away from one, rather than individual device updates.The aggregation remains privacy-preserving while computing the geometric median iteratively.
  • Robustness and Privacy: The geometric median has breakdown point 1/2, so RFA’s convergence remains guaranteed with corruption in up to half the devices’ total weight.This contrasts with FedAvg’s breakdown point of 0, where one corruption can arbitrarily change the aggregate.
  • Extensions to RFA: One-step RFA reduces communication by using a single secure-average iteration, while personalized RFA offsets device heterogeneity with on-device parameters.The one-step variant retains most of RFA’s robustness empirically, and personalization adds device-specific parameters to shared server parameters.

5 Numerical Simulations

The simulations evaluate RFA across three machine-learning tasks, corruption models, aggregation baselines, convergence costs, and two extensions. RFA generally improves robustness under corruption while remaining competitive with FedAvg when corruption is low or absent.

  • Experimental setup: Experiments cover EMNIST character recognition, Shakespeare character-level language modeling, and Sent140 sentiment analysis using linear and neural-network models.The evaluation includes a linear model and ConvNet for EMNIST, an LSTM for Shakespeare, and a linear model for Sent140.
  • Data corruption: RFA achieves 52.8% accuracy versus FedAvg’s 41.2% for the EMNIST linear model under data corruption at ρ = 1/4.This comparison reports more than a 10-percentage-point advantage for RFA.
  • Data corruption: RFA is within one standard deviation of FedAvg on the Shakespeare LSTM and nearly equal on the EMNIST ConvNet under data corruption.The paper notes that neural-network training under corrupted data is not well understood in general.
  • Update corruption: Under omniscient corruption at ρ = 1/4, FedAvg approaches 0% accuracy while RFA exceeds 40% on EMNIST linear models and 60% on EMNIST ConvNets.The improvement is reported across all evaluated models, with a similar trend for the Shakespeare LSTM.
  • Overall robustness: RFA is no worse than FedAvg under corruption, often better, and almost as good without corruption while degrading more gracefully as corruption increases.RFA also shows smaller accuracy variability across random runs under corruption.
  • Communication and convergence: RFA requires 3× the secure-average calls to reach the same performance in low-corruption settings but matches FedAvg by outer iterations.The extra communication comes from multiple Weiszfeld iterations, while RFA’s convergence under corruption is more stable.
  • Extensions: One-step RFA reaches 51.4% versus FedAvg’s lower accuracy and nearly matches full RFA’s 52.8% on EMNIST linear data corruption at ρ = 0.25.On EMNIST ConvNet omniscient corruption, one-step RFA reaches 67.9%, compared with 63.0% for full RFA.
  • Extensions: Personalization raises EMNIST linear-model accuracy without corruption from 64.3% to 70.1% for FedAvg and from 62.9% to 69.9% for RFA.At ρ = 1/4, personalized RFA reaches 66.4% with a 3.4% reduction, versus 52.8% and a 10.1% reduction without personalization.

6 Conclusion

The paper concludes that robust aggregation based on geometric-median computation improves federated learning against corrupted updates while preserving privacy and scalability. RFA includes faster and personalization variants, but some theoretical extensions remain open.

  • Conclusion: RFA uses the geometric median and smoothed Weiszfeld algorithm to make federated learning more robust to corrupted device updates.The robust aggregation oracle operates through privacy-preserving secure multi-party computation primitives.
  • Conclusion: RFA preserves device-update privacy by invoking secure multi-party computation primitives with theoretical privacy guarantees.Its variants build on primitives already used at planetary scale.
  • Conclusion: The framework includes a fast single-step robust aggregation variant and an on-device personalization variant for heterogeneity.These variants are described as readily scalable while preserving privacy.
  • Conclusion: Theoretical analysis of personalized RFA and robustness under heterogeneity are identified as directions for future work.The conclusion specifically leaves both extensions for further analysis.

Supplementary Material: Robust Aggregation for Federated Learning

The supplementary material summarizes notation, provides a TensorFlow Federated implementation template, and develops the smoothed Weiszfeld algorithm used for robust aggregation. Its analysis establishes the algorithm’s geometric-median setup, descent behavior, and computational cost.

  • Notation: The notation defines device inputs x_i, targets y_i, feature maps φ(x), local objectives F_i, heterogeneity measures, and personalization parameters u_i.The theory uses least-squares loss, while the notation also records smoothness, strong convexity, noise variance, and federated-learning rounds.
  • Implementation: The supplementary material includes a template implementation of RFA in TensorFlow Federated alongside a standard FedAvg process.The listing shows initialization and iterative federated training structure for both approaches.
  • Geometric median: The geometric median is formulated as the minimizer of a weighted distance objective and is unique under the non-collinearity assumption.The smoothed objective has a unique minimizer denoted the ν-smoothed geometric median.
  • Smoothed Weiszfeld algorithm: The smoothed Weiszfeld algorithm iteratively updates a point from the convex hull using weighted averages of the input points.Each iteration costs O(md) floating-point operations, where m is the number of points and d their dimension.
  • Assumptions: The smoothing parameter satisfies ν < B, where B is the diameter of the convex hull of the input points.For ν ≥ B, the smoothed objective is quadratic throughout the convex hull.

C.3 Derivation

The derivation presents the smoothed Weiszfeld method through equivalent optimization viewpoints. It connects alternating minimization, majorization-minimization, and gradient descent formulations of the same updates.

  • Surrogate formulation: A jointly convex surrogate G is introduced so that minimizing over auxiliary variables recovers the geometric-median objectives g and g_ν.The surrogate uses auxiliary η variables constrained by η_i ≥ ν for the smoothed formulation.
  • Surrogate formulation: The surrogate’s auxiliary-variable minimization yields the smoothed norm used in g_ν.When distances fall below ν, the minimized term becomes a quadratic expression; otherwise it equals the distance.
  • Alternating minimization: Alternating minimization of G produces closed-form updates that give the smoothed Weiszfeld algorithm.The sequences generated by the original updates and the alternating-minimization updates are identical for fixed ν > 0.
  • Majorization-minimization: The smoothed Weiszfeld method is also an iterative majorization-minimization scheme using a first-order surrogate.Its z-step minimizes the current majorizing objective.
  • Gradient descent: The same update can be written as gradient descent on g_ν with an iteration-dependent smoothness quantity L(r).This representation follows from the stated gradient-descent reformulation and the definition of L(r).

C.4 Properties of Iterates

The iterate analysis shows that smoothed Weiszfeld updates remain in the convex hull, decrease the smoothed objective, and admit a global sublinear convergence analysis. The method also maintains bounded auxiliary variables and controlled iteration parameters.

  • Iterate properties: The iterates v(r) remain in the convex hull of the input points for every iteration.This follows from the weighted-average update structure.
  • Iterate properties: The auxiliary variables satisfy ν ≤ η_i(r) ≤ B, and the iteration parameter obeys 1/B ≤ L(r) ≤ 1/ν.Here B is the convex-hull diameter.
  • Convergence: The analysis establishes a global sublinear convergence rate for Algorithm 5.This result follows after the preceding iterate and descent properties are established.
  • Descent: Unless an iterate is already the minimizer, each smoothed Weiszfeld step strictly decreases g_ν.The proof uses alternating minimization and strong convexity of the surrogate subproblem.
  • Distance behavior: The distance from each iterate to the geometric-median minimizer is non-increasing.The property is established for the smoothed algorithm and related to the corresponding unsmoothed result.

C.5 Rate of Convergence

This section establishes convergence guarantees for the smoothed Weiszfeld algorithm and relates them to the original nonsmooth and unsmoothed algorithms. It also situates the results against prior work and describes the experimental setup used later.

  • Theorem 15 establishes a global sublinear convergence rate for Algorithm 5 from an initialization in the convex hull of the input points.
  • The convergence proof uses descent and contraction properties together with convexity and the Cauchy-Schwarz inequality.
  • Faster Rate of Convergence: Under Assumption 16 and ν ≤ eν, Corollary 19 gives a faster rate for the nonsmooth geometric-median objective.Assumption 16 requires that the geometric median does not coincide with any input point.
  • The original unsmoothed Weiszfeld algorithm inherits a corresponding bound under Assumption 16 and the condition that its iterates avoid all input points.The bound depends on the actual iterates and is therefore not informative about performance a priori; the algorithm may also be numerically unstable.
  • Comparison to Prior Work: Compared with prior work, the method avoids pairwise-distance initialization requirements and smoothing behavior that can introduce bias, while obtaining a better dependence on initialization in Theorem 15.
  • Experimental Setup: The experiments cover handwritten-letter recognition, character-level language modeling, and sentiment analysis using linear, convolutional, and recurrent models.

D.3 Evaluation Methodology and Other Details

The evaluation measures performance against communication and local-training axes, using test accuracy and train loss under both clean and corrupted-data settings. Simulations use repeated random runs and TensorFlow-based federated-learning implementations.

  • Evaluation Axes: Communication is measured by the number of calls to a secure average oracle and, separately, by the number of outer iterations.FedAvg and SGD use one oracle call per outer iteration, whereas RFA may require several.
  • Evaluation Axes: Test accuracy measures performance on unseen data, while the function value F is plotted as the train loss minimized by the optimization algorithm.
  • Evaluation Axes: With data corruption, training uses corrupted data but train and test progress are evaluated using corruption-free data.
  • Other Details: The experiments use LEAF to simulate federated learning and TensorFlow to implement the models.
  • Other Details: Each simulation is repeated 5 times with different random seeds; solid lines show means and shaded regions show run-wise minima and maxima.

D.4 Simulation Results: Convergence of The Smoothed Weiszfeld Algorithm

The simulations examine the convergence and weighting behavior of the smoothed Weiszfeld algorithm used by RFA. The results support rapid convergence and reduced influence for corrupted updates while using secure aggregation access.

  • The smoothed Weiszfeld algorithm converges exactly to the smoothed geometric median in a few passes and exhibits local linear convergence.
  • RFA uses a strict budget of 3 iterations for the smoothed Weiszfeld procedure, motivated by the observed convergence behavior.
  • The geometric median expresses the aggregate as a convex combination whose coefficient ratio β_i/α_i measures each device’s influence relative to arithmetic averaging.
  • The smoothed geometric median assigns lower weights to corrupted updates, especially for worse corruptions, while accessing points only through a secure average oracle.

D.5 Additional Simulation Results

Additional experiments study data distribution, communication budgets, client participation, and local computation. The results identify trade-offs that depend on corruption level while showing broadly similar FedAvg and RFA behavior for local computation.

  • Data Distribution: In the i.i.d. Sent140 setting, the 0.3% no-corruption performance gap between RFA and FedAvg completely vanishes.
  • Iteration Budget: A low smoothed-Weiszfeld communication budget is faster under low corruption, whereas more iterations work better under high corruption; the study uses 3 secure-average calls as a compromise.
  • Devices per Round: Selecting 50 devices per round achieves good performance under low corruption, while 10 devices per round is insufficient in that regime.Under high corruption, more devices help, and some 10- or 50-device runs at 25% omniscient corruption diverged.
  • Devices per Round: The number of devices per round should increase with corruption level, consistent with Theorem 4.
  • Local Computation: FedAvg and RFA remain within one standard deviation of each other across amounts of local computation.
  • Local Computation: RFA with one local epoch has slightly lower test accuracy than larger local-computation settings when there is no corruption.
Loading 1912.13445v2…