Non-stationary Projection-free Online Learning with Dynamic and Adaptive
  Regret Guarantees
Yibo Wang Wenhao Yang Wei Jiang Shiyin Lu Bing Wang Haihong Tang Yuanyu Wan Lijun Zhang
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 $\text{BOGD}_\text{IP}$, and establish
an $\mathcal{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
$\mathcal{O}(T^{3/4}(1+P_T)^{1/4})$ by running multiple $\text{BOGD}_\text{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
$\mathcal{O}(T^{3/4})$ static regret by setting $P_T = 0$. Furthermore, we
propose a projection-free method to attain an $\tilde{\mathcal{O}}(\tau^{3/4})$
adaptive regret bound for any interval with length $\tau$, which nearly matches
the static regret over that interval. The essential idea is to maintain a set
of $\text{BOGD}_\text{IP}$ algorithms dynamically, and combine them by a meta
algorithm. Moreover, we demonstrate that it is also equipped with an
$\mathcal{O}(T^{3/4}(1+P_T)^{1/4})$ dynamic regret bound. Finally, empirical
studies verify our theoretical findings.