Efficient Online Linear Optimization with Approximation Algorithms
This work addresses efficient online optimization for NP-hard problems by leveraging approximation algorithms, offering improved computational efficiency for applications in machine learning and operations research.
The paper tackles the problem of online linear optimization with approximation oracles, achieving α-regret bounds of O(T^{-1/3}) for full-information and bandit variants while using only O(log T) average oracle calls per iteration.
We revisit the problem of \textit{online linear optimization} in case the set of feasible actions is accessible through an approximated linear optimization oracle with a factor $α$ multiplicative approximation guarantee. This setting is in particular interesting since it captures natural online extensions of well-studied \textit{offline} linear optimization problems which are NP-hard, yet admit efficient approximation algorithms. The goal here is to minimize the $α$\textit{-regret} which is the natural extension of the standard \textit{regret} in \textit{online learning} to this setting. 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 average oracle complexity of $O(\log{T})$ (or even poly-logarithmic in $T$) and $α$-regret bound $O(T^{-c})$ for a constant $c>0$, for both variants.