# Robust Budget Allocation via Continuous Submodular Functions

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Feb 2017.

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

- [Submodular + Concave](https://mlsanity.com/paper/2106.04769/) (2021)
- [Adversarial Learning for Incentive Optimization in Mobile Payment Marketing](https://mlsanity.com/paper/2112.15434/) (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)
- [Scalable Projection-Free Optimization](https://mlsanity.com/paper/2105.03527/) (2021)
- [An Analysis of Selection Bias Issue for Online Advertising](https://mlsanity.com/paper/2206.03853/) (2022)
- [High Probability Bounds for Stochastic Continuous Submodular Maximization](https://mlsanity.com/paper/2303.11937/) (2023)
- [Toward Trustworthy AI: Multi-Target Adversarial Attacks and Robust Defenses for Continuous Data Summarization](https://mlsanity.com/paper/2606.11804/) (2026)

## Abstract (arXiv)

The optimal allocation of resources for maximizing influence, spread of information or coverage, has gained attention in the past years, in particular in machine learning and data mining. But in applications, the parameters of the problem are rarely known exactly, and using wrong parameters can lead to undesirable outcomes. We hence revisit a continuous version of the Budget Allocation or Bipartite Influence Maximization problem introduced by Alon et al. (2012) from a robust optimization perspective, where an adversary may choose the least favorable parameters within a confidence set. The resulting problem is a nonconvex-concave saddle point problem (or game). We show that this nonconvex problem can be solved exactly by leveraging connections to continuous submodular functions, and by solving a constrained submodular minimization problem. Although constrained submodular minimization is hard in general, here, we establish conditions under which such a problem can be solved to arbitrary precision ε.