New Projection-free Algorithms for Online Convex Optimization with
  Adaptive Regret Guarantees
  We present new efficient \textit{projection-free} algorithms for online
convex optimization (OCO), where by projection-free we refer to algorithms that
avoid computing orthogonal projections onto the feasible set, and instead relay
on different and potentially much more efficient oracles. While most
state-of-the-art projection-free algorithms are based on the
\textit{follow-the-leader} framework, our algorithms are fundamentally
different and are based on the \textit{online gradient descent} algorithm with
a novel and efficient approach to computing so-called \textit{infeasible
projections}. As a consequence, we obtain the first projection-free algorithms
which naturally yield \textit{adaptive regret} guarantees, i.e., regret bounds
that hold w.r.t. any sub-interval of the sequence. Concretely, when assuming
the availability of a linear optimization oracle (LOO) for the feasible set, on
a sequence of length $T$, our algorithms guarantee $O(T^{3/4})$ adaptive regret
and $O(T^{3/4})$ adaptive expected regret, for the full-information and bandit
settings, respectively, using only $O(T)$ calls to the LOO. These bounds match
the current state-of-the-art regret bounds for LOO-based projection-free OCO,
which are \textit{not adaptive}. We also consider a new natural setting in
which the feasible set is accessible through a separation oracle. We present
algorithms which, using overall $O(T)$ calls to the separation oracle,
guarantee $O(\sqrt{T})$ adaptive regret and $O(T^{3/4})$ adaptive expected
regret for the full-information and bandit settings, respectively.
