Improved Algorithms for Online Submodular Maximization via First-order Regret Bounds

Nicholas J. A. Harvey, Christopher Liaw, Tasuku SomaNeurIPS 2020 · OpenReview

Introduction

Submodular functions are often described as the discrete analogue of convex or concave functions. They appear naturally in machine learning and game theory tasks like sensor placement, document summarization, and viral marketing, where the principle of "diminishing returns" applies.

In the online setting, a player must choose a set of items at each time step $t$ without knowing the specific submodular reward function $f_t$ that will subsequently be revealed by an adversary. The goal is to minimize approximate regret: the difference between a fixed fraction (the approximation ratio $\alpha$) of the best possible set in hindsight and the total reward actually gained by the algorithm.

Previous algorithms for this problem yielded regret bounds that scaled poorly with the size of the ground set ($n$) or the constraint size ($k$). This paper significantly sharpens the performance guarantees for online submodular maximization, closing the gap between theoretical upper bounds and practical achievability by exploiting the internal structure of these optimization problems.

Methodology

The primary innovation of this work is the application of first-order regret bounds from Online Linear Optimization (OLO) as a building block for submodular problems. While standard "zeroth-order" bounds typically scale with $\sqrt{T}$ (where $T$ is the time horizon), first-order bounds adapt to the actual rewards received, scaling with the square root of the total rewards or losses.

  • For Monotone Functions (Matroid Constraints): The authors adapt the "online continuous greedy" algorithm. This approach reduces the complex submodular problem into a series of simpler OLO subproblems. By employing OLO solvers that feature first-order regret bounds, they exploit the fact that the sum of rewards across these subproblems is naturally constrained, leading to a much tighter overall bound.
  • For Non-monotone Functions (Unconstrained): The authors build upon the "online double greedy" framework, reducing the problem to "USM-balance" subproblems. They solve these using Blackwell approachability—a classic tool from game theory. Crucially, they derive a novel first-order regret bound for the specific Blackwell instances that arise here, a significant technical contribution previously absent in the literature.

Key Insights

  • Data-Dependent Efficiency: Submodular maximization subproblems are not just generic OLO tasks; they possess a specific structure where the total reward is bounded. Standard bounds are overly pessimistic because they assume the worst-case reward at every single step. First-order bounds "notice" when rewards are small and provide tighter guarantees accordingly.
  • Bridging Offline and Online with Curvature: For monotone functions, the paper incorporates "curvature" ($c$), a measure of how far a function is from being linear. The authors provide the first $O(\sqrt{T})$ regret bound for the bounded curvature setting in the online world, matching the sophisticated approximation ratios known in offline optimization.
  • Blackwell as a First-Order Tool: Applying Blackwell approachability to obtain first-order bounds for non-monotone problems suggests that Blackwell's framework is far more powerful for "fine-grained" regret analysis than previously recognized in the submodular community.

Key Results

The paper provides substantial improvements over the state-of-the-art, tightening bounds by factors related to the size of the problem domain.

Summary of improved regret bounds

As highlighted in the comparison above, the key improvements include:

  • Monotone + Matroid: Regret is improved from $O(k\sqrt{nT})$ to $O(\sqrt{kT \ln(n/k)})$. In scenarios where the ground set $n$ is much larger than the constraint $k$, this represents a massive reduction in regret.
  • Non-monotone Unconstrained: The $1/2$-regret is improved from $O(n\sqrt{T})$ to $O(\sqrt{nT})$, yielding a factor of $\sqrt{n}$ improvement.
  • Curvature Awareness: The monotone algorithm achieves a $(1 - c/e - \epsilon)$-regret bound. When the curvature $c < 1$, this ratio is strictly better than the standard $(1 - 1/e)$ ratio.
  • Horizon Independence: Unlike many online algorithms, these methods do not require knowing the total number of rounds $T$ in advance.

Limitations and Future Work

While theoretically robust, the paper notes several limitations that pave the way for future research:

  • Computational Complexity: The algorithm for monotone functions is theoretically polynomial-time but computationally demanding. It requires solving submodular function minimization (SFM) problems for its projection steps. While SFM is polynomial, it is often too slow for high-speed, real-time online applications.
  • Full-Information vs. Bandits: This work operates in the "full-information" setting, where the player sees the entire function $f_t$ after making a choice. In many real-world scenarios (like ad clicks), the algorithm only observes the reward for the specific set it picked (the "bandit" setting). Extending these tight first-order bounds to the bandit setting remains an open and difficult challenge.
  • Discretization Errors: The proof for the monotone case relies on a continuous-time analysis that must be discretized for implementation. This introduces an $\epsilon$ error term in the approximation ratio; reducing this overhead is a potential area for algorithmic refinement.

Summary updated

Abstract

We consider the problem of nonnegative submodular maximization in the online setting. At time step t, an algorithm selects a set S<em>t ∈ C ⊆ 2^V where C is a feasible family of sets. An adversary then reveals a submodular function f</em>t. The goal is to design an efficient algorithm for minimizing the expected approximate regret. In this work, we give a general approach for improving regret bounds in online submodular maximization by exploiting “first-order” regret bounds for online linear optimization. - For monotone submodular maximization subject to a matroid, we give an efficient algorithm which achieves a (1 − c/e − ε)-regret of O(√kT ln(n/k)) where n is the size of the ground set, k is the rank of the matroid, ε &gt; 0 is a constant, and c is the average curvature. Even without assuming any curvature (i.e., taking c = 1), this regret bound improves on previous results of Streeter et al. (2009) and Golovin et al. (2014). - For nonmonotone, unconstrained submodular functions, we give an algorithm with 1/2-regret O(√ nT), improving on the results of Roughgarden and Wang (2018). Our approach is based on Blackwell approachability; in particular, we give a novel first-order regret bound for the Blackwell instances that arise in this setting
BibTeX
@inproceedings{harvey2020improved,
  author = {Nicholas J. A. Harvey and Christopher Liaw and Tasuku Soma},
  title = {{Improved Algorithms for Online Submodular Maximization via First-order Regret Bounds}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=A1cAGFDMdT},
}
Figure