论文标题
对会员甲骨文的无投射自适应遗憾
Projection-free Adaptive Regret with Membership Oracles
论文作者
论文摘要
在在线凸优化的框架内，大多数迭代算法都需要对凸集的投影计算，这在计算上可能很昂贵。为了解决这个问题，HK12提出了对替换较便宜的计算代替投影的无预测方法的研究。最常见的方法是基于Frank-Wolfe方法，该方法使用线性优化计算代替投影。 GK22的最新工作给基于弗兰克·沃尔夫（Frank Wolfe）的方法提供了sublrinear的自适应遗憾保证。 在这项工作中，我们给出了基于Mhammedi22启发的不同技术的无投影算法，该技术通过set-Membership Computation代替了预测。我们提出了一种简单的基于梯度的算法，并具有Minkowski正则化，该算法达到了近乎最佳的自适应遗憾界限。对于一般的凸损失函数，我们将以前的自适应后悔界限从$ O（t^{3/4}）$提高到$ O（\ sqrt {t}）$，然后再到紧密间隔绑定的$ \ tilde {o} {o}（\ sqrt {i}）$ i $ i $ e $ i $ demotes Interval Interve interceptal长度。对于强凸功能，我们使用无投射算法获得了第一个多同源物的自适应后悔界限。
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.
