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.
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:
- 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.
- 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