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.

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

高效牛顿迭代算法实现无投影在线凸优化

Projection-Free Online Convex Optimization via Efficient Newton  Iterations

We prove that the Cram\'er transform of the uniform measure on a convex body
in $\mathbb{R}^n$ is a $(1+o(1)) n$-self-concordant barrier, improving a
seminal result of Nesterov and Nemirovski. This gives the first explicit
construction of a universal barrier for convex bodies with optimal
self-concordance parameter. The proof is based on basic geometry of log-concave
distributions, and elementary duality in exponential families.

本文通过对数凹分布的基本几何和指数族内元素的基础对偶性证明了一致测度空间中凸体均匀测度的 Cramér 变换是一种 $(1+o (1)) n$- 自共轭障碍，改进了 Nesterov 和 Nemirovski 的开创性成果，这为具有最佳自共轭参数的凸体提供了第一个显式的通用障碍物构造。

熵障碍：一种简单且最优的通用自协调障碍

The entropic barrier: a simple and optimal universal self-concordant  barrier

Many scientific and engineering applications feature nonsmooth convex
minimization problems over convex sets. In this paper, we address an important
instance of this broad class where we assume that the nonsmooth objective is
equipped with a tractable proximity operator and that the convex constraint set
affords a self-concordant barrier. We provide a new joint treatment of proximal
and self-concordant barrier concepts and illustrate that such problems can be
efficiently solved, without the need of lifting the problem dimensions, as in
disciplined convex optimization approach. We propose an inexact path-following
algorithmic framework and theoretically characterize the worst-case analytical
complexity of this framework when the proximal subproblems are solved
inexactly. To show the merits of our framework, we apply its instances to both
synthetic and real-world applications, where it shows advantages over standard
interior point methods. As a by-product, we describe how our framework can
obtain points on the Pareto frontier of regularized problems with
self-concordant objectives in a tuning free fashion.

通过使用可计算的接近算子和自共轭障碍的凸约束集，提出了一种新的关于近端和自共轭障碍概念的混合处理方法，并提出了一种非精确路径跟踪算法框架，可以有效地解决非光滑凸最小化问题，同时可以以无调谐自由的方式获得自共轭目标正则化问题的 Pareto 前沿点。