On the Convergence of FedAvg on Non-IID Data

Abstract

Federated learning enables a large amount of edge computing devices to jointly learn a model without data sharing. As a leading algorithm in this setting, Federated Averaging (\texttt{FedAvg}) runs Stochastic Gradient Descent (SGD) in parallel on a small subset of the total devices and averages the sequences only once in a while. Despite its simplicity, it lacks theoretical guarantees under realistic settings. In this paper, we analyze the convergence of \texttt{FedAvg} on non-iid data and establish a convergence rate of $\mathcal{O}(\frac{1}{T})$ for strongly convex and smooth problems, where $T$ is the number of SGDs. Importantly, our bound demonstrates a trade-off between communication-efficiency and convergence rate. As user devices may be disconnected from the server, we relax the assumption of full device participation to partial device participation and study different averaging schemes; low device participation rate can be achieved without severely slowing down the learning. Our results indicate that heterogeneity of data slows down the convergence, which matches empirical observations. Furthermore, we provide a necessary condition for \texttt{FedAvg} on non-iid data: the learning rate $\eta$ must decay, even if full-gradient is used; otherwise, the solution will be $\Omega (\eta )$ away from the optimal.

2020 International Conference on Learning Representations

References in corpus (22)

• Communication-Efficient Learning of Deep Networks from Decentralized Data
• Federated Learning: Strategies for Improving Communication Efficiency
• Federated Learning with Non-IID Data
• How To Backdoor Federated Learning
• Federated Optimization:Distributed Optimization Beyond the Datacenter
• Differentially Private Federated Learning: A Client Level Perspective
• Federated Optimization in Heterogeneous Networks
• Asynchronous Federated Optimization
• Communication Efficient Distributed Optimization using an Approximate Newton-type Method
• Divide and Conquer Kernel Ridge Regression: A Distributed Algorithm with Minimax Optimal Rates
• Sparsified SGD with Memory
• Don't Use Large Mini-Batches, Use Local SGD
• Local SGD Converges Fast and Communicates Little
• Distributed Coordinate Descent Method for Learning with Big Data
• Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms
• AIDE: Fast and Communication Efficient Distributed Optimization
• Federated Deep Reinforcement Learning
• CoCoA: A General Framework for Communication-Efficient Distributed Optimization
• First Analysis of Local GD on Heterogeneous Data
• Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization
• Stochastic, Distributed and Federated Optimization for Machine Learning
• A General Distributed Dual Coordinate Optimization Framework for Regularized Loss Minimization

Cited by in corpus (155)

