Exploiting the Curvature of Feasible Sets for Faster Projection-Free Online Learning
In this paper, we develop new efficient projection-free algorithms for Online
Convex Optimization (OCO). Online Gradient Descent (OGD) is an example of a
classical OCO algorithm that guarantees the optimal $O(\sqrt{T})$ regret bound.
However, OGD and other projection-based OCO algorithms need to perform a
Euclidean projection onto the feasible set $\mathcal{C}\subset \mathbb{R}^d$
whenever their iterates step outside $\mathcal{C}$. For various sets of
interests, this projection step can be computationally costly, especially when
the ambient dimension is large. This has motivated the development of
projection-free OCO algorithms that swap Euclidean projections for often much
cheaper operations such as Linear Optimization (LO). However, state-of-the-art
LO-based algorithms only achieve a suboptimal $O(T^{3/4})$ regret for general
OCO. In this paper, we leverage recent results in parameter-free Online
Learning, and develop an OCO algorithm that makes two calls to an LO Oracle per
round and achieves the near-optimal $\widetilde{O}(\sqrt{T})$ regret whenever
the feasible set is strongly convex. We also present an algorithm for general
convex sets that makes $\widetilde O(d)$ expected number of calls to an LO
Oracle per round and guarantees a $\widetilde O(T^{2/3})$ regret, improving on
the previous best $O(T^{3/4})$. We achieve the latter by approximating any
convex set $\mathcal{C}$ by a strongly convex one, where LO can be performed
using $\widetilde {O}(d)$ expected number of calls to an LO Oracle for
$\mathcal{C}$.