In this paper, we present a first-order projection-free method, namely, the universal conditional gradient sliding (UCGS) method, for solving ε-approximate solutions to convex differentiable optimization problems. For objective functions with Hölder continuous gradients, we show that UCGS is able to terminate with ε-solutions with at most O((1/ε)^(2/(1+3v))) gradient evaluations and O((1/ε)^(4/(1+3v))) linear objective optimizations, where v is the exponent and of the Hölder condition. Furthermore, UCGS is able to perform such computations without requiring any specific knowledge of the smoothness information v. In the weakly smooth case when v is in (0,1), both complexity results improve the current state-of-the-art O((1/ε)^(1/v)) 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.
Citation
Submitted to SIOPT March 2021