Revisiting Decomposition-Invariant Conditional Gradient Methods for Polytopes

Abstract

We revisit Decomposition-Invariant Conditional Gradient methods, originally introduced by Garber and Meshi in 2016, for minimizing a convex and $\beta$-smooth function over a polytope in $\reals^n$, under an $\alpha$-quadratic growth condition. For 2-level polytopes we design a simple and parameter-free dyadic step-size rule that yields a linear convergence rate which scales with the dimension of the optimal face and not with the ambient dimension as in standard away-step-based conditional gradient methods for polytopes. For general polytopes, under a slightly stronger condition of $\alpha_{\mathrm{F}}$-\textit{facial quadratic growth}, we introduce a method whose number of iterations to reach an $\epsilon$-approximate solution is of the order $n+\frac{\beta{}D^2}{\alpha{}r^{*2}} + \frac{(d^*+1)\beta{}D^2}{\alpha_{\mathrm{F}}}\log(1/\epsilon)$, where $d^*$ is the dimension of the optimal face, $r^*$ is a separation parameter between the optimal set and faces that do not contain an optimal solution, and $D$ is the diameter of the polytope. This method is also parameter-free and only relies on standard line-search computations. The second result improves upon previous conditional gradient methods, whose number of iterations to $\epsilon$-approximation scales with $\frac{\beta{}D^2n}{\alpha}\log(1/\epsilon)$, in a meaningful regime $\max\{\frac{\alpha}{\alpha_{\rm F}}(d^*+1), \frac{1}{r^{*2}}\} \ll n$