收录:
摘要:
In this paper, we study a class of online non-monotone maximization problems under general constraint set. In each round, the function fed back by the environment is of composite structure: the sum of a DR-submodular function and a concave function. This setting covers a wide range of applications. We propose a Frank-Wolfe type online algorithm for solving the considered problem. In our algorithm, there is no need to have the ability to obtain exact gradients of the revealed functions. Adopting the Lyapunov function approach and variance reduction technique, the algorithm is shown to have the bi-criteria competitive ratio (1/4 , 3/8) with sub-linear regret under selecting suitable parameters.(c) 2023 Elsevier B.V. All rights reserved.
关键词:
通讯作者信息:
电子邮件地址:
来源 :
THEORETICAL COMPUTER SCIENCE
ISSN: 0304-3975
年份: 2023
卷: 979
1 . 1 0 0
JCR@2022
归属院系: