# Adding vs. Averaging in Distributed Primal-Dual Optimization

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Feb 2015.

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

- [Heterogeneous Federated Learning: State-of-the-art and Research Challenges](https://mlsanity.com/paper/2307.10616/) (2023)
- [Gradient-Leakage Resilient Federated Learning](https://mlsanity.com/paper/2107.01154/) (2021)
- [SpreadGNN: Serverless Multi-task Federated Learning for Graph Neural Networks](https://mlsanity.com/paper/2106.02743/) (2021)
- [Can 5th Generation Local Training Methods Support Client Sampling? Yes!](https://mlsanity.com/paper/2212.14370/) (2022)
- [Distributed Learning Systems with First-order Methods](https://mlsanity.com/paper/2104.05245/) (2021)
- [Towards Demystifying Serverless Machine Learning Training](https://mlsanity.com/paper/2105.07806/) (2021)
- [FedP3: Federated Personalized and Privacy-friendly Network Pruning under Model Heterogeneity](https://mlsanity.com/paper/2404.09816/) (2024)
- [Federated Empirical Risk Minimization via Second-Order Method](https://mlsanity.com/paper/2305.17482/) (2023)
- [Towards a Better Theoretical Understanding of Independent Subnetwork Training](https://mlsanity.com/paper/2306.16484/) (2023)
- [Local and Global Uniform Convexity Conditions](https://mlsanity.com/paper/2102.05134/) (2021)
- [Delayed Projection Techniques for Linearly Constrained Problems: Convergence Rates, Acceleration, and Applications](https://mlsanity.com/paper/2101.01505/) (2021)
- [A Privacy-Preserving and Trustable Multi-agent Learning Framework](https://mlsanity.com/paper/2106.01242/) (2021)
- [Reducing Training Time in Cross-Silo Federated Learning using Multigraph Topology](https://mlsanity.com/paper/2207.09657/) (2022)
- [FedAPM: Federated Learning via ADMM with Partial Model Personalization](https://mlsanity.com/paper/2506.04672/) (2025)
- [On the Optimal Batch Size for Byzantine-Robust Distributed Learning](https://mlsanity.com/paper/2305.13856/) (2023)
- [Personalized Federated Learning via ADMM with Moreau Envelope](https://mlsanity.com/paper/2311.06756/) (2023)
- [On ADMM in Heterogeneous Federated Learning: Personalization, Robustness, and Fairness](https://mlsanity.com/paper/2407.16397/) (2024)
- [On the Relationship Between CoCoA and ADMM for Distributed Empirical Risk Minimization](https://mlsanity.com/paper/2502.00470/) (2025)
- [Sheaf-Based Federated Representation Learning](https://mlsanity.com/paper/2608.10016/) (2026)

## Abstract (arXiv)

Distributed optimization methods for large-scale machine learning suffer from a communication bottleneck. It is difficult to reduce this bottleneck while still efficiently and accurately aggregating partial work from different machines. In this paper, we present a novel generalization of the recent communication-efficient primal-dual framework (CoCoA) for distributed optimization. Our framework, CoCoA+, allows for additive combination of local updates to the global parameters at each iteration, whereas previous schemes with convergence guarantees only allow conservative averaging. We give stronger (primal-dual) convergence rate guarantees for both CoCoA as well as our new variants, and generalize the theory for both methods to cover non-smooth convex loss functions. We provide an extensive experimental comparison that shows the markedly improved performance of CoCoA+ on several real-world distributed datasets, especially when scaling up the number of machines.