Indexed by:
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:
Reprint Author's Address:
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: