Name
Abstract | ||
|---|---|---|
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,ldots,n}) and a sequence of (T) nonnegative (not necessarily monotone) submodular functions arrive over time. 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-(tfrac 12)-regret algorithm for this problem, meaning that for every sequence of nonnegative submodular functions, the algorithmu0027s expected total value is at least (tfrac{1}{2}) times that of the best subset in hindsight, up to an error term sublinear in (T). The factor of (tfrac 12) cannot be improved upon by any polynomial-time online algorithm, unless (NP = RP). Prior to our work, the best result known was that picking a subset uniformly at random in every time step achieves no (tfrac 14)-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. |
Year | Venue | Field |
|---|---|---|
2018 | COLT | Sublinear function,Online algorithm,Regret,Subroutine,Computer science,Optimal learning,Submodular set function,Algorithm,Submodular maximization,Monotone polygon |
DocType | Citations | PageRank |
Conference | 1 | 0.44 |
References | Authors | |
0 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tim Roughgarden | 1 | 4177 | 353.32 |
| Joshua R. Wang | 2 | 69 | 5.83 |