  In the framework of online convex optimization, most iterative algorithms
require the computation of projections onto convex sets, which can be
computationally expensive. To tackle this problem HK12 proposed the study of
projection-free methods that replace projections with less expensive
computations. The most common approach is based on the Frank-Wolfe method, that
uses linear optimization computation in lieu of projections. Recent work by
GK22 gave sublinear adaptive regret guarantees with projection free algorithms
based on the Frank Wolfe approach.
  In this work we give projection-free algorithms that are based on a different
technique, inspired by Mhammedi22, that replaces projections by set-membership
computations. We propose a simple lazy gradient-based algorithm with a
Minkowski regularization that attains near-optimal adaptive regret bounds. For
general convex loss functions we improve previous adaptive regret bounds from
$O(T^{3/4})$ to $O(\sqrt{T})$, and further to tight interval dependent bound
$\tilde{O}(\sqrt{I})$ where $I$ denotes the interval length. For strongly
convex functions we obtain the first poly-logarithmic adaptive regret bounds
using a projection-free algorithm.
