# Stochastic Continuous Submodular Maximization: Boosting via Non-oblivious Function

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 43 references that are in the map.
- First posted on arXiv 3 Jan 2022.

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [Matrix Completion has No Spurious Local Minimum](https://mlsanity.com/paper/1605.07272/) (2016)
- [Restricted Strong Convexity Implies Weak Submodularity](https://mlsanity.com/paper/1612.00804/) (2016)
- [Non-convex Robust PCA](https://mlsanity.com/paper/1410.7660/) (2014)
- [Online Continuous Submodular Maximization](https://mlsanity.com/paper/1802.06052/) (2018)
- [On Graduated Optimization for Stochastic Non-Convex Problems](https://mlsanity.com/paper/1503.03712/) (2015)
- [Gradient Methods for Submodular Maximization](https://mlsanity.com/paper/1708.03949/) (2017)
- [Online Continuous Submodular Maximization: From Full-Information to Bandit Feedback](https://mlsanity.com/paper/1910.12424/) (2019)
- [Guaranteed Non-convex Optimization: Submodular Maximization over Continuous Domains](https://mlsanity.com/paper/1606.05615/) (2016)
- [Projection-Free Online Optimization with Stochastic Gradient: From Convexity to Submodularity](https://mlsanity.com/paper/1802.08183/) (2018)
- [Conditional Gradient Method for Stochastic Submodular Maximization: Closing the Gap](https://mlsanity.com/paper/1711.01660/) (2017)
- [Submodular Maximization Beyond Non-negativity: Guarantees, Fast Algorithms, and Applications](https://mlsanity.com/paper/1904.09354/) (2019)
- [Guess Free Maximization of Submodular and Linear Sums](https://mlsanity.com/paper/1810.03813/) (2018)
- [Submodular + Concave](https://mlsanity.com/paper/2106.04769/) (2021)
- [Continuous Submodular Function Maximization](https://mlsanity.com/paper/2006.13474/) (2020)

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

- [Learning from Teaching Regularization: Generalizable Correlations Should be Easy to Imitate](https://mlsanity.com/paper/2402.02769/) (2024)
- [Utility-Diversity Aware Online Batch Selection for LLM Supervised Fine-tuning](https://mlsanity.com/paper/2510.16882/) (2025)
- [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)
- [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)
- [Boosting Gradient Ascent for Continuous DR-submodular Maximization](https://mlsanity.com/paper/2401.08330/) (2024)
- [Unified Projection-Free Algorithms for Adversarial DR-Submodular Optimization](https://mlsanity.com/paper/2403.10063/) (2024)
- [Online Learning for Non-monotone Submodular Maximization: From Full Information to Bandit Feedback](https://mlsanity.com/paper/2208.07632/) (2022)
- [Upper-Linearizability of Online Non-Monotone DR-Submodular Maximization over Down-Closed Convex Sets](https://mlsanity.com/paper/2602.20578/) (2026)
- [Online Learning for Approximately-Convex Functions with Long-term Adversarial Constraints](https://mlsanity.com/paper/2508.16992/) (2025)
- [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)
- [Stochastic Submodular Maximization via Polynomial Estimators](https://mlsanity.com/paper/2303.09960/) (2023)
- [High Probability Bounds for Stochastic Continuous Submodular Maximization](https://mlsanity.com/paper/2303.11937/) (2023)
- [Online Two-Stage Submodular Maximization](https://mlsanity.com/paper/2510.19480/) (2025)
- [Distributed Online Bandit Submodular Maximization with Bounded Sampling Violations](https://mlsanity.com/paper/2607.00680/) (2026)

## Abstract (arXiv)

In this paper, we revisit Stochastic Continuous Submodular Maximization in both offline and online settings, which can benefit wide applications in machine learning and operations research areas. We present a boosting framework covering gradient ascent and online gradient ascent. The fundamental ingredient of our methods is a novel non-oblivious function F derived from a factor-revealing optimization problem, whose any stationary point provides a (1-e-γ)-approximation to the global maximum of the γ-weakly DR-submodular objective function f∈ C1,1L(X). Under the offline scenario, we propose a boosting gradient ascent method achieving (1-e-γ-ε2)-approximation after O(1/ε2) iterations, which improves the (fracγ21+γ2) approximation ratio of the classical gradient ascent algorithm. In the online setting, for the first time we consider the adversarial delays for stochastic gradient feedback, under which we propose a boosting online gradient algorithm with the same non-oblivious function F. Meanwhile, we verify that this boosting online algorithm achieves a regret of O(√D) against a (1-e-γ)-approximation to the best feasible solution in hindsight, where D is the sum of delays of gradient feedback. To the best of our knowledge, this is the first result to obtain O(√T) regret against a (1-e-γ)-approximation with O(1) gradient inquiry at each time step, when no delay exists, i.e., D=T. Finally, numerical experiments demonstrate the effectiveness of our boosting methods.