# Compressed Proximal Federated Learning for Non-Convex Composite Optimization on Heterogeneous Data

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 35 of its 48 references that are in the map.
- First posted on arXiv 8 Mar 2026.

## Builds on (most cited first, 30 of 35)

- [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)
- [Federated Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016)
- [On the Convergence of FedAvg on Non-IID Data](https://mlsanity.com/paper/1907.02189/) (2019)
- [Federated Learning with Non-IID Data](https://mlsanity.com/paper/1806.00582/) (2018)
- [Federated Learning Based on Dynamic Regularization](https://mlsanity.com/paper/2111.04263/) (2021)
- [Federated Learning in Mobile Edge Networks: A Comprehensive Survey](https://mlsanity.com/paper/1909.11875/) (2019)
- [Sparsified SGD with Memory](https://mlsanity.com/paper/1809.07599/) (2018)
- [Sparse Communication for Distributed Gradient Descent](https://mlsanity.com/paper/1704.05021/) (2017)
- [Qsparse-local-SGD: Distributed SGD with Quantization, Sparsification, and Local Computations](https://mlsanity.com/paper/1906.02367/) (2019)
- [FedDC: Federated Learning with Non-IID Data via Local Drift Decoupling and Correction](https://mlsanity.com/paper/2203.11751/) (2022)
- [Federated Learning with Compression: Unified Analysis and Sharp Guarantees](https://mlsanity.com/paper/2007.01154/) (2020)
- [FedPD: A Federated Learning Framework with Optimal Rates and Adaptivity to Non-IID Data](https://mlsanity.com/paper/2005.11418/) (2020)
- [On Biased Compression for Distributed Learning](https://mlsanity.com/paper/2002.12410/) (2020)
- [EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback](https://mlsanity.com/paper/2106.05203/) (2021)
- [PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization](https://mlsanity.com/paper/2008.10898/) (2020)
- [Stochastic Controlled Averaging for Federated Learning with Communication Compression](https://mlsanity.com/paper/2308.08165/) (2023)
- [Federated Learning for Generalization, Robustness, Fairness: A Survey and Benchmark](https://mlsanity.com/paper/2311.06750/) (2023)
- [Federated Composite Optimization](https://mlsanity.com/paper/2011.08474/) (2020)
- [Unified Analysis of Stochastic Gradient Methods for Composite Convex and Smooth Optimization](https://mlsanity.com/paper/2006.11573/) (2020)
- [FedADMM: A Federated Primal-Dual Algorithm Allowing Partial Participation](https://mlsanity.com/paper/2203.15104/) (2022)
- [Momentum Provably Improves Error Feedback!](https://mlsanity.com/paper/2305.15155/) (2023)
- [FedDR -- Randomized Douglas-Rachford Splitting Algorithms for Nonconvex Federated Composite Optimization](https://mlsanity.com/paper/2103.03452/) (2021)
- [A Unified Analysis of Stochastic Gradient Methods for Nonconvex Federated Optimization](https://mlsanity.com/paper/2006.07013/) (2020)
- [Improving Fairness for Data Valuation in Horizontal Federated Learning](https://mlsanity.com/paper/2109.09046/) (2021)
- [3LC: Lightweight and Effective Traffic Compression for Distributed Machine Learning](https://mlsanity.com/paper/1802.07389/) (2018)
- [Innovation Compression for Communication-efficient Distributed Optimization with Linear Convergence](https://mlsanity.com/paper/2105.06697/) (2021)
- [Fast Composite Optimization and Statistical Recovery in Federated Learning](https://mlsanity.com/paper/2207.08204/) (2022)
- [Proximal Stochastic Recursive Momentum Methods for Nonconvex Composite Decentralized Optimization](https://mlsanity.com/paper/2211.11954/) (2022)

## Abstract (arXiv)

Federated Composite Optimization (FCO) has emerged as a promising framework for training models with structural constraints (e.g., sparsity) in distributed edge networks. However, simultaneously achieving communication efficiency and convergence robustness remains a significant challenge, particularly when dealing with non-smooth regularizers, statistical heterogeneity, and the restrictions of biased compression. To address these issues, we propose FedCEF (Federated Composite Error Feedback), a novel algorithm tailored for non-convex FCO. FedCEF introduces a decoupled proximal update scheme that separates the proximal operator from communication, enabling clients to handle non-smooth terms locally while transmitting compressed information. To mitigate the noise from aggressive quantization and the bias from non-IID data, FedCEF integrates a rigorous error feedback mechanism with control variates. Furthermore, we design a communication-efficient pre-proximal downlink strategy that allows clients to exactly reconstruct global control variables without explicit transmission. We theoretically establish that FedCEF achieves sublinear convergence to a bounded residual error under general non-convexity, which is controllable via the step size and batch size. Extensive experiments on real datasets validate FedCEF maintains competitive model accuracy even under extreme compression ratios (e.g., 1%), significantly reducing the total communication volume compared to uncompressed baselines.