Text

Efficient Online Linear Optimization with Approximation Algorithms

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(log T) calls to the approximation oracle per iteration, on average. These are the first results to obtain both the average oracle complexity of O(log T) (or even polylogarithmic in T) and α -regret bound O(T−c) for a constant c > 0 for both variants.

Ketersediaan

Informasi Detail

Judul Seri

MATHEMATICS OF OPERATIONS RESEARCH; Vol.46 No.1 February 2021

No. Panggil

-

Penerbit

: .,

Deskripsi Fisik

p. 204 - 220

Bahasa

English

ISBN/ISSN

-

Klasifikasi

-

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

ONLINE LEARNING
APPROXIMATION ALGORITHMS
ONLINE ALGORITHMS
REGRET MINIMIZATION
ONLINE LINEAR OPTIMIZATION

Info Detail Spesifik

https://doi.org/10.1287/moor.2020.1053

Pernyataan Tanggungjawab

Dan Garber

Versi lain/terkait

Lampiran Berkas

Komentar