Unified Projection-Free Algorithms for Adversarial DR-Submodular Optimization
<|reference_start|>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 $\alpha$-regret bounds or have better $\alpha$-regret bounds than the state of the art, where $\alpha$ is a corresponding approximation bound in the offline setting. In the monotone setting, the proposed approach gives state-of-the-art sub-linear $\alpha$-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.<|reference_end|>
@article{pedramfar2024unified,
    title={Unified Projection-Free Algorithms for Adversarial DR-Submodular
  Optimization},
    author={Mohammad Pedramfar, Yididiya Y. Nadew, Christopher J. Quinn, Vaneet
  Aggarwal},
    journal={arXiv preprint arXiv:2403.10063},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.10063},
    primaryClass={cs.LG cs.AI cs.CC math.OC}
}