# Improved Regret Bounds for Online Submodular Maximization

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 29 references that are in the map.
- First posted on arXiv 15 Jun 2021.

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Norm](https://mlsanity.com/paper/1902.03736/) (2019)
- [Fast Algorithms for Online Stochastic Convex Programming](https://mlsanity.com/paper/1410.7596/) (2014)
- [Online Continuous Submodular Maximization](https://mlsanity.com/paper/1802.06052/) (2018)
- [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)
- [Continuous DR-submodular Maximization: Structure and Algorithms](https://mlsanity.com/paper/1711.02515/) (2017)
- [Conditional Gradient Method for Stochastic Submodular Maximization: Closing the Gap](https://mlsanity.com/paper/1711.01660/) (2017)
- [Efficient Projection-Free Online Methods with Stochastic Recursive Gradient](https://mlsanity.com/paper/1910.09396/) (2019)
- [Online Submodular Maximization under a Matroid Constraint with Application to Learning Assignments](https://mlsanity.com/paper/1407.1082/) (2014)
- [Continuous Submodular Function Maximization](https://mlsanity.com/paper/2006.13474/) (2020)
- [Online Continuous DR-Submodular Maximization with Long-Term Budget Constraints](https://mlsanity.com/paper/1907.00316/) (2019)

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

- [Fast First-Order Methods for Monotone Strongly DR-Submodular Maximization](https://mlsanity.com/paper/2111.07990/) (2021)
- [Nearly Minimax Optimal Submodular Maximization with Bandit Feedback](https://mlsanity.com/paper/2310.18465/) (2023)

## Abstract (arXiv)

In this paper, we consider an online optimization problem over T rounds where at each step t∈[T], the algorithm chooses an action xt from the fixed convex and compact domain set K. A utility function ft(·) is then revealed and the algorithm receives the payoff ft(xt). This problem has been previously studied under the assumption that the utilities are adversarially chosen monotone DR-submodular functions and O(√T) regret bounds have been derived. We first characterize the class of strongly DR-submodular functions and then, we derive regret bounds for the following new online settings: (1) ftt=1T are monotone strongly DR-submodular and chosen adversarially, (2) ftt=1T are monotone submodular (while the average frac1Tsumt=1T ft is strongly DR-submodular) and chosen by an adversary but they arrive in a uniformly random order, (3) ftt=1T are drawn i.i.d. from some unknown distribution ft~ D where the expected function f(·)=mathbbEft~D[ft(·)] is monotone DR-submodular. For (1), we obtain the first logarithmic regret bounds. In terms of the second framework, we show that it is possible to obtain similar logarithmic bounds with high probability. Finally, for the i.i.d. model, we provide algorithms with tildeO(√T) stochastic regret bound, both in expectation and with high probability. Experimental results demonstrate that our algorithms outperform the previous techniques in the aforementioned three settings.