Universal Conditional Gradient Sliding for Convex Optimization
提出一种无需投影的一阶方法UCGS，用于求解凸可微优化问题的ε近似解，在Hölder连续梯度条件下，无需知道光滑性参数即可达到最优复杂度，改进了现有条件梯度法的结果。
In this paper, we present a first-order projection-free method, namely, the universal conditional gradient sliding (UCGS) method, for solving $\varepsilon$-approximate solutions to convex differentiable optimization problems. For objective functions with Hölder continuous gradients, we show that UCGS is able to terminate with $\varepsilon$-solutions with at most $O((M_νD_X^{1+ν}/{\varepsilon})^{2/(1+3ν)})$ gradient evaluations and $O((M_νD_X^{1+ν}/{\varepsilon})^{4/(1+3ν)})$ linear objective optimizations, where $ν\in (0,1]$ and $M_ν>0$ are the exponent and constant of the Hölder condition. Furthermore, UCGS is able to perform such computations without requiring any specific knowledge of the smoothness information $ν$ and $M_ν$. In the weakly smooth case when $ν\in (0,1)$, both complexity results improve the current state-of-the-art $O((M_νD_X^{1+ν}/{\varepsilon})^{1/ν})$ results on first-order projection-free method achieved by the conditional gradient method. Within the class of sliding-type algorithms, to the best of our knowledge, this is the first time a sliding-type algorithm is able to improve not only the gradient complexity but also the overall complexity for computing an approximate solution. In the smooth case when $ν=1$, UCGS matches the state-of-the-art complexity result but adds more features allowing for practical implementation.