Parameter-free Locally Accelerated Conditional Gradients
Parameter-free Locally Accelerated Conditional Gradients
复制标题
DOI：
--
复制
发表时间：
2021-02
影响因子：
5
通讯作者：
Alejandro Carderera;Jelena Diakonikolas;Cheuk Yin Lin;S. Pokutta
中科院分区：
文献类型：
--
作者：
Alejandro Carderera;Jelena Diakonikolas;Cheuk Yin Lin;S. Pokutta
无投影条件梯度（CG）方法是约束优化设置的首选算法，其中投影通常在计算上是禁止的，但在约束集上的线性优化在计算上仍然是可行的。与基于投影的方法不同，CG的全局加速收敛速度通常无法达到。然而，最近的一项关于局部加速CG（LaCG）的研究表明，对于许多感兴趣的设置，CG的局部加速是可能的。LaCG的主要缺点是它需要目标函数的光滑性和强凸性参数的知识。我们通过引入一种新的无参数局部加速CG（PF-LaCG）算法来消除这种限制，为此我们提供了严格的收敛保证。我们的理论结果得到了数值实验的补充，这些实验证明了局部加速，并展示了PF-LaCG在迭代次数和挂钟时间方面对非加速算法的实际改进。
Projection-free conditional gradient (CG) methods are the algorithms of choice for constrained optimization setups in which projections are often computationally prohibitive but linear optimization over the constraint set remains computationally feasible. Unlike in projection-based methods, globally accelerated convergence rates are in general unattainable for CG. However, a very recent work on Locally accelerated CG (LaCG) has demonstrated that local acceleration for CG is possible for many settings of interest. The main downside of LaCG is that it requires knowledge of the smoothness and strong convexity parameters of the objective function. We remove this limitation by introducing a novel, Parameter-Free Locally accelerated CG (PF-LaCG) algorithm, for which we provide rigorous convergence guarantees. Our theoretical results are complemented by numerical experiments, which demonstrate local acceleration and showcase the practical improvements of PF-LaCG over non-accelerated algorithms, both in terms of iteration count and wall-clock time.