论文标题
对均匀凸集的无投影优化
Projection-Free Optimization on Uniformly Convex Sets
论文作者
论文摘要
Frank-Wolfe方法以$ \ MATHCAL {O}（1/T）$的通用均方根速率解决了流畅的约束凸优化问题，并且IT（或其变体）对两个基本约束类别的加速收敛速度（或其变体）都具有加速的收敛速率：多面体和强烈的连接集。均匀的凸点集合非均值集合强烈凸集，并形成大量的\ textit {弯曲}凸集集合集合在机器学习和信号处理中通常遇到的。例如，$ \ ell_p $ -balls对于所有$ p> 1 $都均匀地凸出，但仅在$ p \ in] 1,2] $中强烈凸出。我们表明，这些集合系统地诱导了原始Frank-Wolfe算法的加速收敛速率，该算法在已知速率之间不断插值。我们的加速收敛速率强调，这是约束集的曲率（不仅是其强凸度）导致加速收敛速率。这些结果还重要地表明，Frank-Wolfe算法适应更通用的约束设置结构，从而解释了更快的经验收敛。最后，当该集合仅在局部均匀凸面并在线线性优化方面提供相似的结果时，我们还显示了加速的收敛速率。
The Frank-Wolfe method solves smooth constrained convex optimization problems at a generic sublinear rate of $\mathcal{O}(1/T)$, and it (or its variants) enjoys accelerated convergence rates for two fundamental classes of constraints: polytopes and strongly-convex sets. Uniformly convex sets non-trivially subsume strongly convex sets and form a large variety of \textit{curved} convex sets commonly encountered in machine learning and signal processing. For instance, the $\ell_p$-balls are uniformly convex for all $p > 1$, but strongly convex for $p\in]1,2]$ only. We show that these sets systematically induce accelerated convergence rates for the original Frank-Wolfe algorithm, which continuously interpolate between known rates. Our accelerated convergence rates emphasize that it is the curvature of the constraint sets -- not just their strong convexity -- that leads to accelerated convergence rates. These results also importantly highlight that the Frank-Wolfe algorithm is adaptive to much more generic constraint set structures, thus explaining faster empirical convergence. Finally, we also show accelerated convergence rates when the set is only locally uniformly convex and provide similar results in online linear optimization.
