Source-linked AI summary
An Optimal Algorithm for Online Unconstrained Submodular Maximization
Tim Roughgarden, Joshua R. Wang
TL;DR
Online USM asks how to make computationally efficient subset choices as nonnegative submodular functions arrive, relative to the best fixed subset in hindsight. The paper develops a polynomial-time algorithm with a tight 1/2-regret guarantee. Its analysis uses a specialized balance subproblem and extends to adaptive adversaries.
Problem
Online USM requires computationally efficient online subset choices against arriving nonnegative submodular functions, compared with the best fixed subset in hindsight.
Source: §1 · p. 2Method
A two-phase framework reduces online USM to a USM Balance Subproblem and uses a tailored subroutine with potential-based analysis.
Source: §1 · p. 3, §1.2 · p. 5Results
1/2-regret is achievable in polynomial time, and no larger factor is achievable unless RP = NP; in the value-oracle model, the lower bound is unconditional.
Source: §1 · p. 3Takeaways & Limitations
The paper resolves the online-versus-offline guarantee question positively for online USM.
Source: §1 · p. 3The stated setting has adversarial submodular functions valued in [0,1]; the results also cover polynomially evaluable functions and value oracles.
Source: §1 · pp. 2–3
Abstract
from arXiv · showhide
We consider a basic problem at the interface of two fundamental fields: submodular optimization and online learning. In the online unconstrained submodular maximization (online USM) problem, there is a universe $[n]=\{1,2,...,n\}$ and a sequence of $T$ nonnegative (not necessarily monotone) submodular functions arrive over time. The goal is to design a computationally efficient online algorithm, which chooses a subset of $[n]$ at each time step as a function only of the past, such that the accumulated value of the chosen subsets is as close as possible to the maximum total value of a fixed subset in hindsight. Our main result is a polynomial-time no-$1/2$-regret algorithm for this problem, meaning that for every sequence of nonnegative submodular functions, the algorithm's expected total value is at least $1/2$ times that of the best subset in hindsight, up to an error term sublinear in $T$. The factor of $1/2$ cannot be improved upon by any polynomial-time online algorithm when the submodular functions are presented as value oracles. Previous work on the offline problem implies that picking a subset uniformly at random in each time step achieves zero $1/4$-regret. A byproduct of our techniques is an explicit subroutine for the two-experts problem that has an unusually strong regret guarantee: the total value of its choices is comparable to twice the total value of either expert on rounds it did not pick that expert. This subroutine may be of independent interest.
1 Introduction
Online USM asks for efficient online subset choices against arriving nonnegative submodular functions, benchmarked against the best fixed subset in hindsight. The paper establishes a tight 1/2-regret guarantee and outlines a two-phase approach built around the USM Balance Subproblem.
1 Introduction
- Online USM chooses subsets of a known universe as submodular functions arrive, but generic no-regret methods require exponential computation per round.The objective compares accumulated online reward with the total value of the best fixed subset in hindsight.Source: §1 · pp. 2–3
- 1/2-regret is achievable in polynomial time for online USM, and no larger factor is achievable unless RP = NP.The lower bound follows from the offline USM hardness reduction; in the value-oracle model, the lower bound is unconditional.Source: §1 · p. 3
1.1 Related Work
- Existing offline-to-online reductions do not apply to USM, while a general black-box reduction is impossible for some problems; the paper resolves the online-versus-offline question for this natural problem.The prior reductions covered linear online optimization or required an exact best-response oracle.Source: §1 · p. 3
1.2 Our Techniques
- The first phase reduces online USM performance to a subroutine's performance on the USM Balance Subproblem; using a no-regret two-experts algorithm already yields no-1/3-regret.That improves on the previously best no-1/4-regret guarantee from choosing a uniform random point each round.Source: §1.2 · p. 4
- The second phase designs a Balance Subproblem subroutine because ordinary two-experts no-regret guarantees are insufficient for the desired 1/2-regret result.The analysis uses potential functions to relate algorithm state to its no-regret guarantee, and a covariance argument handles adaptive adversaries.Source: §1.2 · pp. 4–5
2 An Online USM Framework
The framework reduces online USM to sequential binary choices for each element, with their guarantees controlled by a USM Balance Subproblem. The analysis relates those binary decisions to the best fixed set in hindsight.
2 An Online USM Framework
- The framework turns choosing among 2^n subsets into n sequential yes/no decisions, one for each element.It starts with the empty set and the full universe as candidate solutions, then makes them agree element by element.Source: §2 · p. 5
- Each binary subroutine receives after-the-fact marginal values from the latest function, and the required subroutine guarantee is formalized as the USM Balance Subproblem.For each element, the framework considers adding it to one candidate set or removing it from the other.Source: §2 · p. 5
2.1 The USM Balance Subproblem
- In the balance problem, each round the algorithm chooses yes or no before the adversary reveals (αt, βt), updating the algorithm’s reward and two missed-opportunity totals.The two totals are Cyes and Cno; Ralg denotes the algorithm’s accumulated reward.Source: §2.1 · p. 6
- The proof tracks evolving versions of the algorithm’s set, the offline-optimal set, and the full-universe candidate to relate each binary decision to hindsight value.It checks how yes/no choices affect these sets using submodularity; the analysis accounts for rounds when a subroutine may choose a negative value.Source: §2.1 · pp. 7, 10
- A no-regret two-experts subroutine gives Algorithm 1 O(n · g(T)) 1/3-regret for Online USM.The USM Balance Subproblem guarantee is that the algorithm’s reward is comparable to the better of the adversary’s two missed-opportunity totals, in expectation.Source: §2.1 · pp. 7, 10
3 An Optimal No-1 2-Regret Algorithm for Online USM
The paper presents USM BALANCER as a subroutine for the USM Balance Subproblem. Combined with the framework, it yields a no-1/2-regret algorithm for Online USM, and the paper identifies this ratio as optimal.
3 An Optimal No-1 2-Regret Algorithm for Online USM
- The paper gives a no-regret algorithm for the USM Balance Subproblem, attaining the optimal α in α-regret terms; Theorem 2.1 converts Online USM inapproximability (nothing better than 1/2) into balance-subproblem inapproximability (nothing better than 1).Source: §3 · p. 10
- USM BALANCER chooses an item with probability pt and updates x using the adversary point’s convex-combination weights.The stated update is x ← x + (1 − 2pt)cu + cr − cℓ.Source: §3 · p. 11
- USM BALANCER is the proposed subroutine for solving the USM Balance Subproblem.Its regret proof is deferred to Appendix A.Source: §3 · p. 11
- Algorithm 1 has O(n T) 1/2-regret when using USM BALANCER as a subroutine.This follows by combining USM BALANCER’s guarantee with the reduction in Theorem 2.1.Source: §3 · p. 11
A Proof of Theorem 3.1
The proof establishes the balance guarantee using concentration under an oblivious adversary and a potential-based invariant. It handles the adversary’s extremal moves and extends the argument to their convex combinations.
A Proof of Theorem 3.1
- Because the target guarantee places a maximum inside the expectation, the proof aligns the two cost variables’ expectations before bounding that maximum.It shifts the lower-mean cost by the difference in expectations to obtain a same-mean comparison.Source: A Proof of Theorem 3.1 · p. 13
- Against an oblivious adversary, Cyes and Cno each have variance O(T), supporting bounds on how far they exceed their means.Cyes is a weighted sum of independent Bernoulli variables; Cno has the same variance bound, though the two totals are not independent.Source: A Proof of Theorem 3.1 · p. 14
- The proof adds potential functions to Ralg, Cyes, and Cno, then maintains an invariant showing the algorithm’s sum is at least the larger adversary sum.The potentials depend on the algorithm’s current x.Source: A Proof of Theorem 3.1 · p. 14
- For the right and left extremal moves, potential changes cancel reward and cost changes up to error; the up move is handled similarly.The proof extends the invariant from these three moves to every convex combination of them.Source: A Proof of Theorem 3.1 · p. 16
B Adaptive Adversaries
The section shows that Online USM techniques can handle adaptive adversaries, and that the USM BALANCER needs no algorithmic changes. Its proof uses an invariant valid for any adversarial sequence and controls deviations of Bernoulli variables from their means.
B Adaptive Adversaries
- The Online USM framework’s deterministic decomposition handles adaptive adversaries; using multiplicative weights also inherits that subroutine’s immunity.An oblivious adversary can simulate an adaptive one against a deterministic online algorithm.Source: B Adaptive Adversaries · p. 17
- The USM BALANCER handles adaptive adversaries without algorithmic changes, although its proof requires moving away from expectations.The algorithm’s coin flips and adversarial inputs are intertwined in this setting.Source: B Adaptive Adversaries · p. 17
- The proof relies on an invariant that holds for any adversarial sequence, then relates it to the desired regret guarantee in expectation.The challenge is that an adaptive adversary may choose a future Bernoulli mean based on a past variable.Source: B Adaptive Adversaries · p. 17
- Bernoulli variables minus their means have zero pairwise covariance even under adaptive choices, supporting an O(T) variance bound and an expected-deviation bound via Jensen’s inequality.The same approach yields similar inequalities for the other three pairs of matching sums.Source: B Adaptive Adversaries · pp. 17–18