Conditional gradient algorithms (also often called Frank-Wolfe algorithms) are popular due to their simplicity of only requiring a linear optimization oracle and more recently they also gained significant traction for online learning. While simple in principle, in many cases the actual implementation of the linear optimization oracle is costly. We show a general method to lazify various conditional gradient algorithms, which in actual computations leads to several orders of magnitude of speedup in wall-clock time. This is achieved by using a faster separation oracle instead of a linear optimization oracle, relying only on few linear optimization oracle calls.

Conditional gradient algorithms (also often called Frank-Wolfe algorithms) are popular due to their simplicity of only requiring a linear optimization oracle and more recently they also gained significant traction for online learning. While simple in principle, in many cases the actual implementation of the linear optimization oracle is costly. We show a general method to lazify various conditional gradient algorithms, which in actual computations leads to several orders of magnitude of speedup in wall-clock time. This is achieved by using a faster separation oracle instead of a linear optimization oracle, relying only on few linear optimization oracle calls.

In this work we introduce a conditional accelerated lazy stochastic gradient descent algorithm with optimal number of calls to a stochastic first-order oracle and convergence rate $O(1/\epsilon^2)$ improving over the projection-free, Online Frank-Wolfe based stochastic gradient descent of (Hazan and Kale, 2012) with convergence rate $O(1/\epsilon^4)$.

Yannakakis [27, 26] showed that the matching problem does not have a small symmetric linear program. Rothvoß [23] recently proved that any, not necessarily symmetric, linear program also has exponential size. It is natural to ask whether the matching problem can be expressed compactly in a framework such as semidefinite programming (SDP) that is more powerful than linear programming but still allows efficient optimization. We answer this question negatively for symmetric SDPs: any symmetric SDP for the matching problem has exponential size. We also show that an O(k)-round Lasserre SDP relaxation for the asymmetric metric traveling salesperson problem yields at least as good an approximation as any symmetric SDP relaxation of size nk. The key technical ingredient underlying both these results is an upper bound on the degree needed to derive polynomial identities that hold over the space of matchings or traveling salesperson tours.

Motivated by [12], we provide a framework for studying the size of linear programming formulations as well as semidefinite programming formulations of combinatorial optimization problems without encoding them first as linear programs. This is done via a factorization theorem for the optimization problem itself (and not a specific encoding of such). As a result we define a consistent reduction mechanism that degrades approximation factors in a controlled fashion and which, at the same time, is compatible with approximate linear and semidefinite programming formulations. Moreover, our reduction mechanism is a minor restriction of classical reductions establishing inapproximability in the context of PCP theorems. As a consequence we establish strong linear programming inapproximability (for LPs with a polynomial number of constraints) for several problems that are not 0/1-CSPs: we obtain a 3/2-epsilon inapproximability for Vertex Cover (which is not of the CSP type) answering an open question in [12], we answer a weak version of our sparse graph conjecture posed in [6] showing an inapproximability factor of 1/2+ε for bounded degree IndependentSet, and we establish inapproximability of MaxMULTICUT (a non-binary CSP). In the case of SDPs, we obtain relative inapproximability results for these problems.