Back to Search
Start Over
Efficient Online Linear Optimization with Approximation Algorithms.
- Source :
- Mathematics of Operations Research; Feb2021, Vol. 46 Issue 1, p204-220, 17p
- Publication Year :
- 2021
-
Abstract
- We revisit the problem of online linear optimization in the case where the set of feasible actions is accessible through an approximated linear optimization oracle with a factor α multiplicative approximation guarantee. This setting in particular is interesting because it captures natural online extensions of well-studied offline linear optimization problems that are NP-hard yet admit efficient approximation algorithms. The goal here is to minimize the α-regret, which is the natural extension to this setting of the standard regret in online learning. We present new algorithms with significantly improved oracle complexity for both the full-information and bandit variants of the problem. Mainly, for both variants, we present α-regret bounds of O (T − 1 / 3 ) , were T is the number of prediction rounds, using only O (l o g T) calls to the approximation oracle per iteration, on average. These are the first results to obtain both the average oracle complexity of O (l o g T) (or even polylogarithmic in T) and α -regret bound O (T − c ) for a constant c > 0 for both variants. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 0364765X
- Volume :
- 46
- Issue :
- 1
- Database :
- Complementary Index
- Journal :
- Mathematics of Operations Research
- Publication Type :
- Academic Journal
- Accession number :
- 148514717
- Full Text :
- https://doi.org/10.1287/moor.2020.1053