SCAFFOLD: Stochastic Controlled Averaging for Federated Learning

Abstract

Federated Averaging (FedAvg) has emerged as the algorithm of choice for federated learning due to its simplicity and low communication cost. However, in spite of recent research efforts, its performance is not fully understood. We obtain tight convergence rates for FedAvg and prove that it suffers from `client-drift' when the data is heterogeneous (non-iid), resulting in unstable and slow convergence. As a solution, we propose a new algorithm (SCAFFOLD) which uses control variates (variance reduction) to correct for the `client-drift' in its local updates. We prove that SCAFFOLD requires significantly fewer communication rounds and is not affected by data heterogeneity or client sampling. Further, we show that (for quadratics) SCAFFOLD can take advantage of similarity in the client's data yielding even faster convergence. The latter is the first result to quantify the usefulness of local-steps in distributed optimization.

v2 contains analysis of FedAvg, non-convex rates of Scaffold, and experimental evaluation. v3 fixes typos, ICML version. v4 slightly improves rate of SCAFFOLD for general convex functions

References in corpus (39)

• Communication-Efficient Learning of Deep Networks from Decentralized Data
• Federated Learning: Strategies for Improving Communication Efficiency
• Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour
• Federated Learning with Non-IID Data
• Federated Optimization: Distributed Machine Learning for On-Device Intelligence
• Federated Learning for Mobile Keyboard Prediction
• On the Convergence of FedAvg on Non-IID Data
• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• Measuring the Effects of Non-Identical Data Distribution for Federated Visual Classification
• Applied Federated Learning: Improving Google Keyboard Query Suggestions
• Federated Optimization in Heterogeneous Networks
• Communication Efficient Distributed Optimization using an Approximate Newton-type Method
• Fair Resource Allocation in Federated Learning
• Agnostic Federated Learning
• SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
• Sparsified SGD with Memory
• Local SGD Converges Fast and Communicates Little
• On the Convergence of Local Descent Methods in Federated Learning
• Federated Learning for Emoji Prediction in a Mobile Keyboard
• Distributed Mean Estimation with Limited Communication
• Communication Complexity of Distributed Convex Learning and Optimization
• AIDE: Fast and Communication Efficient Distributed Optimization
• Federated Learning Of Out-Of-Vocabulary Words
• Distributed Learning with Compressed Gradient Differences
• Variance Reduced Local SGD with Lower Communication Complexity
• The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication
• Stochastic Recursive Gradient Algorithm for Nonconvex Optimization
• First Analysis of Local GD on Heterogeneous Data
• Unified Optimal Analysis of the (Stochastic) Gradient Method
• Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization
• Distributed Stochastic Variance Reduced Gradient Methods and A Lower Bound for Communication Complexity
• Convergence of Distributed Stochastic Variance Reduced Methods without Sampling Extra Data
• Estimate Sequences for Stochastic Composite Optimization: Variance Reduction, Acceleration, and Robustness to Noise
• Communication trade-offs for synchronized distributed SGD with large step size
• Federated Learning of N-gram Language Models
• On Convergence of Distributed Approximate Newton Methods: Globalization, Sharper Bounds and Beyond
• One Method to Rule Them All: Variance Reduction for Data, Parameters and Many New Methods
• FedDANE: A Federated Newton-Type Method
• How Good is SGD with Random Shuffling?

Cited by in corpus (93)

