Decentralized Submodular Maximization: Bridging Discrete and Continuous Settings

Abstract

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.

References in corpus (12)

• Communication Efficient Distributed Optimization using an Approximate Newton-type Method
• DSA: Decentralized Double Stochastic Averaging Gradient Algorithm
• Decentralized Quasi-Newton Methods
• The Landscape of Empirical Risk for Non-convex Losses
• Guaranteed Non-convex Optimization: Submodular Maximization over Continuous Domains
• Greed is Good: Near-Optimal Submodular Maximization via Greedy Optimization
• NESTT: A Nonconvex Primal-Dual Splitting Method for Distributed and Stochastic Optimization
• Submodular Functions: from Discrete to Continous Domains
• Gradient Methods for Submodular Maximization
• Online Submodular Maximization under a Matroid Constraint with Application to Learning Assignments
• Distributed Nonconvex Multiagent Optimization Over Time-Varying Networks
• Conditional Gradient Method for Stochastic Submodular Maximization: Closing the Gap

Cited by in corpus (4)

• Optimal DR-Submodular Maximization and Applications to Provable Mean Field Inference
• Optimal Algorithms for Submodular Maximization with Distributed Constraints
• Submodular Norms with Applications To Online Facility Location and Stochastic Probing
• Distributed control and game design: From strategic agents to programmable machines