# Achieving Linear Speedup for Composite Federated Learning

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 25 of its 32 references that are in the map.
- First posted on arXiv 3 Feb 2026.

## Builds on (most cited first, 25 of 25)

- [Very Deep Convolutional Networks for Large-Scale Image Recognition](https://mlsanity.com/paper/1409.1556/) (2014)
- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Federated Optimization in Heterogeneous Networks](https://mlsanity.com/paper/1812.06127/) (2018)
- [Federated Learning: Challenges, Methods, and Future Directions](https://mlsanity.com/paper/1908.07873/) (2019)
- [On the Convergence of FedAvg on Non-IID Data](https://mlsanity.com/paper/1907.02189/) (2019)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [Stochastic model-based minimization of weakly convex functions](https://mlsanity.com/paper/1803.06523/) (2018)
- [Better Theory for SGD in the Nonconvex World](https://mlsanity.com/paper/2002.03329/) (2020)
- [FedPD: A Federated Learning Framework with Optimal Rates and Adaptivity to Non-IID Data](https://mlsanity.com/paper/2005.11418/) (2020)
- [Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimization](https://mlsanity.com/paper/1308.6594/) (2013)
- [Distributed Mean Estimation with Limited Communication](https://mlsanity.com/paper/1611.00429/) (2016)
- [Federated Composite Optimization](https://mlsanity.com/paper/2011.08474/) (2020)
- [Stochastic Gradient Descent for Nonconvex Learning without Bounded Gradient Assumptions](https://mlsanity.com/paper/1902.00908/) (2019)
- [Fast Composite Optimization and Statistical Recovery in Federated Learning](https://mlsanity.com/paper/2207.08204/) (2022)
- [Composite federated learning with heterogeneous data](https://mlsanity.com/paper/2309.01795/) (2023)
- [A Normal Map-Based Proximal Stochastic Gradient Method: Convergence and Identification Properties](https://mlsanity.com/paper/2305.05828/) (2023)
- [Nonconvex Federated Learning on Compact Smooth Submanifolds With Heterogeneous Data](https://mlsanity.com/paper/2406.08465/) (2024)
- [A trust region-type normal map-based semismooth Newton method for nonsmooth nonconvex composite optimization](https://mlsanity.com/paper/2106.09340/) (2021)
- [Distributed Stochastic Optimization under a General Variance Condition](https://mlsanity.com/paper/2301.12677/) (2023)
- [A New Random Reshuffling Method for Nonsmooth Nonconvex Finite-sum Optimization](https://mlsanity.com/paper/2312.01047/) (2023)
- [A Proximal Operator for Inducing 2:4-Sparsity](https://mlsanity.com/paper/2501.18015/) (2025)
- [Non-convex composite federated learning with heterogeneous data](https://mlsanity.com/paper/2502.03958/) (2025)
- [FedCanon: Non-Convex Composite Federated Learning with Efficient Proximal Operation on Heterogeneous Data](https://mlsanity.com/paper/2504.11903/) (2025)
- [Composite Optimization with Error Feedback: the Dual Averaging Approach](https://mlsanity.com/paper/2510.03507/) (2025)
- [Distributed Normal Map-based Stochastic Proximal Gradient Methods over Networks](https://mlsanity.com/paper/2412.13054/) (2024)

## Abstract (arXiv)

This paper proposes FedNMap, a normal map-based method for composite federated learning, where the objective consists of a smooth loss and a possibly nonsmooth regularizer. FedNMap leverages a normal map-based update scheme to handle the nonsmooth term and incorporates a local correction strategy to mitigate the impact of data heterogeneity across clients. Under standard assumptions, including smooth local losses, weak convexity of the regularizer, and bounded stochastic gradient variance, FedNMap achieves linear speedup with respect to both the number of clients and the number of local updates for nonconvex losses, both with and without the Polyak-Lojasiewicz condition. To the best of our knowledge, this is the first algorithm establishing linear speedup for nonconvex composite federated learning. Numerical experiments corroborate our theoretical findings and demonstrate the linear speedup of FedNMap.