论文标题
避免在弗兰克·沃尔夫（Frank Wolfe）变种中
Avoiding bad steps in Frank Wolfe variants
论文作者
论文摘要
对弗兰克·沃尔夫（Frank Wolfe）（FW）变体的分析通常会因存在不同种类的“好”和“坏”步骤而变得复杂。在本文中，我们旨在通过摆脱步骤之间的区别来简化其中一些变体的收敛分析，并通过确保每次迭代中目标的大量降低来提高现有速率。为了做到这一点，我们定义了短步链（SSC）过程，该过程以连续的短步骤跳过梯度计算，直到满足适当的停止条件。这项技术使我们能够在一般平滑的非凸设置中提供统一的分析和收敛速率，以及在Kurdyka-lojasiewicz（KL）属性下的线性收敛速率。据我们所知，尽管该设置已被广泛研究用于近端梯度类型方法，但尚未对正在研究的Frank Wolfe变体进行过分析。一个角度条件，以确保通过方法选择的方向具有最陡峭的斜率至常数，用于进行我们的分析。我们证明，Awary Step Frank-Wolfe（AFW），成对的Frank-Wolfe（PFW）和Frank-Wolfe方法在face Direction（FDFW）上满足了这种情况。
The analysis of Frank Wolfe (FW) variants is often complicated by the presence of different kinds of "good" and "bad" steps. In this article we aim to simplify the convergence analysis of some of these variants by getting rid of such a distinction between steps, and to improve existing rates by ensuring a sizable decrease of the objective at each iteration. In order to do this, we define 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 a linear convergence rate under a Kurdyka-Lojasiewicz (KL) property. While this setting has been widely studied for proximal gradient type methods, to our knowledge, it has not been analyzed before for the Frank Wolfe variants under study. An angle condition, ensuring that the directions selected by the methods have the steepest slope possible up to a constant, is used to carry out our analysis. We prove that this condition is satisfied on polytopes by the away step Frank-Wolfe (AFW), the pairwise Frank-Wolfe (PFW), and the Frank-Wolfe method with in face directions (FDFW).
