# Guaranteed Non-convex Optimization: Submodular Maximization over Continuous Domains

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

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Jun 2016.

## Built on by (most cited first, 30 of 31)

- [Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization](https://mlsanity.com/paper/2102.11050/) (2021)
- [Submodular Reinforcement Learning](https://mlsanity.com/paper/2307.13372/) (2023)
- [Stochastic Continuous Submodular Maximization: Boosting via Non-oblivious Function](https://mlsanity.com/paper/2201.00703/) (2022)
- [Where MLLMs Attend and What They Rely On: Explaining Autoregressive Token Generation](https://mlsanity.com/paper/2509.22496/) (2025)
- [Submodular + Concave](https://mlsanity.com/paper/2106.04769/) (2021)
- [Bandit Multi-linear DR-Submodular Maximization and Its Applications on Adversarial Submodular Bandits](https://mlsanity.com/paper/2305.12402/) (2023)
- [A Unified Approach for Maximizing Continuous DR-submodular Functions](https://mlsanity.com/paper/2305.16671/) (2023)
- [From Linear to Linearizable Optimization: A Novel Framework with Applications to Stationary and Non-stationary DR-submodular Optimization](https://mlsanity.com/paper/2405.00065/) (2024)
- [Fast First-Order Methods for Monotone Strongly DR-Submodular Maximization](https://mlsanity.com/paper/2111.07990/) (2021)
- [Improved Projection-free Online Continuous Submodular Maximization](https://mlsanity.com/paper/2305.18442/) (2023)
- [Nearly Minimax Optimal Submodular Maximization with Bandit Feedback](https://mlsanity.com/paper/2310.18465/) (2023)
- [Decentralized Projection-free Online Upper-Linearizable Optimization with Applications to DR-Submodular Optimization](https://mlsanity.com/paper/2501.18183/) (2025)
- [Communication-Efficient Decentralized Online Continuous DR-Submodular Maximization](https://mlsanity.com/paper/2208.08681/) (2022)
- [Online Submodular Maximization via Online Convex Optimization](https://mlsanity.com/paper/2309.04339/) (2023)
- [Unified Projection-Free Algorithms for Adversarial DR-Submodular Optimization](https://mlsanity.com/paper/2403.10063/) (2024)
- [G"odel Test: Can Large Language Models Solve Easy Conjectures?](https://mlsanity.com/paper/2509.18383/) (2025)
- [Online Learning for Non-monotone Submodular Maximization: From Full Information to Bandit Feedback](https://mlsanity.com/paper/2208.07632/) (2022)
- [Improved Regret Bounds for Online Submodular Maximization](https://mlsanity.com/paper/2106.07836/) (2021)
- [Submodular Maximization via Taylor Series Approximation](https://mlsanity.com/paper/2101.07423/) (2021)
- [Joint Continuous and Discrete Model Selection via Submodularity](https://mlsanity.com/paper/2102.09029/) (2021)
- [One Gradient Frank-Wolfe for Decentralized Online Convex and Submodular Optimization](https://mlsanity.com/paper/2210.16790/) (2022)
- [Bridging the Gap Between General and Down-Closed Convex Sets in Submodular Maximization](https://mlsanity.com/paper/2401.09251/) (2024)
- [Improved Approximate Regret for Decentralized Online Continuous Submodular Maximization via Reductions](https://mlsanity.com/paper/2602.09502/) (2026)
- [γ-weakly θ-up-concavity: A Unified Framework for Non-Convex Optimization Beyond DR-Submodular and OSS Functions](https://mlsanity.com/paper/2602.13506/) (2026)
- [Scalable Projection-Free Optimization](https://mlsanity.com/paper/2105.03527/) (2021)
- [Game of Trojans: A Submodular Byzantine Approach](https://mlsanity.com/paper/2207.05937/) (2022)
- [High Probability Bounds for Stochastic Continuous Submodular Maximization](https://mlsanity.com/paper/2303.11937/) (2023)
- [Discrete and Continuous Difference of Submodular Minimization](https://mlsanity.com/paper/2506.07952/) (2025)
- [Toward Trustworthy AI: Multi-Target Adversarial Attacks and Robust Defenses for Continuous Data Summarization](https://mlsanity.com/paper/2606.11804/) (2026)
- [Distributed Online Bandit Submodular Maximization with Bounded Sampling Violations](https://mlsanity.com/paper/2607.00680/) (2026)

## Abstract (arXiv)

Submodular continuous functions are a category of (generally) non-convex/non-concave functions with a wide spectrum of applications. We characterize these functions and demonstrate that they can be maximized efficiently with approximation guarantees. Specifically, i) We introduce the weak DR property that gives a unified characterization of submodularity for all set, integer-lattice and continuous functions; ii) for maximizing monotone DR-submodular continuous functions under general down-closed convex constraints, we propose a Frank-Wolfe variant with (1-1/e) approximation guarantee, and sub-linear convergence rate; iii) for maximizing general non-monotone submodular continuous functions subject to box constraints, we propose a DoubleGreedy algorithm with 1/3 approximation guarantee. Submodular continuous functions naturally find applications in various real-world settings, including influence and revenue maximization with continuous assignments, sensor energy management, multi-resolution data summarization, facility location, etc. Experimental results show that the proposed algorithms efficiently generate superior solutions compared to baseline algorithms.