Name
Abstract | ||
|---|---|---|
We consider algorithms for "smoothed online convex optimization" problems, a variant of the class of online convex optimization problems that is strongly related to metrical task systems. Prior literature on these problems has focused on two performance metrics: regret and the competitive ratio. There exist known algorithms with sublinear regret and known algorithms with constant competitive ratios; however, no known algorithm achieves both simultaneously. We show that this is due to a fundamental incompatibility between these two metrics - no algorithm (deterministic or randomized) can achieve sublinear regret and a constant competitive ratio, even in the case when the objective functions are linear. However, we also exhibit an algorithm that, for the important special case of one-dimensional decision spaces, provides sublinear regret while maintaining a competitive ratio that grows arbitrarily slowly. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1145/2465529.2465533 | SIGMETRICS |
Keywords | Field | DocType |
simultaneous bound,learning theory,online algorithms | Metrical task system,Sublinear function,Online algorithm,Mathematical optimization,Regret,Computer science,Performance metric,Convex optimization,Competitive analysis | Conference |
Volume | Issue | ISSN |
abs/1508.03769 | 1 | 0163-5999 |
Citations | PageRank | References |
23 | 1.04 | 29 |
Authors | ||
7 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| L. L.H. Andrew | 1 | 918 | 52.52 |
| Siddharth Barman | 2 | 199 | 26.26 |
| Katrina Ligett | 3 | 923 | 66.19 |
| Minghong Lin | 4 | 444 | 16.14 |
| Adam Meyerson | 5 | 2132 | 146.08 |
| Alan Roytman | 6 | 93 | 7.52 |
| Adam Wierman | 7 | 1635 | 106.57 |