Federated Composite Optimization

Abstract

Federated Learning (FL) is a distributed learning paradigm that scales on-device learning collaboratively and privately. Standard FL algorithms such as FedAvg are primarily geared towards smooth unconstrained settings. In this paper, we study the Federated Composite Optimization (FCO) problem, in which the loss function contains a non-smooth regularizer. Such problems arise naturally in FL applications that involve sparsity, low-rank, monotonicity, or more general constraints. We first show that straightforward extensions of primal algorithms such as FedAvg are not well-suited for FCO since they suffer from the "curse of primal averaging," resulting in poor convergence. As a solution, we propose a new primal-dual algorithm, Federated Dual Averaging (FedDualAvg), which by employing a novel server dual averaging procedure circumvents the curse of primal averaging. Our theoretical analysis and empirical experiments demonstrate that FedDualAvg outperforms the other baselines.

arXiv commentAccepted to ICML 2021. Code repository see https://github.com/hongliny/FCO-ICML21

References in corpus (24)

• Federated Learning for Mobile Keyboard Prediction
• Federated Optimization:Distributed Optimization Beyond the Datacenter
• Optimal Distributed Online Prediction using Mini-Batches
• Improving Federated Learning Personalization via Model Agnostic Meta Learning
• Adaptive Personalized Federated Learning
• LEAF: A Benchmark for Federated Settings
• Federated Meta-Learning with Fast Convergence and Efficient Communication
• Agnostic Federated Learning
• A Unified Theory of Decentralized SGD with Changing Topology and Local Updates
• 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
• DSA: Decentralized Double Stochastic Averaging Gradient Algorithm
• Adaptive Federated Optimization
• Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization
• FedSplit: An algorithmic framework for fast federated optimization
• Accelerating Stochastic Gradient Descent For Least Squares Regression
• Lower Bounds and Optimal Algorithms for Personalized Federated Learning
• The Approximate Duality Gap Technique: A Unified Theory of First-Order Methods
• Federated Learning for Ranking Browser History Suggestions
• On the Computation and Communication Complexity of Parallel SGD with Dynamic Batch Sizes for Stochastic Non-Convex Optimization
• Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regression
• Accelerated Distributed Dual Averaging over Evolving Networks of Growing Connectivity
• A Richer Theory of Convex Constrained Optimization with Reduced Projections and Improved Rates
• Federated Nonconvex Sparse Learning

Cited by in corpus (4)

• Riemannian Low-Rank Model Compression for Federated Learning with Over-the-Air Aggregation
• Proximal and Federated Random Reshuffling
• Rate-Distortion Theoretic Bounds on Generalization Error for Distributed Learning
• A Communication-efficient Local Differentially Private Algorithm in Federated Optimization