Spotlight
Stochastic Continuous Submodular Maximization: Boosting via Non-oblivious Function
Qixin Zhang · Zengde Deng · Zaiyi Chen · Haoyuan Hu · Yu Yang
Ballroom 3 & 4
Abstract:
In this paper, we revisit Stochastic Continuous Submodular Maximization in both offline and online settings, which can benefit wide applications in machine learning and operations research areas. We present a boosting framework covering gradient ascent and online gradient ascent. The fundamental ingredient of our methods is a novel non-oblivious function derived from a factor-revealing optimization problem, whose any stationary point provides a -approximation to the global maximum of the -weakly DR-submodular objective function . Under the offline scenario, we propose a boosting gradient ascent method achieving -approximation after iterations, which improves the approximation ratio of the classical gradient ascent algorithm.In the online setting, for the first time we consider the adversarial delays for stochastic gradient feedback, under which we propose a boosting online gradient algorithm with the same non-oblivious function . Meanwhile, we verify that this boosting online algorithm achieves a regret of against a -approximation to the best feasible solution in hindsight, where is the sum of delays of gradient feedback. To the best of our knowledge, this is the first result to obtain regret against a -approximation with gradient inquiry at each time step, when no delay exists, i.e., . Finally, numerical experiments demonstrate the effectiveness of our boosting methods.
Chat is not available.