论文标题
二阶条件梯度滑动
Second-order Conditional Gradient Sliding
论文作者
论文摘要
当需要高精度解决方案时，由于其局部二次收敛而需要高精度解决方案时，受约束的二阶凸优化算法是选择方法。这些算法需要在每次迭代时解决约束二次子问题的解决方案。我们介绍\ emph {二阶条件梯度滑动}（SOCGS）算法，该算法使用无投射算法来求解受约束的二次典型子问题不明显。当可行区域是多层元素时，算法在有限数量的线性收敛迭代后，在原始间隙中二次收敛。一旦进入二次制度，SOCGS算法就需要$ \ MATHCAL {O}（\ log（\ log 1/\ varepsilon））$一阶和Hessian Oracle调用，以及$ \ Mathcal {o}（O}（O}（\ log log（\ varepsilon） $ \ varepsilon $ - 最佳解决方案。当只能通过线性优化的Oracle有效访问可行区域，并且计算功能的一阶信息（尽管可能）是昂贵的，则该算法很有用。
Constrained second-order convex optimization algorithms are the method of choice when a high accuracy solution to a problem is needed, due to their local quadratic convergence. These algorithms require the solution of a constrained quadratic subproblem at every iteration. We present the \emph{Second-Order Conditional Gradient Sliding} (SOCGS) algorithm, which uses a projection-free algorithm to solve the constrained quadratic subproblems inexactly. When the feasible region is a polytope the algorithm converges quadratically in primal gap after a finite number of linearly convergent iterations. Once in the quadratic regime the SOCGS algorithm requires $\mathcal{O}(\log(\log 1/\varepsilon))$ first-order and Hessian oracle calls and $\mathcal{O}(\log (1/\varepsilon) \log(\log1/\varepsilon))$ linear minimization oracle calls to achieve an $\varepsilon$-optimal solution. This algorithm is useful when the feasible region can only be accessed efficiently through a linear optimization oracle, and computing first-order information of the function, although possible, is costly.
