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