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.

本研究分析了在线凸优化问题在不同情境下的处理方法，并在具有完全适应性对手的在线线性优化算法为在线凸优化算法提供了一个模板，同时将需要完全信息反馈的算法转换为具有相近遗憾界限的半强盗反馈算法。此外，通过对半强盗反馈中使用确定性算法的完全适应性对手和使用随机算法的毫无意识对手进行比较，我们证明了可以在面对不可避免对手时，设计针对完全适应性对手的算法使用仅具有随机半强盗反馈也能获得类似界限。基于此，我们提出了将一阶算法转换为零阶算法，并具有相近遗憾界限的通用元算法框架。我们的框架允许在不同情境下分析在线优化，如全信息反馈、强盗反馈、随机遗憾、对手遗憾和各类非稳定遗憾。利用我们的分析，我们提供了第一个使用线性优化预言机的无投影在线凸优化算法。