  Conditional gradient methods (CGM) are widely used in modern machine
learning. CGM's overall running time usually consists of two parts: the number
of iterations and the cost of each iteration. Most efforts focus on reducing
the number of iterations as a means to reduce the overall running time. In this
work, we focus on improving the per iteration cost of CGM. The bottleneck step
in most CGM is maximum inner product search (MaxIP), which requires a linear
scan over the parameters. In practice, approximate MaxIP data-structures are
found to be helpful heuristics. However, theoretically, nothing is known about
the combination of approximate MaxIP data-structures and CGM. In this work, we
answer this question positively by providing a formal framework to combine the
locality sensitive hashing type approximate MaxIP data-structures with CGM
algorithms. As a result, we show the first algorithm, where the cost per
iteration is sublinear in the number of parameters, for many fundamental
optimization algorithms, e.g., Frank-Wolfe, Herding algorithm, and policy
gradient.
