mlsanityData to 14 Oct 2026

Fast Composite Optimization and Statistical Recovery in Federated Learning

arXiv 2207.08204 ↗First posted 17 Jul 2022cs.LG stat.MLcited by 12

Not on the map. Why?

Abstract (arXiv)

As a prevalent distributed learning paradigm, Federated Learning (FL) trains a global model on a massive amount of devices with infrequent communication. This paper investigates a class of composite optimization and statistical recovery problems in the FL setting, whose loss function consists of a data-dependent smooth loss and a non-smooth regularizer. Examples include sparse linear regression using Lasso, low-rank matrix recovery using nuclear norm regularization, etc. In the existing literature, federated composite optimization algorithms are designed only from an optimization perspective without any statistical guarantees. In addition, they do not consider commonly used (restricted) strong convexity in statistical recovery problems. We advance the frontiers of this problem from both optimization and statistical perspectives. From optimization upfront, we propose a new algorithm named textitFast Federated Dual Averaging for strongly convex and smooth loss and establish state-of-the-art iteration and communication complexity in the composite setting. In particular, we prove that it enjoys a fast rate, linear speedup, and reduced communication rounds. From statistical upfront, for restricted strongly convex and smooth loss, we design another algorithm, namely textitMulti-stage Federated Dual Averaging, and prove a high probability complexity bound with linear speedup up to optimal statistical precision. Experiments in both synthetic and real data demonstrate that our methods perform better than other baselines. To the best of our knowledge, this is the first work providing fast optimization algorithms and statistical recovery guarantees for composite problems in FL.

Key facts. Cited by 12 papers in the map (data through 14 Oct 2026). Builds on 27 of its 76 references that are in the map. First posted on arXiv 17 Jul 2022.

Builds on

27 of 76 references.

References · 27

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,669
  2. 2019Advances and Open Problems in Federated Learningcited by 3,046
  3. 2018Federated Optimization in Heterogeneous Networkscited by 2,987
  4. 2019On the Convergence of FedAvg on Non-IID Datacited by 1,229
  5. 2018LEAF: A Benchmark for Federated Settingscited by 792
  6. 2018Local SGD Converges Fast and Communicates Littlecited by 605
  7. 2018Parallel Restarted SGD with Faster Convergence and Less Communication: Demystifying Why Model Averaging Works for Deep Learningcited by 278
  8. 2019Tighter Theory for Local SGD on Identical and Heterogeneous Datacited by 266
  9. 2019Qsparse-local-SGD: Distributed SGD with Quantization, Sparsification, and Local Computationscited by 181
  10. 2019On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimizationcited by 180
  11. 2020Is Local SGD Better than Minibatch SGD?cited by 151
  12. 2020Minibatch vs Local SGD for Heterogeneous Distributed Learningcited by 147
15 more
  1. 2013Communication Efficient Distributed Optimization using an Approximate Newton-type Methodcited by 132
  2. 2021Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradientscited by 123
  3. 2019Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronizationcited by 107
  4. 2020Federated Accelerated Stochastic Gradient Descentcited by 85
  5. 2013Regularized M-estimators with nonconvexity: Statistical and algorithmic theory for local optimacited by 66
  6. 2020Federated Composite Optimizationcited by 49
  7. 2016Efficient Distributed Learning with Sparsitycited by 38
  8. 2021FedDR -- Randomized Douglas-Rachford Splitting Algorithms for Nonconvex Federated Composite Optimizationcited by 29
  9. 2021Communication-efficient SGD: From Local SGD to One-Shot Averagingcited by 19
  10. 2020The Cost of Privacy in Generalized Linear Models: Algorithms and Minimax Lower Boundscited by 15
  11. 2013Optimal computational and statistical rates of convergence for sparse nonconvex learning problemscited by 14
  12. 2019Distributed High-dimensional Regression Under a Quantile Loss Functioncited by 12
  13. 2014Primal-dual subgradient methods for minimizing uniformly convex functionscited by 11
  14. 2019Least Squares Approximation for a Distributed Systemcited by 8
  15. 2021Statistical Estimation and Inference via Local SGD in Federated Learningcited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 4; 2024: 2; 2025: 2; 2026: 4.

12 papers.

  1. 2023Composite federated learning with heterogeneous datacited by 7
  2. 2024Nonconvex Federated Learning on Compact Smooth Submanifolds With Heterogeneous Datacited by 5
  3. 2025FedCanon: Non-Convex Composite Federated Learning with Efficient Proximal Operation on Heterogeneous Datacited by 4
  4. 2023Federated Gradient Matching Pursuitcited by 1
  5. 2026Subspace Optimization for Efficient Federated Learning under Heterogeneous Datacited by 1
  6. 2023FedCliP: Federated Learning with Client Pruningcited by 0
  7. 2023Feature Norm Regularized Federated Learning: Transforming Skewed Distributions into Global Insightscited by 0
  8. 2024Federated Frank-Wolfe Algorithmcited by 0
  9. 2025Decentralized Nonconvex Composite Federated Learning with Gradient Tracking and Momentumcited by 0
  10. 2026Achieving Linear Speedup for Composite Federated Learningcited by 0
  11. 2026Compressed Proximal Federated Learning for Non-Convex Composite Optimization on Heterogeneous Datacited by 0
  12. 2026Entropy-Regularized Probabilistic Gates for Sparse Model Discovery in Scarce-Data Federated Learningcited by 0