论文标题
回溯线路搜索条件梯度滑动
Backtracking linesearch for conditional gradient sliding
论文作者
论文摘要
我们提出了最初在\ cite {lan2016 -Conditional}中开发的条件梯度滑动（CGS）方法的修改。尽管CGS方法是无预测的一阶方法理论的理论突破，因为它是第一个达到理论绩效限制的限制的理论，但在实施中，它需要对lipschitz的知识，以了解目标函数$ l $ $ l $的梯度和总梯度评估的数量。这种要求在实际实施中造成了困难，这不仅是因为很难选择满足收敛条件的$ l $和$ n $的适当值，而且还因为保守选择$ l $和$ n $可以减少CGS方法的实际数值。我们提出的方法称为使用LinesEarch（CGS-LS）的条件梯度滑动方法，不需要$ L $和$ n $的知识，并且能够在理论上要求的迭代数量之前终止。尽管在数值实施方面更实用，但我们提出的CGS-LS方法的理论性能仍然与CGS方法的理论性能一样好。我们提出了数值实验，以显示我们在实践中提出的方法的效率。
We present a modification of the conditional gradient sliding (CGS) method that was originally developed in \cite{lan2016conditional}. While the CGS method is a theoretical breakthrough in the theory of projection-free first-order methods since it is the first that reaches the theoretical performance limit, in implementation it requires the knowledge of the Lipschitz constant of the gradient of the objective function $L$ and the number of total gradient evaluations $N$. Such requirements imposes difficulties in the actual implementation, not only because that it can be difficult to choose proper values of $L$ and $N$ that satisfies the conditions for convergence, but also since conservative choices of $L$ and $N$ can deteriorate the practical numerical performance of the CGS method. Our proposed method, called the conditional gradient sliding method with linesearch (CGS-ls), does not require the knowledge of either $L$ and $N$, and is able to terminate early before the theoretically required number of iterations. While more practical in numerical implementation, the theoretical performance of our proposed CGS-ls method is still as good as that of the CGS method. We present numerical experiments to show the efficiency of our proposed method in practice.
