A Generalized Approach to Online Convex Optimization
Mohammad Pedramfar Vaneet Aggarwal
In this paper, we analyze the problem of online convex optimization in
different settings. We show that any algorithm for online linear optimization
with fully adaptive adversaries is an algorithm for online convex optimization.
We also show that any such algorithm that requires full-information feedback
may be transformed to an algorithm with semi-bandit feedback with comparable
regret bound. We further show that algorithms that are designed for fully
adaptive adversaries using deterministic semi-bandit feedback can obtain
similar bounds using only stochastic semi-bandit feedback when facing oblivious
adversaries. We use this to describe general meta-algorithms to convert first
order algorithms to zeroth order algorithms with comparable regret bounds. Our
framework allows us to analyze online optimization in various settings, such
full-information feedback, bandit feedback, stochastic regret, adversarial
regret and various forms of non-stationary regret. Using our analysis, we
provide the first efficient projection-free online convex optimization
algorithm using linear optimization oracles.