论文标题
重新访问预测的在线学习：强烈的凸案例
Revisiting Projection-free Online Learning: the Strongly Convex Case
论文作者
论文摘要
主要基于经典的Frank-Wolfe方法，近年来对机器学习社区产生了浓厚的兴趣，因为它们在许多应用中处理凸的限制因素，但对于许多应用程序而言，计算预测通常是计算在高维度上是高维度的设置，并且可能对大多数标准的标准投资方法的使用，因此近年来对机器学习社区产生了浓厚的兴趣。特别是，对在线学习的无预测方法进行了重大研究。在本文中，我们重新访问了由Hazan和Kale \ Cite \ Cite {Hazan12}建议的在线Frank-Wolfe（OFW）方法，并填补了几年来一直没有注意到的空白：OFW在强烈的convex函数上实现了更快的$ O（T^{2/3}）$的速度（t^{2/3}）$（在强烈的convex convex conve conve conve conve conve conver conver conce $ o o（the conty $ o o o o o o o o o o o o（t）凸功能），其中$ t $是序列长度。这有点令人惊讶，因为众所周知，对于离线优化，一般而言，强大的凸度不会导致弗兰克·沃尔夫的速度更快。我们还在强凸度下重新审视强盗设置，并证明了$ \ tilde o（t^{2/3}）$的类似界限（而不是$ o（而不是$ o（t^{3/4}）$，没有强凸）。因此，在当前的面对面中，具有强烈凸出和非滑动功能的全信息和匪徒设置的最佳无投影上限符合$ t $中的对数因素。
Projection-free optimization algorithms, which are mostly based on the classical Frank-Wolfe method, have gained significant interest in the machine learning community in recent years due to their ability to handle convex constraints that are popular in many applications, but for which computing projections is often computationally impractical in high-dimensional settings, and hence prohibit the use of most standard projection-based methods. In particular, a significant research effort was put on projection-free methods for online learning. In this paper we revisit the Online Frank-Wolfe (OFW) method suggested by Hazan and Kale \cite{Hazan12} and fill a gap that has been left unnoticed for several years: OFW achieves a faster rate of $O(T^{2/3})$ on strongly convex functions (as opposed to the standard $O(T^{3/4})$ for convex but not strongly convex functions), where $T$ is the sequence length. This is somewhat surprising since it is known that for offline optimization, in general, strong convexity does not lead to faster rates for Frank-Wolfe. We also revisit the bandit setting under strong convexity and prove a similar bound of $\tilde O(T^{2/3})$ (instead of $O(T^{3/4})$ without strong convexity). Hence, in the current state-of-affairs, the best projection-free upper-bounds for the full-information and bandit settings with strongly convex and nonsmooth functions match up to logarithmic factors in $T$.
