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

Author:

Lian, Yuefang (Lian, Yuefang.) | Xu, Dachuan (Xu, Dachuan.) (Scholars:徐大川) | Du, Donglei (Du, Donglei.) | Zhou, Yang (Zhou, Yang.)

Indexed by:

CPCI-S EI Scopus

Abstract:

In this paper, we concentrate on a stochastic non-monotone DR-submodular maximization problem over a convex constraint C, where the objective function arises as an expectation of a set of stochastic functions. We develop an algorithm named SPIDER-FW, which is a stochastic version of the classical Frank-Wolfe algorithm with 1/4 (1- min(x epsilon C) parallel to x parallel to(infinity))F(x*) - epsilon (in expectation) approximation guarantee, the best guarantee so far for the above setting, achieved with O(1/epsilon) iterations, and O(1/epsilon(2)) first-order oracle calls.

Keyword:

Continuous DR-submodular Gradient estimator Frank-Wolfe algorithm Potential function Stochastic optimization

Author Community:

  • [ 1 ] [Lian, Yuefang]Beijing Univ Technol, Beijing Inst Sci & Engn Comp, Beijing 100124, Peoples R China
  • [ 2 ] [Xu, Dachuan]Beijing Univ Technol, Beijing Inst Sci & Engn Comp, Beijing 100124, Peoples R China
  • [ 3 ] [Du, Donglei]Univ New Brunswick, Fac Management, Fredericton, NB E3B 9Y2, Canada
  • [ 4 ] [Zhou, Yang]Shandong Normal Univ, Sch Math & Stat, Jinan, Shandong, Peoples R China

Reprint Author's Address:

Show more details

Related Keywords:

Source :

COMPUTING AND COMBINATORICS, COCOON 2022

ISSN: 0302-9743

Year: 2022

Volume: 13595

Page: 1-11

Cited Count:

WoS CC Cited Count: 2

SCOPUS Cited Count: 1

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 5

Affiliated Colleges:

Online/Total:657/10616252
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.