Non-stationary Projection-Free Online Learning with Dynamic and Adaptive Regret Guarantees

Projection-free online learning has drawn increasing interest due to its efficiency in solving high-dimensional problems with complicated constraints. However, most existing projection-free online methods focus on minimizing the static regret, which unfortunately fails to capture the challenge of changing environments. In this paper, we investigate non-stationary projection-free online learning, and choose dynamic regret and adaptive regret to measure the performance. Specifically, we first provide a novel dynamic regret analysis for an existing projection-free method named BOGDIP, and establish an O (T^¾ (1+PT) ) dynamic regret bound, where PT denotes the path-length of the comparator sequence. Then, we improve the upper bound to O (T^¾ (1+PT) ^¼) by running multiple BOGDIP algorithms with different step sizes in parallel, and tracking the best one on the fly. Our results are the first general-case dynamic regret bounds for projection-free online learning, and can recover the existing O (T^¾) static regret by setting PT = 0. Furthermore, we propose a projection-free method to attain an O (? ^¾) adaptive regret bound for any interval with length? , which nearly matches the static regret over that interval. The essential idea is to maintain a set of BOGDIP algorithms dynamically, and combine them by a meta algorithm. Moreover, we demonstrate that it is also equipped with an O (T^¾ (1+PT) ^¼) dynamic regret bound. Finally, empirical studies verify our theoretical findings.