# Fast Composite Optimization and Statistical Recovery in Federated Learning

arXiv: https://arxiv.org/abs/2207.08204 · HTML: https://mlsanity.com/paper/2207.08204/

## 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 (most cited first, 27 of 27)

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Federated Optimization in Heterogeneous Networks](https://mlsanity.com/paper/1812.06127/) (2018)
- [On the Convergence of FedAvg on Non-IID Data](https://mlsanity.com/paper/1907.02189/) (2019)
- [LEAF: A Benchmark for Federated Settings](https://mlsanity.com/paper/1812.01097/) (2018)
- [Local SGD Converges Fast and Communicates Little](https://mlsanity.com/paper/1805.09767/) (2018)
- [Parallel Restarted SGD with Faster Convergence and Less Communication: Demystifying Why Model Averaging Works for Deep Learning](https://mlsanity.com/paper/1807.06629/) (2018)
- [Tighter Theory for Local SGD on Identical and Heterogeneous Data](https://mlsanity.com/paper/1909.04746/) (2019)
- [Qsparse-local-SGD: Distributed SGD with Quantization, Sparsification, and Local Computations](https://mlsanity.com/paper/1906.02367/) (2019)
- [On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization](https://mlsanity.com/paper/1905.03817/) (2019)
- [Is Local SGD Better than Minibatch SGD?](https://mlsanity.com/paper/2002.07839/) (2020)
- [Minibatch vs Local SGD for Heterogeneous Distributed Learning](https://mlsanity.com/paper/2006.04735/) (2020)
- [Communication Efficient Distributed Optimization using an Approximate Newton-type Method](https://mlsanity.com/paper/1312.7853/) (2013)
- [Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradients](https://mlsanity.com/paper/2102.07053/) (2021)
- [Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization](https://mlsanity.com/paper/1910.13598/) (2019)
- [Federated Accelerated Stochastic Gradient Descent](https://mlsanity.com/paper/2006.08950/) (2020)
- [Regularized M-estimators with nonconvexity: Statistical and algorithmic theory for local optima](https://mlsanity.com/paper/1305.2436/) (2013)
- [Federated Composite Optimization](https://mlsanity.com/paper/2011.08474/) (2020)
- [Efficient Distributed Learning with Sparsity](https://mlsanity.com/paper/1605.07991/) (2016)
- [FedDR -- Randomized Douglas-Rachford Splitting Algorithms for Nonconvex Federated Composite Optimization](https://mlsanity.com/paper/2103.03452/) (2021)
- [Communication-efficient SGD: From Local SGD to One-Shot Averaging](https://mlsanity.com/paper/2106.04759/) (2021)
- [The Cost of Privacy in Generalized Linear Models: Algorithms and Minimax Lower Bounds](https://mlsanity.com/paper/2011.03900/) (2020)
- [Optimal computational and statistical rates of convergence for sparse nonconvex learning problems](https://mlsanity.com/paper/1306.4960/) (2013)
- [Distributed High-dimensional Regression Under a Quantile Loss Function](https://mlsanity.com/paper/1906.05741/) (2019)
- [Primal-dual subgradient methods for minimizing uniformly convex functions](https://mlsanity.com/paper/1401.1792/) (2014)
- [Least Squares Approximation for a Distributed System](https://mlsanity.com/paper/1908.04904/) (2019)
- [Statistical Estimation and Inference via Local SGD in Federated Learning](https://mlsanity.com/paper/2109.01326/) (2021)

## Built on by (most cited first, 12 of 12)

- [Composite federated learning with heterogeneous data](https://mlsanity.com/paper/2309.01795/) (2023)
- [Nonconvex Federated Learning on Compact Smooth Submanifolds With Heterogeneous Data](https://mlsanity.com/paper/2406.08465/) (2024)
- [FedCanon: Non-Convex Composite Federated Learning with Efficient Proximal Operation on Heterogeneous Data](https://mlsanity.com/paper/2504.11903/) (2025)
- [Federated Gradient Matching Pursuit](https://mlsanity.com/paper/2302.10755/) (2023)
- [Subspace Optimization for Efficient Federated Learning under Heterogeneous Data](https://mlsanity.com/paper/2604.25467/) (2026)
- [FedCliP: Federated Learning with Client Pruning](https://mlsanity.com/paper/2301.06768/) (2023)
- [Feature Norm Regularized Federated Learning: Transforming Skewed Distributions into Global Insights](https://mlsanity.com/paper/2312.06951/) (2023)
- [Federated Frank-Wolfe Algorithm](https://mlsanity.com/paper/2408.10090/) (2024)
- [Decentralized Nonconvex Composite Federated Learning with Gradient Tracking and Momentum](https://mlsanity.com/paper/2504.12742/) (2025)
- [Achieving Linear Speedup for Composite Federated Learning](https://mlsanity.com/paper/2602.03357/) (2026)
- [Compressed Proximal Federated Learning for Non-Convex Composite Optimization on Heterogeneous Data](https://mlsanity.com/paper/2603.07654/) (2026)
- [Entropy-Regularized Probabilistic Gates for Sparse Model Discovery in Scarce-Data Federated Learning](https://mlsanity.com/paper/2607.00275/) (2026)

## 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.