• A Survey on Federated Learning Systems: Vision, Hype and Reality for Data Privacy and Protection
• SCAFFOLD: Stochastic Controlled Averaging for Federated Learning
• Measuring the Effects of Non-Identical Data Distribution for Federated Visual Classification
• Improving Federated Learning Personalization via Model Agnostic Meta Learning
• FedML: A Research Library and Benchmark for Federated Machine Learning
• FedBN: Federated Learning on Non-IID Features via Local Batch Normalization
• FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization
• Multi-Armed Bandit Based Client Scheduling for Federated Learning
• UVeQFed: Universal Vector Quantization for Federated Learning
• Over-the-Air Federated Learning from Heterogeneous Data
• Personalized Federated Learning with Moreau Envelopes
• Federated Neural Collaborative Filtering
• FedPD: A Federated Learning Framework with Optimal Rates and Adaptivity to Non-IID Data
• Learning to Detect Malicious Clients for Robust Federated Learning
• Pervasive AI for IoT applications: A Survey on Resource-efficient Distributed Artificial Intelligence
• Label-Efficient Self-Supervised Federated Learning for Tackling Data Heterogeneity in Medical Imaging
• Federated Learning: A Signal Processing Perspective
• On the Convergence of Local Descent Methods in Federated Learning
• A Field Guide to Federated Optimization
• Federated Learning in Mobile Edge Networks: A Comprehensive Survey
• Overcoming Forgetting in Federated Learning on Non-IID Data
• FedGroup: Efficient Clustered Federated Learning via Decomposed Data-Driven Measure
• A Decentralized Federated Learning Framework via Committee Mechanism with Convergence Guarantee
• Adaptive Federated Optimization
• Flexible Clustered Federated Learning for Client-Level Data Distribution Shift
• Blockchain-based Federated Learning with SMPC Model Verification Against Poisoning Attack for Healthcare Systems
• Attack of the Tails: Yes, You Really Can Backdoor Federated Learning
• STAR-RIS Integrated Non-Orthogonal Multiple Access and Over-the-Air Federated Learning: Framework, Analysis, and Optimization
• An Experimental Study of Byzantine-Robust Aggregation Schemes in Federated Learning
• The Non-IID Data Quagmire of Decentralized Machine Learning
• Towards Efficient and Stable K-Asynchronous Federated Learning with Unbounded Stale Gradients on Non-IID Data
• Distilled One-Shot Federated Learning
• Federated Mutual Learning
• Improving Fairness for Data Valuation in Horizontal Federated Learning
• FedSAE: A Novel Self-Adaptive Federated Learning Framework in Heterogeneous Systems
• Federated Learning for Healthcare Informatics
• First Analysis of Local GD on Heterogeneous Data
• Joint Privacy Enhancement and Quantization in Federated Learning
• FedLab: A Flexible Federated Learning Framework
• Communication-Efficient Stochastic Zeroth-Order Optimization for Federated Learning
• A Bayesian Federated Learning Framework with Online Laplace Approximation
• A Communication Efficient Collaborative Learning Framework for Distributed Features
• FedCluster: Boosting the Convergence of Federated Learning via Cluster-Cycling
• A first look into the carbon footprint of federated learning
• Federated Learning with Unbiased Gradient Aggregation and Controllable Meta Updating
• A Survey on Vulnerability of Federated Learning: A Learning Algorithm Perspective
• CSAFL: A Clustered Semi-Asynchronous Federated Learning Framework
• Distributed Traffic Synthesis and Classification in Edge Networks: A Federated Self-supervised Learning Approach
• FedDef: Defense Against Gradient Leakage in Federated Learning-based Network Intrusion Detection Systems
• Adaptive Model Pooling for Online Deep Anomaly Detection from a Complex Evolving Data Stream
• Semi-Synchronous Federated Learning for Energy-Efficient Training and Accelerated Convergence in Cross-Silo Settings
• FedCV: A Federated Learning Framework for Diverse Computer Vision Tasks
• SAFELearning: Enable Backdoor Detectability In Federated Learning With Secure Aggregation
• No Fear of Heterogeneity: Classifier Calibration for Federated Learning with Non-IID Data
• End-to-End Evaluation of Federated Learning and Split Learning for Internet of Things
• Federated PCA on Grassmann Manifold for IoT Anomaly Detection
• Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradients
• Federated Learning via Posterior Averaging: A New Perspective and Practical Algorithms
• Auto-FedAvg: Learnable Federated Averaging for Multi-Institutional Medical Image Segmentation
• Time-sensitive Learning for Heterogeneous Federated Edge Intelligence
• Faster On-Device Training Using New Federated Momentum Algorithm
• Local-Global Knowledge Distillation in Heterogeneous Federated Learning with Non-IID Data
• Graph Federated Learning for CIoT Devices in Smart Home Applications
• Turbo-Aggregate: Breaking the Quadratic Aggregation Barrier in Secure Federated Learning
• FedGAN: Federated Generative Adversarial Networks for Distributed Data
• FedBE: Making Bayesian Model Ensemble Applicable to Federated Learning
• A Survey on Federated Learning and its Applications for Accelerating Industrial Internet of Things
• Federated Active Learning (F-AL): an Efficient Annotation Strategy for Federated Learning
• MimiC: Combating Client Dropouts in Federated Learning by Mimicking Central Updates
• Client-Edge-Cloud Hierarchical Federated Learning
• Privacy Sensitive Speech Analysis Using Federated Learning to Assess Depression
• A Privacy Preserving System for Movie Recommendations Using Federated Learning
• Decentralized and Model-Free Federated Learning: Consensus-Based Distillation in Function Space
• An Optimal Transport Approach to Personalized Federated Learning
• FedCM: Federated Learning with Client-level Momentum
• FedRFQ: Prototype-Based Federated Learning with Reduced Redundancy, Minimal Failure, and Enhanced Quality
• Improving Performance of Federated Learning based Medical Image Analysis in Non-IID Settings using Image Augmentation
• Federated brain tumor segmentation: an extensive benchmark
• Federated Bandit: A Gossiping Approach
• Speeding up Heterogeneous Federated Learning with Sequentially Trained Superclients
• FedJAX: Federated learning simulation with JAX
• FedEval: A Holistic Evaluation Framework for Federated Learning
• Stragglers Are Not Disaster: A Hybrid Federated Learning Algorithm with Delayed Gradients
• Resisting Backdoor Attacks in Federated Learning via Bidirectional Elections and Individual Perspective
• FedSynthCT-Brain: A Federated Learning Framework for Multi-Institutional Brain MRI-to-CT Synthesis
• Cross-domain Federated Object Detection
• BROADCAST: Reducing Both Stochastic and Compression Noise to Robustify Communication-Efficient Federated Learning
• Accurate and Fast Federated Learning via IID and Communication-Aware Grouping
• Achieving Linear Speedup with Partial Worker Participation in Non-IID Federated Learning
• A Theoretical Perspective on Differentially Private Federated Multi-task Learning
• Effective Federated Adaptive Gradient Methods with Non-IID Decentralized Data
• Federated Uncertainty-Aware Learning for Distributed Hospital EHR Data
• Adaptive Histogram-Based Gradient Boosted Trees for Federated Learning
• Joint Device Scheduling and Resource Allocation for Latency Constrained Wireless Federated Learning
• FedCau: A Proactive Stop Policy for Communication and Computation Efficient Federated Learning
• Local Stochastic Gradient Descent Ascent: Convergence Analysis and Communication Efficiency
• Asynchronous Online Federated Learning with Reduced Communication Requirements
• FedSiam: Towards Adaptive Federated Semi-Supervised Learning
• Federated Learning for Commercial Image Sources
• Byzantine-Resilient Secure Federated Learning
• Joint Local Relational Augmentation and Global Nash Equilibrium for Federated Learning with Non-IID Data
• Faster Non-Convex Federated Learning via Global and Local Momentum
• Federated learning with class imbalance reduction
• Differentially Private Federated Learning with Laplacian Smoothing
• Memory-Based Optimization Methods for Model-Agnostic Meta-Learning and Personalized Federated Learning
• Auction Based Clustered Federated Learning in Mobile Edge Computing System
• Auxo: Efficient Federated Learning via Scalable Client Clustering
• FedPAGE: A Fast Local Stochastic Gradient Method for Communication-Efficient Federated Learning
• Federated Learning on Non-iid Data via Local and Global Distillation
• Real-time End-to-End Federated Learning: An Automotive Case Study
• Clustered Data Sharing for Non-IID Federated Learning over Wireless Networks
• Robust Training in High Dimensions via Block Coordinate Geometric Median Descent
• Voting-based Approaches For Differentially Private Federated Learning
• A Safe Genetic Algorithm Approach for Energy Efficient Federated Learning in Wireless Communication Networks
• Anarchic Federated Learning
• Improved Convergence Analysis and SNR Control Strategies for Federated Learning in the Presence of Noise
• A Primal-Dual Algorithm for Hybrid Federated Learning
• Bandwidth Allocation for Multiple Federated Learning Services in Wireless Edge Networks
• Communication-Efficient Federated Learning with Compensated Overlap-FedAvg
• FedHealth 2: Weighted Federated Transfer Learning via Batch Normalization for Personalized Healthcare
• 2SFGL: A Simple And Robust Protocol For Graph-Based Fraud Detection
• Accurate and Fast Federated Learning via Combinatorial Multi-Armed Bandits
• Multi-Level Analyzation of Imbalance to Resolve Non-IID-Ness in Federated Learning
• FedSEAL: Semi-Supervised Federated Learning with Self-Ensemble Learning and Negative Learning
• SPATL: Salient Parameter Aggregation and Transfer Learning for Heterogeneous Clients in Federated Learning
• An Element-Wise Weights Aggregation Method for Federated Learning
• Source Inference Attacks in Federated Learning
• PFA: Privacy-preserving Federated Adaptation for Effective Model Personalization
• Federated Learning with Fair Averaging
• Convergence Analysis and System Design for Federated Learning over Wireless Networks
• Multi-Level Local SGD for Heterogeneous Hierarchical Networks
• Slicing-Based AI Service Provisioning on Network Edge
• Curse or Redemption? How Data Heterogeneity Affects the Robustness of Federated Learning
• FedSmart: An Auto Updating Federated Learning Optimization Mechanism
• Exploiting Heterogeneity in Robust Federated Best-Arm Identification
• Global Multiclass Classification and Dataset Construction via Heterogeneous Local Experts
• Cross-Gradient Aggregation for Decentralized Learning from Non-IID data
• Delayed Projection Techniques for Linearly Constrained Problems: Convergence Rates, Acceleration, and Applications
• FedGPO: Heterogeneity-Aware Global Parameter Optimization for Efficient Federated Learning
• CDMA: A Practical Cross-Device Federated Learning Algorithm for General Minimax Problems
• Optimal Complexity in Decentralized Training
• Local SGD Optimizes Overparameterized Neural Networks in Polynomial Time
• Demystifying the Effects of Non-Independence in Federated Learning
• FDNAS: Improving Data Privacy and Model Diversity in AutoML
• Slashing Communication Traffic in Federated Learning by Transmitting Clustered Model Updates
• CFedAvg: Achieving Efficient Communication and Fast Convergence in Non-IID Federated Learning
• Federated Dynamic Neural Network for Deep MIMO Detection
• Gain without Pain: Offsetting DP-injected Nosies Stealthily in Cross-device Federated Learning
• Federated Learning using Smart Contracts on Blockchains, based on Reward Driven Approach
• Learn More by Using Less: Distributed Learning with Energy-Constrained Devices
• Matrix Sketching for Secure Collaborative Machine Learning
• Loosely Coupled Federated Learning Over Generative Models
• Can Federated Learning Save The Planet?
• Compositional federated learning: Applications in distributionally robust averaging and meta learning
• Towards Heterogeneous Clients with Elastic Federated Learning