论文标题
弗兰克·沃尔夫（Frank-Wolfe）的仿射不变分析
Affine Invariant Analysis of Frank-Wolfe on Strongly Convex Sets
论文作者
论文摘要
众所周知，当约束集合强烈凸出时，富有兴趣的弗兰克 - 沃尔夫（FW）算法会享有加速的融合率。但是，这些结果依赖于规范依赖的假设，通常与FW的仿生性属性相矛盾，通常会产生非伴随的界限。在这项工作中，我们介绍了有关该问题的新结构假设（例如定向平滑度），并得出了对弗兰克·沃尔夫（Frank-Wolfe）的仿射不变的，规范无关的分析。根据我们的分析，我们提出了一个仿射不变的回溯线路搜索。有趣的是，我们表明，尽管在步骤大小的计算中使用了仿射依赖性规范，但使用目标函数的平滑度出奇地收敛到仿射不变的步长尺寸。这表明我们不一定需要事先知道该集合的结构以享受仿射不变的加速率。
It is known that the Frank-Wolfe (FW) algorithm, which is affine-covariant, enjoys accelerated convergence rates when the constraint set is strongly convex. However, these results rely on norm-dependent assumptions, usually incurring non-affine invariant bounds, in contradiction with FW's affine-covariant property. In this work, we introduce new structural assumptions on the problem (such as the directional smoothness) and derive an affine invariant, norm-independent analysis of Frank-Wolfe. Based on our analysis, we propose an affine invariant backtracking line-search. Interestingly, we show that typical backtracking line-searches using smoothness of the objective function surprisingly converge to an affine invariant step size, despite using affine-dependent norms in the step size's computation. This indicates that we do not necessarily need to know the set's structure in advance to enjoy the affine-invariant accelerated rate.
