# Decomposable Submodular Maximization in Federated Setting

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 56 references that are in the map.
- First posted on arXiv 31 Jan 2024.

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

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [On the Convergence of FedAvg on Non-IID Data](https://mlsanity.com/paper/1907.02189/) (2019)
- [Local SGD Converges Fast and Communicates Little](https://mlsanity.com/paper/1805.09767/) (2018)
- [Federated Optimization: Distributed Machine Learning for On-Device Intelligence](https://mlsanity.com/paper/1610.02527/) (2016)
- [Adaptive Federated Learning in Resource Constrained Edge Computing Systems](https://mlsanity.com/paper/1804.05271/) (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)
- [Practical Secure Aggregation for Federated Learning on User-Held Data](https://mlsanity.com/paper/1611.04482/) (2016)
- [cpSGD: Communication-efficient and differentially-private distributed SGD](https://mlsanity.com/paper/1805.10559/) (2018)
- [Is Local SGD Better than Minibatch SGD?](https://mlsanity.com/paper/2002.07839/) (2020)
- [The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregation](https://mlsanity.com/paper/2102.06387/) (2021)
- [Optimal Client Sampling for Federated Learning](https://mlsanity.com/paper/2010.13723/) (2020)
- [FedSplit: An algorithmic framework for fast federated optimization](https://mlsanity.com/paper/2005.05238/) (2020)
- [Local SGD: Unified Theory and New Efficient Methods](https://mlsanity.com/paper/2011.02828/) (2020)
- [The Skellam Mechanism for Differentially Private Federated Learning](https://mlsanity.com/paper/2110.04995/) (2021)
- [The Fundamental Price of Secure Aggregation in Differentially Private Federated Learning](https://mlsanity.com/paper/2203.03761/) (2022)
- [Gradient Methods for Submodular Maximization](https://mlsanity.com/paper/1708.03949/) (2017)
- [Conditional Gradient Method for Stochastic Submodular Maximization: Closing the Gap](https://mlsanity.com/paper/1711.01660/) (2017)
- [Distributed Submodular Maximization](https://mlsanity.com/paper/1411.0541/) (2014)
- [The Power of Randomization: Distributed Submodular Maximization on Massive Datasets](https://mlsanity.com/paper/1502.02606/) (2015)
- [Decentralized Submodular Maximization: Bridging Discrete and Continuous Settings](https://mlsanity.com/paper/1802.03825/) (2018)
- [Fast and Private Submodular and k-Submodular Functions Maximization with Matroid Constraints](https://mlsanity.com/paper/2006.15744/) (2020)
- [Differentially Private Decomposable Submodular Maximization](https://mlsanity.com/paper/2005.14717/) (2020)
- [Sparsification of Decomposable Submodular Functions](https://mlsanity.com/paper/2201.07289/) (2022)
- [Cut Sparsification and Succinct Representation of Submodular Hypergraphs](https://mlsanity.com/paper/2307.09110/) (2023)

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

- [RobustFSM: Submodular Maximization in Federated Setting with Malicious Clients](https://mlsanity.com/paper/2511.02029/) (2025)

## Abstract (arXiv)

Submodular functions, as well as the sub-class of decomposable submodular functions, and their optimization appear in a wide range of applications in machine learning, recommendation systems, and welfare maximization. However, optimization of decomposable submodular functions with millions of component functions is computationally prohibitive. Furthermore, the component functions may be private (they might represent user preference function, for example) and cannot be widely shared. To address these issues, we propose a em federated optimization setting for decomposable submodular optimization. In this setting, clients have their own preference functions, and a weighted sum of these preferences needs to be maximized. We implement the popular em continuous greedy algorithm in this setting where clients take parallel small local steps towards the local solution and then the local changes are aggregated at a central server. To address the large number of clients, the aggregation is performed only on a subsampled set. Further, the aggregation is performed only intermittently between stretches of parallel local steps, which reduces communication cost significantly. We show that our federated algorithm is guaranteed to provide a good approximate solution, even in the presence of above cost-cutting measures. Finally, we show how the federated setting can be incorporated in solving fundamental discrete submodular optimization problems such as Maximum Coverage and Facility Location.