Accelerating Frank-Wolfe Algorithm using Low-Dimensional and Adaptive Data Structures

Understand

In this paper, we study the problem of speeding up a type of optimization algorithms called Frank-Wolfe, a conditional gradient method.

• We develop and employ two novel inner product search data structures, improving the prior fastest algorithm in [Shrivastava, Song and Xu, NeurIPS 2021].
• * The first data structure uses low-dimensional random projection to reduce the problem to a lower dimension, then uses efficient inner product data structure.
• It has preprocessing time $\tilde O(nd^{\omega-1}+dn^{1+o(1)})$ and per iteration cost $\tilde O(d+n^\rho)$ for small constant $\rho$.