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 $\cK$ 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 for projections. However, the computation of the
Newton iterates requires a matrix inverse, which can still be expensive. As our
main contribution, we show how the stability of the Newton iterates can be
leveraged to compute the inverse Hessian only a vanishing fraction of the
rounds, leading to a new efficient projection-free OCO algorithm with a
state-of-the-art regret bound.

本文提出了一种新的在线凸优化投影免费算法，并通过利用牛顿迭代的稳定性来计算逆海森矩阵以获得具有最先进遗憾边界的新的高效算法。