Unified Projection-Free Algorithms for Adversarial DR-Submodular Optimization
This work addresses optimization problems in machine learning and AI, offering incremental improvements in projection-free algorithms for adversarial settings.
The paper tackles adversarial continuous DR-submodular optimization by introducing unified projection-free Frank-Wolfe algorithms, achieving proven sub-linear α-regret bounds in non-monotone settings and state-of-the-art results in monotone settings across various scenarios.
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.