论文标题
在足够的坡度条件下分析无投影一阶方法的统一框架
A unifying framework for the analysis of projection-free first-order methods under a sufficient slope condition
论文作者
论文摘要
存在不同种类的“好”和“坏”步骤的分析通常会使一阶方法的分析变得复杂。在本文中，我们提出了一个无预测方法的统一框架，旨在通过摆脱步骤之间的这种区别来简化收敛分析。我们框架中采用的主要工具是短步链（SSC）过程，该过程以连续的短步骤跳过梯度计算，直到满足适当的停止条件。这项技术使我们能够在一般平滑的非凸设置中提供统一的分析和收敛速率，以及在Kurdyka-lojasiewicz（KL）属性下的收敛速率，据我们所知，该设置尚未在研究中进行投射的无预测方法进行分析。在这种情况下，我们证明局部收敛率与在相同条件下预计梯度方法的局部收敛率相当。我们的分析依赖于足够的斜率条件，确保方法选择的方向具有最陡峭的斜率，直至可行的方向之间的常数。除其他外，多种弗兰克·沃尔夫（FW）的变体满足了这种情况，并通过具有光滑边界的凸形集中的一些无投影方法来满足这种情况。
The analysis of projection-free first order methods is often complicated by the presence of different kinds of "good" and "bad" steps. In this article, we propose a unifying framework for projection-free methods, aiming to simplify the converge analysis by getting rid of such a distinction between steps. The main tool employed in our framework is the Short Step Chain (SSC) procedure, which skips gradient computations in consecutive short steps until proper stopping conditions are satisfied. This technique allows us to give a unified analysis and converge rates in the general smooth non convex setting, as well as convergence rates under a Kurdyka-Lojasiewicz (KL) property, a setting that, to our knowledge, has not been analyzed before for the projection-free methods under study. In this context, we prove local convergence rates comparable to those of projected gradient methods under the same conditions. Our analysis relies on a sufficient slope condition, ensuring that the directions selected by the methods have the steepest slope possible up to a constant among feasible directions. This condition is satisfied, among others, by several Frank-Wolfe (FW) variants on polytopes, and by some projection-free methods on convex sets with smooth boundary.
