• 综合
  • 标题
  • 关键词
  • 摘要
  • 学者
  • 期刊-刊名
  • 期刊-ISSN
  • 会议名称
搜索

作者:

Feng, Junkai (Feng, Junkai.) | Yang, Ruiqi (Yang, Ruiqi.) | Zhang, Haibin (Zhang, Haibin.) (学者:张海斌) | Zhang, Zhenning (Zhang, Zhenning.)

收录:

EI Scopus SCIE

摘要:

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.

关键词:

Bi-criteria competitive ratio DR-submodular Concave Regret Online optimization

作者机构:

  • [ 1 ] [Feng, Junkai]Beijing Univ Technol, Beijing Inst Sci & Engn Comp, Beijing 100124, Peoples R China
  • [ 2 ] [Yang, Ruiqi]Beijing Univ Technol, Beijing Inst Sci & Engn Comp, Beijing 100124, Peoples R China
  • [ 3 ] [Zhang, Haibin]Beijing Univ Technol, Beijing Inst Sci & Engn Comp, Beijing 100124, Peoples R China
  • [ 4 ] [Zhang, Zhenning]Beijing Univ Technol, Beijing Inst Sci & Engn Comp, Beijing 100124, Peoples R China

通讯作者信息:

查看成果更多字段

相关关键词:

来源 :

THEORETICAL COMPUTER SCIENCE

ISSN: 0304-3975

年份: 2023

卷: 979

1 . 1 0 0

JCR@2022

被引次数:

WoS核心集被引频次:

SCOPUS被引频次: 1

ESI高被引论文在榜: 0 展开所有

万方被引频次:

中文被引频次:

近30日浏览量: 0

归属院系:

在线人数/总访问数:575/4980932
地址:北京工业大学图书馆(北京市朝阳区平乐园100号 邮编:100124) 联系我们:010-67392185
版权所有:北京工业大学图书馆 站点建设与维护:北京爱琴海乐之技术有限公司