Projection-Free Online Convex Optimization via Efficient Newton Iterations

This paper presents new projection-free algorithms for Online Convex Optimization (OCO) over a convex domain \mathcal{K} \subset \mathbb{R} d . Classical OCO algorithms (such as Online Gradient Descent) typically need to perform Euclidean projections onto the convex set \mathcal{K} to ensure feasibility of their iterates. Alternative algorithms, such as those based on the Frank-Wolfe method, swap potentially-expensive Euclidean projections onto \mathcal{K} for linear optimization over \mathcal{K} . However, such algorithms have a sub-optimal regret in OCO compared to projection-based algorithms. In this paper, we look at a third type of algorithms that output approximate Newton iterates using a self-concordant barrier for the set of interest. The use of a self-concordant barrier automatically ensures feasibility without the need of projections.