Improved Projection-free Online Continuous Submodular Maximization
Improved Projection-free Online Continuous Submodular Maximization
复制标题
改进的无投影在线连续子模最大化
DOI：
10.48550/arxiv.2305.18442
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Mingli Song
中科院分区：
文献类型：
--
作者：
Yucheng Liao;Yuanyu Wan;Chang Yao;Mingli Song
我们研究了单调和连续 DR 子模奖励函数的在线学习问题，该问题最近受到了极大的关注。为了有效地处理这个问题，特别是在决策集复杂的情况下，之前的研究提出了一种高效的无投影算法，称为 Mono-Frank-Wolfe (Mono-FW)，总共使用 $O(T)$ 梯度评估和线性优化步骤。然而，它仅达到$O(T^{4/5})$的$(1-1/e)$-regret界限。在本文中，我们提出了一种改进的无投影算法，即 POBGA，它将遗憾限制为 $O(T^{3/4})$，同时保持与 Mono-FW 相同的计算复杂度。我们的关键思想不是修改 Mono-FW，而是将基于投影的算法（称为在线提升梯度上升）、不可行的投影技术和分块技术进行新颖的组合。此外，我们考虑去中心化设置并开发了 POBGA 的变体，这不仅将这种设置的高效无投影算法的当前最佳遗憾界限从 $O(T^{4/5})$ 降低到 $O(T^{3/4})$，而且还降低了总通信复杂度从 $O(T)$ 到 $O(\sqrt{T})$。
We investigate the problem of online learning with monotone and continuous DR-submodular reward functions, which has received great attention recently. To efficiently handle this problem, especially in the case with complicated decision sets, previous studies have proposed an efficient projection-free algorithm called Mono-Frank-Wolfe (Mono-FW) using $O(T)$ gradient evaluations and linear optimization steps in total. However, it only attains a $(1-1/e)$-regret bound of $O(T^{4/5})$. In this paper, we propose an improved projection-free algorithm, namely POBGA, which reduces the regret bound to $O(T^{3/4})$ while keeping the same computational complexity as Mono-FW. Instead of modifying Mono-FW, our key idea is to make a novel combination of a projection-based algorithm called online boosting gradient ascent, an infeasible projection technique, and a blocking technique. Furthermore, we consider the decentralized setting and develop a variant of POBGA, which not only reduces the current best regret bound of efficient projection-free algorithms for this setting from $O(T^{4/5})$ to $O(T^{3/4})$, but also reduces the total communication complexity from $O(T)$ to $O(\sqrt{T})$.