Online Improper Learning with an Approximation Oracle

One of the most fundamental and well-studied questions in learning theory is whether one can learn a given problem using an optimization oracle. For online learning in games, it was shown by Kalai and Vempala (2005) that an optimization oracle giving the best decision in hindsight is sufficient for attaining optimal regret. However, in many non-convex settings, such an optimization oracle is either unavailable or NPhard to compute. In contrast, in many such cases, efficient approximation algorithms are usually known, and are guaranteed to return a solution within a certain multiplicative factor of the optimum.