Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structures
This addresses a bottleneck in optimization for machine learning practitioners, offering a theoretical improvement over linear scan methods, though it is incremental as it builds on existing approximate data-structures.
The paper tackled the problem of high per-iteration cost in conditional gradient methods (CGM) by developing a framework to combine approximate maximum inner product search (MaxIP) data-structures with CGM, resulting in sublinear cost per iteration for algorithms like Frank-Wolfe, Herding, and policy gradient.
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.