A Single Recipe for Online Submodular Maximization with Adversarial or Stochastic Constraints

Omid Sadeghi, Prasanna Sanjay Raut, Maryam Fazel

Overview

In the realm of online optimization, decision-makers are frequently tasked with maximizing a sequence of continuous submodular (DR-submodular) rewards while simultaneously adhering to long-term convex constraints, such as a budget. This paper introduces a unified algorithmic framework that achieves sub-linear regret and constraint violations regardless of whether the incoming constraints are adversarial or stochastic. Crucially, this eliminates the need for the algorithm to know the environment's regime in advance.

The Challenge: Diminishing Returns and Unknown Environments

In standard online optimization, a decision-maker must make sequential choices before observing the actual reward or cost of that choice, typically with the sole goal of maximizing total accumulated reward. However, real-world applications—like online ad placement or crowdsourcing—impose budgets or resource limits. These limits act as long-term constraints that must be satisfied on average over time.

Prior research has predominantly addressed this problem under two restrictive conditions: when the reward functions are strictly concave, or when the constraints are strictly linear.

Comparison of prior works on online optimization with constraints.

Yet, many real-world rewards exhibit "diminishing returns," a property best modeled by DR-submodular functions. Because these functions are generally non-concave, they are notoriously difficult to optimize. Furthermore, the resource constraints arriving at each step might be adversarial (worst-case, arbitrarily changing) or stochastic (drawn from a random distribution). Previously, algorithms needed prior knowledge of which regime they were operating in to perform well. This paper bridges that gap by introducing the first unified approach for DR-submodular maximization with general convex constraints.

Proposed Methodology

The authors propose two algorithms based on a primal-dual approach to tackle these challenges:

  1. Algorithm 1 (The Main Recipe): This core algorithm merges the Meta-Frank-Wolfe method (standard for submodular maximization) with a Lyapunov drift technique (typically used in convex optimization to handle constraints). It runs $K$ parallel instances of online gradient ascent. At each time step, it updates "primal" variables to maximize a penalized reward (the actual reward minus a penalty for breaking the constraint) and updates $K$ "dual" variables to track the accumulated constraint violations.
  2. Algorithm 2 (The Faster Variant): Algorithm 1 can be computationally heavy because it requires evaluating gradients $K$ times per step. Inspired by the Mono-Frank-Wolfe method, Algorithm 2 divides the total time horizon $T$ into blocks of length $K$. By playing the exact same action for every step within a block, the algorithm reduces computational complexity by a factor of $K$.

Key Insights

  • One Algorithm to Rule Them All: A well-tuned primal-dual algorithm can adapt to both adversarial and stochastic environments. It achieves optimal bounds for the stochastic case while remaining robust to adversarial constraints, removing the need for separate, regime-specific algorithms.
  • Taming Non-Concavity: Even though DR-submodular functions are non-concave, they possess a property called "concavity along non-negative directions." The authors cleverly exploit this to prove that Lyapunov drift techniques—traditionally reserved for strictly convex/concave problems—can still guarantee sub-linear constraint violations in this setting.
  • The Efficiency vs. Optimality Trade-off: By freezing the algorithm's action over blocks of time (Algorithm 2), computational costs drop drastically. Theoretical analysis shows that this "lazy" updating still guarantees sub-linear regret, albeit at a slightly slower convergence rate.

Experimental Validation and Results

The authors validated their algorithms using both real-world and synthetic data across three motivating applications: Online Joke Recommendation (using the Jester dataset to maximize impressions under a time budget), Online Task Assignment in Crowdsourcing, and Online Welfare Maximization with Production Cost.

The theoretical and empirical results are strong:

  • Adversarial Environments: Algorithm 1 achieves $O(T^{1-\epsilon/2})$ static regret and $O(T^{1-\epsilon/2})$ constraint violation against a benchmark with a window size of $W = T^{1-\epsilon}$.
  • Stochastic Environments: Algorithm 1 achieves the gold-standard $O(\sqrt{T})$ bounds for both regret and constraint violation, both in expectation and with high probability.
  • Faster Variant: Algorithm 2 trades a bit of performance for speed, achieving $O(T^{2/3})$ regret and constraint violation in both settings.
  • Dynamic Environments: The authors also prove dynamic regret bounds of $O(\sqrt{T P_T^*})$, where $P_T^*$ represents how much the optimal benchmark action changes over time.
  • Empirical Performance: In experiments, Algorithm 1 successfully kept budget consumption strictly below required thresholds while matching or beating the utility of prior baselines, which often violated budgets more aggressively.

Limitations and Future Work

While the framework is robust, it has a few limitations. First, to achieve the optimal dynamic regret bounds, the algorithm's hyperparameters must be tuned using $P_T^*$ (the path length of the optimal sequence). Because this value is unknown ahead of time in reality, the authors suggest integrating adaptive online learning techniques in future work. Second, despite the speedups in Algorithm 2, Algorithm 1's requirement to maintain $K$ dual variables and perform $K$ gradient evaluations per time step could remain a bottleneck in highly latency-sensitive applications.

Summary updated

Abstract

In this paper, we consider an online optimization problem in which the reward functions are DR-submodular, and in addition to maximizing the total reward, the sequence of decisions must satisfy some convex constraints on average. Specifically, at each round $t\in\{1,\dots,T\}$, upon committing to an action $x_t$, a DR-submodular utility function $f_t(\cdot)$ and a convex constraint function $g_t(\cdot)$ are revealed, and the goal is to maximize the overall utility while ensuring the average of the constraint functions $\frac{1}{T}\sum_{t=1}^T g_t(x_t)$ is non-positive. Such cumulative constraints arise naturally in applications where the average resource consumption is required to remain below a prespecified threshold. We study this problem under an adversarial model and a stochastic model for the convex constraints, where the functions $g_t$ can vary arbitrarily or according to an i.i.d. process over time slots $t\in\{1,\dots,T\}$, respectively. We propose a single algorithm which achieves sub-linear (with respect to $T$) regret as well as sub-linear constraint violation bounds in both settings, without prior knowledge of the regime. Prior works have studied this problem in the special case of linear constraint functions. Our results not only improve upon the existing bounds under linear cumulative constraints, but also give the first sub-linear bounds for general convex long-term constraints.
BibTeX
@inproceedings{sadeghi2020single,
  author = {Omid Sadeghi and Prasanna Sanjay Raut and Maryam Fazel},
  title = {{A Single Recipe for Online Submodular Maximization with Adversarial or Stochastic Constraints}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=sI1gXm87j7},
}
Figure