Efficient Online Linear Optimization with Approximation Algorithms
We revisit the problem of 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 offline linear optimization problems which are NP-hard, yet admit efficient approximation algorithms. The goal here is to minimize the ↵-regret which is the natural extension of the standard regret in 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
), 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.
This paper addresses the problem of online linear optimization when the feasible set is such that doing exact projections into it is NP-hard but there is an approximate algorithm for maximizing linear functions in the feasible set with a constant approximation ratio. This paper is an extension to "Playing games with approximation algorithms", by Kakade et al with a similar algorithm with substantially better computational complexity.
The main issue with the previous work (kakade et al)  addressed in this paper is the linear (in the length of the online prediction history) number of calls to the approximation algorithm required in each online prediction round. Needing to essentially remember the entire history and have ever more expensive computation in each iteration is prohibitive and doesn't match most other work in online learning.
This paper proposes a new infesible projection algorithm which given an input either returns its approximate projection into the feasible set or returns an infeasible point which is a convex combination of a known set of feasible points and is not too far from the input. Using this infeasible projection algorithm it's possible to make a stochastic online optimization algorithm which has better complexity (roughly because projecting a point which is near from an existing projection is easy).
It is unclear what is applicability of this algorithm, however, as well as what would be the interest of it to the community. This seems to be of at most theoretical interest, and the paper should provide better justification of why this result is useful if it is to belong in nips.