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 highdimensional 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 BOGD IP , and establish an O(T 3/4 (1 + P T )) dynamic regret bound, where P T denotes the path-length of the comparator sequence. Then, we improve the upper bound to O(T 3/4 (1 + P T ) 1/4 ) by running multiple BOGD IP 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 3/4 ) static regret by setting P T = 0. Furthermore, we propose a projection-free method to attain an Õ(τ 3/4 ) 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 BOGD IP algorithms dynamically, and combine them by a meta algorithm. Moreover, we demonstrate that it is also equipped with an O(T 3/4 (1 + P T ) 1/4 ) dynamic regret bound. Finally, empirical studies verify our theoretical findings.