• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
搜索

Author:

Feng, Junkai (Feng, Junkai.) | Yang, Ruiqi (Yang, Ruiqi.) | Zhang, Haibin (Zhang, Haibin.) | Zhang, Zhenning (Zhang, Zhenning.)

Indexed by:

EI Scopus SCIE

Abstract:

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.

Keyword:

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

Author Community:

  • [ 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

Reprint Author's Address:

Show more details

Related Keywords:

Source :

THEORETICAL COMPUTER SCIENCE

ISSN: 0304-3975

Year: 2023

Volume: 979

1 . 1 0 0

JCR@2022

Cited Count:

WoS CC Cited Count:

SCOPUS Cited Count:

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 0

Affiliated Colleges:

Online/Total:1008/10895139
Address:BJUT Library(100 Pingleyuan,Chaoyang District,Beijing 100124, China Post Code:100124) Contact Us:010-67392185
Copyright:BJUT Library Technical Support:Beijing Aegean Software Co., Ltd.