Unified Projection-Free Algorithms for Adversarial DR-Submodular Optimization

This paper introduces unified projection-free Frank-Wolfe type algorithms for adversarial continuous DR-submodular optimization, spanning scenarios such as full information and (semi-)bandit feedback, monotone and non-monotone functions, different constraints, and types of stochastic queries. For every problem considered in the non-monotone setting, the proposed algorithms are either the first with proven sub-linear α-regret bounds or have better α-regret bounds than the state of the art, where α is a corresponding approximation bound in the offline setting. In the monotone setting, the proposed approach gives state-of-the-art sub-linear α-regret bounds among projection-free algorithms in 7 of the 8 considered cases while matching the result of the remaining case. Additionally, this paper addresses semi-bandit and bandit feedback for adversarial DR-submodular optimization, advancing the understanding of this optimization area. In the ICLR publication, there was a typo in the last sentence in the paragraph following Theorem 1 on page 8, specializing the results to a value oracle that resulted in an incorrect value in Table 1 . In particular, the regret bound for the setting of full-information zeroth-order feedback (for both monotone and non-monotone objectives, for any class of constraint sets) is Õ(T 4-β 5 ) and not Õ(T 3-β 5 ).