  To deal with non-stationary online problems with complex constraints, we
investigate the dynamic regret of online Frank-Wolfe (OFW), which is an
efficient projection-free algorithm for online convex optimization. It is
well-known that in the setting of offline optimization, the smoothness of
functions and the strong convexity of functions accompanying specific
properties of constraint sets can be utilized to achieve fast convergence rates
for the Frank-Wolfe (FW) algorithm. However, for OFW, previous studies only
establish a dynamic regret bound of $O(\sqrt{T}(V_T+\sqrt{D_T}+1))$ by
utilizing the convexity of problems, where $T$ is the number of rounds, $V_T$
is the function variation, and $D_T$ is the gradient variation. In this paper,
we derive improved dynamic regret bounds for OFW by extending the fast
convergence rates of FW from offline optimization to online optimization. The
key technique for this extension is to set the step size of OFW with a line
search rule. In this way, we first show that the dynamic regret bound of OFW
can be improved to $O(\sqrt{T(V_T+1)})$ for smooth functions. Second, we
achieve a better dynamic regret bound of $O(T^{1/3}(V_T+1)^{2/3})$ when
functions are smooth and strongly convex, and the constraint set is strongly
convex. Finally, for smooth and strongly convex functions with minimizers in
the interior of the constraint set, we demonstrate that the dynamic regret of
OFW reduces to $O(V_T+1)$, and can be further strengthened to
$O(\min\{P_T^\ast,S_T^\ast,V_T\}+1)$ by performing a constant number of FW
iterations per round, where $P_T^\ast$ and $S_T^\ast$ denote the path length
and squared path length of minimizers, respectively.
