# Decentralized Submodular Maximization: Bridging Discrete and Continuous Settings

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Feb 2018.

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

- [On the Convergence of Distributed Stochastic Bilevel Optimization Algorithms over a Network](https://mlsanity.com/paper/2206.15025/) (2022)
- [Submodular + Concave](https://mlsanity.com/paper/2106.04769/) (2021)
- [Improved Projection-free Online Continuous Submodular Maximization](https://mlsanity.com/paper/2305.18442/) (2023)
- [Decentralized Projection-free Online Upper-Linearizable Optimization with Applications to DR-Submodular Optimization](https://mlsanity.com/paper/2501.18183/) (2025)
- [Resource-Aware Distributed Submodular Maximization: A Paradigm for Multi-Robot Decision-Making](https://mlsanity.com/paper/2204.07520/) (2022)
- [Communication-Efficient Decentralized Online Continuous DR-Submodular Maximization](https://mlsanity.com/paper/2208.08681/) (2022)
- [One Gradient Frank-Wolfe for Decentralized Online Convex and Submodular Optimization](https://mlsanity.com/paper/2210.16790/) (2022)
- [Decomposable Submodular Maximization in Federated Setting](https://mlsanity.com/paper/2402.00138/) (2024)
- [GreedyML: A Parallel Algorithm for Maximizing Constrained Submodular Functions](https://mlsanity.com/paper/2403.10332/) (2024)
- [Federated Frank-Wolfe Algorithm](https://mlsanity.com/paper/2408.10090/) (2024)
- [Adaptive Threshold-Driven Continuous Greedy Method for Scalable Submodular Optimization](https://mlsanity.com/paper/2604.03419/) (2026)
- [Distributed Online Bandit Submodular Maximization with Bounded Sampling Violations](https://mlsanity.com/paper/2607.00680/) (2026)
- [Dec-BFTRL: Squre-Root Regret for Decentralized Online Upper-Linearizable Optimization under Separation Access with Application to Continuous Submodular Maximization](https://mlsanity.com/paper/2608.30271/) (2026)

## Abstract (arXiv)

In this paper, we showcase the interplay between discrete and continuous optimization in network-structured settings. We propose the first fully decentralized optimization method for a wide class of non-convex objective functions that possess a diminishing returns property. More specifically, given an arbitrary connected network and a global continuous submodular function, formed by a sum of local functions, we develop Decentralized Continuous Greedy (DCG), a message passing algorithm that converges to the tight (1-1/e) approximation factor of the optimum global solution using only local computation and communication. We also provide strong convergence bounds as a function of network size and spectral characteristics of the underlying topology. Interestingly, DCG readily provides a simple recipe for decentralized discrete submodular maximization through the means of continuous relaxations. Formally, we demonstrate that by lifting the local discrete functions to continuous domains and using DCG as an interface we can develop a consensus algorithm that also achieves the tight (1-1/e) approximation guarantee of the global discrete solution once a proper rounding scheme is applied.