Timezone: »

 
Poster
Stochastic Continuous Submodular Maximization: Boosting via Non-oblivious Function
Qixin Zhang · Zengde Deng · Zaiyi Chen · Haoyuan Hu · Yu Yang

Thu Jul 21 03:00 PM -- 05:00 PM (PDT) @ Hall E #1213
in Poster Session 3 »
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 $F$ derived from a factor-revealing optimization problem, whose any stationary point provides a $(1-e^{-\gamma})$-approximation to the global maximum of the $\gamma$-weakly DR-submodular objective function $f\in C^{1,1}_L(\mathcal{X})$. Under the offline scenario, we propose a boosting gradient ascent method achieving $(1-e^{-\gamma}-\epsilon^{2})$-approximation after $O(1/\epsilon^2)$ iterations, which improves the $(\frac{\gamma^2}{1+\gamma^2})$ 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 $F$. Meanwhile, we verify that this boosting online algorithm achieves a regret of $O(\sqrt{D})$ against a $(1-e^{-\gamma})$-approximation to the best feasible solution in hindsight, where $D$ is the sum of delays of gradient feedback. To the best of our knowledge, this is the first result to obtain $O(\sqrt{T})$ regret against a $(1-e^{-\gamma})$-approximation with $O(1)$ gradient inquiry at each time step, when no delay exists, i.e., $D=T$. Finally, numerical experiments demonstrate the effectiveness of our boosting methods.
Keywords: OPT: First-order · OPT: Non-Convex · OPT: Stochastic · T: Online Learning and Bandits · T: Optimization · MISC: Online Learning, Active Learning and Bandits

Author Information

Qixin Zhang (City University of Hong Kong)
Zengde Deng (Cainiao Network)
Zaiyi Chen (University of Science and Technology of China)
Haoyuan Hu (Artificial Intelligence Department, Zhejiang Cainiao Supply Chain Management Co.)
Yu Yang (City University of Hong Kong)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors