论文标题
通过平均步骤加速Frank-Wolfe
Accelerating Frank-Wolfe via Averaging Step Directions
论文作者
论文摘要
Frank-Wolfe方法是稀疏约束优化的一种流行方法，由于其快速的 /视水复杂性。但是，折衷的是，其最糟糕的情况全球融合相对较慢，重要的是，从根本上讲，其流量速度慢，也就是说，融合率是由离散化错误所限制的。在这项工作中，我们考虑了一个经过修改的Frank-Wolfe，其中阶跃方向是过去Oracle呼叫的简单加权平均值。此方法几乎不需要内存和计算开销，事实证明，该离散化错误术语。从数值上讲，我们表明此方法在几个问题上提高了收敛率，尤其是在检测到稀疏歧管之后。从理论上讲，我们表明该方法的总体全局收敛速率为$ O（1/k^p）$，其中$ 0 <p <1 $;经过多种识别后，此速率将速度升至$ o（1/k^{3p/2}）$。我们还观察到，该方法从很早的阶段就达到了这种加速率，这表明该方法的加速模式有希望。
The Frank-Wolfe method is a popular method in sparse constrained optimization, due to its fast per-iteration complexity. However, the tradeoff is that its worst case global convergence is comparatively slow, and importantly, is fundamentally slower than its flow rate--that is to say, the convergence rate is throttled by discretization error. In this work, we consider a modified Frank-Wolfe where the step direction is a simple weighted average of past oracle calls. This method requires very little memory and computational overhead, and provably decays this discretization error term. Numerically, we show that this method improves the convergence rate over several problems, especially after the sparse manifold has been detected. Theoretically, we show the method has an overall global convergence rate of $O(1/k^p)$, where $0< p < 1$; after manifold identification, this rate speeds to $O(1/k^{3p/2})$. We also observe that the method achieves this accelerated rate from a very early stage, suggesting a promising mode of acceleration for this family of methods.