• FedKD: Communication Efficient Federated Learning via Knowledge Distillation
• Ensemble Distillation for Robust Model Fusion in Federated Learning
• Personalized Federated Learning: A Meta-Learning Approach
• FedML: A Research Library and Benchmark for Federated Machine Learning
• Three Approaches for Personalization with Applications to Federated Learning
• Personalized Federated Learning with Moreau Envelopes
• Label-Efficient Self-Supervised Federated Learning for Tackling Data Heterogeneity in Medical Imaging
• Federated Learning: A Signal Processing Perspective
• A Unified Theory of Decentralized SGD with Changing Topology and Local Updates
• Adaptive Federated Optimization
• Do Gradient Inversion Attacks Make Federated Learning Unsafe?
• Optimal Client Sampling for Federated Learning
• An Experimental Study of Byzantine-Robust Aggregation Schemes in Federated Learning
• Towards Efficient and Stable K-Asynchronous Federated Learning with Unbounded Stale Gradients on Non-IID Data
• Fast Federated Learning by Balancing Communication Trade-Offs
• Client Selection in Federated Learning: Convergence Analysis and Power-of-Choice Selection Strategies
• Distilled One-Shot Federated Learning
• Acceleration for Compressed Gradient Descent in Distributed and Federated Optimization
• Federated Graph Classification over Non-IID Graphs
• Communication-Efficient Stochastic Zeroth-Order Optimization for Federated Learning
• The Internet of Federated Things (IoFT): A Vision for the Future and In-depth Survey of Data-driven Approaches for Federated Learning
• FedCluster: Boosting the Convergence of Federated Learning via Cluster-Cycling
• Throughput-Optimal Topology Design for Cross-Silo Federated Learning
• Is Local SGD Better than Minibatch SGD?
• Model Pruning Enables Localized and Efficient Federated Learning for Yield Forecasting and Data Sharing
• FedCV: A Federated Learning Framework for Diverse Computer Vision Tasks
• Tighter Theory for Local SGD on Identical and Heterogeneous Data
• Federated Transfer-Ordered-Personalized Learning for Driver Monitoring Application
• Distributed Stochastic Consensus Optimization with Momentum for Nonconvex Nonsmooth Problems
• Federated Learning via Posterior Averaging: A New Perspective and Practical Algorithms
• Optimal Gradient Compression for Distributed and Federated Learning
• Personalized Federated Learning using Hypernetworks
• FedACK: Federated Adversarial Contrastive Knowledge Distillation for Cross-Lingual and Cross-Model Social Bot Detection
• Federated Fuzzy Neural Network with Evolutionary Rule Learning
• Recent theoretical advances in decentralized distributed convex optimization
• A Unified Analysis of Stochastic Gradient Methods for Nonconvex Federated Optimization
• Reducing Communication for Split Learning by Randomized Top-k Sparsification
• Semi-FedSER: Semi-supervised Learning for Speech Emotion Recognition On Federated Learning using Multiview Pseudo-Labeling
• An Optimal Transport Approach to Personalized Federated Learning
• FedCM: Federated Learning with Client-level Momentum
• Dynamic Fusion based Federated Learning for COVID-19 Detection
• Federated brain tumor segmentation: an extensive benchmark
• FedJAX: Federated learning simulation with JAX
• FedEval: A Holistic Evaluation Framework for Federated Learning
• Speeding up Heterogeneous Federated Learning with Sequentially Trained Superclients
• Federated Residual Learning
• A Better Alternative to Error Feedback for Communication-Efficient Distributed Learning
• Federated Survival Forests
• The Federated Tumor Segmentation (FeTS) Challenge
• Scaling Survival Analysis in Healthcare with Federated Survival Forests: A Comparative Study on Heart Failure and Breast Cancer Genomics
• CDKT-FL: Cross-Device Knowledge Transfer using Proxy Dataset in Federated Learning
• Achieving Linear Speedup with Partial Worker Participation in Non-IID Federated Learning
• Device Heterogeneity in Federated Learning: A Superquantile Approach
• OnDev-LCT: On-Device Lightweight Convolutional Transformers towards federated learning
• Federated Learning with Superquantile Aggregation for Heterogeneous Data
• Federated Stain Normalization for Computational Pathology
• FedSKETCH: Communication-Efficient and Private Federated Learning via Sketching
• Faster Non-Convex Federated Learning via Global and Local Momentum
• Local SGD: Unified Theory and New Efficient Methods
• Boosting multi-demographic federated learning for chest radiograph analysis using general-purpose self-supervised representations
• TurboSVM-FL: Boosting Federated Learning through SVM Aggregation for Lazy Clients
• FedDANE: A Federated Newton-Type Method
• Auxo: Efficient Federated Learning via Scalable Client Clustering
• Personalized Federated Learning with Multi-branch Architecture
• A Robust Federated Learning Approach for Combating Attacks Against IoT Systems Under non-IID Challenges
• Clustered Data Sharing for Non-IID Federated Learning over Wireless Networks
• A Federated Learning Benchmark on Tabular Data: Comparing Tree-Based Models and Neural Networks
• Personalised Federated Learning On Heterogeneous Feature Spaces
• Improved Convergence Analysis and SNR Control Strategies for Federated Learning in the Presence of Noise
• Bandwidth Allocation for Multiple Federated Learning Services in Wireless Edge Networks
• Federated Nonconvex Sparse Learning
• Towards Fast and Stable Federated Learning: Confronting Heterogeneity via Knowledge Anchor
• Server Averaging for Federated Learning
• Synthetic data shuffling accelerates the convergence of federated learning under data heterogeneity
• Rate-Distortion Theoretic Bounds on Generalization Error for Distributed Learning
• A Stochastic Operator Framework for Optimization and Learning with Sub-Weibull Errors
• A Stochastic Newton Algorithm for Distributed Convex Optimization
• Cross-Gradient Aggregation for Decentralized Learning from Non-IID data
• AdaptCL: Efficient Collaborative Learning with Dynamic and Adaptive Pruning
• Compare Where It Matters: Using Layer-Wise Regularization To Improve Federated Learning on Heterogeneous Data
• Communication-Efficient Zeroth-Order Distributed Online Optimization: Algorithm, Theory, and Applications
• FedSmart: An Auto Updating Federated Learning Optimization Mechanism
• A Communication-efficient Local Differentially Private Algorithm in Federated Optimization
• CDMA: A Practical Cross-Device Federated Learning Algorithm for General Minimax Problems
• The Minimax Complexity of Distributed Optimization
• Local Methods with Adaptivity via Scaling
• Vicinal Feature Statistics Augmentation for Federated 3D Medical Volume Segmentation
• CFedAvg: Achieving Efficient Communication and Fast Convergence in Non-IID Federated Learning
• Linear Speedup in Personalized Collaborative Learning
• TOFU: Towards Obfuscated Federated Updates by Encoding Weight Updates into Gradients from Proxy Data
• Compositional federated learning: Applications in distributionally robust averaging and meta learning
• On Second-order Optimization Methods for Federated Learning
• Local SGD for Near-Quadratic Problems: Improving Convergence under Unconstrained Noise Conditions