Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization

Abstract

In federated optimization, heterogeneity in the clients' local datasets and computation speeds results in large variations in the number of local updates performed by each client in each communication round. Naive weighted aggregation of such models causes objective inconsistency, that is, the global model converges to a stationary point of a mismatched objective function which can be arbitrarily different from the true objective. This paper provides a general framework to analyze the convergence of federated heterogeneous optimization algorithms. It subsumes previously proposed methods such as FedAvg and FedProx and provides the first principled understanding of the solution bias and the convergence slowdown due to objective inconsistency. Using insights from this analysis, we propose FedNova, a normalized averaging method that eliminates objective inconsistency while preserving fast error convergence.

References in corpus (20)

• Very Deep Convolutional Networks for Large-Scale Image Recognition
• Federated Learning: Strategies for Improving Communication Efficiency
• Federated Learning with Non-IID Data
• Measuring the Effects of Non-Identical Data Distribution for Federated Visual Classification
• Federated Optimization:Distributed Optimization Beyond the Datacenter
• Asynchronous Federated Optimization
• On the Convergence of Local Descent Methods in Federated Learning
• Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms
• On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization
• Adaptive Federated Optimization
• Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization
• Variance Reduced Local SGD with Lower Communication Complexity
• FedSplit: An algorithmic framework for fast federated optimization
• The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication
• First Analysis of Local GD on Heterogeneous Data
• Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization
• MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling
• Faster On-Device Training Using New Federated Momentum Algorithm
• Local AdaAlter: Communication-Efficient Stochastic Gradient Descent with Adaptive Learning Rates
• A Distributed Hierarchical SGD Algorithm with Sparse Global Reduction

Cited by in corpus (39)

• FedALA: Adaptive Local Aggregation for Personalized Federated Learning
• Label-Efficient Self-Supervised Federated Learning for Tackling Data Heterogeneity in Medical Imaging
• FedCP: Separating Feature Information for Personalized Federated Learning via Conditional Policy
• Client Selection in Federated Learning: Convergence Analysis and Power-of-Choice Selection Strategies
• A Bayesian Federated Learning Framework with Online Laplace Approximation
• FedCluster: Boosting the Convergence of Federated Learning via Cluster-Cycling
• The OARF Benchmark Suite: Characterization and Implications for Federated Learning Systems
• Async-HFL: Efficient and Robust Asynchronous Federated Learning in Hierarchical IoT Networks
• Model Pruning Enables Localized and Efficient Federated Learning for Yield Forecasting and Data Sharing
• Unsupervised Recurrent Federated Learning for Edge Popularity Prediction in Privacy-Preserving Mobile Edge Computing Networks
• One-shot Federated Learning without Server-side Training
• Optimizing Performance of Federated Person Re-identification: Benchmarking and Analysis
• Federated Fuzzy Neural Network with Evolutionary Rule Learning
• Reducing Communication for Split Learning by Randomized Top-k Sparsification
• Improving Performance of Federated Learning based Medical Image Analysis in Non-IID Settings using Image Augmentation
• Federated brain tumor segmentation: an extensive benchmark
• Being Bayesian in the 2020s: opportunities and challenges in the practice of modern applied Bayesian statistics
• Federated Learning with Superquantile Aggregation for Heterogeneous Data
• OnDev-LCT: On-Device Lightweight Convolutional Transformers towards federated learning
• Device Heterogeneity in Federated Learning: A Superquantile Approach
• FedDebug: Systematic Debugging for Federated Learning Applications
• Navigating Alignment for Non-identical Client Class Sets: A Label Name-Anchored Federated Learning Framework
• Federated Learning for Commercial Image Sources
• Federated Semi-Supervised Learning with Class Distribution Mismatch
• Federated Learning on Non-iid Data via Local and Global Distillation
• Clustered Data Sharing for Non-IID Federated Learning over Wireless Networks
• Learning to Transmit with Provable Guarantees in Wireless Federated Learning
• Multi-Level Analyzation of Imbalance to Resolve Non-IID-Ness in Federated Learning
• Towards Fast and Stable Federated Learning: Confronting Heterogeneity via Knowledge Anchor
• SPATL: Salient Parameter Aggregation and Transfer Learning for Heterogeneous Clients in Federated Learning
• Federated Modality-specific Encoders and Partially Personalized Fusion Decoder for Multimodal Brain Tumor Segmentation
• Blinder: End-to-end Privacy Protection in Sensing Systems via Personalized Federated Learning
• Synthetic data shuffling accelerates the convergence of federated learning under data heterogeneity
• Data Selection for Efficient Model Update in Federated Learning
• Cross-Gradient Aggregation for Decentralized Learning from Non-IID data
• Communication-Efficient Zeroth-Order Distributed Online Optimization: Algorithm, Theory, and Applications
• Dubhe: Towards Data Unbiasedness with Homomorphic Encryption in Federated Learning Client Selection
• A Communication-efficient Local Differentially Private Algorithm in Federated Optimization
• FedTVD: Balancing Data Quality and Quantity for Robust Federated Learning