# Boosting Gradient Ascent for Continuous DR-submodular Maximization

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 71 references that are in the map.
- First posted on arXiv 16 Jan 2024.

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

- [Matrix Completion has No Spurious Local Minimum](https://mlsanity.com/paper/1605.07272/) (2016)
- [Convergence Rate of Frank-Wolfe for Non-Convex Objectives](https://mlsanity.com/paper/1607.00345/) (2016)
- [Online Continuous Submodular Maximization](https://mlsanity.com/paper/1802.06052/) (2018)
- [Projection-Free Online Optimization with Stochastic Gradient: From Convexity to Submodularity](https://mlsanity.com/paper/1802.08183/) (2018)
- [Continuous DR-submodular Maximization: Structure and Algorithms](https://mlsanity.com/paper/1711.02515/) (2017)
- [Submodular Maximization Beyond Non-negativity: Guarantees, Fast Algorithms, and Applications](https://mlsanity.com/paper/1904.09354/) (2019)
- [Stochastic Continuous Submodular Maximization: Boosting via Non-oblivious Function](https://mlsanity.com/paper/2201.00703/) (2022)
- [Resolving the Approximability of Offline and Online Non-monotone DR-Submodular Maximization over General Convex Sets](https://mlsanity.com/paper/2210.05965/) (2022)
- [Bandit Multi-linear DR-Submodular Maximization and Its Applications on Adversarial Submodular Bandits](https://mlsanity.com/paper/2305.12402/) (2023)
- [Continuous Submodular Function Maximization](https://mlsanity.com/paper/2006.13474/) (2020)
- [A Unified Approach for Maximizing Continuous DR-submodular Functions](https://mlsanity.com/paper/2305.16671/) (2023)
- [An improved approximation algorithm for maximizing a DR-submodular function over a convex set](https://mlsanity.com/paper/2203.14740/) (2022)
- [Lyapunov function approach for approximation algorithm design and analysis: with applications in submodular maximization](https://mlsanity.com/paper/2205.12442/) (2022)
- [Continuous Non-monotone DR-submodular Maximization with Down-closed Convex Constraint](https://mlsanity.com/paper/2307.09616/) (2023)

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

- [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)
- [Decentralized Projection-free Online Upper-Linearizable Optimization with Applications to DR-Submodular Optimization](https://mlsanity.com/paper/2501.18183/) (2025)
- [Combatting Dimensional Collapse in LLM Pre-Training Data via Diversified File Selection](https://mlsanity.com/paper/2504.20644/) (2025)
- [Upper-Linearizability of Online Non-Monotone DR-Submodular Maximization over Down-Closed Convex Sets](https://mlsanity.com/paper/2602.20578/) (2026)
- [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)

## Abstract (arXiv)

Projected Gradient Ascent (PGA) is the most commonly used optimization scheme in machine learning and operations research areas. Nevertheless, numerous studies and examples have shown that the PGA methods may fail to achieve the tight approximation ratio for continuous DR-submodular maximization problems. To address this challenge, we present a boosting technique in this paper, which can efficiently improve the approximation guarantee of the standard PGA to optimal with only small modifications on the objective function. The fundamental idea of our boosting technique is to exploit non-oblivious search to derive a novel auxiliary function F, whose stationary points are excellent approximations to the global maximum of the original DR-submodular objective f. Specifically, when f is monotone and γ-weakly DR-submodular, we propose an auxiliary function F whose stationary points can provide a better (1-e-γ)-approximation than the (γ2/(1+γ2))-approximation guaranteed by the stationary points of f itself. Similarly, for the non-monotone case, we devise another auxiliary function F whose stationary points can achieve an optimal frac1-min_boldsymbolx∈C|boldsymbolx|∞4-approximation guarantee where C is a convex constraint set. In contrast, the stationary points of the original non-monotone DR-submodular function can be arbitrarily bad~citepchen2023continuous. Furthermore, we demonstrate the scalability of our boosting technique on four problems. In all of these four problems, our resulting variants of boosting PGA algorithm beat the previous standard PGA in several aspects such as approximation ratio and efficiency. Finally, we corroborate our theoretical findings with numerical experiments, which demonstrate the effectiveness of our boosting PGA methods.