Projection-free Online Learning in Dynamic Environments

Authors

  • Yuanyu Wan Nanjing University
  • Bo Xue Nanjing University
  • Lijun Zhang Nanjing University

Keywords:

Online Learning & Bandits, Optimization, Time-Series/Data Streams

Abstract

To efficiently solve high-dimensional problems with complicated constraints, projection-free online learning has received ever-increasing research interest. However, previous studies either focused on static regret that is not suitable for dynamic environments, or only established the dynamic regret bound under the smoothness of losses. In this paper, without the condition of the smoothness, we propose a novel projection-free online algorithm, and achieve an O(max{T^{2/3}V_T^{1/3},T^{1/2}}) dynamic regret bound for convex functions and an O(max{(TV_Tlog T)^{1/2},log T}) dynamic regret bound for strongly convex functions, where T is the time horizon and V_T denotes the variation of loss functions. Specifically, we first improve an existing projection-free algorithm called online conditional gradient (OCG) to enjoy small dynamic regret bounds with the prior knowledge of V_T. To work with unknowable V_T, we maintain multiple instances of the improved OCG that can handle different functional variations, and combine them with a meta-algorithm that can track the best one. Experimental results validate the efficiency and effectiveness of our algorithm.

Downloads

Published

2021-05-18

How to Cite

Wan, Y., Xue, B., & Zhang, L. (2021). Projection-free Online Learning in Dynamic Environments. Proceedings of the AAAI Conference on Artificial Intelligence, 35(11), 10067-10075. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/17208

Issue

Section

AAAI Technical Track on Machine Learning IV